The periodic rural postman problem (PRPP) is variant of the classical rural postman problem whose appli11 cations arise in garbage collection and street sweeping. In the PRPP each required arc/edge of a graph must be visited a given number of times over an m-day planning period in such a way that service days are equally 13 spaced. The PRPP amounts to select a service day combination for each required arc/edge and to determine a postman tour for each day of the planning period. The objective is to minimize the total distance travelled. 15 In this paper a simple but eective heuristic for the undirected PRPP is presented. Extensive computational results indicate that the algorithm is capable of providing high quality solutions. To our knowledge this is the 17 rst methodological paper devoted to a periodic arc routing problem.
A Heuristic for the Periodic Rural Postman Problem
GHIANI, GIANPAOLO;TRIKI, CHEFI
2005-01-01
Abstract
The periodic rural postman problem (PRPP) is variant of the classical rural postman problem whose appli11 cations arise in garbage collection and street sweeping. In the PRPP each required arc/edge of a graph must be visited a given number of times over an m-day planning period in such a way that service days are equally 13 spaced. The PRPP amounts to select a service day combination for each required arc/edge and to determine a postman tour for each day of the planning period. The objective is to minimize the total distance travelled. 15 In this paper a simple but eective heuristic for the undirected PRPP is presented. Extensive computational results indicate that the algorithm is capable of providing high quality solutions. To our knowledge this is the 17 rst methodological paper devoted to a periodic arc routing problem.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
