CVRP reload (multiple trips)

[Hoang Thai Quach]

Hi,

I'm testing the CVRP Load from this link

https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py

Objective: 295064
dropped orders: []
dropped reload stations: [3, 4]
Route for vehicle 0:
 0 Load(0) Time(0,0) -> 13 Load(0) Time(10,200) -> 1 Load(8) Time(53,386) -> 12 Load(0) Time(130,463) -> 5 Load(8) Time(172,505) -> 10 Load(0) Time(250,583) -> 11 Load(3) Time(267,600) -> 7 Load(7) Time(290,831) -> 15 Load(10) Time(309,850) -> 0 Load(13) Time(330,1500)
Distance of the route: 2716m
Load of the route: 13
Time of the route: 330min

Route for vehicle 1:
 0 Load(0) Time(0,0) -> 17 Load(0) Time(5,150) -> 9 Load(3) Time(45,550) -> 8 Load(7) Time(66,700) -> 6 Load(10) Time(84,850) -> 0 Load(13) Time(105,1500)
Distance of the route: 1872m
Load of the route: 13
Time of the route: 105min

Route for vehicle 2:
 0 Load(0) Time(0,0) -> 14 Load(0) Time(2,84) -> 21 Load(3) Time(30,104) -> 19 Load(11) Time(72,146) -> 2 Load(15) Time(97,171) -> 18 Load(0) Time(176,250) -> 20 Load(4) Time(201,550) -> 16 Load(12) Time(244,950) -> 0 Load(15) Time(265,1500)
Distance of the route: 2876m
Load of the route: 15
Time of the route: 265min

Total Distance of all routes: 7464m
Total Load of all routes: 41
Total Time of all routes: 700min

I think the output is not correct

1) Load of the route is calculated only for last trip of the vehicle

2) Index of the node in route is not correct: For example Vehicle 0 goes to node 1 and loads 8. Node 1. does not have demand value 8, and why Vehicle goes to node 13 and load 0?

Can some one show me how to correct index of the node for problem 2?

Thank you very much,

Thai

[Rummel]

Hello Thai,

Regarding your point 2:
I find the print somewhat misleading with regard to the load. First, the node ID is specified, which corresponds to the index of the data lists (0 to 21). The load indicates the load with which the vehicle reaches the node, i.e. before loading or unloading.
Let's take your example:
0 Load(0) Time(0,0) -> 13 Load(0) Time(10,200) -> 1 Load(8) Time(53,386) -> 12 Load(0) Time(130,463) -> ...

0 Load(0) Time(0,0): The vehicle starts at node 0 (depot) with load 0.
13 Load(0) Time(10,200): Nothing is loaded at node 0 and it continues to node 13 (designated as location 8 with a demand of 8 in the data) with a load of 0.
1 Load(8) Time(53,386): At node 13, 8 units are loaded and it continues to node 1 (referred to as "unload depot_first" in the data).
12 Load(0) Time(130,463): The 8 units are unloaded at node 1 and it continues empty to node 12 (referred to as location 7 in the data).

Does this help you any further?

Best Johannes

[Hoang Thai Quach]

thank you Johannes,

your explaination is very good and I understand now. In the output of CVRP (https://developers.google.com/optimization/routing/cvrp),  the load for each node is after loading and leaving the node, not the load before reaching the node and it is really confusing with cvrp_load.py.

Thai

[Rummel]

Hello Thai,

please check the CVRP tutorial again. I would say the printed loading there is before the loading at the node, too.

Best Johannes

[Hoang Thai Quach]

Here is the output of CVRP example on the website. Vehicle 0 goes to Node 4. and Load is 4, if before loading at the node, the load must be 0.

Objective: 6208
Route for vehicle 0:
 0 Load(0) ->  4 Load(4) ->  3 Load(6) ->  1 Load(7) ->  7 Load(15) ->  0 Load(15)
Distance of the route: 1552m

Load of the route: 15

Route for vehicle 1:
 0 Load(0) ->  14 Load(4) ->  16 Load(12) ->  10 Load(14) ->  9 Load(15) ->  0 Load(15)
Distance of the route: 1552m

Load of the route: 15

Route for vehicle 2:
 0 Load(0) ->  12 Load(2) ->  11 Load(3) ->  15 Load(11) ->  13 Load(15) ->  0 Load(15)
Distance of the route: 1552m

Load of the route: 15

Route for vehicle 3:
 0 Load(0) ->  8 Load(8) ->  2 Load(9) ->  6 Load(13) ->  5 Load(15) ->  0 Load(15)
Distance of the route: 1552m

Load of the route: 15

Total distance of all routes: 6208m
Total load of all routes: 60

Best regards,

Thai

[Rummel]

Oh, interesting.

I haven't run the code by myself. I referenced to the output given at the section "Running the program":

0 Load(0) -> 4 Load(0) -> 3 Load(4) -> 1 Load(6) -> ...