3
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Thanks a lot for your valuable input @Kuifje . I had looked at the above-mentioned post and one thing is unclear to me how do you minimize multiple flows in one go? My current implementation does the src-dest at one time, solving the product of stop1*stop2 as result. As I see the post was made by you, do you have any details on implementation? I mean codifying the problem? $\endgroup$
    – J. Alan
    Commented Nov 25, 2022 at 12:38
  • $\begingroup$ If you look at the model described in the post, there are $N_{ij}$ variables on each edge, which are used to "merge" all of the different flows in one go. I do have a complete implementation of the problem. Is this for academia or other ? $\endgroup$
    – Kuifje
    Commented Nov 25, 2022 at 12:59
  • $\begingroup$ Ok, I'll look closely at the post. Just a clarification, I'm currently working on a home assignment for my course in OR at uni. Even if you can't or don't wish to share the implementation, a brief description/pseudo-code would suffice as well. Thanks a lot again. $\endgroup$
    – J. Alan
    Commented Nov 25, 2022 at 14:40
1
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.