An algorithm for the hierarchical Chinese postman problem

The Hierarchical Chinese Postman Problem (HCPP) is a variant of the classical Chinese Postman Problem, in which the arcs are partitioned into clusters and a precedence relation is defined on clusters. Practical applications of the HCPP include snow and ice control on the roads and determination of optimal torch paths in flame cutting. The HCPP is NP-hard in general, but polynomial-time solvable if the precedence relation is linear and each cluster is connected. For this case an exact algorithm, requiring a lower computational effort than previous procedures, is described.