Scientific Program > Talks by Speaker > Laganà Demetrio

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.