Draft:Chinese Postman Problem
| Submission declined on 8 October 2022 by Felix QW (talk). Thank you for your submission, but the subject of this article already exists in Wikipedia. You can find it and improve it at Route inspection problem instead.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
This draft has not been edited in over six months and qualifies to be deleted per CSD G13. Declined by Felix QW 2 years ago. Last edited by Felix QW 2 years ago. Reviewer: Inform author.
|  |
Comment: The topic is already covered in greater detail at Route inspection problem, which Chinese postman problem redirects to. Felix QW (talk) 09:11, 8 October 2022 (UTC)
The Chinese Postman problem (CPP) relates to a graph G with vertices V and edges E. The graph G should be finite, undirected, and connected. The edges are often assigned a finite real-valued weight that is not negative. The Chinese Postman Problem has been proven to be reducible in polynomial time, in constrast to the Mixed Chinese Postman Problem (MCPP) which is NP complete.[1]
The CPP forms the basis of the field of arc routing compared to more complex cases including the MCPP, the directed chinese postman problem DCPP, the windy postman problem WPP, the rural postman problem RPP, and the hierarchical chinese postman problem HCPP.[2] The CPP has many important real-world applications from school bus routing to mail and postal delivery routing to meter reading planning to police car patrolling, street-sweeping, snow-plowing, salt-spreading, newspaper delivery, and delivering packages.[2]
The CPP requires finding a way to traverse every edge in the graph at least once with minimal cost. To do this, the graph can be augmented until it is Eulerian by duplicating edges between odd degree vertices. The optimal tour will then traverse the augmented Eulerian graph. This can be computed using the Hungarian algorithm. The CPP is very important in operations research.
See Also
- Arc routing
- Mixed Chinese postman problem
- NP-completeness
- Large scale capacitated arc routing probem
- Eulerian path
Further Reading
- A. Corberan, Arc Routing:Problems, Methods and Applications, SIAM, 2015.
References
- ^ Haouari, Mohumed (March 2002). "Arc Routing: Theory, Solutions and Applications Moshe Dror (editor) Kluwer Academic Publishers, 2000, ISBN 0-792-37898-9". IIE Transactions. 34 (3): 331–332. doi:10.1080/07408170208936917. ISSN 0740-817X.
- ^ a b Hrsg., Corberán, Ángel (2015). Arc routing : problems, methods, and applications. SIAM. ISBN 978-1-61197-366-2. OCLC 904346272.
{{cite book}}: CS1 maint: multiple names: authors list (link)