The Chinese Postman

The 1997 report

Resolución del problema del cartero chino (CPP) mediante la aplicación de un proceso de branch and bound (Solving the Chinese Postman Problem by a branch-and-bound process). Miquel Monserrat Pons, final-year project at the Escola Tècnica Superior d'Enginyeria Industrial de Barcelona (ETSEIB), supervised by Ramón Companys Pascual, June 1997.

The text refers to an Annex 2 describing the test cases; it is not part of this PDF.

The report is in Spanish. It introduces graphs, matchings and Eulerian circuits, solves the matching step of the Chinese Postman Problem with a purpose-built branch-and-bound search, and studies its behaviour on three districts of Vilanova i la Geltrú. The programs, written in Turbo C, are listed in full in Annex 1. The text is searchable in the viewer below.

Download the PDF (100 pages) Read the 2026 revision

Chapters

The report is written in Spanish; the chapter titles are translated here.

  1. Introduction
  2. Graph theory fundamentals
  3. Matchings
  4. Storing graphs
  5. Eulerian graphs
  6. Combinatorial problems
  7. Branch-and-bound processes
  8. The Chinese Postman Problem (CPP)
  9. Finding the matching
  10. Implementing the algorithm
  11. Behaviour of the algorithm
  12. A heuristic procedure
  13. Conclusions
  14. Bibliography
  15. Budget
  16. Annex 1: program listings

If the viewer does not appear on your device, open the PDF directly.