Solvable cases of the k-person Chinese postman problem

W.l. Pearn*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

Given a network, the well-known Chinese Postman Problem (CPP) is to find a shortest postman tour traversing each arc of the network at least once and returning to the depot where the postman started. The CPP is NP-complete in general, but is polynomial-time solvable if the network is totally undirected, totally directed, mixed but even, windy with symmetric cycles, and windy but Eulerian. The k-person Chinese Postman Problem (k-CPP) is a multiple-vehicle extension of the CPP, which has many real-world applications. The intent of this paper is to generalize some of the above cited results to the k-CPP.

Original languageEnglish
Pages (from-to)241-244
Number of pages4
JournalOperations Research Letters
Volume16
Issue number4
DOIs
StatePublished - 1 Jan 1994

Keywords

  • Chinese postman problem

Fingerprint Dive into the research topics of 'Solvable cases of the k-person Chinese postman problem'. Together they form a unique fingerprint.

Cite this