M. Colombi, Á. Corberán, R. Mansini, I. Plana, J. M. Sanchis Llopis
In this work, we analyze the problem of finding a minimum cost tour starting and ending at the depot while servicing all the required arcs and edges in the specified hierarchical order. We call this problem Hierarchical Mixed Rural Postman Problem (HMRPP). The HMRPP generalizes known problems such as the Hierarchical Chinese Postman Problem and the Rural Postman Problem.
The problem finds application in different contexts where constraints may be imposed on the order in which clusters of streets (edges or arcs) have to be visited. For example, in snow plowing, main streets have to be cleared before secondary streets and, in turn, secondary streets should be cleaned before residential ones.
To solve the problem, we propose a new mathematical formulation and present both a heuristic approach and an exact one. The heuristic approach is a Matheuristic the results of which are then refined by a Tabu Search algorithm. The exact approach consists in a branch-and-cut algorithm based on various classes of valid inequalities.
We test these methods on an extensive set of benchmark instances and present the results obtained.
Keywords: Hierarchy, Mixed Graph, Rural Postman Problem
Scheduled
F4 Routing 3
October 2, 2015 5:00 PM
Salón de actos
