The software routing 260,000 grocery deliveries a week
If you’re a computer science aficionado, you may be familiar with the travelling salesman problem: given a list of different cities and the distances between them, how can a salesman visit each city once using the shortest possible route and then end up back where he started. This is possibly the most popular example of a complex optimization problem there is. As you add more locations, the problem gets more and more difficult so that for a large number of cities it is impossible to find the single optimal solution in a reasonable amount of time.
Ocado has many salesmen (our delivery drivers) travelling to multiple cities (our customers’ houses) and, as if that wasn’t enough, the scale of this problem just keeps on growing: in the last year alone, the number of average orders per week has increased from 225,000 to 260,000 and our active customer base has grown by 12%. How can we find the optimal paths for our drivers when the goalposts are constantly moving?
To give you an idea of just how hard this problem is, let us consider a small subset of what we need to solve each day: fitting a mere 2,000 orders onto 100 vans. The number of possible solutions to this problem is so large that expressing it as an integer would take nearly as much print as this entire article. Or alternatively, try saying the word “trillion” twice per second for two minutes flat!
The problem is too complex for humans to figure out alone so we once again turn to technology for the solution to this dilemma.
Originally we outsourced the project and used routing software from a third party, however as the company expanded and we added many more day to day deliveries and routes, we quickly outgrew it. Since 2007 we have been using our in-house routing software which employs a real-time optimization algorithm to help us decide which deliveries to assign to each van and the order in which they should be completed, while also ensuring we do our best to arrive on time for all our deliveries.
The algorithm makes several million route calculations per second to identify the best delivery routes for our drivers. The video below gives you a visualization of what the output of the algorithm looks like, augmented by real-time traffic data coming from the satnav devices onboard our vans:
As you can imagine, this is by no means an easy feat. When we started working on the in-house solution, the general consensus was that it would be almost impossible to scale the software up to match extremely high levels of demand. However, against all odds we did it!
This breakthrough did not cause us to reach a standstill however. We have been continuously evolving the routing software ever since, adding major features such as a routing simulation environment so we can gauge the impact of changes to the optimiser with a short feedback loop, hardware resilience, using cloud-based delivery and predictions for parking durations based on historical data.
So how does it work?
The algorithm works by rapidly attempting small moves and assessing the impact of each move upon the overall solution by evaluating a cost function. This allows us to calculate the optimal route for each van. While the mathematics shall remain a mystery (have a look at our data science job openings if you’d like to learn more), the engineering effort is immense because of the performance requirements. The optimiser runs approximately 4 million moves per second, and is required to gracefully adapt to the problem itself, changing as customers dynamically request slots and book orders.
You can picture this optimising process as a series of peaks and valleys in an almost endless landscape, where a peak represents the highest cost possible and a valley represents an optimal solution. Your job is to explore your local area, and head towards the lowest nearby point. However, there are multiple peaks and valleys so you can’t be sure that once you are in a valley it is the lowest possible point. There are far too many possibilities to ever be sure of this. We can, however, come up with a good estimation. Once you have climbed down to the lowest point of a valley, you will get teleported to a different location on the map and will start the search for the lowest possible point near you all over again. This process of randomisation means we can start to map out all the valleys, and keep track of the deepest one we have found, meaning we can always know what the best solution is so far. Obviously the real world software doesn’t involve hiking or teleportation – it is a function running on internal servers, but this helps us to picture how that function is working.
The program runs all day, every day, using rapid incremental movements so it can always be searching for more efficient solutions to the problem. Even if we can never know we have achieved the final, fully optimised solution, we can at least know we are always approaching it.
The software platform is constantly running multiple instances of the optimiser simultaneously, each iteration focussing on a specific area for a certain day. This means that a customer can book a delivery slot online late on a Thursday night for delivery the following day, and the software can make sure it incorporates this new slot into the route optimisation for Friday. The software is quick and efficient, meaning that additions and revisions of delivery bookings can be taken into account when calculating the best possible solution within the time available. When you visit Ocado.com, the webshop is actually communicating directly with our routing software to establish which delivery slots are still available. When you click on the day you wish to receive your delivery in the calendar, the real time optimiser will return the available slots within 500ms!
Our vans are equipped with a range of IoT sensors that log relevant data during deliveries such as location, wheel speed, engine revs, braking, fuel consumption, and cornering speed. Our engineers can then feed this data into the routing software so that the algorithm is constantly learning and re-optimizing the delivery routes, therefore making the routes we drive tomorrow hopefully better than the ones we’ve driven today. Read more about how the Internet of Things is improving our grocery retail business here.
The secret ingredient to our routing success is the broad range of variables we take into account when calculating the cost function, including van capacities, weights, volumes, fuel consumption and even driver experience. Explaining just how all these factors fit together to produce the final result would be telling, but the product is the culmination of years of tweaks and modifications based upon feedback from simulations and real world performance measures.
The work of our technology team means we regularly find ourselves in a position to solve our own problems within retail without outsourcing to third parties. Once again, the close collaboration between our retail and technology teams continues to keep us a step ahead.
Holly Godwin, Technology Communications Assistant