GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for th...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2013-12, Vol.40 (12), p.3206-3217
Main Authors: Luiz Usberti, Fábio, Morelato França, Paulo, França, André Luiz Morelato
Format: Article
Language:English
Subjects:
Arc routing
Buses (vehicles)
Carp
Combinatorial analysis
Comparative analysis
Deviation
Evolutionary
Evolutionary path-relinking
Garbage collection
GRASP filtering
Heuristic
Infeasible solution space search
Mathematical models
Metaheuristics
Optimization techniques
Reactive parameters
Route optimization
Searching
Stochastic models
Studies
Transportation problem (Operations research)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2011.10.014