Improved lower bounds and exact algorithm for the capacitated arc routing problem

DOI10.1007/s10107-011-0497-4zbMath1262.90100OpenAlexW2117319367MaRDI QIDQ1942278

Jean-François Cordeau, Gilbert Laporte, Enrico Bartolini

Publication date: 18 March 2013

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

Full work available at URL: https://doi.org/10.1007/s10107-011-0497-4

zbMATH Keywords

column generationvalid inequalitiesarc routingset partitioning

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Dynamic programming (90C39)

Related Items

Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition, Efficient elementary and restricted non-elementary route pricing, A hybrid metaheuristic approach for the capacitated arc routing problem, Improved bounds for large scale capacitated arc routing problem, Lane covering with partner bounds in collaborative truckload transportation procurement, Constructive heuristics for the mixed capacity arc routing problem under time restrictions with intermediate facilities, The commodity-split multi-compartment capacitated arc routing problem, A generic exact solver for vehicle routing and related problems, Fast upper and lower bounds for a large‐scale real‐world arc routing problem, Crossover iterated local search for SDCARP, Iterated local search and column generation to solve arc-routing as a permutation set-covering problem, Branch-price-and-cut for the mixed capacitated general routing problem with time windows, A districting-based heuristic for the coordinated capacitated arc routing problem, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, A computational comparison of flow formulations for the capacitated location-routing problem, Robust drone selective routing in humanitarian transportation network assessment

Uses Software

• CPLEX
• VRP
• CVRPSEP
• CVRPSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• Exploiting sparsity in pricing routines for the capacitated arc routing problem
• Routeing winter gritting vehicles
• The capacitated arc routing problem: Valid inequalities and facets
• A cutting plane algorithm for the capacitated arc routing problem
• A guided local search heuristic for the capacitated arc routing problem
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• An efficient transformation of the generalized vehicle routing problem
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• New lower bound for the capacitated arc routing problem
• Solving capacitated arc routing problems using a transformation to the CVRP
• New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
• Recent results on Arc Routing Problems: An annotated bibliography
• Exact methods based on node-routing formulations for undirected arc-routing problems
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• A Decade of Capacitated Arc Routing
• The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases
• New lower bounds for the Capacitated Arc Routing Problem
• Capacitated arc routing problems
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Odd Minimum Cut-Sets and b-Matchings
• NODE DUPLICATION LOWER BOUNDS FOR THE CAPACITATED ARC ROUTING PROBLEM
• The Capacitated Arc Routing Problem: Lower bounds
• Exact solution of the generalized routing problem through graph transformations
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Arc Routing Problems, Part II: The Rural Postman Problem
• Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem