Adding subtour elimination lazy constraints with callbacks for multiple vehicles & multiple days.
Awaiting user inputDear friends, as seen in another community post I checked out https://colab.research.google.com/github/Gurobi/modelingexamples/blob/master/lost_luggage_distribution/lost_luggage_distribution_gcl.ipynb#scrollTo=xzVolezWKRT
I adapted their solution to my model.
Basically, I have 2 types of ships that have to do maintenance in an offshore wind farm and got to visit each node within 2 days.
Here is my attempt at implementing this part:
from itertools import permutations
number_turbines = 4
vessels = [0,1]
days = [1,2]
travel_decision = model.addVars(vijd, vtype=GRB.BINARY,
lb=0, ub=1, name="travel_decision")
all_nodes = [0,1,2,3,4,5,6,7,8,9]
#every turbine has two nodes, one for delivery, one for pickup
#therefore harbor has nodes 0&9, 14 are turbine delivery nodes, 58 turbine pickupnodes
def subtourelim(model, where):
if where == GRB.Callback.MIPSOL:
# make a list of edges selected in the solution
vals = model.cbGetSolution(model._travel_decision)
selected = tuplelist((i, j) for v, i, j, d in
model._travel_decision.keys() if vals[v, i, j, d] > 0.5)
# find the shortest cycle in the selected edge list
tour = subtour(selected)
if len(tour) < len(all_nodes):
for v in vessels:
for d in days:
model.cbLazy(quicksum(
model._travel_decision[v, i, j, d] for i, j in permutations(tour, 2))
<= len(tour)  1)
# Given a tuplelist of edges, find the
# shortest subtour not containing harbor (0)
def subtour(edges):
unvisited = list(range(1, len(all_nodes)))
cycle = range(len(all_nodes) + 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
The output of my model is then (Ship 0, Day 1) route: [9>2>6>1>5>0], as intended!
for (Ship 0, Day 2) route: [3>7>4>8>3] AND [0>9] as not intended!
So it's basically doing a huge subtour in the wind farm itself and going from harbor to harbor, instead of driving to the farm doing the tour and coming back as it's supposed to.
So my question is, how do I create the subtourelimination constraints for two vessels and two days? It should be fairly easy but I am still a novice at coding :)
Any help would be greatly appreciated!!
Kind regards,
Daniel

I ran some more tests for n=8 turbines. Therefore all_nodes = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]
with [18] as delivery nodes, [916] as pickup nodes, and [0,17] as the harbor nodes.
For Vessel 0 I got the following routes:
For Day 1:
0170
198163111
For Day 2: (correct!)
0177155130
For Day 3:
0170
2104126142
So my model successfully suppresses all subtours apart from the subtour from harbor to harbor.
It should be only a few changes in my callback function to also include the harbor nodes in the subtour suppression, but I cannot find them.
Help me Obi Wan Kenobi, you're my only hope
0 
Hi Daniel,
You could check in the callback which subtours are eliminated by printing them. You will then see whether you even come across subtours with harbors and if yes, you can then more easily understand what is happening in the subtour function. If the computed subtour is correct, then maybe you are missing some variables in your \(\texttt{vessels}\) and \(\texttt{days}\) \(\texttt{for}\)loops when adding lazy constraints.
Best regards,
Jaromił1
Please sign in to leave a comment.
Comments
2 comments