OR and Ocado are beating the vehicle routing problem

Ocado’s business is, primarily, about delivering packages to customers’ front doors within a small window of time – often referred to as “the last mile” deliveries. Every day, each of its vans (and it has a very large number of them) has to be loaded (in a certain order) and its driver provided with a clearly defined route.

Although the primary objective is to deliver every parcel to its right destination within the agreed timeslot, there is an almost equally important secondary consideration. This is to do so using the minimum amount of fuel. There are also some obvious constraints: each van has a weight limit, a capacity limit and each driver has time constraints.

The “best route” may not always be the shortest route connecting all of the customers. The route will need to take into account road closures and delays due to road works, also likely traffic holdups such as school times and local road use restrictions, congestion and pollution charges.

For the above reasons, the vehicle routing problem is dynamic and non-linear, it changes over time, with orders being added, removed, or modified. Ocado realising this flux exists in vehicle routing proposed a solution that was able to cope with these “on-the-fly” changes.

In vehicle routing problems, Ocado assumed that travel times were known between any pair of locations. To solve this optimisation part of the problem separately from the vehicle routing problem, it applied Machine Learning (ML) methods based on large amounts of historical data. The predicted travel times were then used by Ocado’s bespoke vehicle routing algorithms to provide best fit solutions.

Vehicle routing is an NP-hard problem.

Ocado systematically explored possible mathematical optimisation solutions including: mixed-Integer and linear programming; Constraint Programming; Simulated Annealing; Metaheuristics and; genetic algorithms were used. A more sophisticated method that involved a combination of metaheuristics and a genetic algorithm was used too – using genetic algorithms, allowed Ocado to maintain a collection of several solutions at the same time.

Ocado’s simulation generated events like order placement, cancellation or modification and fed them into their algorithm. It simulated the actual dynamic environment where the algorithms operated and allowed a comparison of performance and solution quality under similar conditions.

Ocado’s routing algorithms make 14 million calculations per second to optimise delivery journeys for Ocado.com alone. It allows for Ocado’s partners to keep their deliveries on time and manage driver and vehicle operations at scale. These advanced data science and machine-learning solutions enable Ocado partners to achieve highly efficient, optimised, last-mile deliveries.

More at: https://www.cardiff.ac.uk/news/view/2585000-improving-vehicle-routing-with-ocado-group