A Hybrid Learning-Based Matheuristic to Solve the Vehicle Routing Problem with Stochastic Demands
(2026) CPAIOR 2026 — Location: Rabot, Marrocco (26.May.2026)
Files
978-3-032-27242-3_27.pdf
Open Access - Adobe PDF
- 1.54 MB
Details
- Authors
Reynal, Gaël 
Desaulniers, Guy Rousseau, Louis-Martin
- Abstract
- The vehicle routing problem with stochastic demands is a combinatorial optimization problem that arises in industrial applications such as waste management and facility replenishment. In these applications , one could aim at using a specific number of vehicles to better align with available resources, thereby including a fixed-fleet constraint in the problem. Standard column generation heuristics, that are usually efficient in this context, struggle to handle this additional constraint and cannot quickly produce good feasible solutions, mainly because the labeling algorithm used during the pricing becomes inefficient. We introduce a hybrid pricing heuristic that generates columns by combining a greedy component aiming for a quick generation of good columns, a reinforcement learning module to compute critical routes disregarded by the greedy construction, and a tabu search procedure to explore the search space around the generated routes. We embed our method within an existing restricted master heuristic framework: we first p erform a column generation phase using our pricing heuristic to quickly generate a set of high-quality columns, which we then complete with a greedy random-ized adaptive search procedure. The resulting restricted master problem is then solved as a mixed-integer program. We evaluate our approach on 40 benchmark instances with up to 60 customers and achieve an average optimality gap of 1% within a 5-min total computation time. Our matheuristic also provides more best average solution cost and optimal solutions than the competing heuristics considered.
- Affiliations
Citations
Reynal, G., Cappart, Q., Desaulniers, G., & Rousseau, L.-M. (2026). A Hybrid Learning-Based Matheuristic to Solve the Vehicle Routing Problem with Stochastic Demands. Integration of Constraint Programming, Artificial intelligence, and Operations Research, 16595, 453-469. https://doi.org/10.1007/978-3-032-27242-3_27 (Original work published 2026)