GraphHopper.com | Forum | GitHub | Maps | Blog

Unexpected behaviour using Timewindows and MIN Completion Time


#1

Hi all,

I experienced an unexpected behavior when using time windows. The objective is set to MIN COMPLETION_TIME. My problem is, that the service always starts at the earliest time possible, even if that results in waiting time at the next service (and hence the overall time needed increases).
Example:
Service A: time window 8am - 9am, duration 15min
Service B: time window 9:30am - 10am
Let’s say the drive in between takes 1 hour
Then the vehicle is supposed to start the service A at 8am, from 8:15 - 9:15 it drives to B and then has to wait until 9:30am to start service B. If the vehicle would have started 15mins later, no waiting time would be necessary.
Another unwanted problem is, that the vehicle always starts at the earliest start time (for example midnight) and then has to wait at the first service (in this example until 8am at A).
Are these two problems correlated? (Because if the vehicle has to wait anyways, it doesn’t matter, if it does so before the first or second service and the overall time needed cannot be reduced)
Did I misunderstand the functionality of the algorithm or do I have to use it differently? Is there any way to minimize the necessary waiting time?

Another question, I have come across is the behavior regarding the different objectives. I discovered, that the result is exactly the same, no matter, whether I set the objective to Min Completion_Time or to Min Vehicle and Min Completion_Time (as second objective). When does the algorithm decide, whether it is better to use one vehicle more or less? How is the assessment done?

Thanks


#2

earliest_start:
Currently, the "earliest_start" of a vehicle needs to be specified. If not specified, the vehicle starts at 0. Furthermore, it is not yet possible that the algorithm determines the start time of the vehicle. Therefore, your vehicles always start at "earliest_start", no matter whether that makes sense or not.

objective function:
For a number of problems, these two objectives, i.e. min completion_time and min vehicles AND min completion_time, yield the same results. Sometimes, however, these two objectives are competing objectives.
To illustrate this, the following 4 figures show an example.

You can see the objective specification in the left editor. As you can see in the first two figures, both objectives yield the same result. However, if you just specify that vehicles do not need to return to the depot (“return_to_depot”: false), both objectives yield different results.

Here you can find the example in json: minCompletionTime.txt (2.8 KB)
You can use our route editor to reproduce the results above and to play with different objectives.