Learning to repeatedly solve routing problems
This work addresses the problem of efficiently solving routing problems after minor data changes for logistics and operations research, representing an incremental improvement over existing methods.
The paper tackles the reoptimization of the capacitated vehicle routing problem with static clients and changed demands by predicting edges likely to remain in an optimal solution, reducing complexity and speeding up resolution. The approach achieved solutions with an optimality gap of 0% to 1.7% on benchmark instances within reasonable computing time.
In the last years, there has been a great interest in machine-learning-based heuristics for solving NP-hard combinatorial optimization problems. The developed methods have shown potential on many optimization problems. In this paper, we present a learned heuristic for the reoptimization of a problem after a minor change in its data. We focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) and changed demands. Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution after a change of client demands. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while yielding a good quality solution. The proposed approach resulted in solutions with an optimality gap ranging from 0\% to 1.7\% on different benchmark instances within a reasonable computing time.