Overview
The Chinese postman problem is a classic problem in graph theory and combinatorial optimization. Also called the route inspection problem, it asks for the shortest closed walk (a circuit) that traverses every edge of a graph at least once. The motivating image is a postal carrier or street sweeper who must travel every street and return to the starting point while minimizing total distance or cost; variants change whether streets are directed, have asymmetric costs, or only a subset must be served.
Key concepts and properties
An Eulerian circuit — a closed trail that uses every edge exactly once — is an ideal solution when it exists. A connected undirected graph has an Eulerian circuit precisely when every vertex has even degree. If the graph is already Eulerian, the Chinese postman solution is simply any Euler tour. When some vertices have odd degree, edges must be repeated to make all degrees even, increasing the total length.
Algorithm outline for undirected graphs
The standard polynomial-time method for an undirected weighted graph proceeds roughly as follows:
- Identify all vertices of odd degree.
- Compute shortest-path distances between every pair of odd vertices (using Dijkstra or all-pairs algorithms).
- Find a minimum-weight perfect matching among the odd vertices where edge weights are the shortest-path distances; duplicate the corresponding original edges along those shortest paths.
- With all degrees now even, form an Eulerian multigraph and extract an Euler circuit that is a shortest closed route visiting each original edge at least once.
This reduction uses a minimum-weight perfect matching subroutine (for which Edmonds' blossom algorithm is a well-known solution), so the overall approach runs in polynomial time for undirected graphs.
Directed, mixed and other variants
For directed graphs the problem is often solved by balancing in- and out-degrees via min-cost flow or circulation techniques and then finding an Euler tour of the balanced directed multigraph. Some variants are much harder: the windy postman problem (edge costs depend on traversal direction) and the rural postman problem (only a specified subset of edges must be covered) are NP-hard in general. Mixed graphs that include both directed and undirected edges likewise admit formulations that are computationally more difficult than the undirected case.
History, terminology and applications
The problem is commonly attributed to a paper from the early 1960s often credited to a Chinese researcher (frequently cited as Mei-Ku Kwan or a similar romanization). The English name "Chinese postman problem" was popularized later; one early adopter of the name was Alan Goldman of the U.S. National Bureau of Standards. The term "route inspection" is also widely used.
Practical uses and notable facts
Applications extend beyond postal delivery: planning street sweeping, snow plowing, garbage collection, meter reading and maintenance routing are typical uses. The method of pairing odd vertices by shortest paths is a key insight that converts an edge-covering objective into a matching problem on a smaller set of vertices. For further background on related graph theory concepts see Eulerian path and introductions to route inspection techniques; for application-oriented discussions see materials on postal routing and logistics optimization.
While the undirected Chinese postman problem has efficient exact algorithms, many real-world constraints (time windows, vehicle capacities, asymmetric costs, or partial coverage requirements) lead to harder problems that require heuristics or integer programming. Researchers continue to study specialized formulations and faster implementations for large-scale networks.