Location Routing Problem - Lazy Subtour Elimination Constraints
Answered
Good Day,
I am currently working on a multi-depot location routing problem with capacitated vehicles and depots. (Full model explanation can be found here).
Because of the nature of routing problems, adding the subtour elimination constraints before optimization can greatly increase model size for larger scale problems.
To tackle that problem I have looked into implementing lazy constraints and have found multiple Gurobi examples using this approach (tsp and lost luggage).
Unfortunately both of those examples only deal with a single depot and not multiple possible starting points for the routing process. In my case the selection of multiple depots with different cost-characteristics is neccessary.
When limiting my model to a single depot (0) the following code snipet from the lost luggage example worked and produced a solution not containing any subtours:
# Callback - use lazy constraints to eliminate sub-tours
def subtourelim(model, where):
if where == GRB.Callback.MIPSOL:
# make a list of edges selected in the solution
vals = model.cbGetSolution(model._x)
selected = tuplelist((i,j) for i, j, k in model._x.keys()
if vals[i, j, k] > 0.5)
# find the shortest cycle in the selected edge list
tour = subtour(selected)
if len(tour) < n:
for k in K: # changed from vans to K
model.cbLazy(quicksum(model._x[i, j, k]
for i, j in permutations(tour, 2))
<= len(tour)-1)
# Given a tuplelist of edges, find the shortest subtour not containing depot (0)
def subtour(edges):
unvisited = list(range(1, n))
cycle = range(n+1) # initial length has 1 more city
while unvisited:
thiscycle = []
neighbors = unvisited
while neighbors:
current = neighbors[0]
thiscycle.append(current)
if current != 0:
unvisited.remove(current)
neighbors = [j for i, j in edges.select(current, '*')
if j == 0 or j in unvisited]
if 0 not in thiscycle and len(cycle) > len(thiscycle):
cycle = thiscycle
return cycle
I have tried to adapt the subtour function for multiple depots but with no success (the model runs but produces subtours). These were some of the changes I had tried for a two depot instance:
depots= {0,1}
def subtour(edges):
unvisited = list(range(2, n)) # start with first customer = (2)
cycle = range(n+1) # initial length has 1 more city
while unvisited:
thiscycle = []
neighbors = unvisited
while neighbors:
current = neighbors[0]
thiscycle.append(current)
if current not in depots: # instead of !=0
unvisited.remove(current)
neighbors = [j for i, j in edges.select(current, '*')
if j in depots or j in unvisited] # instead of j==0
if depots not in thiscycle and len(cycle) > len(thiscycle): #instead of "0 not in"
cycle = thiscycle
return cycle
Since I did not find a way to inspect what the function is actually doing, I'm having a hard time understanding where I went wrong. Is there a way to adapt the original code to work for multiple depots?
Any suggestions would be greatly appreciated.
Kind Regards,
Michael Renner
-
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,
Mario1 -
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 -
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,
Mario2 -
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 -
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.
Comments
5 comments