A Branch-and-cut algorithm for the Periodic Rural Postman Problem with Irregular Services on Mixed Graphs
Demetrio Laganà  1@  , Enrique Benavent  2@  , Angel Corberán  2@  , Francesca Vocaturo  3@  
1 : Department of Mechanical, Energy and Management Engineering, University of Calabria
87036 Arcavacata di Rende (CS) -  Italy
2 : Universidad de Valencia
3 : Department of Economics, Statistics and Finance, University of Calabria
87036 Arcavacata di Rende (CS) -  Italy

In this paper, we deal with an extension of the rural postman problem in which some links of a mixed graph must be traversed once (or a specified number of times) over a given time horizon. These links represent entities that must be serviced a number of times in some sub-periods of a given time horizon. The aim is to design a set of least-cost tours, one for each period in the time horizon, that satisfy the service requirements. We refer to this problem as the periodic rural postman problem with irregular services (PRPPIS).
Some practical applications of the problem can be found in road maintenance operations and road network surveillance. In order to solve the PRPPIS, we propose a mathematical model and a branch-and-cut algorithm. In the solution framework, constraints ensuring connectivity and other valid inequalities are identified by using specific separation procedures. Some valid inequalities consider the particular nature of the PRPPIS. We show the effectiveness of the solution approach through an extensive experimental phase.

Online user: 1 RSS Feed