6.4.14 Multiroute Chinese Postman Problem

Just as in the case of node covering, multiroute edge-covering problems are very meaningful and applicable in the urban environment. Urban areas are obviously subdivided on a routine basis into smaller districts that can be covered by a single mailman or refuse-collection truck or parking-meter reader or snowplowing truck. This districting aspect is an integral part of the multiroute Chinese postman problem. This problem is usually referred to as the constrained Chinese postman problem (CCPP), since the need to subdivide an area into many routes arises due to some constraint(s), such as the maximum distance that a mailman can cover walking during a normal day or the maximum weight or volume of solid waste that a refuse collection truck can carry or, very often, other limits on some measures of workload that have been agreed on in a labor contract.

The CCPP has not been investigated extensively to date, but practical approaches to it--in the context of the delivery of urban services--have been suggested for both undirected [STRI 70] and directed [BELT 74] networks. Because of the relative ease with which the single-tour Chinese postman problem can be solved, the "route first, cluster second" strategy seems to be the favored one in this case: a giant tour is first found and then divided into m subtours, where m is the number of available vehicles. However, with no "best way" available for breaking up the giant tour into shorter subtours, this approach depends to a large extent on the ability and experience of the analyst. In fact, the approach described below for an undirected network [STRI 70] is most effective when carried out manually with the assistance of a good map.

The key to the success of the approach is to subdivide the graph G', on which the large, single tour is drawn (see Section 6.4.4) in such a way as not to create odd-degree nodes on the boundaries between subtours. Since G' has been derived by applying a CP algorithm to the original graph G. G' has no odd-degree nodes. Therefore, all the nodes in the interior of subtours will be even-degree nodes and the partitioning process can create odd-degree nodes only on the boundaries between subtours. To avoid this, it is important to draw continuous boundaries for each subtour, so that an even number of edges is incident on each node. The following describes informally a possible heuristic approach:

Constrained Chinese Postman "Algorithm" (Algorithm G.9)

STEP	1:	Using a CP algorithm, create an Eulerian graph from the given network whose edges are to be covered.
STEP	2:	Sketch out roughly the boundaries of the m subtours in accordance with the given constraints on tour lengths, vehicle capacities, and so on.
STEP	3:	Carefully draw a continuous boundary for each subtour so that an even number of edges is incident to every node.

It is clear that the procedure above does not really describe an algorithm in the strict sense but rather outlines a procedure for obtaining a good solution to the CCPP.

Example 14: Tour of the Mailman, Revisited

Consider again the mailman,s problem that we used in an earlier example (Figure 6.12). The modified graph G' which was found by applying our CP algorithm for the solution of the single tour was shown in Figure 6.18 and is copied in Figure 6.34. It is a network with no nodes of odd degree and with total edge length equal to 3,830 distance units.

Suppose now that an upper limit of 1,500 distance units is placed on the length of a mailman's tour. We then attempt to subdivide the single 3,830-unit tour into three approximately equal tours, each of which satisfies the 1,500-unit limit. (Alternatively, it might have been specified that the district in question must be covered by three mailmen.)

On Figure 6.34 the rough outlines of three approximately equal-length tours are sketched in accordance with Step 2 of the CCPP algorithm. Note that these outlines may overlap since they serve only as an aid in defining the approximate physical boundaries of the subtours. In Step 3 the three subtours are designed in detail with continuous boundaries to ensure both the existence of an Eulerian tour and an increase in the total distance covered, which is as small as possible. The three subtours shown in Figure 6.35 are 1,210, 1,300, and 1,320 units long. Their total length in this particular case turns out to be exactly equal to the length of the single tour from which they were derived.

Two disadvantages of the approach that we just illustrated are readily apparent. First, some trial-and-error work may be required before a set of feasible tours is obtained. This is due to the fact that the subdivision of the tour is initially made by inspection alone. Second, the algorithm above does