A Scatter Search for the periodic capacitated arc routing problem - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2006

A Scatter Search for the periodic capacitated arc routing problem

(1) , (1) , (1)
1

Abstract

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 and versions

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

Identifiers

Cite

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
10 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More