Relative time window for shipments

[jwoyame]

This is a feature suggestion.

First: Vroom is excellent, very well written. Thank you especially to @jcoupey for your efforts.

Use case

Currently, you can set time_windows for both pickup and drop-off jobs in a shipment. But suppose you wanted to deliver a pizza within 30 minutes.

Example: A customer wants her pizza around 5pm. You set a pick-up window of [4:00, 4:45], but you don't want the driver to have it in the car for more than 30 minutes. For that reason you have to set a drop-off window too, perhaps [4:30, 5:15]. But that leaves the possibility for a solution where the pickup happens at 4:00 and the drop-off occurs at 5:15, leaving the pizza in the car for over an hour.

That might seem like a rare need, but there are practical cases where a pickup or a drop-off could happen any time of day, but the difference between the two jobs must be constrained. Another case would be an Uber Pool ride, where someone wants to be picked up between 7am and 8am but doesn't want to ride around for the entire day before reaching their drop-off 😀

Solution

The problem exists because there is no way to lock one job to another one's time margin throughout the optimization process. I propose a new time_gap property for pickup and drop-off jobs.

For the pizza example, the pickup's time_windows would have [4:00, 4:45], and the drop-off would have a time_gap of 30. As the pickup's earliest and latest is dynamically updated, the drop-off job's latest is constrained to the pickup's earliest + time_gap. The existing logic will be able to protect the drop-off from being pushed out later.

This could work in the other direction, where the time_gap can be put on the pick-up, and the drop-off's earliest and latest will serve as the anchor. It should also work even if time_windows are not assigned.

Looking at tw_route.cpp, this seems like it would not be too big of a change. Since it is still window-based, it would not require the entire route to be compressed to exact ETAs first.

Thank you for any comments or further refinements.

[jcoupey]

I definitely get your point and how this could be useful in some situations so I'm happy to flag this as a feature request. But honestly I don't see an easy way to make that happen any time soon.

As the pickup's earliest and latest is dynamically updated, the drop-off job's latest is constrained to the pickup's earliest + time_gap. The existing logic will be able to protect the drop-off from being pushed out later.

It's tempting to hope that working with time margins is enough to include a max time gap but it is not. Earliest and latest times are dynamically updated upon each route modification. This requires going through (part of) the route back and forth but is not a bottleneck as actual route modifications are scarce compared to non-applied modifications for which we check the time validity.
Currently those checks require at most going once (onward) through the modified portion of the route and computing wanabee new earliest dates, then check against the first know latest date at the end of the modified portion. The problem here is that updating the earliest date for one of the pickups can potentially trigger a change for the latest date of the associated delivery down the line. And we have no way to have this come into play without significantly increasing algorithmic complexity.

Put it differently, you can see the validity check as a constraints satisfaction problem where constraints are derived from tasks precedences: start -> T1 -> T2 -> T3 -> T4 -> T5 -> end. Going through that linear chain forward provides earliest dates for all tasks. But then if T2 and T4 are respectively the pickup and delivery for a single shipment, then the max time gap would introduce a backward arrow from T4 to T2. We'd be introducing a cycle in the dependency graph and simply going through the (linear) chain is not possible anymore to check validity.