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