Waitrose is the latest retailer to recruit UK start-up On the Dot for same day deliveries, using machine learning to optimize routes. The supermarket group joins 100 customers including Wickes, ASOS, Curry’s PC World, and Dixons, many fighting to compete over time to delivery with Amazon.
On the Dot has attracted investment of £17.7mn ($23mn) since its launch in 2015, including a recent £8mn injection from its parent company City Sprint Group. Its selling point is use of machine learning to optimize the solution for the travelling salesman problem, a long-standing challenge in mathematical graph and optimization theory.
With a fleet of 5000 couriers including bike and vans, the service offers hope to retailers of all sizes of avoiding having to become Amazon third party sellers to deliver the same day anywhere in the UK, which entails tight squeezes on margins.
Waitrose is the first significant food retailer to recruit the service, initially for a trial of both same day and two-hour delivery within parts of the greater London area. This requires a solution to extended versions of the travelling salesman problem, which in its basic form addresses the challenge of visiting all locations in a given set while covering the least possible total distance. This has numerous applications beyond actually selling or delivery, including manufacture of printed circuit boards and packing boxes in a factory ready for transportation, where costs can be reduced significantly by minimizing distances covered in the process.
In its basic form, the problem can be solved exactly such that the optimum route can be calculated beyond all doubt. But the computational cost of running the algorithm grows exponentially with number of nodes on the graph, equating to the homes wanting deliveries in Waitrose’ case. In one celebrated example an exact solution for visiting 15,112 German towns was found in 2001 based on linear programming on a parallel network using an algorithm that would have taken 22.6 years on a single 500 MHz Alpha processor.
To reduce this drastically, numerous algorithms that deliver approximate solutions consuming far less computation time have been devised. But another complication is that in practice the shortest possible route is not always desirable for various reasons.
It may not be the quickest or the cheapest. It may involve taking slow roads when faster alternatives are available over longer hops. All sorts of other factors may come into play, such as the need to deliver to a certain home first in order to meet a two hour deliver deadline even when that is not on the shortest path.
In some cases, it is desirable to keep each route as short as possible, especially when it is getting close to the time when a given sales or delivery person is due to finish work for the day. That is when the nearest neighbor (NN) algorithm may come into play, prioritizing nearby nodes over ones further away even though this adds on average about 25% to the total distance covered compared with the shortest path.
On the Dot has to take such factors into account in optimizing its model. The firm’s CTO Taher Khaliq explained that keeping drivers happy and maintaining a steady workflow for them were also factors that had to be taken into account. The firm was fortunate in having data going back 20 years, about deliveries and this enables ML to be applied on different time scales both to calculate the best routes at a given time and also improve deployment and location of drivers on a longer-term basis.
Even these more complex versions of the travelling salesman problem have attracted attention for a long time. An algorithm published at Princeton University in 1987 took account of factors such as cost of travel, total budget and unpredictability of fares for a salesperson travelling by train. It is only recently though that computational power has reached the point such algorithms can be run against large numbers of places to visit and also allow ML to be employed for optimization to particular applications.
ML scores by being able to solve the problem for situations where certain routes are not allowed for various reasons, as well as optimizing for ongoing delivery deadlines that vary between locations, as again in the Waitrose case. This can be done by adjusting the weights assigned to the various routes with very large ones for those that are not allowed at all. Such models can take accurate account of the cost of each route or of moving between any given pair of nodes in the network.
With delivery becoming a major battleground in the age of online retail services, ML is featuring increasingly for process optimization, but given that scale is important for efficiency, it is possible that the field will just create new dominant players. The success of Roofoods, owner of the Deliveroo brand, expanding from its UK base across Europe and into Asia Pacific, suggests this may be the case.