Number of paths in asymmetric capacitated vehicle routing problem

Question

This seems like a natural question, but I was not able to find an answer. My question is this. Consider a CVRP where $n$ customers have to be serviced by $m$ vehicles on any given day. All the vehicles have the same maximum capacity $J$, and all depart from a warehouse depot $W$ to make the deliveries. Each customer gets a single package so that $n$ packages are delivered, where, $\forall$ package weights $w_i (i = 1,\ldots,n$), $ 0 < w_i \leq J$.

My question is that how many paths are possible in this case? For TSP, I understand that it is $(n-1)!/2$. But, in CVRP, due to capacity constraints, there are many infeasible paths (since it will exceed the maximum weight). So, is there a way to find only the feasible paths? I am looking for an analytical formula (or some bounds?) rather than a way to enumerate all the paths (though an efficient way to do this would also be interesting to know).

Answer 1

I am pretty sure, this is not the best way to tackle such a problem, specifically from the computational complexity point of view, but at least it might be represented as an effort to solve small-scale problems. As you mentioned:

• All the vehicles have the same maximum capacity $J$
• Each customer gets a single package so that n packages are delivered...

I have tried to use a bin packing problem to calculate an estimate on the required vehicles as a lower bound and whose related routes. Please, be aware that, generalized assignment problem is another option to achieve the feasible routes when there are different capacities for vehicles w.r.t the route cost.

As a simple example, suppose there are $10$ customers with the following demands:

  item1   26, item2   57, item3   18, item4    8,
  item5   45, item6   12, item7   22, item8   29,
  item9    5, item10  11

And $5$ vehicles with the capacity of $60$.

Actually, there are around $41$ different states(!!!) to assign the required demands to the vehicles to achieve feasible solutions. If the problem size changes from $10$ customers to $20$, the solving time increases exponentially and takes an age to solve such a tiny problem. Definitely, this is a case to show some feasible solution but NOT the optimal solution, as the problem has not considered the traveling cost. I hope it would be helpful.