如何使用 OR-Tools 在路线问题中将分组订单分配给单个车辆？

Question

我正在使用 OR-Tools 解决路线问题，其中订单组（集装箱）必须由同一辆车交付，但任何车辆都可以分配给该组。组内的订单不能在车辆之间分配，求解器应优化组到车辆的分配。

这是我迄今为止尝试过的：

我施加了一个约束，确保每个组最多由一辆车提供服务，但求解器找不到解决方案。

for i in range(self.num_items):
    group = self.items_group[i]
    idx = i+self.num_depots
    group_vehicles[group].append(self.routing.VehicleVar(self.manager.NodeToIndex(idx)))

for v_list in group_vehicles.values():
    used_vehicles = [v for v in v_list if v>-1]
    constraint = len(used_vehicles)==0 or self.routing.solver().Max(used_vehicles)==self.routing.solver().Min(used_vehicles)
    self.routing.solver().Add(constraint>0)

我尝试在同一组内的订单之间添加成对约束，以确保它们由同一辆车服务，但这种方法也失败了。

我正在努力正确执行此要求。显然，这个问题确实有一个解决方案，只是为了确保我的工作没有任何其他限制，除了这个。有人对如何在 OR-Tools 中建模此类约束有任何建议吗？

预先感谢您的帮助！

Answer 1

在求解开始时，所有节点均未分配，因此 VehicleVar 等于

-1

（未访问时使用的信号量值）。

由于求解器将尝试逐个添加节点来构建其第一个解决方案，因此您的约束必须是“我组中的所有 VehicleVar 必须为 -1 或使用相同的车辆索引值”。

注意：您也可以尝试使用

ActiveVar(index)

，它是一个布尔值，如果未访问节点，则设置为 false，又名

ActiveVar(index) * VehicleVar(index)

如果未访问则为

0

，否则为

vehicle_index

...

Answer 2

您可能首先想尝试惩罚

，而不是添加硬约束

cost += 10000* self.routing.solver().Max(used_vehicles)==self.routing.solver().Min(used_vehicles)

看看求解器是否能找到可行的解决方案，或者您的程序是否存在错误。有时它有助于放松问题，以帮助求解者找到初始可行的解决方案，这在更受约束的原始问题中可能很难达到。