Gurobi Python求解VRP时车场始终出现在解中的原因咨询

车场始终出现在解中的核心原因 #

1. 纯客户构成的回路被MTZ约束天然禁止 #

你当前使用的是带累积量u的MTZ类子回路消除约束，其中仅对两端均为客户点的边(i,j)设置了蕴含约束x[i,j]==1 → u[i] + q[i] = u[j]，且所有客户的需求q[i]均为正值。
假设存在一个完全不经过车场的客户回路，例如1→2→3→1，代入约束可得：

u1 + q1 = u2
u2 + q2 = u3
u3 + q3 = u1
将三式累加后得到q1+q2+q3 = 0，和客户需求为正的前提矛盾，因此所有不包含车场的解都是不可行解，优化器无法输出这类结果。

2. 只有包含车场的路径能满足约束 #

当路径包含车场时，涉及车场的边(0,i)或(j,0)不会触发MTZ的蕴含约束：

• 对于从车场出发的边(0,i)，没有u[0] + q[0] = u[i]的限制，仅需满足u[i]≥q[i]即可，不会出现需求累加矛盾
• 对于回车场的边(j,0)，同样没有u[j] + q[j] = u[0]的限制，不会触发矛盾
  因此哪怕车场到所有客户的距离极大，优化器也只能选择包含车场的可行解，否则没有符合约束的解可以输出。

补充说明 #

你当前写的出入边约束注释存在笔误：

• 第一组约束quicksum(x[i,j] for j in V if j !=i) ==1 for i in N是客户点的出边数为1，不是入边
• 第二组约束quicksum(x[i,j] for i in V if i !=j) ==1 for j in N是客户点的入边数为1，不是出边

内容的提问来源于stack exchange，提问作者kaiyu wei