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


F4 Routing 3
October 2, 2015  5:00 PM
Salón de actos

Other papers in the same session

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.