GRASP and Path Relinking for the Clustered Prize-collecting Arc Routing Problem |
| |
Authors: | Julián Aráoz Elena Fernández Carles Franquesa |
| |
Institution: | 1. Statistics and Operations Research Department, Technical University of Catalonia, Campus Nord, C5-208, Jordi Girona 1–3, 08034, Barcelona, Spain
|
| |
Abstract: | The Clustered Prize-collecting Arc Routing Problem is an arc routing problem where each demand edge is associated with a profit which is collected once if the edge is serviced, independently of the number of times it is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. This paper presents GRASP and Path Relinking heuristics for the Clustered Prize-collecting Arc Routing Problem. For the constructive phase of the GRASP two different strategies are considered. One of them follows a bottom-up style whereas the other one is a top-down procedure. The best solutions obtained with both strategies are used as elite solutions for the Path Relinking. The results of extensive computational experiments are presented and analyzed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|