The shortest walk that covers every street
A postman has to walk down every street of a district and return to the office. Some streets must be walked twice; the question is which ones, so that the extra distance is as small as possible.
This site revisits a 1997 final-year engineering project on this problem, the Chinese Postman Problem, with today's implementations, and follows the paths it left open: streets that need no service, several postmen, vehicles with a capacity. Read both reports, run the solver in your browser, or use the code.
The problem
A route that walks every street exactly once and returns to its start exists only when every junction joins an even number of streets: Euler proved this for the seven bridges of Königsberg, in a paper written in 1735 and published in 1741. Real districts have junctions with an odd number of streets, so some streets must be walked again. The Chinese mathematician Kwan Mei-Ko posed the question in 1960: which streets should be repeated so that the extra distance is as small as possible?
The answer pairs up the odd junctions so that the total distance between paired junctions is minimal, repeats the streets along those connections, and then walks the result. Mail delivery, refuse collection, snow ploughing and street sweeping all build on this problem, usually with added limits such as vehicle capacity or working shifts.
Nearly thirty years later
The method of 1997 is unchanged in outline; each stage now uses what is available today (the polynomial algorithms were already published in 1997; their implementations reach much further), and the paths the project left open are followed up, each with its measured distance from the best known solution.
| Problem | 1997 | 2026 |
|---|---|---|
| Every street, two-way | Exact up to about 20 odd junctions on a 150 MHz Pentium, then a time-limited search | Exact in polynomial time: 12,000 odd junctions in two minutes |
| One-way streets | Proposed as future work | Exact |
| One-way and two-way together | Not in scope | Exact for towns of up to 400 junctions and most up to 1,600; beyond that, within about 1% of a proven bound |
| Only some streets to serve | Proposed: a dearer first pass | Exact on every benchmark network; the quick method is within 0.7% on average |
| Several postmen | Noted: a shift limits the work | Optimal in 61 of 62 cases where the optimum is known |
| Vehicles with a capacity | — | Within 6% of the best published solutions (median) |
| Platform | Turbo C on MS-DOS | Python, open source, also in the browser |
Details, charts and every result file: 2026 report, chapters 7 to 10, and Extensions.
Read and run
- 2026 report
The revised report: matching, Eulerian circuits, one-way and mixed streets, experiments on 92 benchmark networks.
- Extensions
The paths left open in 1997, followed up: streets that need service only once, several postmen, vehicles with a capacity. How hard each one is, and how close the answers come to the optimum.
- Solve a network
Pick an example, upload a file in the 1997 format, or choose an area of OpenStreetMap, and watch the postman's tour, or several postmen sharing the streets. The solver runs in your browser.
- 1997 report
The original final-year project, ETSEIB, supervised by Ramón Companys Pascual. Readable online and downloadable.
- Code and data
Python package, tests, benchmark instances and every result file, under the MIT licence.
How to cite
If you use the code, the results or the report, please cite:
Monserrat Pons, M. (2026). The Chinese Postman Problem — 2026 revision (version 2026.3.0). Software and report. https://github.com/miquelmp/chinese-postman-problem
The original project:
Monserrat Pons, M. (1997). Resolución del problema del cartero chino (CPP) mediante la aplicación de un proceso de branch and bound. Final-year project, ETSEIB, Universitat Politècnica de Catalunya. Supervisor: R. Companys Pascual.
GitHub shows the same reference in APA and BibTeX under “Cite this repository”, from the file CITATION.cff.