6.4.4 Solving the Chinese Postman's Problem
We now return to the Chinese postman,s problem and solve the problem of finding the minimum length, edge-covering tour of a graph G(N, A) with no restrictions placed on G other than that it be connected and undirected.
The solution procedure consists of adding, in a judicious manner, artificial edges, parallel to the existing ones, to the original graph G to obtain a new graph G1(N, A1) on which an Euler tour can be drawn. This means that the addition of the artificial edges should be such as to turn all odd-degree nodes on G into even-degree nodes on G1. Moreover, this should be accomplished by selecting that combination of artificial edges which results in the minimumlength tour at the end. The addition of an artificial edge in parallel to an existing one in the original network simply means that the existing edge will have to be traversed twice in the final Chinese postman,s tour.
An important observation is helpful at this point.
Lemma: The number of nodes of odd degree in an undirected graph G is always even.
We now describe the solution approach in general terms:
Chinese Postman Algorithm--Undirected Graph (Algorithm 6.5)
A pairwise matching of a subset N' N of nodes of a graph G is a pairing of all the nodes in N' (assuming that the number of nodes in N' is even). A minimum-length pairwise matching of the nodes in An is then a matching such that the total length of the shortest paths between the paired nodes is minimum.
In Algorithm 6.5, we have concentrated exclusively on the shortest paths between pairs of odd-degree nodes. That this should be so can be seen as follows. Were a supposedly optimal pairwise matching between odd-degree nodes to contain a path, P1, between any given pair of nodes that is not the shortest path, P. between these two nodes, the solution could be improved by simply substituting P for P1 in the drawing of the artificial edges, since the length of P is, by definition, smaller than the length of P1.
In reviewing Algorithm 6.5, we can see that its only difficulty lies in
Step 2, since Steps 1, 3, and 4 are all very simple. For Step 2, however,
the number of possible pairwise matching combinations increases very quickly
with the number of odd-degree nodes. Some thought will show that with m odd
degree nodes in G (remember that m is always even), there are
possible distinct pairwise matching combinations. Thus, for m = 4, there are I · 3 = 3 possible combinations (as we have already seen in our last example), for m = 10,945 combinations, and for m = 20, about 655 million combinations.
Fortunately, an efficient, but quite complicated algorithm for minimum length matchings on undirected graphs is now available. This algorithm is based on the theory of matching on graphs that has been developed in recent years primarily by J. Edmonds. The interested reader is referred to [EDMO 73] or to [CHRI 753 for its details. Here we only note that the algorithm is an exact one (i.e., finds the optimum matchings) and efficient computer-implemented versions solve the problem in time proportional to n3, where n is the number of nodes in the graph under consideration. The algorithm not only finds the minimum-length matchings but also identifies the shortest path associated with each pair. It follows that in the worst case Algorithm 6.5 is also O(n3).
Manual approach to matching. When Edmonds' minimum-length matching algorithm is used in Step 2 of Algorithm 6.5, an optimum solution to the Chinese postman,s problem is obtained. Experience has shown, however, that whenever the Chinese postman problem is posed in a geographical context (and this of course is the case in urban service systems applications), then excellent--in the sense of being very close to the optimum--manual solutions can be obtained practically by inspection with the aid of a good map. The map can be used to perform all four steps of Algorithm 6.5, and the only step where one risks deviating from the optimum solution is in finding the minimum-length matching in Step 2.
The manual search for an approximately minimum-length matching of odd-degree nodes in Step 2 is greatly aided by the following key observation:
In a minimum-length matching of the odd-degree nodes, no two shortest paths in the matching can have any edges in common.
To see this, consider Figure 6.16, assuming that nodes a, b, c, and d are
all of odd degree and that the shortest paths between, say, the pairs of
nodes a-c and Kd have edge (p, q) in common. Then it is impossible that the
minimum-length pairwise matching contain the pairs a-c and Fd, since it would
then be possible to obtain a better (shorter) matching by coupling
together nodes a and b into one pair and nodes c and d into another. This latter matching will reduce the sum of the shortest path lengths by at least 2 (p, q) units.
Other observations (of a somewhat more complicated nature) have also been made (see [STRI 70]) with regard to finding good approximate solutions to minimum-length matching problems without using a matching algorithm. It has been the authors' experience that, whenever good maps of urban areas are available, it takes only a limited amount of practice with some examples before one develops the ability to find virtually by inspection excellent solutions to matching problems (by taking advantage of the foregoing observations).