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
-
正式なコメント
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
投稿コメントは受け付けていません。
コメント
1件のコメント