如何使用gurobipy消除子轮廓并在访问点中强制执行特定顺序？

Question

我知道Gurobi网站上有一个TSP示例。我花了很多时间来理解它，但是我却不能（完全）理解它。因此，我决定自己制作一个更简单的代码。

问题：我无法摆脱子游览，而且我不知道在到达交货地点之前应如何以及在访问限制之前要包括哪些限制。不必立即从取货点到交货点。如果在到达交货点之前访问了多个接送点，则很好。

我的代码执行以下操作：它生成包含以下内容的随机订单：取货点，交货点和要发送的包裹数量（如果成功，我还希望包括交货时间，车辆容量，多辆车辆等） 。生成订单后，它会在车辆，提取点和交付点之间创建一个距离矩阵。然后，我使用Gurobi优化器找到最佳路线。我能够添加阻止从点i到点i行驶的约束。我添加了应该访问每个点的约束，并且由于它是一个对称矩阵，因此我还添加了阻止在两个点之间移动的约束：0-4-0-4 -...

# Using spyder 3.6 and gurobi. For simplicity I only added the DISTANCE matrix, not how the orders and distance matrix are created

import numpy as np
from gurobipy import *

DISTANCE = [[0, 96.64884893, 94.41398202, 88.23264702, 18.86796226, 97.52948272, 105.99056562],
    [96.64884893, 0, 183.14202139, 19.02629759, 80.77747211, 194.17775362, 189.1692364],
    [94.41398202, 183.14202139, 0, 169.53170795, 113.25193155, 55.22680509, 122.58874337],
    [88.23264702, 19.02629759, 169.53170795, 0, 74.81310046, 185.01081049, 187.01069488],
    [18.86796226, 80.77747211, 113.25193155, 74.81310046, 0, 114.28035702, 113.35784049],
    [97.52948272, 194.17775362, 55.22680509, 185.01081049, 114.28035702, 0, 73.00684899],
    [105.99056562, 189.1692364, 122.58874337, 187.01069488, 113.35784049, 73.00684899, 0]]

dist = np.array(DISTANCE)
n=dist.shape[0]

# Create model
m = Model('Pickup_Deliver_Optimizer')

# Add variables
x = {}                    
for i in range(n):  
    for j in range(n):  
        x[i,j] = m.addVar(vtype=GRB.BINARY)  

# Objective function
obj = (quicksum(x[i,j]*DISTANCE[i][j] for i in range(n) for j in range(n)))
m.setObjective(obj, GRB.MINIMIZE)

# Constraints
# Constraint that does not allow to travel from point i to point i
for i in range(n):
    m.addConstr(x[i,i],GRB.EQUAL,0) 

# To prevent the vehicle from returning to the same point from the previous point: if x[i,j] == 1, then x[j,i] == 0
m.addConstrs((x[i,j] == 1) >> (x[j,i] == 0) for i in range(n) for j in range(n))

# Visit all points by making a connection between two points
for i in range(n):
    m.addConstr(quicksum(x[i,j] for j in range(n)),GRB.EQUAL,1)
    m.addConstr(quicksum(x[j,i] for j in range(n)),GRB.EQUAL,1)

# The vehicle should return to its starting point
m.addConstr(quicksum(x[i,0] for i in range(n)),GRB.EQUAL,1)

# The vehicle always starts at its starting point
m.addConstr(quicksum(x[0,i] for i in range(n)),GRB.EQUAL,1)

m.update()
m.optimize()

使用来自Gurobi的TSP示例，最佳解决方案应为〜522。我得到的结果是〜457。差异是不同路线的结果。根据Gurobi示例，正确的应该是[0、4、1、3、2、5、6、0]。我的代码创建了以下两个循环：[0，4，1，3，0]和[2，5，6，2]。与Gurobi示例中的一条路线相比，两条路线的距离要短，因此我将两条路线作为最佳解决方案。我知道出了什么问题，但是我不知道如何使用addConstr（）解决此问题。根据Wikipedia https://en.wikipedia.org/wiki/Travelling_salesman_problem上的Miller-Tucker-Zemlin方法，我在网上查看了该子行程背后的理论是什么，我将不得不添加一个新的约束'u'。但是，我认为通过添加这样的约束可以更轻松地解决它：

# Create one route
for j in range(n):
    if j != 0:
        m.addConstrs((x[i,j] == 1) >> (quicksum(x[j,k] == 1)) for i in range(n) for k in range(n))

这行代码不起作用，但是看起来像这样的东西应该可以解决问题。这将迫使节点相互连接。

我似乎无法解决的第二个问题是在交货地点之前到达接载地点。 DISTANCE矩阵中的奇数行/列表示拾取点，偶数行/列表示交货点（行/列0是车辆的起点）。我可以使用当前变量x [i，j]来解决这个问题，还是需要添加一个其他变量（我期望如此）？

非常感谢您的帮助。

Answer 1

如果要使用指标约束，则需要定义新的二进制变量（请参见here）。

我想您最好通过添加减少子行程约束作为切入点。为此，您需要检查当前解决方案中是否有任何子行程，即不包含所有节点的行程，并禁止它们进行下一轮优化。概述了here和here。我链接这些是因为您没有指定已经检查过的TSP代码。

PySCIPOpt中还有一个直观的实现使用networkx to compute subtours。