How to calculate the number of solutions for the vehicle routing problem (VRP)? The vehicle routing problem is a combinatorical optimization problem, looking for the optimal solution to serve a number of customers by a number of vehicles, starting from a central depot. Each customer has to be visited (For a more detailed description please have a look at the literature)
If the number of possible solutions for the (symmetric) travelling salesman problem can be calculated with (n−1)!/2, how about the number of solutions for the VRP?
Thanks in advance.
 A: I stumbled on the same question while doing some related research on VRPs. And, despite rummaging through the literature for some time using the limited knowhow of a measly PhD student, I found nothing. It might as well be reported somewhere, but at least I was not able to find the answer. However, I managed to experimentally came up with a formula that gives the right number of solutions to small symmetric CVRPs.
A VRP reminder: a valid VRP solution is one where each vehicle leaves from a depot and returns there, every customer is visited exactly once, and there are no subtours (tours that do not start and end from the depot). Smallest number of vehicles is 1 (TSP) and largest $n$, where $n$ is the number of customers.
When I stumbled on this, being a programmer first, mathematician second, I coded the fastest VRP solution enumerator I could come up with that is capable of checking 5M solutions per second on a Dell i5 laptop. It spat out a sequence
$$1, 2, 7, 34, 206, 1486, 12412, 117692, 1248004, 14625856, \ldots$$
which, according to oeis.org sequence #A011800, is the  

Number of labeled forests of n nodes each component of which is a path

It does not seem to far fetched that this count in some way connected to CVRP.  Unfortunately, the formula generating that sequence is nowhere as pretty as the $n!/2$ for TSP. The number of solutions for a VRP with a symmetric distances is:
$$
{ \small \begin{alignat}{3}
& \left|R_\text{CVRP}\right|=\sum_{k=0}^{n} \left| s_1(n,k) \right| b(k), \quad \text{where} & \label{eq:solutions} \\
& s_1(n,m) = \sum_{k=0}^{n-m} \binom{n-1+k}{n-m+k} \binom{2n-m}{n-m-k} s_2(n-m+k,k) & \label{eq:s1} \\
& s_2(n,m) = \sum_{k=0}^{m} \frac{\binom{m}{k} k^n}{m! (-1)^{(k-m)}} & \label{eq:s2} \\
& b(k) = \sum_{j=0}^{k}\sum_{i=0}^{j} \frac{(-1)^i (k-2 i)^k \binom{j}{i}}{2^j j!}, \quad b(0)=1 &
\end{alignat}
}$$
I have verified that the sequence works at least up to VRP $n=13$. I have asked help from a mathematician friend of mine to take a look, but as answering this question does not help me in completing my PhD, I have been ignoring this stray research path for some time now. A more rigorous approach would be to check if the formula and it's components ($s_1(n,m)$, $s_2(n,m)$ and $b(n)$) could be derived from the basic combinatorical properties of the VRP solutions.
References


*

*The OEIS sequence page : https://oeis.org/A011800

*J. Rasku, T. Karkkainen and P. Hotokka. Solution Space Visualization as a Tool for Vehicle Routing Algorithm Development, Proceedings of FORS40, 2013.

*J. Rasku. C++ CVRP Solution Generator. Avalable in Github yorak/cvrp-solution-generator.

