Я пытаюсь построить модель, взяв за отправную точку коммивояжер. Вместо того, чтобы быть просто коммивояжером, мне нужно, чтобы несколько продавцов достигли одного и того же конечного узла, а затем вернулись к исходному узлу. Лог c тот же самый, пытаясь свести к минимуму расстояние, пройденное всеми продавцами, и что между всеми ими они покрывают каждый узел (город). Я реализовал модель с помощью решателя Excel, но у него есть проблемы с субтурами, поэтому я решил использовать gurobi, так как в нем было предварительно наложено ограничение, чтобы исправить это в примере коммивояжера .
Базовые Модель оптимизации c выглядит так:
Плюс ограничения субтура.
Модель, которую я делаю, более сложна, потому что для нее нужно время прибытия, ограничения по объему и другие, поэтому, если я не могу выполнить эту работу, я определенно не смогу продолжить.
Перед вводом код, который я вводил:
nodes = ['Node 1', 'Node 2', ... , 'Node9']
dist = {(Node1,Node2): 0.03, ..., (Node9, Node8): 0.5} #--> Distances between nodes for different nodes
salesmans = ['salesman1', 'salesman2']
Код, который я использовал в gurobi / python:
import math
import json
from itertools import combinations,product
def subtourelim(model, where):
if where == GRB.Callback.MIPSOL:
# make a list of edges selected in the solution
vals = model.cbGetSolution(model._vars)
selected = gp.tuplelist((i, j, k) for i, j, k in model._vars.keys()
if vals[i, j, k] > 0.5)
# find the shortest cycle in the selected edge list
tour = subtour(selected)
if len(tour) < len(nodes):
# add subtour elimination constr. for every pair of cities in subtour
model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
<= len(tour)-1)
def subtour(edges):
unvisited = nodes[:]
cycle = nodes[:] # Dummy - guaranteed to be replaced
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(thiscycle) <= len(cycle):
cycle = thiscycle # New shortest subtour
return cycle
import gurobipy as gp
from gurobipy import GRB
m = gp.Model()
# Variables: is city 'i' adjacent to city 'j' on the tour?
vars = m.addVars(dist.keys(), salesmans, obj=dist, vtype=GRB.BINARY, name='asignacion')
# Constraints: A node can't be visited by itself o leave to visit itself
for i, j, k in vars.keys():
if i==j:
m.addConstr(vars[i, j, k] == 0)
# From each node you have to visit one other node
m.addConstrs((vars.sum(i,'*','*') == 1 for i in nodes))
# Each node has to be visited once
m.addConstrs((vars.sum('*',j,'*') == 1 for j in nodes))
# Optimize the model
m._vars = vars
m.Params.lazyConstraints = 1
m.optimize(subtourelim)
Когда я просто пытаюсь добавить эти несколько ограничений, у модели есть ошибки по функциям субтура, которые я не понимаю
ValueError Traceback (most recent call last)
callback.pxi in gurobipy.CallbackClass.callback()
<ipython-input-2-a1cb8952ed8c> in subtourelim(model, where)
13 if len(tour) < len(nodes):
14 # add subtour elimination constr. for every pair of cities in subtour
---> 15 model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
16 <= len(tour)-1)
gurobi.pxi in gurobipy.quicksum()
<ipython-input-2-a1cb8952ed8c> in <genexpr>(.0)
13 if len(tour) < len(nodes):
14 # add subtour elimination constr. for every pair of cities in subtour
---> 15 model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j, k in combinations(tour, 2))
16 <= len(tour)-1)
ValueError: not enough values to unpack (expected 3, got 2)
Если кто-нибудь может мне помочь, я был бы очень-очень признателен :)