Choose ETA along a fixed route

[jcoupey]

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:

1. how to choose ETA for all steps?
2. 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...).

[jcoupey]

I've just pushed the current state of my work on this, and the docs have been updated in the PR branch. TL;DR:

• switch solving mode with -c;
• add a vehicle.steps array to describe expected ordering for tasks in a vehicle route, along with (optional) steps hard timing constraints;
• get feedback with the violations array at step, route and summary level on top of the usual solution output schema.

Difficult instances are the ones with long routes and multiple time windows because those translate to binary variables in the Mixed Integer Program. I've put a lot of efforts on ad-hoc tunings so that solving with GLPK is fast enough for most use-cases. This includes:

• solving the problem sequentially as two MIP to avoid troubles with huge objective coefficients and float precision;
• computing and using an upper bound for violations;
• shifting the planning horizon in a problem-dependant way to avoid scaling problems, yet retain enough margin for potential lead time and delay (based on violations upper bound);
• computing lower/upper bounds for ETA to narrow down the search;
• based on the above, force binary variables to zero whenever possible to guide the branch-and-bound process;
• ...

For MIP lovers, I wrote down the mathematical model in this LaTeX file. This is rather a rough sketch because as mentioned above, there's much more to it in the actual implementation. As usual, the devil is in the details...

Happy to have any feedback on tests!