2

This seems like a natural question, but I was not able to find an answer. My question is this. Consider a capacitated vehicle routing problem (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 traveling salesperson problem, I understand that it is $(n-1)!/2$. Is there a way to find an analytical solution for the vehicle routing problem (VRP) and CVRP?

The VRP is the same as the problem above but without any weight (capacity) restrictions. 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).

Edit: one idea for finding the answer for VRP is presented here: How to calculate the number of solutions for the vehicle routing problem (VRP)?.

arunisnowhere
  • 33
  • Most of us do not attend your specific class or read your specific textbook; it would be good to elaborate on the meaning of your acronyms, and how you've been taught to solve these problems – FShrike Dec 22 '21 at 10:22
  • TSP and VRP are extremely well-known acronyms and problems in combinatorial optimization and have been so since the 1950s or so. Nevertheless, I have now edited the question to expand the acronyms. I dont see the point of mentioning "how I have been taught to solve these problems", when I am requesting a solution or a hint. This is a weird (and unhelpful) comment. – arunisnowhere Dec 22 '21 at 13:46

0 Answers0