OR Tools单车辆CVRP重载功能Java实现返回空解决方案排查

问题排查与修复方案 #

核心错误点

• 容量维度初始化参数错误
  调用routing.addDimension添加容量维度时，第四个参数fix_start_cumul_to_zero设为了true，强制容量维度初始值为0，和车辆从仓库出发时满载的业务逻辑完全冲突，也和后续用负需求模拟补货的逻辑不兼容，直接导致大部分场景下无合法解。
• 析取约束传入索引类型错误
  routing.addDisjunction方法接收的是OR-Tools内部的routing索引，代码中错误调用manager.indexToNode拿到自定义节点ID传入，相当于给错误节点设置了允许跳过的析取约束，导致求解器被强制要求访问所有虚拟补货节点，无法构造合法路径。
• 容量维度取值范围未适配补货逻辑
  用负需求表示补货时，会触发容量维度累积值低于0的情况，而OR-Tools默认维度累积值最小值为0，补货操作会被直接判定为非法，排除所有合法路径。
• 多趟数计算存在浮点精度风险
  用浮点数运算计算最小趟数，容易因精度问题导致计算的趟数少于实际需要，无法覆盖全部需求。
• 求解时间偏短
  使用GUIDED_LOCAL_SEARCH元启发式算法时，1秒的求解时间对于部分场景偏短，可能提前终止返回空结果。

修复代码示例

1. 调整容量维度初始化逻辑

// 关闭固定初始值为0的配置
routing.addDimension(demandCallbackIndex, 0, data.vehicleCapacity, false, "Capacity");
RoutingDimension capacityDimension = routing.getDimensionOrDie("Capacity");
// 手动设置车辆起点初始容量为满载
for (int i = 0; i < data.vehicleNumber; i++) {
  long startIndex = routing.start(i);
  capacityDimension.setCumulVarLowerBound(startIndex, data.vehicleCapacity);
  capacityDimension.setCumulVarUpperBound(startIndex, data.vehicleCapacity);
}

2. 修正析取约束的索引转换

for(int i = 1; i <= data.multiTrips - 1; i++) {
  // 转换为OR-Tools内部的routing索引再传入
  long routingIndex = manager.nodeToIndex(i);
  routing.addDisjunction(new long[] { routingIndex }, 0);
}

3. 调整需求符号避免容量累积为负
   将补货节点的需求从负运力改为正运力，客户需求改为负，容量维度记录剩余运力：每送一个客户减去对应需求（不会低于0），每到补货节点加上运力回到满载状态，不会出现负数非法值。
4. 替换多趟数计算为整数运算

private static int calculateMultiTrips(long totalVolume, int capacity) {
    return (int) ((totalVolume + capacity - 1) / capacity);
}

5. 适当延长求解时间
   将搜索参数中的时间限制调整为2-5秒，避免求解器提前终止。

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