6.4.9 Multiroute Problems

We have so far discussed only single-tour problems of the edge-covering or node-covering types. Yet most of the time, we have to deal with the routing of not one but several vehicles that must share the task of providing services to some specific populated area. In solid waste collection, for an obvious example, a sanitation department must route many vehicles through many districts into which a city has been subdivided.

Multiroute problems started to attract attention in the mathematical literature only rather recently (most of the available material dates after 1970). The reasons are manifold: (1) the single-route problems (Chinese postman, traveling salesman) are difficult in themselves and have thus attracted most of the attention directed to this area; (2) multiroute problems are more complex (and thus less inviting) than single-route ones; and (3) very powerful computers are needed even for the most straightforward heuristic approaches to these latter problemS--and such computers did not become available until the late 1960's.

It should also be noted at the outset that available algorithms for multirouting are, at this time, almost exclusively heuristic. Generally, they combine single-route algorithms (for node or edge covering, as the case might be) with some method for partitioning the geographical region or the total workload at hand into "smaller" entities which are consistent with some set of problem constraints. In fact, in applications of these algorithms to urban service systems, the overall strategy, as a rule, has been either:

1.	To partition the city (or region), first, into districts and then design optimal single routes within each one of the districts; or
2.	To design, first, a single "grand optimal route" for the whole city and then subdivide the route into a number of subroutes each to be covered by a separate vehicle.

We shall refer to the former as the "cluster first, route second" approach and to the latter as the "route first, cluster second,, approach [BODI 75]. Which is to be preferred depends on the relative efficiency of the algorithms and analytical tools that one can bring to bear on the particular situation at hand. To date, anyway, the "cluster first, route second" approach has been the one most often followed.

In the following sections we shall examine multiroute node-covering problems first since they have attracted a good deal more attention than have multiroute edge-covering problems.