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

DOI10.1016/J.DAM.2020.02.012MaRDI QIDQ2664007zbMATH OpenOpenAlexFDO

Authors 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 programmingpolynomial formulationsymmetry breakingvehicle routing

Mathematics Subject Classification ID

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

Recommendations

• Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
• scientific article; zbMATH DE number 6913886
• On the capacitated vehicle routing problem
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation

Cites work

• A new branch-and-cut algorithm for 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
• Cut-and-solve: An iterative search strategy for combinatorial optimization problems
• scientific article; zbMATH DE number 2134197 (Why is no real title available?)
• Improved branch-cut-and-price for capacitated vehicle routing
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• Local branching
• Optimal Routing under Capacity and Distance Restrictions
• Projection results for vehicle routing
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Solving symmetric vehicle routing problems asymmetrically
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Technical Note—Rounding Symmetric Traveling Salesman Problems with an Asymmetric Assignment Problem
• The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time
• The vehicle routing problem
• Vehicle Routing

Cited in

(2)

• Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
• Domain-independent dynamic programming

Describes a project that uses

Uses Software

• VRP
• CVRPSP

This page was built for publication: A symmetry-free polynomial formulation of the capacitated vehicle routing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664007)