New lower bound for the Capacitated Arc Routing Problem
Computers & Operations ResearchPublished 22 April 2005
Sanne Wøhlk
Citations26
SJR quartileQ1
SJR score1.60
SNIP2.02
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new lower bound is presented, the Multiple Cuts Node Duplication Lower Bound, for the undirected Capacitated Arc Routing Problem and it is proved that this new bound dominates the existing bounds for the problem.
Abstract
We present a new lower bound, the Multiple Cuts Node Duplication Lower Bound, for the undirected Capacitated Arc Routing Problem. We prove that this new bound dominates the existing bounds for the problem. Computational results are also provided.
Keywords
Computer ScienceEngineering
NetworksCapacitated arc routing problems
568 Citations1981Bruce Golden, Richard T. Wong
The intent in this paper is to define a capacitated arc routing problem, to provide mathematical programming formulations, to perform a computational complexity analysis, and to present an approximate solution strategy for this class of problems.
Computers & Operations ResearchComputational experiments with algorithms for a class of routing problems
305 Citations1983Bruce Golden, James DeArmon +1 more
This paper focuses on the development and testing of algorithms for solving the capacitated Chinese postman problem and extensive computational results are presented and analyzed.
NetworksThe Capacitated Arc Routing Problem: Lower bounds
160 Citations1992Enrique Benavent, Vicente Campos +2 more
New lower bounds are developed for the Capacitated Arc Routing Problem, in which a fleet of vehicles must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity.
Computers & Operations ResearchTransforming arc routing into node routing problems
116 Citations1987W. L. Pearn, Arjang A. Assad +1 more
This paper describes how the Capacitated Arc Routing Problem can be formulated as a standard vehicle routing problem, which allows us to transform arc routing into node routing problems and establishes the equivalence of these two classes of problems.
Computational Optimization and ApplicationsThe Capacitated Arc Routing Problem: Valid Inequalities and Facets
107 Citations1998José-Manuel Belenguer, Enrique Benavent
The resulting partial description of the polyhedron has been used to develop a cutting plane algorithm for the Capacitated Arc Routing Problem that outperformed all the existing lower bounds for the CARP on a set of 34 instances taken from the literature.
American Journal of Mathematical and Management SciencesThe Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases
56 Citations1987Arjang A. Assad, W. L. Pearn +1 more
NetworksNew lower bounds for the Capacitated Arc Routing Problem
35 Citations1988Wen Lea Pearn
This paper briefly reviews two existing lower bounding procedures—the Matching Lower Bound and the Node Scanning Lower Bound—then introduces a new bounding technique to provide tighter lower bounds on the problem solutions.
Journal of the Operations Research Society of JapanNODE DUPLICATION LOWER BOUNDS FOR THE CAPACITATED ARC ROUTING PROBLEM
25 Citations1992Yasufumi Saruwatari, Ryuichi Hirabayashi +1 more
This paper presents a new lower bounding procedure for the capacitated arc routing problem (CARP), one of the arc routing problems, which gives the tight lower bounds and it is easy to develop an exact algorithm for their network structures.