vroom
vroom copied to clipboard
VROOM-Project
Max travel time in a route
Is it possible to set maximum working hours for a vehicle, instead of setting a fixed time window?
Instead of setting time window to 08:00-16:00 it would be great to set working time to 8 hours and the start and end time for the vehicle is flexible depending on the time windows on the jobs
There is no built-in way to do this right now. It could probably be added without too much changes to the current solving process. What would be required would be to store the current working hours for all routes, and then write checks for every solution change (heuristic addition or local search step) to rule out the ones that break this constraint.
Having efficient (read constant time) checks for local search neighbourhood validity would probably require to store more data, e.g. elapsed/remaining working hours at all steps for all routes.
start and end time for the vehicle is flexible depending on the time windows on the jobs
Note that this already happens to present a "compact" schedule and minimize waiting times (albeit without max length limitation) in the sense that we set ETA based on job time windows in order to end routes ASAP and start at the latest possible time.
Related #227.
On second thoughts, I'm not sure this would be as straightforward as I previously exposed with the current approach without blowing up computing times. The thing is we don't store any start and end time while solving ; we only store (for all steps in a route) the earliest and latest possible arrival dates matching timing constraints. At best, we have lower and higher bounds on the working time for a route.
So coming up with the working time would amount to deciding the actual arrival times along the route (the present a compact schedule process mentioned above). This would require going through the route twice. For efficiency reasons, that's something we don't really want added in a hot spot like a validity check.
That's a feature we are interested in, as well as https://github.com/VROOM-Project/vroom/issues/227
@braktar the need behind #227 (which is a closed discussion) is ticketed as a feature request in #354.
The "max distance" constraint would be similar to "max travel time" and totally doable with the current approach. What makes "max working hours" difficult over "max travel time" is that we have no way to account for waiting times while checking validity.
@jcoupey are you certain #780 resolves the original issue?
Instead of setting time window to 08:00-16:00 it would be great to set working time to 8 hours and the start and end time for the vehicle is flexible depending on the time windows on the jobs
After trying out max_travel_time in current master branch we've realised it accounts only for driving time, which means service times may push the overall route time to be more than specified limit, hence the implementation and the original issue do not match.
we've realised it accounts only for driving time
That's correct: #780 is explicitly titled "Handle vehicle max travel time", just as this issue has been renamed to account for total travel time, not total working hours. See above discussion for why.