Learning to repeatedly solve routing problems
From MaRDI portal
Abstract: 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.
Recommendations
- Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands
- Complexity and approximation in reoptimization
- Deep policy dynamic programming for vehicle routing problems
- On the use of learnheuristics in vehicle routing optimization problems with dynamic inputs
- Learning heuristics for the TSP by policy gradient
Cites work
- A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX
- A generic exact solver for vehicle routing and related problems
- A machine learning-based approximation of strong branching
- Branch-and-price: Column generation for solving huge integer programs
- Column Generation
- Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems
- Learning when to use a decomposition
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- New benchmark instances for the capacitated vehicle routing problem
- Shortest Path Problems with Resource Constraints
Cited in
(4)- Learning to Approximate Industrial Problems by Operations Research Classic Problems
- Learn and route: learning implicit preferences for vehicle routing
- Fast Shapley value approximation through machine learning with application in routing problems
- Beyond fifty years of vehicle routing: insights into the history and the future
This page was built for publication: Learning to repeatedly solve routing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196890)
