Sufficient graph conditions for VRP

Question

I'm trying to create a program to solve basic Vehicle Routing Problem and, to test it, I would like to write a function to generate valid graphs.

I found in this course (p. 11) that a graph must be strongly connected to be eligible to VRP.

This condition doesn't seems to be sufficient and it might be some constraints missing ( e.g, doesn't take into account the number of vehicles we have).

Do somebody knows what are the graph conditions to allow VRP according to the number of vehicles or where I can find literature about it?

EDIT

The VRP version I want to implement is the classic one without any variation as describes on the Wikipedia page.

We have a network of customers and a depot represented as a graph. We have at our disposition a an N number of vehicles.

The goal is then to find N cycles (vehicle ride) such as:

• Each cycle start and finish at the depot node
• All graph nodes (customers) must be include in a cycle
• Two cycles cannot share nodes or edges

Here's an example with 4 vehicles:

This problem can be see as an extension of the TSP (Travelling Salesman Problem).

Answer 1

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$.

Answer 2

To generate test problems, I would suggest the following.

1. Start by picking (randomly or otherwise) the dimensions of the problem (number of source nodes, number of sink nodes, number of vehicles, number of intermediate nodes in the graph, ...).
2. Assign (random) supplies and demands such that the problem is feasible (supply meets demand).
3. Assignments vehicles and loads to sources and sinks in a feasible manner (meaning you use the correct number of vehicles and respect demand and supply limits).
4. Route those vehicles by assigning a random sequence of intermediate nodes to each vehicle. (Note that we have no arcs yet.) The only constraint on the routes is that no node appears more than once in a route (to avoid cycles), and of course every route starts at a source and ends at a sink. There is no need for the route to be "efficient"; we are just making sure the problem is feasible.
5. Add arcs along the routes generated in the previous step. If the problem is capacitated, set capacities on those arcs to keep the routes feasible.
6. Add additional arcs between random pairs of nodes until you have the number of arcs chosen in the initial step.
7. Randomly add nonnegative or strictly positive costs to each arc.

You now have a feasible VRP with the chosen dimensions and characteristics (single or multiple vehicles, capacitated arcs or not, ...).