VROOM-Project / vroom

Vehicle Routing Open-source Optimization Machine
http://vroom-project.org/
BSD 2-Clause "Simplified" License
1.34k stars 336 forks source link

Break not done as early as possible leads to unassigned shipments #883

Open fbaierl opened 1 year ago

fbaierl commented 1 year ago

I have encountered a problem with the following example:

Input: route_should_be_possible.txt

Output: result.txt

All four shipments should easily be doable if the break is taken at the start of the vehicle (at the beginning of the time-window given for the break), but VROOM does not seem to use this time-slot at all.

If I extend the break timewindow to the end of the vehicle timewindow it works since the break can then be taken after doing the shipments:

Input (with extended break time): input2.txt

Output (with extended break time): output2.txt

So from what I am understanding VROOM refuses to put the break as early as possible, even though there would be plenty of time there to do it since the break is only 30 minutes and the break would be possible from 6:30am:

image

The vehicle instead does the break at 8:31am right before starting the first delivery. Before that, the vehicle would have had almost 2 hours to do the break which it does not use. Instead, VROOM decides to not do one shippment and do the break later.

image

We are using VROOM v1.13-rc1.

Unfortunately, I was not able to create a standalone problem since I am getting a connection error using the provided scripts. I tried rewriting the script files to point to a non-locally running instance of osrm, so I added our osrm url everywhere where the script said "0.0.0.0". Is something like this not possible?

The problem also happens when using the vroom demo server.

jcoupey commented 1 year ago

I reproduced the problem. Namely, the solution provided is Break -> 2 -> 3 -> 4 -> 5 -> 0 -> 1 (using pickup/delivery ids) and tasks 6 and 7 are unassigned, while Break -> 6 -> 7 -> 2 -> 3 -> 4 -> 5 -> 0 -> 1 is valid with all tasks assigned.

I added our osrm url everywhere where the script said "0.0.0.0". Is something like this not possible?

You may have better luck using a raw IP address instead of the URL.