Delivery companies face the challenge of routing their vehicles: finding the shortest route to deliver goods to reduce fuel costs. The more delivery points there are, the more complex it is to find the ideal route. Algorithms have been designed to address this problem for a few hundred cities, but these solutions become too slow when applied to a larger number of cities. Researchers at the Massachusetts Institute of Technology (MIT) have used machine learning to speed up solutions to vehicle routing problems for large sets of cities.

The vehicle routing problem

The most studied Vehicle Routing Problem (VRP) is the one formulated by William Rowan Hamilton in 1859: the traveling salesman. In its most classic form, his statement is as follows: “A commercial traveler must visit a definite number of cities once and only once and return to his starting point. Find the order of visiting the cities that minimizes the total distance traveled by the traveler”. This combinatorial optimization problem, which belongs to the class of NP-complete problems, becomes very complex when applied to a large number of cities and its solution then requires a much too long time. Approximate methods, or approximation algorithms, are used.

Depots in charge of delivering parcels to customers (commonly called last mile delivery), have to take into account various elements: the location of delivery points, the drivers’ schedules and the time slots at which customers would like to be delivered, the cost of fuel… Larger companies like Fedex, for example, choose to use subcontractors who are assigned a delivery area, thus dividing the routing problem.

This is the same kind of approach that was followed by MIT researchers when approaching their study titled: “Learning to Delegate for Large-Scale Vehicle Routing.” The study focuses only on the shortest route and does not consider other routing problems.

Accelerating algorithmic solvers

Sirui Li, Zhongxia Yan, and Cathy Wu, Gilbert W. Winslow Assistant Professor of Career Development in the Department of Civil and Environmental Engineering and the Institute for Data, Systems, and Society, developed a machine learning strategy that accelerates some of the strongest algorithmic solvers by 10 to 100 times. Cathy Wu said:

“For us, that’s where machine learning comes in. Can we predict which of these subproblems, if we were to solve them, would lead to a greater improvement in the solution, saving time and computational expense?”

The solver’s algorithms divided the delivery problem into smaller subproblems to solve (200 subproblems for routing vehicles between 2,000 cities). Cathy Wu and colleagues’ team created a neural network that identifies the most useful subproblems to solve, instead of solving them all, to increase the quality of the solution while using less computation. Marc Kuo, founder and CEO of Routific, an intelligent logistics platform for optimizing delivery routes, states:

“Most academic research tends to focus on specialized algorithms for small problems, trying to find better solutions at the expense of processing times. But in the real world, companies don’t care about finding better solutions, especially if they take too much time to compute,” Kuo says. In the world of last-mile logistics, time is money, and you can’t make your entire warehouse operation wait for a slow algorithm to return routes. An algorithm has to be hyper-fast to be practical.”

Finding the best possible solution

Finding the right answer to routing problems is usually not possible because the number of possible solutions is far too large. Cathy Wu explains:

“The name of the game for these types of problems is to design efficient algorithms…that are optimal within a certain factor. But the goal is not to find optimal solutions. That’s too hard. Instead, we want to find the best possible solutions. Even a 0.5 percent improvement in solutions can result in a significant increase in revenue for a company.”

The approach, which the researchers called “learning to delegate,” sped up the process of selecting subproblems by 1.5 to 2 times, to the surprise of Cathy Wu and her colleagues:

“We don’t know why these subproblems are better than other subproblems. This is actually an interesting line of future work. If we had insights here, these could lead to the design of even better algorithms.”

On the other hand, the quality of the results also surprised the researchers. ” A neural network trained on the solutions of “medium quality” subproblems available as input data “would generally give medium quality results.” In this case, however, the researchers, with medium-quality solutions obtained high-quality results much faster than state-of-the-art methods. This method could find many applications such as the path of a robot in a warehouse… Cathy Wu concludes:

“Since the method can work with a variety of solvers, it can be useful for a variety of resource allocation problems. We can unlock new applications that will now be possible because the cost of solving the problem is 10 to 100 times lower.”

Marc Kuo adds:

“This work pushes the boundaries of solving large-scale vehicle routing problems quickly. Some of Routific’s recent algorithmic advances were inspired by Wu’s work.”

Wu, social and engineering systems PhD student Sirui Li, and electrical and computer engineering PhD student Zhongxia Yan presented their research this week at the NeurIPS 2021 conference, research that was the source of this article.

Translated from Une équipe de chercheurs du MIT accélère le routage des véhicules grâce à l’apprentissage automatique