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: