On the Hierarchical Chinese Postman Problem with linear ordered classes

P. Korteweg, T. Volgenant

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)
4 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)41-52
JournalEuropean Journal of Operational Research
Volume169
Issue number1
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'On the Hierarchical Chinese Postman Problem with linear ordered classes'. Together they form a unique fingerprint.

  • Cite this