6.5 Solving the CPP on a city map It has been pointed out that good solutions to urban Chinese postman problems can usually be found quite easily, even for large networks, if a good map is available.

The map of Figure P6.5 involves about 50 nodes and 90 arcs. It is based on a test problem due to P. Authier (University of Sherbrooke, Canada). There are 38 odd-degree nodes in the network (i.e., more than 10²¹ alternative matchings)! Solve the CPP for this network using Algorithm 6.5 and finding a matching of odd-degree nodes by inspection (plus trial and error). Make a photocopy of the map and indicate (by doubling lines in red pencil or in ink) the street segments that must be traversed twice in your solution. (A tour is required; distances are in tens of feet.)

What is the total distance that will be traversed twice in your solution ? (In the optimal solution the answer is 8,360 feet, including the length of dead-end street-- which must be traversed twice anyway.)