Solving the hierarchical Chinese postman problem as a rural postman problem

Solving the hierarchical Chinese postman problem as a rural postman problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.