MIP的多个旅行推销员问题

Question

我一直在尝试使用MIP Link中已经制作的代码在普通TSP中实现mTSP

所以这是我到目前为止在python中拥有的代码，它向我抛出一个我不理解的错误：

places = ['Antwerp', 'Bruges', 'C-Mine', 'Dinant', 'Ghent',
          'Grand-Place de Bruxelles', 'Hasselt', 'Leuven',
          'Mechelen', 'Mons', 'Montagne de Bueren', 'Namur',
          'Remouchamps', 'Waterloo']

salesman=['Salesman1','Salesman2']

# distances in an upper triangular matrix
dists = [[83, 81, 113, 52, 42, 73, 44, 23, 91, 105, 90, 124, 57],
         [161, 160, 39, 89, 151, 110, 90, 99, 177, 143, 193, 100],
         [90, 125, 82, 13, 57, 71, 123, 38, 72, 59, 82],
         [123, 77, 81, 71, 91, 72, 64, 24, 62, 63],
         [51, 114, 72, 54, 69, 139, 105, 155, 62],
         [70, 25, 22, 52, 90, 56, 105, 16],
         [45, 61, 111, 36, 61, 57, 70],
         [23, 71, 67, 48, 85, 29],
         [74, 89, 69, 107, 36],
         [117, 65, 125, 43],
         [54, 22, 84],
         [60, 44],
         [97],
         []]

# number of nodes and list of vertices
n, V, S = len(dists), set(range(len(dists))), set(range(len(salesman)))


# distances matrix
c = [[0 if i == j
      else dists[i][j-i-1] if j > i
      else dists[j][i-j-1]
      for j in V] for i in V]

model = Model()

# binary variables indicating if arc (i,j) is used on the route or not
x = [[[model.add_var(var_type=BINARY) for j in V] for i in V] for s in S]

# objective function: minimize the distance
model.objective = minimize(xsum(c[i][j]*x[i][j][s] for i in V for j in V for s in S))

错误是：

IndexError                                Traceback (most recent call last)
<ipython-input-52-8550246fcd90> in <module>
     48 
     49 # objective function: minimize the distance
---> 50 model.objective = minimize(xsum(c[i][j]*x[i][j][s] for i in V for j in V for s in S))
     51 
     52 

~/opt/anaconda3/lib/python3.7/site-packages/mip/model.py in xsum(terms)
   1453     """
   1454     result = mip.LinExpr()
-> 1455     for term in terms:
   1456         result.add_term(term)
   1457     return result

<ipython-input-52-8550246fcd90> in <genexpr>(.0)
     48 
     49 # objective function: minimize the distance
---> 50 model.objective = minimize(xsum(c[i][j]*x[i][j][s] for i in V for j in V for s in S))
     51 
     52 

IndexError: list index out of range

而且这对我来说没有意义，因为我只是创建了另一个总结。预先非常感谢。

Answer 1

这是Python问题，而不是Gurobi问题。您不完全了解嵌套列表理解的工作原理。

我们可以通过以下方式重现此内容：

x = [[["x%s%s%s" % (i,j,k) for i in range(2)] for j in range(2)] for k in range(3)]
i = 0
j = 0
k = 2
x[i][j][k]

x不是x[i][j][k]，而是x[k][j][i]。因此，在上面的示例中，我们看到：

[[['x000', 'x100'], ['x010', 'x110']], [['x001', 'x101'], ['x011', 'x111']], [['x002', 'x102'], ['x012', 'x112']]]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-13-a2e90cc605ea> in <module>()
      4 j = 0
      5 k = 2
----> 6 x[i][j][k]

IndexError: list index out of range

如果我们会输入：

i = 0
j = 0
k = 2
print(x[k][j][i])

我们会看到：

x002

结论：尝试：

x = [[[model.add_var(var_type=BINARY) for s in S] for j in V] for i in V]
...
x[i][j][s]