On the Hierarchical Chinese Postman Problem with linear ordered classes

On the Hierarchical Chinese Postman Problem with linear ordered classes

0.00 Avg rating0 Votes
Article ID: iaor20063670
Country: Netherlands
Volume: 169
Issue: 1
Start Page Number: 41
End Page Number: 52
Publication Date: Feb 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: postman problem
Abstract:

The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn4) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity.

Reviews

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