NODE DUPLICATION LOWER BOUNDS FOR THE CAPACITATED ARC ROUTING PROBLEM
Journal of the Operations Research Society of JapanPublished 1 January 1992Open access
Yasufumi Saruwatari, Ryuichi Hirabayashi, Naonori Nishida
Citations25
SJR quartileQ4
SJR score0.12
SNIP0.14
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
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.
Abstract
It is well-known that the tight lower bounds determine the effectiveness of the branch and bound method for the NP-hard problems. In this paper, we present a new lower bounding procedure for the capacitated arc routing problem (CARP), one of the arc routing problems. They give the tight lower bounds and it is easy to develop an exact algorithm using their network structures.
Keywords
Engineering
VEHICLE ROUTING: METHODS AND STUDIES
694 Citations1988Bruce Golden, Arjang A. Assad
Algorithmic Techniques for Vehicle Routing Systems and Models for Complex Routing Environments.
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.
NetworksOn general routing problems
246 Citations1976Jan Karel Lenstra, A. H. G. Rinnooy Kan
It is shown that a proposed conversion of required nodes to required arcs is not allowed and that the problem remains polynomial complete if Q = θ, and the proposed transformations from M vehicle to single vehicle problems are shown to be incorrect.
NetworksAn exact algorithm for the asymmetrical capacitated vehicle routing problem
158 Citations1986Gilbert Laporte, Hélène Mercure +1 more
An exact algorithm for the asymmetrical capacitated vehicle routing problem, i.
Mathematical programming studiesAn algorithm for the Rural Postman problem on a directed graph
88 Citations1986Nicos Christofides, Vicente Campos +2 more
This paper presents a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems.
Computers & Operations ResearchRouting electric meter readers
85 Citations1979Helman I. Stern, Moshe Dror
An optimization problem closely related to the M-Chinese postman problem—an edge oriented routing problem—a heuristic procedure is used to solve an example from the City of Beersheva and provides conditions under which the algorithm should have practical utility.
NetworksPostman tour on a graph with precedence relation on arcs
67 Citations1987Moshe Dror, Helman I. Stern +1 more
The problem of finding the minimum length of feasible postman tour is NP-complete because the precedence relation on sets of arcs is general.
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.
Operations research proceedingsSubtour Elimination Algorithm for the Capacitated Arc Routing Problem
4 Citations1992Yasufumi Saruwatari, Ryuichi Hirabayashi +1 more
The capacitated arc routing problem (CARP) is a set of cycles with minimum-cost such that each demand arc is serviced by exactly one vehicle, each cycle starts and ends at the depot and total demand of each cycle does not exceed the vehicle capacity.