Back

G-2001-10

Solving the Hierarchical Chinese Postman Problem as a Rural Postman Problem

, , , and

BibTeX reference

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.

, 11 pages

This cahier was revised in August 2002

Research Axis

Research application

Publication

Solving the hierarchical chinese postman problem as a rural postman problem
, , , and
European Journal of Operational Research, 155, 40–50, 2004 BibTeX reference