Scientific Program > Talks by Speaker > Laganà Demetrio

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