Are you waiting for your holiday package to arrive? There is a math problem you need to solve before the delivery truck arrives at your door. MIT researchers have a strategy to speed up this process.

This approach can be applied to vehicle routing problems like last-mile delivery. The goal is to deliver goods from one central depot to multiple cities and keep travel costs low. Although algorithms exist to solve the problem in a few hundred cities only, they are too slow to be applied to larger cities.

Cathy Wu, Gilbert W. Winslow Career Developer Assistant Professor in Civil and Environmental Engineering and Institute for Data, Systems and Society, and her students devised a machine-learning strategy to speed up some of the most powerful algorithmic solvers by between 10 and 100 times.

Solver algorithms break down the delivery problem into smaller subproblems. For example, 200 subproblems can be solved to route vehicles between 2,000 cities. Wu and her collaborators add to this process by using a machine-learning algorithm to identify the most valuable subproblems instead of solving them all. This increases the quality of the solution, while using orders of magnitude less compute.

Their approach, which they call “learning-to-delegate,” can be used across a variety of solvers and a variety of similar problems, including scheduling and pathfinding for warehouse robots, the researchers say.

Marc Kuo, founder of Routific and CEO, is excited by the work. This smart logistics platform optimizes delivery routes. Wu’s work inspired some of Routific’s most recent algorithmic innovations, he says.

“Most academic research tends focus on algorithms that solve small problems. This is to try to find faster solutions while reducing processing times. Kuo says that businesses aren’t interested in finding better solutions. This is especially true if the solution takes too long to compute. In the world of last mile logistics, time is not money. You cannot make your warehouse operations wait for slow algorithms to return routes. To be useful, an algorithm must be extremely fast.

Wu, Sirui Li, a social and engineering system doctoral student, and Zhongxia Yan, an electrical engineering and computer science PhD student, presented their research at the 2021 NeurIPS conference.

Selecting good problems

Vehicle routing problems are a type of combinatorial problem that involves using heuristic algorithms in order to find the “good-enough” solution. These problems are often too complex to find the “best” solution.

Wu says that the goal of these kinds of problems is to create efficient algorithms that are optimal within a given factor. But the goal isn’t to find optimal solutions. This is too difficult. We want to find the best solutions possible. A small improvement of 0.5% in solutions can result in a significant increase in revenue for a company.

Researchers have created a number of heuristics over the years to quickly solve combinatorial problems. This is usually done by using a flawed but valid initial solution, and then slowly improving it by making small tweaks to improve routing between cities. This approach is not suitable for large problems like the 2,000+ city routing challenge.

Machine-learning algorithms have been used to solve this problem in recent years. However, while they are faster than human methods, they can be less accurate at scales of just a few cities. Wu and her coworkers decided to explore if there was an efficient way to combine both methods to provide fast, high-quality solutions.

Wu states that machine learning is a key component of our work. “Can we predict which subproblems, if solved, will lead to greater improvement in the solution and save computing time and money?”

A large-scale vehicle routing problem algorithm might select the subproblems to solve randomly or using a carefully designed heuristic. The MIT researchers used a neural network to find subproblems and then solved them. Wu and his colleagues discovered that this process increased the speed of subproblem selection by 1.5 to 2.

Wu says, “We don’t know why subproblems work better than others.” It’s an interesting area of work for the future. These insights could help us design even more efficient algorithms if we had them.

Amazing speed-up

Wu and his colleagues were amazed at how effective the approach was. Machine learning is based on the principle of garbage-in and garbage-out. This means that the quality of any machine-learning approach depends heavily on the data quality. Combinatorial problems are so complex that it is impossible to solve all of its subproblems. Wu says that a neural network trained using the “medium quality” subproblem solutions as input data would typically produce medium-quality results. However, in this instance, researchers were able leverage medium-quality solutions to produce high-quality results significantly faster than state of the art methods.

Vehicle routing and other similar problems require that users create very specific algorithms in order to solve the problem. These heuristics are known for their long-term development.

Learning-to-delegate is an automated way to speed up these heuristics for large issues, regardless of the heuristic or — potentially – the problem.

Wu says that the method works with many solvers so it could be used for resource allocation problems. Because the cost of solving the problem can be reduced by 10 to 100 percent, we may unlock new applications.