Designing a multi-commodity network flow optimizer

Question

I'm trying to solve multi commodity multi source network flow optimization problem using Python-PuLP. Here is how my problem looks like:

The numbers on the arcs represent the order of priority a particular node should receive supply from. For example, D1 should get first serviced by W2, then W1, and W3 respectively.

Variables:

• W = set of all Warehouses (W1, W2, W3)
• D = set of all DCs (D1, D2, D3)
• C = set of all Commodities (C1, C2)
• N = set of all nodes (W1, W2, W3, D1, D2, D3)
• Arcs = set of all connections (w, d) for w $\subset$ W and d $\subset$ D

Current assumptions:

• All commodities have the same Warehouse-DC connection priorities.
• Transport trucks have unlimited capacities and same cost.
  • QUESTION 1 - I would like to know how to include this in the design since I'm currently using the priority in the arcs to identify from which source the commodity should be shipped.

Currently I'm trying to use a for-loop to find solutions for all commodities. I believe there is an elegant way to depict the same problem.

QUESTION 2 - How can I use the optimization design to include many commodities. Eventually I will want to add additional constraints on how much I can transport per arc.

for c in C:

Decision variables:

route -> Arcs 
route_used = 1 iff route is selected, 0 otherwise

Objective:

min $\sum (RouteSelected[(w,d),1]*cost[(w,d)])$

QUESTION 3 - I have not chosen another objective to ensure the maximum fulfilment to all DCs. Should I first run an iteration to solve for maximum fulfilment and then run for minimum of the route selected as defined above? Is there a better way to define this as multi-objective together?

Bounds:

for w, d in route:
    route[(w, d)] >= 0
    route[(w, d)] <= min(Supply[w], Demand[d]

Constraints:

1. Flow conservation constraint

if Total Supply < Total Demand:
    for n in nodes:
        (Supply[n] +  sum(route[(w, d)]) for w, d in Arcs and d==n) <=
        (Demand[n] +  sum(route[(w, d)]) for w, d in Arcs and w==n)
else:
    for n in nodes:
        (Supply[n] +  sum(route[(w, d)]) for w, d in Arcs and d==n) >=
        (Demand[n] +  sum(route[(w, d)]) for w, d in Arcs and w==n)

2. Specific DC priority

When the total supply is less than the total demand, I want to service the demand at a specific DC first irrespective of my objective function. For example, let’s consider DC D1

if Total Supply < Total Demand:

QUESTION 4a - I want to satisfy the maximum possible demand for D1 from all my connected warehouses. How do I define that?

QUESTION 4b - Assuming we always run into situations where supply < demand, how should I let the optimizer know the order of fulfilment. For example, solve for DC1, then DC3, followed by DC2? Or is this inherently used by the choice of optimizer I use?

Answer 1

Question 1

You could simply use the priority function as the cost function on the arcs. This way, it is for example cheaper to ship a commodity to $D_1$ from $W_2$ ($1$ unit of cost per unit of flow) than from $W_1$ ($2$ units of cost per unit of flow). If there are no capacities in the model, the orders of priority will be respected.

Question 2

You should use variables $x_{ij}^p$ that represent the amount of commodity $p$ shipped from node $i$ to node $j$.

Question 3

To ensure maximum fulfillment, you should use demand satisfaction constraints for each DC:

$$ \sum_{i|(i,DC)\in A}x_{i,DC}^p = \mbox{demand}_{DC}^p\quad \mbox{for each DC, for each commodity }p $$

If this is not feasible because of insufficient supply, then you can try to fulfill demand as much as possible by penalizing what is missing. You can introduce slack variables $e_{DC}^p$ and minimize their value in the objective function. The above constraint becomes:

$$ \sum_{i|(i,DC)\in A}x_{i,DC}^p + e_{DC}^p= \mbox{demand}_{DC}^p\quad \mbox{for each DC, for each commodity }p $$

Question 4a

This is covered in Question 3.

Question 4b

Unless you have a good reason to impose the order of fulfillment, I would let the solver choose what is best. But if you really want to impose an order, say for example $DC_1$, then $DC_2$, then $DC_3$, then you can use weights $\omega_1>\omega_2>\omega_3$ in the objective function $$ \min \; \sum_p\sum_{(i,j)\in A}c_{ij}x_{ij}^p + \sum_p\sum_{i\in \{1,2,3\}}\omega_i e_{DC_i}^p $$ This way, the solver will try to fulfill $DC_1$ in priority (but with no guarantee), in order to avoid the largest penalty $\sum_p \omega_1 e_{DC_1}^p$.

You could also add the following constraint to impose that "what is missing" in $DC_1$ should be smaller than "what is missing" in $DC_2$ and $DC_3$: $$ \sum_p e_{DC_1}^p \le \sum_p e_{DC_2}^p \le \sum_p e_{DC_3}^p $$

Answer 2

In addition to what @Kuifje suggested, with the right solver you could consider using a lexicographic objective. (CPLEX now supports this.) Define $T_{\pi, j}$ to be the set of priority $\pi$ suppliers to DC $j$. In your example, these are singletons (e.g., $T_{1, 1} = \lbrace 2\rbrace $), but more generally it might be that multiple suppliers would have the same priority for a DC.

Let $x_{p,i,j} \ge 0$ be the amount of product $p$ sent from source $i$ to DC $j$ (variable), and let $S_{p,i}$ and $D_{p,j}$ be supply of $p$ at source $i$ and demand for $p$ at DC $j$ respectively (parameters). The constraints are simple supply and demand limits: $$\sum_j x_{p,i,j} \le S_{p,i}\quad \forall p, i$$and $$\sum_i x_{p,i,j} \le D_{p,j} \quad \forall p,j.$$ The lexicographic objective is to maximize $(z_1, z_2, \dots, z_{\Pi})$ in descending priority order, where $\Pi$ is the number of priority levels and $$z_{\pi} = \sum_j \sum_{i\in T_{\pi, j}} x_{p,i,j}.$$ In your example, $z_1$ would be the total shipments of anything from W1 to D2 and D3 and from W2 to D1. The lexicographic approach will first try to maximize all shipments from priority 1 suppliers, then maximize shipments of remaining products from priority 2 suppliers, and so on.

There are a few things to note here. The model will handle both supply greater than demand and supply less than demand (or a mix, some products with excess supply and some with excess demand). If you want to prioritize suppliers by product (e.g., D2 wants C1 from W1 but wants C2 from W3), it can be adapted to do that. If you want to prioritize some customers over others (e.g., it's more important for D1 to get product from their priority 1 source than it is for D2 to get product from their priority 1 source), you can attach weights to the $x_{p,i,j}$ in the formula for $z_{\pi}$, giving higher weights to more important DCs.