If you had to hand-deliver 50 packages, how would you go about planning the best route?
That’s a theoretical problem mathematicians and computer scientists have long tussled with, and you might even be familiar with the traveling-salesman problem yourself. Simply put, it asks: given a list of locations and the distances between them all, what is the shortest possible route that visits each location once and returns to the origin? Clearly, solving that problem is an attractive proposition for any e-commerce business that delivers goods, because it means lower fuel costs and fewer drivers.
But there’s a hitch: the problem gets very hard, very quickly. “If one single driver has to go to 57 stops, you already have a quattuorvigintillion possible combinations,” explains Marc Kuo, the CEO of the Vancouver-based route optimization startup Routific. “That’s a one with 75 zeros.” Existing computer systems would take days or weeks to evaluate every possible route. Instead of seeking perfection, then, firms must find smart approaches to improve their routes as much as possible.
The biggest delivery players aren’t keen to talk about the topic. Neither UPS nor DHL responded to requests for interviews. FedEx couldn’t schedule a time to speak about it, even with more than a week’s notice. And a spokesperson from Amazon would say only that the company works “with a number of different delivery service providers, which use high-end technology to deliver on behalf of Amazon.” Beyond that, it had “nothing to share.”
Fortunately, some smaller organizations are less cagey, so we spoke to them.
Optimizing deliveries in the real world is thornier than the traveling-salesman problem on several levels. First, distances between locations need to be calculated, and as anyone who’s used Google Maps will know, there’s always more than one way to make a journey. Will Salter, managing director at Paragon, which provides routing and scheduling software in 60 countries for clients like the U.K. supermarket giant Tesco, says path-finding algorithms used in delivery planning are “highly customized” compared with a Google Maps algorithm. They’ll take into account road conditions, changing traffic flows at different times of day—even the marginal benefits of making a right turn at a junction.
Then hundreds of constraints must be taken into account. You might calculate an amazing route that hits all your deliveries, but can you fit everything in the back of the van? How much longer will it take to unload the frozen food than the staples? Is it worth dropping off heavy items first to save fuel?
But James Lohr, head of planning and delivery systems at Ocado, the world’s largest online-only grocery retailer (see “The Robotic Grocery Store of the Future Is Here”), explains that its system starts by randomly allocating deliveries to vans for a certain geographic area, then works out how long those deliveries will take. Then it makes a combination of small and large changes, from switching the order of two drop-offs to switching entire chunks of deliveries between vehicles—each time evaluating whether it’s an improvement. Making four million moves a second and keeping track of the best solutions, it slowly approaches the most optimal route it can find.
Away from the heavy computational weight of planning for large organizations, some firms are developing systems targeted at small businesses, too. Routific’s Kuo, for instance, explains that his company hopes to provide route-planning power using cloud-based services that drivers access via a smartphone. “It’s kind of a shocker, but many drivers still plan routes with pen and paper,” he says. His firm’s algorithm also makes incremental changes to routes, but when a small change makes a big difference, attention is focused around that drop-off to maximize improvement, and then the algorithm moves on. Routific claims its service reduces the length of delivery routes by 40 percent.
Recommended for You
There’s a decent chance that you’ve already interacted with these algorithms without realizing it. Paragon (working on behalf of Ikea and catalogue retailer Argos) and Ocado both suck data from their analyses when offering up delivery windows to customers on their websites. It proposes only routes that fit well with its current plans for the days ahead.
That’s a courtesy to drivers that hasn’t, perhaps, always existed. Paragon, Ocado, and Routific have all experienced cultural problems when it comes to convincing experienced delivery drivers that their algorithms know better than they do. “At one point, if you went to the place where drivers ate lunch and said you were a route planner, you’d be scared for your life,” says Ocado’s Lohr. “I’m exaggerating slightly, of course, but it can be politically difficult.”
Meanwhile, more layers of difficulty keep being added to the optimization problem itself—and there looks to be no end in sight. Paragon’s Salter explains that clients keep asking for new features to be added. Routes that minimize carbon dioxide emissions. for instance, have become a favorite. “Every year we’re taking into account more and more constraints,” he says. “I don’t think it’s possible to truly optimize [the routes] we’re planning.”
Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.Subscribe today