Skip to main content

Location Routing Problem - Lazy Subtour Elimination Constraints

Answered

Comments

5 comments

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Michael,

    First of all, which of the constraints and/or variables of the formulation from the other post did you remove such that you get integer solutions in the MIPSOL callback that contain subtours (since the other formulation forbids them already)?

    Which cycles are actually left? Only cycles among customer nodes or also cycles that include more than one depot?

    What I usually do in such cases to output additional information in the callback methods, like the list of edges that are selected in the current solution and then which paths the method subtour() follows in the subgraph defined by the solution edges.

    Best regards,
    Mario

    1
  • Michael Renner
    Conversationalist
    First Question

    Hello Mario,

    Thank you for your answer.

    First of all, which of the constraints and/or variables of the formulation from the other post did you remove such that you get integer solutions in the MIPSOL callback that contain subtours (since the other formulation forbids them already)?

    I removed the decision variable Ulk, which was an auxiliary variable just for sub-tour elimination as well as constraint (4) which was responsible for catching the subtours.

    Which cycles are actually left? Only cycles among customer nodes or also cycles that include more than one depot?

    So far I have detected only cycles among customer nodes. Example in which (0) is the depot and all other nodes are customers:

    Route for Vehicle 1: 0 -> 8 -> 10 -> 13 -> 0 (This seems fine at first)
    Route for Vehicle 1: 2 -> 25 -> 27 -> 49 -> 51 -> 39 -> 38 -> 19 -> 20 -> 2 
    But somehow the vehicle has subtours which are not connected to the main route and do not connect back to the depot.

    All other variables: zij, yi seem to be set correctly. 

    What I usually do in such cases to output additional information in the callback methods, like the list of edges that are selected in the current solution and then which paths the method subtour() follows in the subgraph defined by the solution edges.

    That is a good idea, I will try to implement it right away.

    At the moment I'm unsure if reusing the method from the examples and modifying it is the correct way to go about implementing the subtour elimination in my case. If there are any pointers you could give me regarding the implementation of lazy subtour constraints I'd appreciate it.

    Best Regards,

    Michael Renner

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Michael,

    The examples should mainly demonstrate how lazy callbacks (or other features) work within Gurobi. Computational efficiency of the subroutines, as the method subtour() here, is not a primary goal. So, if performance is critical in your application (as it is usually the case), you might consider different procedures to find cycles in your solution.

    What you basically want is a Depth-First-Search (DFS) procedure in the subgraph defined by the selected edges in the solution. Only the edges between customers are relevant, all edges to depots can be ignored since they are not part of any cycle that you want to cut off. You might even consider to build a small graph structure for this based on an adjacency list. There are a lot of efficient pseudo-code implementations in the web for DFS or cycle detection. You might only need to adapt them slightly to fit your needs.

    Best regards,
    Mario

    1
  • Michael Renner
    Conversationalist
    First Question

    Hi Mario,

    thank you for your pointers. I'll have a look at Depth-First-Search procedures and see if I'm able to implement it as such.

    Best Regards,

    Michael Renner

    0
  • Ismail Gokay Dogan
    Gurobi-versary
    First Comment

    Hello Micheal,

    If you are working with multiple depot's I guess you have a vehicle set for each depot.

    First you should seperate those sets (i,j,k) pairs according to your depots since each k can depart from one depot.

    Then for each depot you are going to have a selected edge list, create a subgraph with those edges and detect all cycles. You can use networkx package for constructing the graph and simple_cycle method to detect all cycles in your subgraph. Then you can detect cycles which do not include depot. 

    Now you are ready to add lazy constraints according to those sublists.

    0

Please sign in to leave a comment.