使用Google OR-Tools求解带AddDisjunction的VRP时无可行解

核心约束冲突导致无解 #

你的代码中存在路径约束逻辑矛盾，这是添加最大距离约束后无解的根本原因：

• 你设定Depot(0)只能前往节点9-16，但节点9-16的出边被完全限制：
  • 不能返回Depot（通过移除到End节点的边）
  • 不能前往i-8节点（比如9→1）
  • 不能前往其他9-16节点（代码中循环移除了所有同组节点的出边）
• 这意味着：如果车辆从Depot出发前往任意9-16节点，后续没有任何合法的下一个节点可去，路线无法继续也无法返回Depot；如果跳过所有9-16节点，Depot又没有其他可去的节点（因为你移除了Depot到1-8的边），只能直接返回，路线距离为0，远低于你期望的接近5000的目标。

当添加最大距离约束后，求解器找不到满足“路线距离在0到7000之间且符合路径约束”的可行解，因此直接返回“No solution found”。

修复步骤 #

1. 修正路径约束逻辑 #

根据你的需求，调整节点间的合法连接：

• 允许节点9-16前往其他9-16节点（移除代码中对9-16节点间出边的限制）
• 或者调整1-8节点的约束，允许9-16节点前往1-8节点（去掉9-16到i-8节点的出边限制），这样车辆可以从9-16到1-8，再返回Depot，形成合法闭环。

比如修改9-16节点的约束代码：

else:
    # 仅移除到i-8节点的边，保留到其他9-16节点的边
    nodo_da_eliminare = manager.NodeToIndex(i - N)  # 原代码i-N+1是错误的，修正为i-N（9对应1）
    routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
    connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
    # 移除下面的循环，允许9-16节点之间互相访问
    # for j in range(N + 1,2*N + 1):
    #     nodo_da_eliminare = manager.NodeToIndex(j)
    #     routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
    #     connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)

2. 调整目标函数与约束的匹配 #

你的目标是让路线距离尽可能接近5000，当前的目标函数写法可能导致求解器优先级混乱，建议改用线性化的软约束：

# 替换原目标函数代码
total_distance_var = time_dimension.CumulVar(routing.End(vehicle_id))
# 最小化总距离与5000的差值绝对值，转化为线性约束
slack_plus = routing.NewIntVar(0, 5000, 'slack_plus')
slack_minus = routing.NewIntVar(0, 7000, 'slack_minus')
routing.AddConstraint(total_distance_var + slack_minus - slack_plus == 5000)
routing.AddVariableMinimizedByFinalizer(slack_plus + slack_minus)

3. 调整Disjunction惩罚值 #

当前所有节点惩罚值都是100，建议给必访节点设置极高惩罚（比如100000），可选节点设置较低惩罚，避免求解器跳过关键节点导致路线无法形成。

验证修复 #

修正约束后，求解器可以找到合法路线：比如0→9→10→...→16→1→0（如果允许9-16到1-8的话），或者0→9→10→11→0（如果允许9-16之间通行并调整返回逻辑），同时满足最大距离约束。

内容的提问来源于stack exchange，提问作者Andrea Nucci