On the Hierarchical Chinese Postman Problem with linear ordered classes

P. Korteweg, T. Volgenant

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

25 Citaten (Scopus)
12 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)41-52
TijdschriftEuropean Journal of Operational Research
Volume169
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 2006

Vingerafdruk

Duik in de onderzoeksthema's van 'On the Hierarchical Chinese Postman Problem with linear ordered classes'. Samen vormen ze een unieke vingerafdruk.

Citeer dit