# Subtour Elimination for several vehicles (VRP)

Hi,

I try to implement the Subtour Elimination constraint for a Vehice Routing Problem with the "callback methode".

I tried to modify the code from tsp.py so it would work with several vehicles (highlited in bold). My variables consist of three indices (i,j for the nodes, k for the vehicle), so i added k's where I thought it would be necessary. Additionally, I added a second argument in the subtour-function (motivation: for every vehicle k the function looks for subtours seperately) and implemented a for-loop in the subtourelim function to eliminate subtours for every vehicle k.

Nevertheless, I still get a solution with subtours if I use more than just one vehicle. Following the code for the functions subtourelim and subtour.

def subtourelim(model, where):

for k in SetK:#SetK=[k for k in range(K)], where K is the maximal number of vehicles used

if where == GRB.Callback.MIPSOL:

vals = model.cbGetSolution(model._vars)

# find the shortest cycle in the selected edge list

tour = subtour(vals,k)

if len(tour) < I: # I is the number of nodes to be visited

# add subtour elimination constr. for every pair of cities in tour

model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j in combinations(tour, 2))

<= len(tour)-1)

def subtour(vals,k):

# make a list of edges selected in the solution

edges = gp.tuplelist((i, j,k)for i, j,kin vals.keys() if vals[i, j, k] > 0.5)

unvisited = list(i for i in SetI if selection[i]==1)

cycle = range(num_I+1) # initial length has 1 more city

while unvisited: # true if list is non-empty

thiscycle = []

neighbors = unvisited

while neighbors:

current = neighbors[0]

thiscycle.append(current)

unvisited.remove(current)

neighbors = [j for i, j,kin edges.select(current, '*') if j in unvisited]

if len(cycle) > len(thiscycle):

cycle = thiscycle

return cycle

Please sign in to leave a comment.

## Comments

0 comments