Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems

Planning against journey times that change through the day sounds like a data problem — get better travel times and feed them in. The difficulty is the cost of using them.

An optimiser tries an enormous number of small changes: move this drop to another vehicle, call at these two sites the other way round. With one fixed travel time per stretch of road, working out whether a change helps is quick. Once travel time depends on when a vehicle sets off, changing one part of a route shifts the departure time of everything after it, so the obvious way to check a change is to recompute the rest of the route. Do that on every change and the search slows to the point where it examines far fewer possibilities — and a slower search finds worse plans.

Visser and Spliet show how to do it efficiently, by holding journey times as piecewise linear functions — a curve made of straight segments, giving the time you should expect for any departure time — and working out what a change costs against those curves. It is an important piece of work. Optrak draws on many of its ideas, adapting them to its own needs, particularly around driver scheduling.

It is why Optrak plans against journey times that vary through the day rather than a flat average. A system that treats congestion as a post-hoc adjustment produces a plan chosen on average travel times and then annotated with real ones — which is how a schedule comes to look fine on paper and run an hour late by mid-afternoon.

Read the paper: doi.org/10.1287/trsc.2019.0938

Published in Transportation Science, volume 54, issue 4, pages 1091–1112 (INFORMS, 2020). This is not Optrak’s research — it is external work the product is built on, alongside the methods described in work we build on.