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.
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.”
Going bald? Lab-grown hair cells could be on the way
These biotech companies are reprogramming cells to treat baldness, but it’s still early days.
Meta’s new learning algorithm can teach AI to multi-task
The single technique for teaching neural networks multiple skills is a step towards general-purpose AI.
Meet Altos Labs, Silicon Valley’s latest wild bet on living forever
Funders of a deep-pocketed new "rejuvenation" startup are said to include Jeff Bezos and Yuri Milner.
A horrifying new AI app swaps women into porn videos with a click
Deepfake researchers have long feared the day this would arrive.
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.