旅行推销员的型号

Question

我正在尝试以旅行推销员为起点来构建模型。我不仅需要一个旅行推销员，还需要多个推销员，这些推销员必须到达同一终端节点，然后再返回到原始节点。逻辑是相同的，试图使所有推销员之间的距离最小化，并且他们之间的距离覆盖了每个节点（城市）。我使用excel的求解器实现了该模型，但是它存在子路线问题，因此我决定使用gurobi，因为它已预先约束了traveling salesman example中的内容。

基本的优化模型是这样：

加上子行程约束。

我正在做的模型更加复杂，因为它需要到达时间，数量限制和其他条件，因此，如果我无法完成这项工作，那么我肯定会继续进行。

在输入代码之前，我的输入是：

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)
[当我只是尝试添加一些约束时，该模型在我不理解的subtour函数上有错误

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)
如果有人可以帮助我，我将非常感谢:)

我正在尝试以旅行推销员为起点来构建模型。我不仅需要一个旅行推销员，还需要多个推销员，这些推销员必须到达同一终端节点，并且...

Answer 1

您的问题与古罗比无关。

Answer 2

由于@orlp提示我我的错误，我不得不像这样修复“ subtour_elim”函数：