Chinese Postman Problem: A Thorough British Guide to Route Optimisation and Practical Application

The Chinese Postman Problem is a cornerstone of graph theory and operations research, offering a framework for finding the shortest possible route that traverses every edge of a connected network at least once. In the language of logistics, street maintenance and city planning, this problem translates into a question of how to design efficient tours that cover every street or link while minimising distance, time or cost. The elegance of the Chinese Postman Problem lies in its blend of clear mathematical structure and real-world applicability, from postal routes to waste collection and street-sweeping programmes. This guide unpacks the problem in accessible terms, explains the essential algorithms, and highlights practical strategies for implementation in the modern era of data-rich decision making.

What is the Chinese Postman Problem?

The Chinese Postman Problem, named after a classic route inspection concept, asks for the shortest closed route that visits every edge of a connected graph at least once. In practice, imagine a urban network where each street segment is an edge and each intersection is a node. The aim is to traverse every street while returning to the starting point and doing so with the minimum total distance travelled. There are two principal versions to consider: the Undirected Chinese Postman Problem, where streets are bidirectional, and the Directed Chinese Postman Problem, where streets or routes have a fixed direction, such as one-way streets or time-constrained links. The problem is a fundamental instance of arc and edge routing, and its solutions underpin many real-world operations today.

Origin and importance in modern optimisation

The problem has a storied place in mathematical optimisation and algorithm design. While its name points to a historical anecdote, the essential insight is that balancing the traversal requirements with duplication of edges yields a total route that is as short as possible. In urban planning, the Chinese Postman Problem provides a principled method to design maintenance rounds, delivery circuits and cleaning schedules that must cover every segment of a network. It also offers a lens to understand the structure of networks, the impact of highly connected nodes, and how to reuse existing paths to minimise extra mileage. This makes it a valuable tool for civil engineers, municipal authorities and logisticians alike.

Undirected versus Directed: two faces of the same problem

Crucially, the Chinese Postman Problem comes in two flavours that reflect common real-world constraints. The Undirected Chinese Postman Problem applies when every edge can be traversed in either direction and there is no inherent imbalance in traversal requirements. The Directed Chinese Postman Problem (also known as the Route Inspection Problem in some circles) handles networks where edges have fixed directions or asymmetric traversal costs. Each version has its own mathematical character and its own efficient solving strategy, with the undirected case enabling a classic balance of odds and evens, and the directed case requiring a careful balancing of flow along arcs.

Undirected Chinese Postman Problem: core idea

In the undirected case, every edge is traversable in both directions, and the goal becomes to visit every edge at least once and return to the starting vertex with minimum total length. A key observation is that if a connected graph has all vertices of even degree, it already supports an Eulerian circuit – a closed trail that visits every edge exactly once. If odd-degree vertices exist, you must duplicate a set of edges to make the degrees even, thereby creating an Eulerian multigraph. The challenge reduces to selecting the smallest additional distance to pair up odd vertices so that the resulting graph supports an Euler tour. This pairing is solved optimally by a minimum-weight perfect matching on the complete graph of odd vertices, with edge weights given by the shortest path distances between those vertices in the original graph.

Directed Chinese Postman Problem: core idea

In the directed version, each arc is directed and each vertex has an imbalance defined by the difference between its out-degree and in-degree. To obtain a feasible closed tour that covers every arc, you must duplicate certain arcs to balance these inflows and outflows, effectively ensuring that the graph becomes Eulerian in a directed sense. The standard approach converts the balancing task into a minimum-cost circulation or a minimum-cost flow problem. You compute the net imbalances at each vertex, then solve a flow problem that chooses the cheapest way to route additional traversal along existing shortest-path routes, thereby balancing the network. This yields a feasible closed route with minimal added distance or cost.

Mathematical formulation: how the problem is translated into a solvable model

At its heart, the Chinese Postman Problem is an optimisation on a graph. The standard formalism varies slightly between the undirected and directed cases, but the overarching strategy remains consistent: identify the edges that must be traversed, determine what additions are needed to enable a closed traversal, and optimise those additions to minimise total cost.

Undirected formulation: from degrees to matching

Let G = (V, E) be a connected undirected graph with non-negative edge weights representing distances or costs. If all vertex degrees are even, an Euler tour exists, and the solution is simply the sum of all edge weights. If there are 2k odd-degree vertices, you must duplicate a set of k paths that connect pairs of odd vertices so that every vertex ends up with even degree. The optimal choice is to pair up the odd vertices in such a way that the sum of the shortest path distances between paired vertices is minimised. This is a minimum-weight perfect matching problem on a complete graph H formed by the odd vertices, where the weight of an edge in H corresponds to the shortest path distance in G between its endpoints. The classic and widely used method for finding this matching is the blossom algorithm, developed by Edmonds, which runs in polynomial time. After determining the optimal pairing, you add the corresponding shortest paths to G, creating an Eulerian multigraph, and then traverse an Euler circuit to obtain the optimal route.

Directed formulation: balancing flow with minimum cost

For a directed graph D = (V, A) with arc costs, define for each vertex v the imbalance δ(v) = out-degree(v) – in-degree(v). To admit a closed directed route that covers every arc, you must ensure δ(v) = 0 for all v after duplicating certain arcs. The approach is to solve a minimum-cost flow problem: create a bipartite or auxiliary network that connects surplus nodes (where δ(v) > 0) to deficit nodes (where δ(v) < 0) with edge costs equal to the shortest path distances (or direct arc costs, if appropriate) between nodes. The flow that balances all imbalances with minimum total cost corresponds to the set of arcs to duplicate. When this balancing is achieved, the resulting directed multigraph supports a closed Eulerian circuit, which translates into an optimal route for the problem instance.

Algorithms and practical approaches for solving the Chinese Postman Problem

In practice, solving the Chinese Postman Problem efficiently relies on combining graph traversal techniques with classic optimisation subroutines. Here are the essential algorithmic steps for both major variants, with notes on practical considerations and modern tooling.

Undirected CPP: step-by-step algorithm

1) Check connectivity: Confirm that the input network is connected; if not, the problem is not well-posed in its standard form. 2) Compute total edge weight: Sum all edge costs in the network. 3) Identify odd-degree vertices: List all nodes whose degree is odd. 4) Compute pairwise distances: Use an all-pairs shortest-path algorithm (Floyd–Warshall for dense graphs, Dijkstra for sparse graphs) to determine the shortest distance between every pair of odd vertices. 5) Solve minimum-weight perfect matching: Form a complete graph on the odd vertices with edge weights equal to their shortest-path distances, and compute the minimum-weight perfect matching (via the blossom algorithm). 6) Duplicate the corresponding shortest paths: For each matched pair, duplicate the edges along their shortest path in the original graph. 7) Construct an Eulerian circuit: With all degrees even, an Euler cycle exists; find it using Hierholzer’s algorithm. 8) Extract the route: Translate the Euler circuit into a practical route that covers each edge at least once, starting and ending at a chosen point. 9) Optional real-world refinement: Compress or translate repeated edges into practical truck routes, considering turning constraints and time windows.

Directed CPP: step-by-step algorithm

1) Check feasibility: Ensure the network is strongly connected or can be made so with existing arcs and costs. 2) Compute imbalances δ(v) for all vertices. 3) If all δ(v) = 0, the network already supports a directed Euler tour; traverse it. 4) Build a balancing network: For vertices with δ(v) > 0 (surplus of outgoing arcs) and δ(v) < 0 (surplus of incoming arcs), set up a minimum-cost flow problem to route the required extra traversals along shortest paths between these vertices. 5) Solve the min-cost flow: Use a standard min-cost circulation algorithm or network flow solver to obtain the cheapest augmentation that balances all nodes. 6) Duplicate the arcs along the chosen augmenting paths: This yields a balanced directed multigraph. 7) Find a directed Euler tour: Decompose into an Eulerian circuit or circuit decomposition as appropriate. 8) Implement the route: Convert the circuit into a practical itinerary for vehicles, respecting directionality, timing and traffic constraints.

Computational considerations: performance, data and practicality

For most practical networks—urban street networks and utility grids—the undirected Chinese Postman Problem can be solved efficiently for networks with hundreds to thousands of edges using standard polynomial-time subroutines. The key bottlenecks are typically the following: (a) computing all-pairs shortest paths between odd vertices, (b) solving the minimum-weight perfect matching on a potentially sizeable set of odd vertices, and (c) translating the abstract Eulerian circuit into a real-world route that respects constraints such as one-way streets, time windows and vehicle limits. Modern libraries and software environments make these steps feasible in a matter of seconds to minutes for typical municipal scales, while very large networks may require more scalable, custom implementations or heuristics for approximation.

Practical applications: where the Chinese Postman Problem shines

The relevance of the Chinese Postman Problem extends far beyond the postal context. It provides a principled framework for any operation requiring complete coverage of a network at minimum cost, including:

• Municipal street cleaning and sweep routes, ensuring every street is cleaned while minimising total mileage.
• Garbage and recycling collection rounds, especially in dense urban grids with varied street directions.
• Snow ploughing and maintenance rounds, where timely, complete coverage is essential with limited resources.
• Street lighting maintenance and cable inspection tasks that must visit every segment of a network.
• Delivery and service networks that require full network traversal when visiting all links is mandatory.

Variants and related problems worth knowing about

Alongside the classical Chinese Postman Problem, several related problems provide additional modelling flexibility for real-world constraints. Understanding these variants helps practitioners select the right tool for the task at hand.

Rural Postman Problem

The Rural Postman Problem relaxes the requirement to cover every edge in the network by allowing only a subset of edges to be traversed. This is useful when only certain streets or routes require service, such as specific zones, routes to industrial parks, or areas with permission constraints. The challenge is to cover all required edges while minimising travel on optional edges, and it is substantially more complex than the standard CPP in many cases.

Windy Postman Problem

The Windy Postman Problem introduces direction-sensitive costs, where the cost to traverse an edge depends on the direction of travel. This cost asymmetry models real-world scenarios such as traffic patterns, one-way restrictions with variable times, and variable tolls. Solving this variant often requires adaptations of the standard CPP framework to accommodate asymmetrical costs, while still ensuring a feasible closed tour with minimal overall expenditure.

Capacitated and time-constrained variants

In some settings, the problem must respect vehicle capacity limits or time windows for certain streets or services. While this moves the problem away from the pure CPP, hybrid approaches combine CPP foundations with vehicle routing and scheduling techniques. These variants are increasingly common in practice as logistics and municipal services adopt smarter, more responsive planning processes.

A practical guide to solving the Chinese Postman Problem in the field

For practitioners, translating theory into usable routes involves clear steps, careful data management and robust verification. Here is a practical blueprint for teams tackling CPP challenges in the field.

1. Model your network accurately

Capture a reliable, weighted graph where nodes represent intersections or locations, and edges represent street segments or links with their associated traversal costs. Ensure all essential streets are included and that the network is connected. If certain segments are temporarily unavailable (e.g., due to roadworks), model those constraints explicitly and consider updating the problem accordingly or using a dynamic approach.

2. Choose the right variant

Identify whether your network is best described by the undirected CPP, the directed CPP, or one of the variants. The choice determines the appropriate solution method and affects both complexity and practicality. For many city-scale tasks with two-way streets, the undirected CPP offers a robust starting point; for networks with one-way streets or directionally constrained links, the directed CPP is essential.

3. Gather accurate data and compute shortest paths

Accurate edge costs are critical. Compute the shortest-path distances between candidate vertices (odd-degree vertices for the undirected case or imbalance nodes for the directed case). In urban networks, Dijkstra’s algorithm is efficient when using adjacency lists, while Floyd–Warshall is useful for smaller or dense networks. The choice of data structures and algorithms will impact run times significantly.

4. Apply the balancing step optimally

For undirected graphs, solve the minimum-weight perfect matching to pair up odd vertices with minimal additional distance. For directed graphs, solve the minimum-cost flow or circulation problem to balance in- and out-flows. In both cases, you are identifying the precise set of edges to duplicate to enable a closed route that covers every edge once more than necessary.

5. Construct the Euler tour and translate it to a route

Once the augmented graph is Eulerian (for undirected) or Eulerian in the directed sense, compute an Euler circuit. This circuit corresponds to a route that covers every edge with the minimal duplication identified earlier. Convert the circuit into a practical plan, taking into account turning restrictions, vehicle access, and operational constraints such as driver hours, breaks and safety considerations.

6. Validate and refine

Run a validation phase to ensure the route adheres to all constraints and that no edge is unintentionally omitted. Sensible refinements include smoothing transitions, adjusting start points for efficiency, and testing alternate starting vertices to see if small adjustments yield marginal gains. In practice, it is common to iterate once data quality is improved or constraints are tightened.

Case study: a municipal waste collection route in a mid-sized town

Consider a mid-sized town with a connected street network comprising 120 street segments. The task is to design a waste collection tour that visits every street and returns to the depot with minimal extra mileage. The network contains a mix of two-way streets and a handful of directed segments to reflect one-way restrictions. The steps would typically unfold as follows:

• Model the network as a weighted graph, where edge weights reflect traversal distance and one-way restrictions are captured as directed arcs.
• Compute vertex degrees and identify odd vertices in the undirected portion, as well as any imbalances for the directed portion.
• Calculate all-pairs shortest paths among the relevant vertices to determine optimal pairing or balancing costs.
• Apply the appropriate algorithm: minimum-weight perfect matching for the undirected subproblem or a min-cost flow solution for the directed case.
• Duplicate the chosen paths and compute an Euler tour on the augmented graph.
• Translate the Euler circuit into a practical daily plan for waste collection teams, ensuring routes respect driver hours and safety constraints.

In pilot runs, the method typically yields a route that reduces total distance by a meaningful margin compared with naïve traversals that simply follow each street in sequence. The practical payoff is not only shorter travel but also smoother operations, predictable schedules and better utilisation of staff time.

Common challenges and how to address them

While the Chinese Postman Problem offers a powerful framework, real-world applications often present additional challenges. Here are common issues and practical remedies.

• Data quality: Inaccurate street lengths or missing segments undermine the solution. Regular data validation and integration with GIS systems mitigate this risk.
• Time windows and dynamic constraints: If certain streets are only accessible at certain times or within certain windows, consider a dynamic or rolling CPP approach, or hybrid methods that blend CPP with scheduling techniques.
• One-way streets and traffic patterns: The directed CPP naturally accommodates directionality, but real-world changes such as roadworks or temporary restrictions require frequent updates and re-optimisation.
• Scalability: For very large networks, exact solvers can become computationally heavy. In such cases, well-crafted heuristics and decomposition strategies can yield near-optimal results within practical timeframes.
• localisation and practicalities: The purely mathematical solution may not reflect practical constraints such as turning radii or loading dock times. It is essential to incorporate constraints and perform post-optimisation adjustments for operations.

Technology and software: turning theory into action

Several well-established software tools and libraries support Chinese Postman Problem solutions, often through modular graph and optimisation components. Highlights include:

• Network analysis libraries (e.g., NetworkX in Python) that implement Euler tours, min-cost flow and matching algorithms.
• Specialised optimisation suites with min-cost flow and matching capabilities, such as commercial solvers that handle large-scale instances efficiently.
• Geospatial integration with GIS platforms to ensure spatial accuracy of network representations and to visualise routes effectively.
• Customisable routing engines that combine CPP-based balancing with vehicle routing problem (VRP) features for schedules, capacities and drivers.

Case for ongoing research and future developments

Academic and practical interest in the Chinese Postman Problem continues to grow, driven by smart cities, autonomous vehicles and real-time routing needs. Current research topics include:

• Approximation algorithms and heuristics for very large networks where exact solutions are impractical.
• Dynamic and stochastic variants that adapt to changing traffic conditions or demands.
• Hybrid models combining CPP with Rural Postman or Windy Postman features to reflect real urban systems more accurately.
• Parallel computing strategies to accelerate solution times on large metropolitan networks.

Key takeaways: mastering the Chinese Postman Problem

Whether you are dealing with street cleaning, waste collection or infrastructure inspection, the Chinese Postman Problem offers a principled method to design efficient, comprehensive routes. The core ideas are simple in essence yet powerful in practice: determine which routes must be traversed, balance the network by duplicating carefully chosen paths, and then extract an Eulerian tour that fulfils the requirement with minimal added distance. The undirected and directed versions each have a well-developed theoretical backbone and widely used algorithms, enabling practitioners to deploy optimised solutions in diverse real-world settings. By understanding the problem structure and leveraging modern computational tools, organisations can realise meaningful savings, improved reliability and better service outcomes for the communities they serve.

Final thoughts: why the Chinese Postman Problem remains relevant

The appeal of the Chinese Postman Problem lies in its blend of mathematical clarity and practical utility. It provides a rigorous foundation for full network coverage with minimal redundancy, a principle that resonates across public services and commercial logistics. As cities grow and networks become more complex, the ability to systematically plan routes that cover every required edge while minimising distance becomes not just a theoretical curiosity but a tangible asset. In short, the Chinese Postman Problem is not merely an academic artefact; it is a practical toolkit for smarter, more efficient network traversal in the modern world.