A Periodic Multi-Vehicle Arc Routing Problem
Demetrio Laganà  1@  , Rosario Paradiso  2@  , Francesca Vocaturo  3@  
1 : Department of Mechanical, Energy and Management Engineering  (DIMEG)
University of Calabria -  Italy
2 : Department of Mathematics and Computer Science
University of Calabria -  Italy
3 : Department of Economics, Statistics and Finance "Giovanni Anania"
University of Calabria -  Italy

We deal with a periodic arc routing problem on mixed graphs, in which some links require to be serviced a given number of times over a finite and discrete time horizon. A fleet of homogeneous vehicles is available at the depot to perform the services in each period of the time horizon. Moreover, each vehicle has a maximum length (expressed in terms of time or distance) to be traveled. In practical applications, a required link represents a street in which a given service is regularly planned (e.g., inspection of power lines or of water and gas underground pipelines) or irregular services arise (e.g. inspection of road networks where the traffic conditions sensibly change during the week). The aim is to design several sets of minimum-cost routes, one for each period of the time horizon, that satisfies the service requirements. We refer to this problem as the Periodic multi-vehicle Arc Routing Problem (PARP). For the PARP, an extended set partitioning based formulation is proposed and an exact algorithm is designed. In addition, preliminary results are presented

Online user: 1 RSS Feed