A branch and cut for the Hierarchical Mixed Rural Postman Problem
1 : University of Valencia, Dept. of Statistics and Operational Research
2 : Department of Quantitative Methods [Brescia]
University of Brescia, Department of Quantitative Methods -
Italy
3 : UNIVERSIDAD POLITECNICA DE VALENCIA
The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into subsets that have to be serviced in a hierarchical order. The problem generalizes the Rural Postman Problem and thus is NP-hard. In this talk we present a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than one hour for instances with up to 999 nodes, 694
arcs, 1984 edges and 4 hierarchies.
| Subject : | : | Abstracts |
| Topics | : | Exact methods |
| PDF version | : |  PDF version |
