Adding subtour elimination lazy constraints with callbacks for multiple vehicles & multiple days.

Dear friends, as seen in another community post I checked out https://colab.research.google.com/github/Gurobi/modeling-examples/blob/master/lost_luggage_distribution/lost_luggage_distribution_gcl.ipynb#scrollTo=xzVolezW-KRT
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, 1-4 are turbine delivery nodes, 5-8 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 tuple-list of edges, find the 
# shortest sub-tour 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 sub-tour 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 sub-tour-elimination 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

Daniel Saßmannshausen

January 24, 2023 14:15
Edited

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 [1-8] as delivery nodes, [9-16] as pickup nodes, and [0,17] as the harbor nodes.

For Vessel 0 I got the following routes:

For Day 1:

0-17-0

1-9-8-16-3-11-1

For Day 2: (correct!)

0-17-7-15-5-13-0

For Day 3:

2-10-4-12-6-14-2

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

Jaromił Najman

Gurobi Staff

January 24, 2023 14:54

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ł

Adding subtour elimination lazy constraints with callbacks for multiple vehicles & multiple days.

Comments

Didn't find what you were looking for?