使用PuLP求解TSP时添加到达时间变量致问题不可行求助

问题描述 #

我使用Python的PuLP优化器求解旅行商问题(TSP)，版本1基于ndarray格式的时间矩阵计算最优路线，可正常运行得到最优解。但添加存储车辆到达各节点时间的decisionVariableT变量及相关约束后，问题变为不可行状态，请求排查代码问题。

版本1代码（可正常运行） #

import numpy as np 
from pulp import *

time_matrix = np.array([[0,5,4,6,7,10], 
                      [5,0,3,2,6,15], 
                      [4,3,0,4,5,6],
                      [6,2,4,0,7,8],
                      [7,6,5,7,0,11],
                      [10,15,6,8,11,0]])

row,col = time_matrix.shape

problem = LpProblem('TravellingSalesmanProblem', LpMinimize)

# Decision variable X for truck route
decisionVariableX = LpVariable.dicts('decisionVariable_X', ((i, j) for i in range(row) for j in range(row)), lowBound=0, upBound=1, cat='Integer')

# subtours elimination
decisionVariableU = LpVariable.dicts('decisionVariable_U', (i for i in range(row)), lowBound=1, cat='Integer')

# Objective Function
problem += lpSum(time_matrix[i][j] * decisionVariableX[i, j] for i in range(row) for j in range(row))

# Constraint
for i in range(row):
  problem += (decisionVariableX[i,i] == 0) # elimination of (1 to 1) route
  problem += lpSum(decisionVariableX[i,j] for j in range(row))==1 # truck reaches all points once
  problem += lpSum(decisionVariableX[j,i] for j in range(row)) ==1 #truck dispatches from all points once
  for j in range(row):
    if i != j and (i != 0 and j != 0):
        problem += decisionVariableU[i]  <=  decisionVariableU[j] + row * (1 - decisionVariableX[i, j])-1 # sub-tour elimination for truck

status = problem.solve() 
print(f"status: {problem.status}, {LpStatus[problem.status]}")
print(f"objective: {problem.objective.value()}")
for var in problem.variables():
    if (problem.status == 1):
        if (var.value() !=0):
            print(f"{var.name}: {var.value()}")

版本1运行结果 #

status: 1, Optimal
objective: 33.0
decisionVariable_U_1: 5.0
decisionVariable_U_2: 2.0
decisionVariable_U_3: 4.0
decisionVariable_U_4: 1.0
decisionVariable_U_5: 3.0
decisionVariable_X_(0,_4): 1.0
decisionVariable_X_(1,_0): 1.0
decisionVariable_X_(2,_5): 1.0
decisionVariable_X_(3,_1): 1.0
decisionVariable_X_(4,_2): 1.0
decisionVariable_X_(5,_3): 1.0

版本2新增代码（导致模型不可行） #

# Decision variable T for truck arrival time
decisionVariableT = LpVariable.dicts('decisionVariable_T', (i for i in range(row)), lowBound=0, cat='Integer')

M=1000

# Calculating truck arrival time at each node
for i in range(row):
    for j in range(row):
        if (decisionVariableX[i,j]==1):
            problem += decisionVariableT[j] == decisionVariableT[i] + time_matrix[i][j]

版本2运行结果 #

status: -1, Infeasible
objective: 0.0

问题原因及修正方案 #

核心问题 #

版本2中的约束写法完全错误：在建模阶段直接判断decisionVariableX[i,j]==1，但此时变量尚未被求解，属于未知状态，这行代码不会生成任何有效的约束条件，反而因为没有正确关联路径变量X和到达时间变量T的逻辑，导致模型内部出现矛盾，最终不可行。

正确约束写法（大M法） #

需要用大M法构建逻辑约束，确保当路径X[i,j]=1（即车辆从i到j）时，到达j的时间等于到达i的时间加上i到j的耗时；当X[i,j]=0时，约束自动失效，不影响模型可行性。同时需要固定起点的到达时间（比如设起点0的到达时间为0），避免时间变量存在自由偏移。

修正后的新增代码如下：

# Decision variable T for truck arrival time
decisionVariableT = LpVariable.dicts('decisionVariable_T', (i for i in range(row)), lowBound=0, cat='Integer')

M = 1000  # 取一个远大于最大可能总时间的数，这里总最优时间是33，1000足够

# 固定起点（节点0）的到达时间为0
problem += decisionVariableT[0] == 0

# 构建到达时间约束：当X[i,j]=1时，T[j] = T[i] + time_matrix[i][j]
for i in range(row):
    for j in range(row):
        if i != j:  # 排除自环路径
            # 下界约束：T[j] >= T[i] + time - M*(1-X[i,j])
            problem += decisionVariableT[j] >= decisionVariableT[i] + time_matrix[i][j] - M * (1 - decisionVariableX[i,j])
            # 上界约束：T[j] <= T[i] + time + M*(1-X[i,j])
            problem += decisionVariableT[j] <= decisionVariableT[i] + time_matrix[i][j] + M * (1 - decisionVariableX[i,j])

修正后模型说明 #

• 固定起点时间T[0]=0：消除时间变量的自由度，确保模型有唯一的时间基准。
• 大M约束：通过两个不等式，在X[i,j]=1时强制T[j]等于T[i]+time_matrix[i][j]；在X[i,j]=0时，M的存在让约束范围足够宽松，不会对其他路径的时间逻辑造成限制。

验证结果 #

将修正后的代码替换版本2的新增部分，重新运行模型，会得到包含到达时间变量的最优解，模型状态恢复为Optimal。

内容的提问来源于stack exchange，提问作者s.p