OR-Tools CVRP 与多次行程

Question

我正在尝试使用 OR-Tools 的 Routing Solver 来求解 Multi Trip Capacitated VRP。我需要的是

一个站点，路线从这里开始和结束。
一个卸货地点（不同于仓库）
设置时间window和每个节点的需求

所以车辆应该从每个节点取货，直到容量被填满。然后到“卸货地点”，卸下他们所有的重量，并不断收集节点的需求，直到达到时限或所有货物都被收集。然后return回车厂

CVRP Reload Example 似乎很近，但就我而言，在路线的尽头，车辆应该在仓库前到达卸货地点。换句话说，车辆不能带载到站点（起始、结束位置）。

示例：

0: Depot
1: Unloading Location
2, 3, 4, 5, 6, 7: Nodes to pick up demand


0 > 2 > 3 > 4 > 1 (unload) > 5 > 6 > 7 > 1 (unload) > 0
0 > 2 > 3 > 4 > 1 (unload) > 5 > 6 > 7 > 0 This is the result cvrp_reload returns.

我对 or-tools 还很陌生，正在尝试弄明白。有什么想法可以帮帮我吗？

我正在使用 Python 和 or-tools v8.2
这是 github 的交叉 post。

我认为，可以通过使用 count_dimension 在最后一点（仓库前卸载）之前实施前置约束，但我不知道如何实现。

Answer 1

只需添加

    # Vehicles must be empty upon arrival
    capacity_dimension = routing.GetDimensionOrDie("Capacity")
    for v in range(manager.GetNumberOfVehicles()):
        print(f"vehicle {v}")
        end = routing.End(v)
        #routing.solver().Add(capacity_dimension.CumulVar(end) == 0) # see comment below
        capacity_dimension.SetCumulVarSoftUpperBound(end, 0, 100_000)

可能的输出：

./2442_unload.py
...
I0417 23:53:02.181640 17437 search.cc:260] Solution #317 (372696, objective maximum = 4838552, time = 2969 ms, branches = 3223, failures = 940, depth = 33, MakeInactiveOperator, neighbors = 265820, filtered neighbors = 317, accepted neighbors = 317, memory used = 14.93 MB, limit = 99%)
I0417 23:53:20.290527 17437 search.cc:260] Solution #318 (469816, objective minimum = 372696, objective maximum = 4838552, time = 2987 ms, branches = 3239, failures = 945, depth = 33, MakeInactiveOperator, neighbors = 267395, filtered neighbors = 318, accepted neighbors = 318, memory used = 14.93 MB, limit = 99%)
I0417 23:53:21.045410 17437 search.cc:260] Solution #319 (469816, objective minimum = 372696, objective maximum = 4838552, time = 2988 ms, branches = 3247, failures = 947, depth = 33, MakeActiveOperator, neighbors = 267415, filtered neighbors = 319, accepted neighbors = 319, memory used = 14.93 MB, limit = 99%)
I0417 23:53:22.304931 17437 search.cc:260] Solution #320 (372696, objective maximum = 4838552, time = 2989 ms, branches = 3253, failures = 949, depth = 33, MakeActiveOperator, neighbors = 267464, filtered neighbors = 320, accepted neighbors = 320, memory used = 14.93 MB, limit = 99%)
I0417 23:53:30.987548 17437 search.cc:260] Finished search tree (time = 2998 ms, branches = 3259, failures = 982, neighbors = 268318, filtered neighbors = 320, accepted neigbors = 320, memory used = 14.93 MB)
I0417 23:53:31.046630 17437 search.cc:260] End search (time = 2998 ms, branches = 3259, failures = 982, memory used = 14.93 MB, speed = 1087 branches/s)
Objective: 372696
dropped orders: [25]
dropped reload stations: [3, 5]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 20 Load(0) Time(75,506) -> 12 Load(3) Time(94,525) -> 14 Load(6) Time(119,550) -> 13 Load(10) Time(140,700) -> 8 Load(13) Time(159,1000) -> 0 Load(0) Time(237,1500)
Distance of the route: 2624m
Load of the route: 0
Time of the route: 237min

Route for vehicle 1:
 1 Load(0) Time(0,0) -> 19 Load(0) Time(2,182) -> 24 Load(3) Time(20,200) -> 26 Load(7) Time(42,400) -> 4 Load(15) Time(89,770) -> 7 Load(15) Time(92,773) -> 11 Load(0) Time(169,850) -> 17 Load(3) Time(188,959) -> 10 Load(11) Time(229,1000) -> 1 Load(0) Time(307,1500)
Distance of the route: 2648m
Load of the route: 0
Time of the route: 307min

Route for vehicle 2:
 2 Load(0) Time(0,0) -> 23 Load(0) Time(15,63) -> 22 Load(4) Time(37,85) -> 21 Load(7) Time(85,101) -> 9 Load(10) Time(104,120) -> 18 Load(0) Time(184,200) -> 16 Load(8) Time(226,600) -> 15 Load(12) Time(248,800) -> 6 Load(15) Time(268,1000) -> 2 Load(0) Time(346,1500)
Distance of the route: 2624m
Load of the route: 0
Time of the route: 346min

Total Distance of all routes: 7896m
Total Load of all routes: 0
Total Time of all routes: 890min

注意：我使用了 Soft 约束，否则求解器更愿意删除所有节点并且从不设法逃避此解决方案搜索 space 点。

OR-Tools CVRP 与多次行程

OR-Tools CVRP with Multiple Trips

traveling-salesman

or-tools

vehicle-routing