An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands
Transportation SciencePublished 22 October 2009
Gilbert Laporte, Roberto Musmanno, Francesca Vocaturo
Citations127
SJR quartileQ1
SJR score2.32
SNIP2.03
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.
Abstract
The capacitated arc-routing problem with stochastic demands (CARPSD) is an extension of the well-known capacitated arc-routing problem (CARP) in which demands are stochastic. This leads to the possibility of route failures whenever the realized demand exceeds the vehicle capacity. This paper presents the CARPSD in the context of garbage collection. It describes an adaptive large-scale neighbourhood search heuristic for the problem. Computational results show the superiority of this algorithm over an alternative solution approach.
Keywords
Engineering
Transportation ScienceAn Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows
2,392 Citations2006Stefan Røpke, David Pisinger
This paper presents a heuristic for the pickup and delivery problem based on an extension of the large neighborhood search heuristic previously suggested for solving the vehicle routing problem with time windows that is very robust and is able to adapt to various instance characteristics.
Operations research, computer science. Interface seriesThe Vehicle Routing Problem: Latest Advances and New Challenges
1,456 Citations2008Bruce Golden, S. Raghavan +3 more
A metaheuristics approach to solve the Capacitated Vehicle Routing Problem on Trees and a Genetic Algorithm to Solve the Generalized Orienteering Problem are suggested.
Journal of Computational PhysicsNew Optimization Heuristics
743 Citations1993Gunter Dueck
The quality of the computational results obtained so far by RRT and GDA shows that the new algorithms behave equally well as TA and thus a fortiori better than SA.
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.
Operations ResearchA Vehicle Routing Problem with Stochastic Demand
398 Citations1992Dimitris Bertsimas
This work considers a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic, and proposes heuristics and algorithms to construct an a priori sequence among all customers of minimal expected total length.
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.
Operations ResearchA Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers
279 Citations1996Michel Gendreau, Gilbert Laporte +1 more
A tabu search heuristic is developed for a version of the stochastic vehicle routing problem where customers are present at locations with some probabilities and have random demands and produces an optimal solution in 89.45% of cases.
Operations ResearchA Tabu Search Heuristic for the Capacitated arc Routing Problem
278 Citations2000Alain Hertz, Gilbert Laporte +1 more
A tabu search is proposed for the Capacitated Arc Routing Problem, which outperforms all known heuristics and often produces a proven optimum.
Arc Routing : Theory, Solutions and Applications
277 Citations2000Moshe Dror
Annals of Operations ResearchCompetitive Memetic Algorithms for Arc Routing Problems
275 Citations2004Philippe Lacomme, Christian Prins +1 more
Basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the Capacitated Arc Routing Problem (ECARP) are presented.
Operations ResearchA Priori Optimization
252 Citations1990Dimitris Bertsimas, Patrick Jaillet +1 more
The idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance is introduced.
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.
Computers & Operations ResearchA record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem
198 Citations2006Feiyue Li, Bruce Golden +1 more
A variant of the record-to-record travel algorithm for the standard vehicle routing problem that takes a heterogeneous fleet into account is developed, and computational results on eight benchmark problems are reported.
European Journal of Operational ResearchA guided local search heuristic for the capacitated arc routing problem
181 Citations2003Patrick Beullens, Luc Muyldermans +2 more
A new local search algorithm for the capacitated arc routing problem (CARP) is presented that outperforms the existing heuristics for the CARP and often detects an optimal solution within limited computation time.
Computers & Operations ResearchA cutting plane algorithm for the capacitated arc routing problem
178 Citations2003José-Manuel Belenguer, Enrique Benavent
A cutting plane algorithm is designed and implemented based on some new valid inequalities for the Capacitated Arc Routing Problem that outperformed all the existing lower bounding procedures for the CARP.
Computers & Operations ResearchSolving capacitated arc routing problems using a transformation to the CVRP
171 Citations2005Humberto J. Longo, Marcus Poggi de Aragão +1 more
The paper shows that this approach can be effective and, in particular, that the original instances may generate node routing instances that behave as if the size is not increased, by slightly modifying the well-known transformation by Pearn, Assad and Golden from capacitated arc routing problem to the capacitated vehicle routing problem (CVRP).
Computers & Operations ResearchA deterministic tabu search algorithm for the capacitated arc routing problem
165 Citations2006José Brandão, Richard Eglese
A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances and results show that the proposed algorithm produces high quality results within a reasonable computing time.
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.
Arc Routing
127 Citations2000
Transportation ScienceA Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem
120 Citations2001Alain Hertz, Michel Mittaz
The use of basic algorithmic procedures for the design of heuristics in an arc routing context in a variable neighborhood descent algorithm for the solution of the undirected CARP is reported on.
Journal of HeuristicsA variable neighborhood search for the capacitated arc routing problem with intermediate facilities
108 Citations2007Michael Polacek, Karl F. Doerner +2 more
The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions of the capacitated arc routing problem.
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.
Operations research, computer science. Interface seriesA Decade of Capacitated Arc Routing
98 Citations2008Sanne Wøhlk
This work surveys the latest research within the area of arc routing focusing mainly on the Capacitated Arc Routing Problem (CARP) and its variants.
Archivio istituzionale della ricerca (Alma Mater Studiorum Università di Bologna)Exact methods based on node routing formulations for arc routing problems
90 Citations2006Roberto Baldacci, Vittorio Maniezzo
A general purpose transformation of arc into node routing problems and new results on lower bounds and exact methods for CARP instances are proposed.
NetworksThe capacitated arc routing problem with intermediate facilities
83 Citations2001Gianpaolo Ghiani, Gennaro Improta +1 more
A variant of the classical Capacitated Arc Routing Problem (CARP) in which the vehicle may unload or replenish at intermediate facilities and two lower bounds are developed, based on the Rural Postman Problem and the solution of an RPP.
Lecture notes in computer scienceEvolutionary Algorithms for Stochastic Arc Routing Problems
67 Citations2004Gérard Fleury, Philippe Lacomme +1 more
A memetic algorithm for the SCARP is proposed and compared with two deterministic versions based on average demands, which confirms the expected cost computed by the MA and shows its ability to provide robust solutions, without significant enlargement of the cost of planned trips.
NetworksExact methods based on node-routing formulations for undirected arc-routing problems
67 Citations2006BaldacciR., ManiezzoV.
Computers & Operations ResearchExploiting sparsity in pricing routines for the capacitated arc routing problem
54 Citations2008Adam N. Letchford, Amar Oukil
It is shown how to exploit sparsity in the CARP model to yield faster pricing routines and to solve the problem via branch-cut-and-price.
NetworksExact methods based on node‐routing formulations for undirected arc‐routing problems
49 Citations2005Roberto Baldacci, Vittorio Maniezzo
A general purpose transformation of arc into node‐routing problems and new results on lower bounds and exact methods for CARP instances are proposed.
Journal of the Operational Research SocietyImproving robustness of solutions to arc routing problems
45 Citations2005Gérard Fleury, Philippe Lacomme +2 more
The basic concept of a new technique to compute stochastic capacitated arc routing problem (SCARP), obtained by taking random demands in the CARP, based upon the best method published for CARP: a hybrid genetic algorithm (HGA).
Annals of Operations ResearchUsing mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles
36 Citations2006John Sniezek, Lawrence Bodin
This paper presents the Composite Approach for solving the Capacitated Arc Routing Problem with Vehicle/Site Dependencies (CARP-VSD), two mixed integer programs, the Initial Fleet Mix Generator and the Mathematical Programming Procedure, and a multi-criterion function called the Measure of Goodness.
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.
A hierarchical relaxations lower bound for the capacitated arc routing problem
31 Citations2003Anita Amberg, Stefan Voß
This paper considers an important problem within this frame, the capacitated arc routing problem (CARP), and provides a new lower bounding scheme to obtain bounds on the quality of heuristically obtained solutions, showing that these bounds are more effective than other bounds available from the literature.
Lecture notes in computer scienceApplying Ant Colony Optimization to the Capacitated Arc Routing Problem
28 Citations2004Karl F. Doerner, Richard F. Hartl +2 more
The Capacitated Arc Routing Problem (CARP) is a prototypical optimization problem asking a fleet of vehicles to serve a set of customer demands located on the arcs of a network.
Polyhedral Theory for Arc Routing Problems
28 Citations2000Richard Eglese, Adam N. Letchford
As explained in Chapter 4, most realistic Arc Routing Problems are known to be NP-hard, therefore there will be certain instances which are impossible to solve to optimality within a reasonable time.
Computers & Operations ResearchNew lower bound for the Capacitated Arc Routing Problem
26 Citations2005Sanne Wøhlk
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.
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.