A symmetry-free polynomial formulation of the capacitated vehicle routing problem

DOI10.1016/j.dam.2020.02.012zbMath1462.90018OpenAlexW3012050958MaRDI QIDQ2664007

Jens Lysgaard, Sune Lauth Gadegaard

Publication date: 20 April 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.02.012

zbMATH Keywords

integer programmingvehicle routingsymmetry breakingpolynomial formulation

Mathematics Subject Classification ID

Integer programming (90C10) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Uses Software

• VRP
• CVRPSP

Cites Work

• Unnamed Item
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem
• A result on projection for the vehicle routing problem
• Solving symmetric vehicle routing problems asymmetrically
• Local branching
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Improved branch-cut-and-price for capacitated vehicle routing
• Cut-and-solve: An iterative search strategy for combinatorial optimization problems
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Projection results for vehicle routing
• The Vehicle Routing Problem
• Vehicle Routing
• Integer Programming Formulation of Traveling Salesman Problems
• Optimal Routing under Capacity and Distance Restrictions
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem