What's the cheapest round trip?

The Route of the Postman

The (Chinese) Postman Problem, also called Postman Tour or Route Inspection Problem, is a famous problem in Graph Theory: The postman's job is to deliver all of the town's mail using the shortest route possible. In order to do so, he (or she) must pass each street once and then return to the origin.

We model this problem using a directed graph. Edges and nodes represent streets and intersections, respectively. The length of a street is represented by the weight of the corresponding edge. By using directed edges, it's possible to also account for one-way-streets etc in the graph.

On these pages, we present the Chinese Postman Algorithm for directed graphs. This method finds the shortest directed path (sometimes called "dipath") such that each edge is used at least once.

Outgoing-Graph.
Each node is labeled with the difference of its Out- and In-Degrees. Nodes with a difference different from 0 are called "imbalanced". Knoten mit der Differenz ungleich 0 sind unbalanciert.

On the Left: The bipartite Matching Graph with all imbalanced nodes. Here, we can determine between which nodes we can insert new paths. On the Right: The graph after inserting the new paths.

Matching-Edge.
The matching edges determine, where new paths must be inserted.

Newly Inserted Edge.
The dotted line represents edges that are traversed multiple times.

Euler Tour.
The different colors label the different subtours taken by the Hierholzer method.

The Postman Problem

The standard example for this problem is a postman who needs to traverse all streets of a town and then return to the origin. It's his goal to walk the minimum distance possible. We can model this problem using a graph: A (directed) path (or dipath) is a sequence of edges where each edge's origin node is the ending node of the previous edge. A path is called closed if it ultimately terminates in its origin node (the origin node of the first edge).

A closed path is called Euler Tour, if it contains all edges of the graph exactly once. Thus, the postman problem consists of finding a closed path (Round Tour) in the graph, such that all edges are traversed at least once and the sum of edge weights in the path (Cost of the Round Tour) is minimal.

The Main Idea of the Algorithm

First of all, since any nodes without incoming or outgoing edges do not influence the problem, we can assume that no such edges exist. The problem has a solution if and only if the graph is strongly connected (each node can be reached from every other node) and contains no negative cycles (closed paths with negative total edge weight). If the graph is not strongly connected, then no round tour can exist; if there is a negative cycle somewhere, then the optimal cost will be infinitely small. The problem can be reduced to finding an Euler Tour in the graph. If an Euler Tour exists, it must be the optimal tour, since each edge is traversed exactly once. Otherwise, one or more edges will have to be visited multiple times. This situation can be modeled by adding additional Edges to the graph that represent edges used multiple times (and have the same weight as the original edge). Then the round trip using the edge multiple times will have the same cost as the corresponding Euler Tour in the new graph. Now, we are only left with the problem of identifying the edges that will be used multiple times in the optimal solution.

The number of incoming edges at a vertex is called the In-Degree of that vertex, the number of outgoing ones its Out-Degree. A theorem in graph theory states that a graph has an Euler Tour if and only if the In- and Out-degrees are the same for all vertices of the graph. Therefore, it is sufficient to add additional paths to the graph, such that In- and Out-Degrees match for all nodes after inserting the new paths. The sum of the edge weights of these paths should be minimal. We will specify which paths to add in the Matching-Phase of the algorithm.

After making sure that the graph contains an Euler Tour, we still have to find it. To do so, we may use any appropriate algorithm, such as the Hierholzer method. The cost of the optimal round trip then is exactly the sum of all edge weights in the Euler Tour.

Shortest Paths

We need to insert paths from those nodes with too few outgoing edges to those nodes with too few incoming edges. Since we aim to minimize our costs, these should be shortest paths. One way to find those shortest paths is to use the algorithm of Floyd-Warshall. The Floyd-Warshall Algorithm happens to be especially useful here, as it simultaneously finds the shortest paths between all pairs of vertices. We will then use the costs of the shortest paths in the Matching Phase in order to determine the optimal set of shortest paths to use.

Matching

By inserting additional paths, we aim to balance In- and Out-degrees for all vertices of the graph, as only then an Euler Tour will exist. Let \(\delta_v\) be the difference of out- and in-degrees of node v. We call all nodes v with \(\delta_v \neq 0 \) imbalanced. In order to determine which paths to add, we need a mapping from nodes with negative \(\delta_v\) to those with positive \(\delta_v\). Here \(\delta_v\) specifies the number of new paths that need to start or end in v. Adding a path will increase \(\delta_o\) by 1 in its origin o, and decrease \(\delta_d\) by 1 in its destination d.

The weight of the additional paths must be minimized. In order to reach this goal, we can create a new bipartite graph that contains all imbalanced nodes. We partition the imbalanced vertices into two sets: those with negative and those with positive \(\delta_v\)). \(\delta_v\) determines, how often the vertex v will appear in the new bipartite graph. As an example, a vertex v with \(\delta_v=3\) will have exactly 3 copies in this Matching-graph. For sake of readability, each imbalanced node has only been drawn once in the visualization of the algorithm. Therefore the vertices in the visualization of the matching graph may lie on more than one matching edge (as determined by \(\delta_v\) ).

The weight of an edge in the matching graph represents the length of the shortest path from its origin node (that with negative \(\delta_v\)) to its destination node (that with positive difference). The sum of all in- and out-degrees of any graph will always be balanced. Thus the same is true for the sums of positive and negative \(\delta_v\)s. We therefore end up with a complete bipartite graph. Now, we can use an algorithm for finding optimal weighted matchings (such as the Hungarian Method). This will then yield the optimal matching and we can proceed to add the additional paths. The edges of these paths then represent the edges which will appear multiple times in the optimal Round Trip.

Euler Tour

After adding these additional paths, the in- and out-degrees of all vertices in the graph will be balanced. Then a Euler Tour must exist in the graph and it can be found using the Hierholzer method. The cost of the optimal round trip is given by the sum of all edge weights of this Euler Tour.

What do you want to do next?

What's the (Pseudo-)Code of the algorithm?

Input:  Weighted, directed graph G=(V,E)
Output: Length of a shortest round trip that contains all edges (if such a solution exists.)

        BEGIN
        1. Check for solvability
        2. Find imbalanced nodes
        3. Determine additional paths
        4. Insert additional paths
        5. Determine the Euler Tour
        END

How fast is the algorithm?

How can we prove that the result will always be correct?

Where can I find more information on graph algorithms??

A last remark about this page's content, goal and citations