Polyhedral study of the capacitated vehicle routing problem

DOI10.1007/BF01580599zbMath0790.90029OpenAlexW1998205685MaRDI QIDQ688914

Farid Harche, Cornuéjols, Gérard

Publication date: 1 November 1993

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

Full work available at URL: https://doi.org/10.1007/bf01580599

zbMATH Keywords

polyhedronbranch and cutfacetcapacitated vehicle routingcutting plane algorithmsubtour eliminationcomb inequalitiescentral depottotal distance traveled

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Transportation, logistics and supply chain management (90B06)

Related Items

Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm, A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs, Routing problems: A bibliography, Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route, A result on projection for the vehicle routing problem, Some thoughts on combinatorial optimisation, Bilevel programming and the separation problem, Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems, Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, Recent advances in vehicle routing exact algorithms, A multi-stop routing problem, New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems, On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches, On the complexity of the separation problem for rounded capacity inequalities, Models, relaxations and exact approaches for the capacitated vehicle routing problem, Exact algorithms for routing problems under vehicle capacity constraints, Branch and cut methods for network optimization, Unnamed Item, 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, A branch-and-cut algorithm for an assembly routing problem, A generalized exchange heuristic for the capacitated vehicle routing problem, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, Planning models for freight transportation, Stronger \(K\)-tree relaxations for the vehicle routing problem, A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes, A sweep-based algorithm for the fleet size and mix vehicle routing problem, Survey of facial results for the traveling salesman polytope, Separating capacity constraints in the CVRP using tabu search

Uses Software

• GAMS
• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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