旅行商变体

Question

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

中修复该问题

基本的优化模型是这样的：

加上subtour约束。

我做的模型比较复杂，因为需要到货时间、体积限制等，如果做不出来，我肯定做不下去了。

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

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

您的问题与gurobi无关。

for i, j, k in combinations(tour, 2)

combinations(l, r) returns 个长度为 r 的元组，在本例中为 2。您尝试将其解压缩为三个元素。您是说 combinations(tour, 3) 吗？如果您不遗漏您的问题中的 subtour 限制，我可以提供更准确的建议。

Answer 2

感谢@orlp 提示了我的错误，我不得不像这样修复 "subtour_elim" 函数：

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.01)
        # 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
            for k in salesmans:
                model.cbLazy(gp.quicksum(model._vars[i, j, k] for i, j in combinations(tour, 2)) <= len(tour)-1)

旅行商变体

Traveling salesman variant

python

optimization

traveling-salesman

gurobi