The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time

DOI10.1016/j.ejor.2018.06.002zbMath1403.90578OpenAlexW2808038090MaRDI QIDQ1991101

Adam N. Letchford, Juan-José Salazar-González

Publication date: 30 October 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/125706/1/CVRP_pseudopoly.pdf

zbMATH Keywords

integer programmingcolumn generationvehicle routing

Mathematics Subject Classification ID

Integer programming (90C10) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

The arc-item-load and related formulations for the cumulative vehicle routing problem, A symmetry-free polynomial formulation of the capacitated vehicle routing problem, Multi‐objective optimization of transporting blood products by routing UAVs: the case of Istanbul, Real-time ride-sharing framework with dynamic timeframe and anticipation-based migration

Uses Software

• VRP
• CVRPSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient elementary and restricted non-elementary route pricing
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• A branch and bound algorithm for the capacitated vehicle routing problem
• The vehicle routing problem. Latest advances and new challenges.
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• Combined route capacity and route length models for unit demand vehicle routing problems
• A result on projection for the vehicle routing problem
• The ellipsoid method and its consequences in combinatorial optimization
• The vehicle routing problem: An overview of exact and approximate algorithms
• Multistars, partial multistars and the capacitated vehicle routing problem
• Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
• On the complexity of the separation problem for rounded capacity inequalities
• New benchmark instances for the capacitated vehicle routing problem
• Lagrangean relaxation. (With comments and rejoinder).
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• Improved branch-cut-and-price for capacitated vehicle routing
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Projection results for vehicle routing
• The Truck Dispatching Problem
• Vehicle Routing
• Decomposition Principle for Linear Programs
• A New Algorithm for the 0-1 Knapsack Problem
• An Integer Programming Approach to the Vehicle Scheduling Problem
• The omnipresence of Lagrange