Article ID: | iaor2005543 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 3 |
Start Page Number: | 209 |
End Page Number: | 223 |
Publication Date: | Jul 2004 |
Journal: | Journal of Mathematical Modelling and Algorithms |
Authors: | Laporte Gilbert, Ghiani Gianpaolo, Guerriero Francesca, Musmanno Roberto |
Keywords: | heuristics, networks: path |
This paper deals with the Arc Routing Problem with Intermediate Facilities under Capacity and Length Restrictions (CLARPIF), a variant of the classical Capacitated Arc Routing Problem, in which vehicles may unload or replenish at intermediate facilities and the length of any route may not exceed a specified upper bound. Three heuristics are developed for the CLARPIF: the first is a constructive procedure based on a partitioning approach while the second and the third are tailored Tabu Search procedures. Computational results on a set of benchmark instances with up to 50 vertices and 92 required edges are presented and analyzed.