In some situations, optimized routes are manually modified by end users by e.g. adding jobs or moving jobs inside a route or from a route to another. In that case all ETA, distances etc. are invalidated. People occasionnaly even come up with routes that look better in term of overall cost, but are not valid with regard to initial constraints and it's usually hard to explain, because then one has to track down which constraint is at stake.
On the other hand, a end user may have totally valid reasons to break his own constraints at some point, so it would be useful to be able to answer the following questions, given any route with predefined ordering:
- how to choose ETA for all steps?
- what's the impact in term of constraints violations?
The first could sound like just adding up service and travel times from the vehicle first available date but there's much more to it. If you simply do this, you'll likely end up with invalid arrival dates (wrt job time windows), and if you only try to account for job availability by waiting when arriving early, you'll end up doing foolish things down the line, e.g. if a "late" job is pushed in front of a route.
Optimization
What we basically want is for all input constraints to become soft constraints so as to allow violations (e.g. arriving early/late for a job). Then the question of choosing ETA for all route steps becomes a minimization problem for the sum of timing violations. Of course we also want the output to be consistent with the way we currently design routes: for the same timing violation level, we want to minimize route makespan and perform tasks ASAP.
Because usual timing constraints derived from time windows are now soft, we also need a way for users to provide "hard" timing constraints to make sure we don't pick ETA that are not doable in the field.
I've started working on a POC for this using an linear programming approach. The tricky part is that with multiple time windows, picking the right one to evaluate timing violations requires to use binary variables.
API
Input
We want to modify as little of the existing input syntax. The good news is we only need to pass an additional parameter to a vehicle describing the expected route ordering. More or less an array of step objects with type and id to identify them in order, along with the (optional) hard constraints for all steps.
We should add a command-line flag to switch from the "usual" optimization mode to this mode, telling vroom to expect those new keys in input and act accordingly.
Output
It's mostly a matter of reporting violations. This should be done at step, route and summary level while keeping the same output syntax otherwise. There are two kind of violations: timing violations (delay and lead times related to ETA estimates, see optimization objective above) and the rest that can be simply spotted by going through the route (vehicle over capacity, missing vehicle break, wrong ordering for a shipment pickup and delivery, skill mismatch...).
In some situations, optimized routes are manually modified by end users by e.g. adding jobs or moving jobs inside a route or from a route to another. In that case all ETA, distances etc. are invalidated. People occasionnaly even come up with routes that look better in term of overall cost, but are not valid with regard to initial constraints and it's usually hard to explain, because then one has to track down which constraint is at stake.
On the other hand, a end user may have totally valid reasons to break his own constraints at some point, so it would be useful to be able to answer the following questions, given any route with predefined ordering:
The first could sound like just adding up service and travel times from the vehicle first available date but there's much more to it. If you simply do this, you'll likely end up with invalid arrival dates (wrt job time windows), and if you only try to account for job availability by waiting when arriving early, you'll end up doing foolish things down the line, e.g. if a "late" job is pushed in front of a route.
Optimization
What we basically want is for all input constraints to become soft constraints so as to allow violations (e.g. arriving early/late for a job). Then the question of choosing ETA for all route steps becomes a minimization problem for the sum of timing violations. Of course we also want the output to be consistent with the way we currently design routes: for the same timing violation level, we want to minimize route makespan and perform tasks ASAP.
Because usual timing constraints derived from time windows are now soft, we also need a way for users to provide "hard" timing constraints to make sure we don't pick ETA that are not doable in the field.
I've started working on a POC for this using an linear programming approach. The tricky part is that with multiple time windows, picking the right one to evaluate timing violations requires to use binary variables.
API
Input
We want to modify as little of the existing input syntax. The good news is we only need to pass an additional parameter to a vehicle describing the expected route ordering. More or less an array of step objects with
typeandidto identify them in order, along with the (optional) hard constraints for all steps.We should add a command-line flag to switch from the "usual" optimization mode to this mode, telling
vroomto expect those new keys in input and act accordingly.Output
It's mostly a matter of reporting violations. This should be done at
step,routeandsummarylevel while keeping the same output syntax otherwise. There are two kind of violations: timing violations (delay and lead times related to ETA estimates, see optimization objective above) and the rest that can be simply spotted by going through the route (vehicle over capacity, missing vehicle break, wrong ordering for ashipmentpickup and delivery, skill mismatch...).