Return to 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 and VRP, I understand that it is $2^n$. 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).

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

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 and VRP, I understand that it is $2^n$. 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?

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 and VRP, I understand that it is $2^n$. 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).

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 and VRP, I understand that it is $2^n$. But, in CVRP, due to capacity constraints, there are many infeasible paths (since it will exceed the maximum wight). So, is there a way to find only the feasible paths?

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 and VRP, I understand that it is $2^n$. 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?