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.
Best Answer
You are right that the condition of being strongly connected is not sufficient for the problem as you've stated it. There is no nice characterization of a sufficient condition, because:
On the other hand, if you can solve VRP for complete directed graphs, you can use that to test the condition for arbitrary graphs. Just add edges with cost $\infty$ (or any extremely high constant $C$) wherever an edge does not already exist, and then see if there is a solution with finite cost (or with cost less than $C$).
Actually, the statement about being strongly connected is in a slightly different context. The condition that cycles can't share nodes or edges is artificial in many applications; often, what we actually want is $N$ closed walks that start and end at the depot that cover every node.
This problem reduces to the original problem if we take the transitive closure: for every two nodes $u,v$, add an edge $(u,v)$ whose cost is the total cost of the minimum-cost $u,v$-path. Now we can assume without loss of generality that our closed walks are actually cycles that don't have any nodes in common (except for the depot). A cycle in the transitive closure can always skip a vertex that's redundant without increasing in cost.
This new problem has a solution exactly when the original graph is strongly connected: