6.4.10 Multiroute Node Covering

It is helpful, at this stage, to present a classification of node-covering problems. While the classical traveling salesman problem is a well-defined one, there is a large number of possible extensions and variations on it, and the names of the different types of problems often become confusing. The basic descriptors of a node-covering problem are three:

1.	The number of vehicles (salesmen).
2.	The number of tour origins (which are also the eventual destinations).
3.	The existence of constraints on such items as individual vehicle (salesman) capacity, the maximum length of a tour, and so on.

In general, problems in which no constraints such as those mentioned under (3) are specified are known as "salesman" problems. Thus, the classical TSP is a problem in which a minimum tour must be designed for a single salesman-vehicle using a single origin-destination with no capacity or tour-length constraints.

What is known as the m-traveling salesmen problem (m-TSP), on the other hand, involves the design of a prespecified number, m, of distinct tours that collectively visit each of the demand points at least once while using a single common origin-destination. The objective is to minimize the total distance covered in the m tours.

When there are constraints of the vehicle-capacity or maximum-distance types, we have a vehicle routing problem (VRP). In these cases the (single or many) origins-destinations are usually referred to as depots. In VRP's both the required number of vehicles and their routes are, in general, unknown, and the objective is to minimize an objective function that represents some aspect of or the total cost of the system. In some versions, however, the number of vehicles is specified in advance (chosen so that it is expected tosatisfy the constraints of the situation) and the objective is to design feasible tours of minimum total length.

Having already discussed the TSP, we shall now briefly examine:

1. The m-TSP problem.

2. The single-depot VRP problem.

3. The multidepot VRP problem.

Our choice is dictated by the applicability of these three problems to urban service systems and by the fact that these also seem to be the most often studied variations of multiroute node-covering problems.