An algorithm for the hierarchical Chinese postman problem

The Hierarchical Chinese Postman Problem (HCPP) is a variant of the classic al Chinese Postman Problem, in which the arcs are partitioned into clusters and a precedence relation is defined on clusters. Practical applications o f the HCPP include snow and ice control on the roads and determination of o ptimal torch paths in flame cutting. The HCPP is NP-hard in general, but po lynomial-time solvable if the precedence relation is linear and each cluste r is connected. For this case an exact algorithm, requiring a lower computa tional effort than previous procedures, is described. (C) 2000 Elsevier Sci ence B.V. All rights reserved.