I am referring to the text Vehicle Routing Problems by Toth and Vigo Link.
While describing the Capacitated Vehicle routing problem(VRP), a VRP with the only constraint being on vehicle capacities, the authors say the following
"Several variants of the basic versions of CVRP have been considered in the literature. First, when the number K of available vehicles is greater than $K_{min}$, it may be possible to leave some vehicles unused, and thus at most K circuits must be determined. In this case, fixed costs are often associated with the use of the vehicles, and the additional objective requiring minimization of the number of circuits (i.e., of the vehicles used) is added to that requiring minimization of the total cost. Another frequently considered variant arises when the available vehicles are different, i.e., have different capacities $C_k$, k = 1, . . . , K. Finally, routes containing only one customer may not be allowed."
In the above discussion $K_{min}$ refers to the minimum number of vehicles required, a quantity dependant on the graph. A circuit is a path taken by a vehicle which starts and ends at a home depot and lastly there is a fixed pre-determined cost associated with each edge.
My question is with regard to the final condition about one customer routes not being allowed.
Why is this the case? Surely if all routes are 1 customer routes (assuming an edge between a home depot and all nodes) then we aren't really solving anything, but a few routes being 1 customer ones may be part of an optimal solution.
Answer Posted by OP
It is likely that the condition is just a convention and the problem minus this condition is also of equal interest.
Thanks to @DavidM. for pointing this out.
Edit
A simple formulation of the problem involves an indicator variable $x_{ij} \in \{0,1\}$ for every edge in the Graph of customers.
$x_{ij} = 1$ if the edge $(i,j)$ lies in any of the optimal routes and $x_{ij} = 0$ otherwise
However, in the symmetric version of the problem, the cost $c_{ij}$ associated with each edge $(i,j)$ is the same both ways, i.e. $c_{ij} = c_{ji} \quad \forall \, \text{edges }(i,j)$
Hence, to avoid redundancy, using only $x_{ij}: \, i <j$ is necessary
In the symmetric version of the problem, if single customer routes were allowed then (following the notation present in the link) the range of the variable $x_{0j}$ would have to be $\{0,1,2\}$ (instead of the usual binary nature). To account for the case when a vehicle goes from the home depot to a single customer and then comes back to the depot.
This has to be the case since the cost associated with the edge $(0,j)$ will have to appear twice.