Transportation problem with consolidation within path

Question

There's a supply network design problem that I'm trying to solve, which is as follows:

A certain amount of goods need to be transported from point A to B, and can have stoppages in between with a limit of lets say n. These stoppages can be used to consolidate the goods and send further. The task is to achieve the transportation with minimum cost for the source-destination pairs. These potential stoppages can be any node from the graph G =(V,E).

My first attempt was to use to find the best path between source and destination pair individually, which I'm able to do, but that's not ideal as its not total cost minimization. I'm new to Pyomo and gurobi type modelling. Any advice how can i model the below data would be appreciated.

For optimizing for each src-dest piar, I did this:

stop1 = m.addVars(stops_len, vtype=GRB.BINARY, name='select stop1')
stop2 = m.addVars(stops_len, vtype=GRB.BINARY, name='select stop2')
assign = m.addVars(prod_stop1_stop2, ub=2, vtype=GRB.CONTINUOUS, name='Assign')

Which let me choose the combnination of stop1 and stop2. But this is not enough as i minimizes indiv scr-dest paths, not global cost.

What i wish to solve looks like below format of data:

Source	Dest	Potential stop1	Potential stop2	Goods
A	D	[]	[]	x1
B	D	[]	[]	x2

Potential stops1 and 2 are list of potential stops i find via some meta-heuristic. So, my question is how can i model the data shown above in Pyomo or gurobi or any other tool? Any help would be appreciated.

Answer 1

If your demands are per source-destination pairs, then you are very likely dealing with a variation of the multi-commodity flow problem, where each source-destination pair is a commodity.

The variation is that the edges of your graph have variable capacities (the number of trucks on each edge). Or to be more precise, the capacities are defined in a step-wise fashion. Each time you add a new truck on the edge, the capacity increases (by the capacity of the truck), yielding an extra cost in the cost function.

It is a good idea to define a pool of paths with potential stops for each source-destination pair. The idea is then to select the right combinations, in order to maximize consolidation, which is equivalent to minimizing the total number of trucks used.

You can checkout this post for some insights on the problem (including the linear formulation which selects the bests paths).

Answer 2

I see it more like a variation of Travelling salesman Problem (TSP) with a limit to intervening/transhipment nodes. Gurobi has a solution to that here

The formulation goes like this: A,B are src-dest pairs and nodes be $V=\{n_1,n_2,...n_m\}$.
Define $x_{ij}$ and $y_i$ be binary with $i,j$ as indices for intervening nodes from V and $c_{ij}$ be cost/selection of shipment(edge) from nodes $i$ to $j$.
Define M (or bigM) = large integral number, say number NxN where N is max number of transshipment nodes selected.

Assignment (if bi-directional):
$x_{ij} = x_{ji} \ \forall (i,j) \in\ V\times V$: Ensures arc is selected either way.

Constraints:
C1 = $\sum_i y_i \le N$: Max no. of transshipment nodes selected
C2 = $\sum_{j \in\ V} x_{i,j} \le M*y_i \ \forall i \in\ V, i \neq j$: Edges/arcs selected for a node only when node is in solution.
C2_1= $\sum_{j \in\ V} x_{i,j} \ge y_i \ \forall i \in\ V, j \neq i$: Ensure if node is selected at least 1 associated edge is selected.
C3 = $\sum_{j \in\ V} (x_{ij} - x_{ji}) = 0 \quad \forall i \in\ V, j \neq i$: All nodes selected are transshipment nodes
C4 = $\sum_{i,j \in\ V} x_{ij} \le \sum_{i\in\ V} y_i - 1$: Ensure there's no subtour with transhippment nodes but you may have a look at Gurobi model.
C5 = $\sum_{i \in\ V} x_{A,i} = 1$: Ensure A is connected to one of the nodes.
C6 = $\sum_{i \in\ V} x_{i,B} = 1$: Ensure B is connected to one of the nodes.
C7 = $x_{A,i} + x_{i,B} \le 1 \ \forall i \in\ V$: (Optional) Ensure it doesn't end up choosing just one transshipment node. Optional because need to run couple of times if this is happening.
C8 = $\sum_{i \in\ V} y_i \ge 2$: (Optional), this makes Constr C7 redundant with just 1 constraint.

Objective:
Cost = $\sum_i (cost_{A,i}*x_{A,i}+ cost_{i,B}*x_{i,B}) + \sum_{i,j \in\ V} cost_{i,j}*x_{i,j}$