The periodic rural postman problem (PRPP) is variant of the classical rural postman problem whose applicationsarise in garbage collection and street sweeping. In the PRPP each required arc/edge of a graph mustbe visited a given number of times over an m-day planning period in such a way that service days are equallyspaced. The PRPP amounts to select a service day combination for each required arc/edge and to determinea postman tour for each day of the planning period. The objective is to minimize the total distance travelled.In this paper a simple but effective heuristic for the undirected PRPP is presented. Extensive computationalresults indicate that the algorithm is capable of providing high quality solutions. To our knowledge this is thefirst methodological paper devoted to a periodic arc routing problem.

A Heuristic for the Periodic Rural Postman Problem

MUSMANNO, Roberto;PALETTA, Giuseppe;
2005

Abstract

The periodic rural postman problem (PRPP) is variant of the classical rural postman problem whose applicationsarise in garbage collection and street sweeping. In the PRPP each required arc/edge of a graph mustbe visited a given number of times over an m-day planning period in such a way that service days are equallyspaced. The PRPP amounts to select a service day combination for each required arc/edge and to determinea postman tour for each day of the planning period. The objective is to minimize the total distance travelled.In this paper a simple but effective heuristic for the undirected PRPP is presented. Extensive computationalresults indicate that the algorithm is capable of providing high quality solutions. To our knowledge this is thefirst methodological paper devoted to a periodic arc routing problem.
Arc routing problems; Periodic routing problems
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/145961
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 14
social impact