A Scatter Search for the periodic capacitated arc routing problem - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2006

A Scatter Search for the periodic capacitated arc routing problem

Résumé

This paper considers the Periodic Capacitated Arc Routing Problem (PCARP), a natural extension of the well-known CARP to a multi-period horizon. Its objective is to assign a set of service days to each edge in a given network and to solve the resulting CARP for each period, in order to minimize the required fleet size and the total cost of the trips on the horizon. This new and very hard problem has various applications in periodic operations on street networks, like waste collection and sweeping. A greedy heuristic and a Scatter Search (SS) are developed and evaluated on two sets of PCARP instances derived from classical CARP benchmarks. The results show that the SS strongly improves its initial solutions and clearly outperforms the greedy heuristic. Preliminary lower bounds are also provided. As they are not sufficiently tight, the SS is also tested in the single-period case (CARP) for which tight bounds are available: in fact, it competes with one state-of-the-art metaheuristic proposed for the CARP.

Dates et versions

hal-02478974 , version 1 (14-02-2020)

Identifiants

Citer

Feng Chu, Nacima Labadie, Christian Prins. A Scatter Search for the periodic capacitated arc routing problem. European Journal of Operational Research, 2006, 169 (2), pp.586-605. ⟨10.1016/j.ejor.2004.08.017⟩. ⟨hal-02478974⟩

Collections

CNRS UTT LOSI
13 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More