Article ID: | iaor20051961 |
Country: | Netherlands |
Volume: | 155 |
Issue: | 1 |
Start Page Number: | 44 |
End Page Number: | 50 |
Publication Date: | May 2004 |
Journal: | European Journal of Operational Research |
Authors: | Laporte Gilbert, Gendreau Michel, Ghiani Gianpaolo, Cabral Edgar Alberto |
Keywords: | heuristics |
In the undirected hierarchical Chinese postman problem (HCPP), the edges of a graph are partitioned into clusters and must be serviced while respecting a hierarchy, or precedence relation, between clusters. Two objectives are considered: a hierarchical objective and a makespan objective. In this article, a transformation of the HCPP into an equivalent rural postman problem (RPP) is presented. The HCPP is solved optimally, for both objectives, by applying an exact branch-and-cut RPP algorithm to the transformed problem. Two heuristics based on the RPP algorithm are also described and assessed computationally.