Route optimisation for takeout deliveries?

Posted 03 Aug 2015

High quality takeout deliveries are rapidly becoming very big business, with a number of services such as Caviar, Deliveroo, dine in and Doordash growing rapidly over the last year or two. Consumers can order a wider range of high-quality takeaway food than ever before and have it guaranteed on their doorstep within half an hour or so.

The ‘secret’ of these start-ups is simple - as well as providing the standard online ordering platform common to the last generation (e.g. just eat) they manage their own highly trained delivery fleet. This allows higher-value speciality restaurants, who are unable to run deliveries in-house economically, to happily sign onto the dotted line.

Amazon is making similar moves for supermarket food and other basic goods deliveries, with its one-hour Prime Now delivery service. Sure, the food’s not hot, but the underlying logistics problem is identical.

All this presents huge challenges in terms of the logistics. Orders are arriving in real-time, with drivers already out on the road, to be collected from and delivered to a multitude of locations in the blink of an eye, or thereabouts. Can academic research - particularly from the field of operations research, help tame this logistical beast?

Clearly, this is about optimising vehicle routes - using the least drivers possible and having deliveries done as quickly as possible. These kinds of problems have actually been around for a long time - thousands of papers have been written over seven decades on the vehicle routing problem - which involves generating efficient routes for a fleet of vehicles starting at a depot and delivering to multiple customers.

Our problem is more complex though - the goods don’t start at a single depot, where the vehicles start; they need to be picked up from lots of different places. As we’re picking up from one place, and delivering to another, where neither is the depot, this is a different sort of routing problem - the pickup-delivery problem.

Luckily there is several decades’ worth of research out there on the pickup-delivery problem too, but there’s something else we’ve missed… Our orders arrive in real-time, long after drivers have started their shift, so there’s no magic time period available when we can plan one big set of routes for the whole night. Instead, our planned vehicle routes need to evolve over the night as new orders come in. Technically, this makes the problem dynamic - so we have the dynamic pickup delivery problem.

As a very final step, to be as efficient as possible we should use the wealth of big data sitting in our order database, accumulated over months or years. Surely modern data analytics techniques could chew on this to identify trends and order patterns, which could then be used to construct vehicle routes which anticipate and adjust for likely future orders? Here we are dealing in probability - using probability distributions of future orders to help shape our routes. This gives us our final and complete problem definition - the dynamic and stochastic pickup and delivery problem.

Knowing the name of the problem we’re trying to solve - that Open Door Logistics is developing solutions for right now - is halfway to actually solving it. Sadly from the thousands of research papers we had available for the vehicle routing problem, we’re down to just a couple of works which consider the dynamic and stochastic pickup and delivery problem in any depth. Of course, we only need one good model. Is it out there? Find out more in our next blog post.