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, k in 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, k in 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