GRASP with evolutionary path-relinking for the capacitated arc routing problem
| Autor: | Fábio Luiz Usberti, André Luiz Morelato França, Paulo Morelato França |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Arc routing
Mathematical optimization General Computer Science business.industry GRASP Metaheuristics Infeasible solution space search Management Science and Operations Research Set (abstract data type) Modelling and Simulation Modeling and Simulation Path (graph theory) Local search (optimization) GRASP filtering Routing (electronic design automation) Reactive parameters business Metaheuristic Evolutionary path-relinking Greedy randomized adaptive search procedure Computer Science(all) Mathematics |
| Zdroj: | Computers & Operations Research. 40:3206-3217 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2011.10.014 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect