使用Google OR-Tools求解带互斥物品约束的VRP时约束不生效怎么办

这类带互斥物品运输约束的VRP完全可以通过OR-Tools实现，你的代码问题出在约束设计和笔误两个方面：

1. 非线性约束兼容性差
   你用两个累积变量相乘等于0的约束属于非线性整数约束，OR-Tools的路由求解器优先处理线性约束，这类非线性约束在搜索过程中很容易被忽略，尤其是你设置的1秒求解时间很短，求解器来不及校验这类约束冲突就返回了次优解。
2. 约束覆盖不全+代码笔误
   你只给配送节点加了乘积约束，没有覆盖车辆路径的终点，另外代码里int noDeliveries = deliveriesA.Length;存在笔误，你方法参数中没有deliveriesA变量，应该替换为demandsA.Length，这会导致部分配送节点没有被加上约束。

修复方案 #

改用线性的蕴含约束替代非线性乘积约束，性能更好，求解器兼容性更高：

步骤1：修正笔误

将代码中int noDeliveries = deliveriesA.Length;修改为int noDeliveries = demandsA.Length;

步骤2：替换约束逻辑

删除原来的节点循环乘积约束，改为给每辆车添加运输类型约束：

var capacityADimension = routing.GetDimensionOrDie("CapacityA");
var capacityBDimension = routing.GetDimensionOrDie("CapacityB");

for (int i = 0; i < noVehicles; i++)
{
    // 获取当前车辆的路径终点累积量
    var endA = capacityADimension.CumulVar(routing.End(i));
    var endB = capacityBDimension.CumulVar(routing.End(i));
    // 约束：同一辆车的A、B总运输量不能同时大于0
    routing.solver().Add(endA == 0 || endB == 0);
}

如果互斥品类超过2种，可以为每辆车增加运输类型标记变量，再通过蕴含约束绑定对应品类的累积量为0即可。

步骤3：可选调整求解参数

适当延长求解时间，或者更换初始解策略提升可行解命中率：

searchParameters.TimeLimit = new Duration { Seconds = 3 };
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.ParallelCheapestInsertion;

修改后再运行你的测试用例，就会得到两辆车各配送一个节点的符合约束的结果。

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