OR-Tools带资源约束VRPTW中未使用车辆占用仓库容量问题求助

问题背景 #

在测试带资源约束的VRPTW示例时发现：当数据模型中设置的车辆总数大于实际运营需要的数量时，生成的规划结果会出现未使用的空路线车辆，这类车辆仍然会占用仓库容量，导致实际运营的车辆出发时间被推迟，整体路线规划效率低下。

如下模拟案例中，0号、1号为空驶未使用车辆，两者占用仓库资源导致2号、3号运营车辆出发时间被延后：

Route for vehicle 0:
0 Time(0,0) -> 0 Time(20,20)
Time of the route: 20min

Route for vehicle 1:
0 Time(5,5) -> 0 Time(25,25)
Time of the route: 20min

Route for vehicle 2:
0 Time(10,10) -> 1 Time(17,17) -> 2 Time(25,25) -> 0 Time(30,30)
Time of the route: 20min

Route for vehicle 3:
0 Time(15,15) -> 3 Time(17,20) -> 4 Time(30,30) -> 0 Time(35,35)
Time of the route: 20min

原有约束代码如下，该代码固定所有车辆的仓库占用系数为1，没有区分车辆是否实际投入使用：

depot_usage = [1 for i in range(len(intervals))]
solver.Add(
    solver.Cumulative(intervals, depot_usage, data['depot_capacity'], 'depot'))

解决方法 #

需要将车辆的仓库占用系数和车辆是否被使用的状态绑定，未使用的车辆占用系数设为0，不参与仓库容量累计计算，修改后的代码如下：

depot_usage = []
for vehicle_id in range(data['num_vehicles']):
    # 车辆未使用时资源占用为0，使用时占用为1
    usage = solver.MakeIfElseExpr(
        solver.IsVehicleUsed(vehicle_id),
        1,
        0
    )
    depot_usage.append(usage)

solver.Add(
    solver.Cumulative(intervals, depot_usage, data['depot_capacity'], 'depot')
)

调整后仓库容量累计约束只会统计实际投入运营的车辆的资源占用，空驶未使用的车辆不会再占用仓库容量，也就不会挤压运营车辆的出发时间窗口，规划效率会明显提升。

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