Contiguity constraint in vehicle routing problems

Posted 05 Sep 2022

We’ve been testing a new ‘contiguous constraint’ in our ODL Live vehicle route optimiser, which forces delivery routes to stay in separate areas. This ensures we can generate clean non-overlapping routes even for very hard routing problems, which are under-resourced.

Routes that minimise travel will naturally form petal shapes (like a flower), but delivery drivers prefer routes in compact areas. For a long time, we’ve had multiple methods available in ODL Live which can keep routes in small areas. These previous methods aimed to keep routes compact, but didn’t directly model if a route formed an unbroken (i.e. contiguous) area. As a result, when the vehicle routing problem is under-resourced (i.e. there’s not enough vehicles to serve all the jobs), ODL Live favoured loading jobs over compact routes, and routes would overlap. The new contiguous constraint solves this issue by directly modelling if a route is contiguous or not, and so prevents routes being broken into separate areas.

The result - clean, pretty routes, as demonstrated in this infographic:

Here’s another example but using more realistic data. In this problem, there’s not enough room on the vehicles to fit in all stops, and so the stops shown in purple don’t get loaded onto routes. Each stop has a different volume.

Without the contiguity constraint, the 3 routes would criss-cross Singapore (messily overlapping each other), to find the combination of loaded stops on each route which maximises the total number of assigned stops.

With the contiguity constraint on, the optimiser (1) prioritises keeping routes in their own area, then (2) maximises the loaded stops, and then (3) minimises the cost, which is based on both route compactness and travel. This gives cleaner clustered routes (which would keep a human planner happy).