How to eliminate subtours in a multi-depot capacitated vehicle routing problem?

ユーザーの入力を待っています。

Luca Bonavita

2022年05月19日 18:45

• 
• 
• 

As mentioned in the title, I am currently working a complex vehicle routing problem, which has:

- multiple depots

- multiple vehicles (with different capacities)

In particular, the variable x is cooresponds to the edge (i, j) traversed by vehicle f which departs from depot p. Vc is the whole set of customers, F are the vehicles and finally Vd is the set of depots (called also points of origin).

The constraint i want to add to my linear optimization model is this one:

I have seen that i can solve my problem through lazy constraints and callbacks but i have 2 big problems: 

1) those codes I have found online are related to much easier problems

2) I find it very difficult to understand what the codes do and therefore also to edit them

If anyone would like to help me it would be greatly appreciated

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:36

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Mario Ruthmair

  • Gurobi Staff

  2022年05月20日 13:51

  Hi Luca!

  If you are not experienced with callbacks, I would suggest to start with an easier modeling approach to eliminate subtours without need for callbacks, e.g., by using Big-M constraints with position (or load) variables associated to each customer. In the case of load variables you can also handle the capacity constraints at the same time. Then, if you have a running model you might switch to callbacks.
  The Big-M constraints do not provide very good LP bounds but are a good base line for further developments.

  If you need to implement the subtour elimination constraints you mentioned, then you should start with lazy constraints, since for integer solutions it is trivial to identify subtours. Just check the solution you get for customer cycles using a simple depth-first search on the graph defined by the arcs selected in the solution.

  For fractional solutions (MIPNODE callback), the separation of those inequalities involves solving max-flow problems and is much more advanced. But for feasibility you do not need them, only to strengthen the LP bounds.

  Best regards,
  Mario

  0

投稿コメントは受け付けていません。