Multiple returns to depot

[risinghero]

Thanks for awesome library. Currently I try to solve CVRP with vehicles that can return multiple times to depot. For example, we have one vehcile. Max weight of vehicle is 1000kg and we have two orders with demand equal to 1000kg. We can fill demand like this: depot->order1->depot->order2->depot. The best solution I currently can imagine is to run optimization multiple times for each depot return. Is there better solution?

[Mizux]

Does vehicle capacity automatically manage this for you ? cf https://github.com/google/or-tools/blob/master/examples/cpp/cvrptw.cc#L87

[risinghero]

Unfortunately, no. I thought it should. But when I tried it gives me route: depot->order1->depot. While it should be depot->order1->depot->order2->depot Small addition: I use optional orders with penalty.

[braktar]

Define your Capacity dimension with a slack_max value greater than 1000, set fix_start_cumul_to_zero to false.

Then you will be able to define negative values for some node. In your case, be sure that the slackVar value at the deliveries nodes are equal to zero.

My advice will be to define the deliveries with negative values with a slack value set to 0. And depots return with a value greater or equal than 0 and a non defined slack value.

[risinghero]

Thx @braktar . As I see you suggest to make it like refueling example. I'll have to add some dummy nodes for depot return.

[CnApTaK]

can anyone show any working example? small one? like 1 vehicle and 2 deliveries

[risinghero]

@braktar, @Mizux unfortunately it doesn't work. The problem is that if you add multiple nodes for depot return solver will just stack them. So you visit depot node multiple times and only then go for orders. The reason why refueling example worked is that refieling nodes were selected randomly not in one point.

[braktar]

Indeed, on large instances it tends to stack depot returns and never try to insert missions between. A way to partially avoid this behavior is to define a 'minimum value to reload' as transitVar.

[bertop89]

Any solution regarding this? @risinghero

[risinghero]

@bertop89 no - no good solution(

[bertop89]

@risinghero I tried splitting it into several consecutive VRP instances (routes), but I'm having issues when finding solutions to those consecutive more constrained routes. Tried with several strategies (PARALLEL_CHEAPEST_INSERTION, PATH_MOST_CONSTRAINED_ARC), more relaxed penalties strategies, etc. and still nothing.

[Mizux]

Simply add optional depot to reload/unload your vehicles

example in this related thread: https://github.com/google/or-tools/issues/862#issuecomment-425905173

[Mizux]

@risinghero

Unfortunately, no. I thought it should. But when I tried it gives me route: depot->order1->depot. While it should be depot->order1->depot->order2->depot Small addition: I use optional orders with penalty.

In the current implementation ( <= 6.10), once you define one disjunction for one (set) of node(s) all nodes become optional. So you must add a disjunction for each nodes too. note: to keep some node mandatory you can try to set penalty to kint64max

[risinghero]

@Mizux good day! I will try later. But I have feeling that the best result I can get is smth like this: depot->order1->depot->order2->depot->order3->depot instead of depot->order1->order2->depot->order3->depot Somehow there should be minimization of depot count-maybe add some payment for each visit to them. But how to do this. Value for disjunction cant be negative.

[skyien]

@risinghero Did you find a solution?

[ChadiMezz]

@risinghero It would be extremely helpful if you have results on the problem ! :D

[lperron]

Should be:

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

[luislorenzobotella]

Hi, I tried the example posted by @lperron. Found some odd behavior I can't explain.

If I set all demands to even numbers (i.e. 2, 4, 6, etc.) and I set "_capacity" to an odd number (i.e. 17), it won't find a solution (tried for 90 seconds)

If I change the "_capacity" value to an even number (16, 14.. ) it will solve it at once

Any ideas? Here is the code I am running:

Thanks

reload.txt

[junsophie]

Hi, I tried the example posted by @lperron. Found some odd behavior I can't explain.

If I set all demands to even numbers (i.e. 2, 4, 6, etc.) and I set "_capacity" to an odd number (i.e. 17), it won't find a solution (tried for 90 seconds)

If I change the "_capacity" value to an even number (16, 14.. ) it will solve it at once

Any ideas? Here is the code I am running:

Thanks

reload.txt

Any progress on this issue? I rerun the code, this odd behavior is still there. Can anyone explain it?

[risinghero]

@risinghero Did you find a solution?

No best solution( It works some way with setting pickup and delivery but optimization is not best