Algorithms for the Windy Postman Problem

W.l. Pearn*, Lin Li Mao Lin Li

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

The Windy Postman Problem (WPP), is an interesting generalization of the classical Chinese Postman Problem (CPP), which has many real-world applications. The WPP has been shown to be NP-complete; therefore, it is difficult to solve the problem exactly. For this reason, heuristic solution procedures have been proposed to solve the problem approximately. In this paper, we first review the existing solution procedures, then introduce two new algorithms to solve the WPP near-optimally. Computational results show that the new algorithms outperform the existing solution procedures on some special class of networks.

Original languageEnglish
Pages (from-to)641-651
Number of pages11
JournalComputers and Operations Research
Volume21
Issue number6
DOIs
StatePublished - 1 Jan 1994

Fingerprint Dive into the research topics of 'Algorithms for the Windy Postman Problem'. Together they form a unique fingerprint.

Cite this