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:
- For one vehicle, the condition is that the graph has a Hamiltonian cycle, which is of course an NP-complete problem;
- For $N$ vehicles, the condition is also NP-complete to test: it reduces to the Hamiltonian cycle. Given a graph $G$, create a depot and then add $N-1$ short cycles out of the depot, using entirely separate nodes. Out of the $N$ vehicles, $N-1$ must cover those new cycles, which means the last vehicle must be a Hamiltonian cycle of the original graph.
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:
- The graph must be strongly connected, because any solution gives us a way to find a path from any node $u$ to any other node $v$. (Follow a closed walk in the solution from $u$ to the depot, then follow a closed walk in the solution from the depot to $v$.)
- If the graph is strongly connected, then its transitive closure is the complete directed graph, which certainly has a solution for any $N$.
First of all, $\frac12 (n-1)!$ is counting closed tours that start somewhere, visit all the towns, and return to the start.
A permutation does not give us $n$ of these closed tours. It gives us only one. The permutation $(a_1, a_2, \dots, a_n)$ corresponds to starting at town $a_1$, going to town $a_2$, then to town $a_3$, and so on to $a_n$, then returning to $a_1$.
We divide by $2n$ because each possible closed tour is given by $2n$ different permutations. The permutations $(a_1, a_2, \dots, a_n)$ and $(a_2, a_3, \dots, a_n, a_1)$ and $(a_3, a_4, \dots, a_1, a_2)$ and so on take the same paths, just starting at a different point. (That's the factor of $n$.) The permutations $(a_1, a_2, \dots, a_n)$ and $(a_n, a_{n-1}, \dots, a_1)$ take the same paths, just in reverse order. (That's the factor of $2$.)
So the number of possible closed tours is actually $n!/(2n)$ or $\frac12 (n-1)!$.
Best Answer
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
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