Draft:Chinese Postman Problem
 | Draft article not currently submitted for review.
This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit the draft click on the "Edit" tab at the top of the window. To be accepted, a draft should:
It is strongly discouraged to write about yourself, your business or employer. If you do so, you must declare it. This draft has not been edited in over six months and qualifies to be deleted per CSD G13.
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
Last edited by WalkingRadiance (talk | contribs) 2 years ago. (Update) |
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.
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)