Polyhedral study of the capacitated vehicle routing problem

DOI10.1007/BF01580599zbMath0790.90029MaRDI QIDQ688914

Cornuéjols, Gérard, Farid Harche

Publication date: 1 November 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

polyhedron; branch and cut; facet; capacitated vehicle routing; cutting plane algorithm; subtour elimination; comb inequalities; central depot; total distance traveled

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90B06: Transportation, logistics and supply chain management

Related Items

A generalized exchange heuristic for the capacitated vehicle routing problem, Branch and cut methods for network optimization, Models, relaxations and exact approaches for the capacitated vehicle routing problem, Recent advances in vehicle routing exact algorithms, A multi-stop routing problem, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, A result on projection for the vehicle routing problem, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, Planning models for freight transportation, Some thoughts on combinatorial optimisation, Survey of facial results for the traveling salesman polytope, Separating capacity constraints in the CVRP using tabu search, Stronger \(K\)-tree relaxations for the vehicle routing problem, A sweep-based algorithm for the fleet size and mix vehicle routing problem, Routing problems: A bibliography, New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

Uses Software

• GAMS
• VRP

Cites Work

• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• Polyhedral results for a vehicle routing problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem in graphs with some excluded minors
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• The traveling salesman problem on a graph and some related integer polyhedra
• Optimal Routing under Capacity and Distance Restrictions
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• On the symmetric travelling salesman problem: A computational study
• An Integer Programming Approach to the Vehicle Scheduling Problem
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• Edmonds polytopes and weakly hamiltonian graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item