Delivery at earliest possible time when using time windows

[stefanhahmann]

Hi,

I have discovered that vroom seems to compute routes such that for the case of a pickup and a delivery, where only the delivery has a time window, the delivery will be done at the latest possible time according to the time window.
In my example there is a vehicle with operating time windows from 8:00 - 18:00 and a shipment, where the pickup has no timewindow and the delivery has a time window from 9:00 - 10:00. Even though, it would be possible that the shipment in the resulting route would be planned such that the delivery would be done at 9:00, it is planned that the delivery is at 10:00.
It would be good to have an option that in such cases the route is planned that the delivery takes place at 9:00 (i.e. the earliest possible time).
Is there an easy way to accomplish this with the current implementation?

I am attaching the example that I have used for testing.

earliestLatestExample.txt

Best,
Stefan.

[jcoupey]

Thanks for the detailed explanation and sharing an instance. The general rules for deciding arrival times are:

1. Aim at earliest end of route
2. Go back in time to decide latest possible start (this has the effect of "compacting" the route whenever waiting time can be avoided)
3. Compute all arrivals based on the latest possible start that matches the earliest end of route. If some tasks can move "freely" in a time frame, we favor starting tasks ASAP

In your example, the whole timing is strongly impacted by the vehicle break. It has to be taken at a specific time and breaks are mandatory so they're added to the route no matter what. Then doing the delivery as late as possible is the result of step 2. described above. In the route timeline below, you can see in orange that there is still quite a lot of waiting time at the break, and doing the delivery earlier would only increase this waiting time and not allow for a better completion time. Basically the completion time here is fixed by the break start and service time.

Waiting time shows up in the break step for the solution: vroom -i earliestLatestExample.txt | jq '.routes[0].steps'.

[stefanhahmann]

Thank you very much for the quick response and the explanations regarding this!
With your explanations the resulting route plan makes perfectly sense.

The constraint that a break has to be taken en route is a problem for my use case. For my use case it would make more sense, if the vehicle would return to its end point immediately after all shipments have been served and before the break is taken (and actually take the break at the endpoint). This would also reduce the waiting time for the vehicle.

Is there any way to relax the constraint of the break having to take place on route?

I was wondering, if alternatively it is possible to define multiple time windows for a vehicle but that does not seem to be the case. However, perhaps I could workaround and define the same vehicle twice in the input with working hours in the morning and working hours in the afternoon - but I am unsure if a vehicle with the same id can occur twice in the input?

I really like your visualisation of the timeline! This is very helpful to understand what is going on. Is the code for producing the timeline available somewhere in the vroom repository?

[jcoupey]

it would make more sense, if the vehicle would return to its end point immediately after all shipments have been served and before the break is taken

This is precisely what happens here. After the vertical bar materializing the delivery time, you can see the delivery service in green, then the travel to next step in blue, in that case the next step is the end route. This also shows up in the routes[0].steps[].duration values indicating the accumulated travel time for all steps: values are identical for the break and end steps, meaning the end destination is reached upon starting the break.

This would also reduce the waiting time for the vehicle.

That's what we do as a general rule as we're able to split travel time across breaks (before and after), thus filling potential waiting time related to the break time window. When the overall travel time can be split in different equivalent ways without changing the rest of the route, we favor placing the break ASAP.
In your example, there is simply not enough travel time back to the end of the route to eat up all waiting time. This should also vanish if you have routes packed with more tasks.

define the same vehicle twice in the input with working hours in the morning and working hours in the afternoon

You can do that, note that then you'll get routes with identical vehicle values.

Is the code for producing the timeline available somewhere

It should be, I ticketed this in VROOM-Project/vroom-scripts#17 but did not take the proper time to clean it up and push it, yet.

[stefanhahmann]

In your example, there is simply not enough travel time back to the end of the route to eat up all waiting time. This should also vanish if you have routes packed with more tasks.

Good to know that the late arrival at the delivery location is maybe only an artifact of my simplified example.

You can do that, note that then you'll get routes with identical vehicle values.

Just successfully tried that. Good to know that we could model breaks also this way. For sure the identical vehicle values need to be considered, if we handle it is way.

the accumulated travel time for all steps: values are identical for the break and end steps, meaning the end destination is reached upon starting the break

I have also infered from the duration and the distance in the break and the end step that the end is actually reached at the same time, when the break is reached. However, the arrival time of the end step has confused me. Also I was missing the location of the break. I think, it would be useful to have the location of a break explicitly included in the route plan.

[jcoupey]

the arrival time of the end step has confused me

Here arrival time at the end step is decided by the break start (no choice from the TW) and break service time, so 1630324800+7200. It's basically the completion time for the route.

I think, it would be useful to have the location of a break explicitly included in the route plan

The purpose of the breaks objects is precisely to describe a situation where the break can occur anywhere/anytime between other tasks. In some situations, it will happen to take place at the previous or next task's location, but in general the travel time between previous and next tasks can be arbitrarily split across the break to accommodate timing constraints. In practice this means leaving previous location, stopping for a break somewhere (read "a location different to any of those provided in input and depending on the actual route") then driving for the rest of the trip to next task.

[jcoupey]

Closing as answered.