The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form of v routes, 1 for each vehicle, each route giving the order of the deliviers the vehicle has to make. The ultimate goal is to find a schedule that minimizes the total route cost. It can be shown that the total amount of possible schedules is $\frac{(n+v-1)!}{(v-1)!}$ which is quite an enormous search space.
However what I would like to know is, given a partial schedule, how large the remaining search space is, or in other words, how much solutions "follow" from it. Let's say for instance that we have to make 3 deliveries, and have 3 vehicles. A partial solution would be:
| Vehicle | Deliveries |
|---------|------------|
| A | 2, 1 |
| B | |
| C | |
We can schedule delivery 3 as the single delivery for B or C, or we can schedule it for A as its first, second, or last delivery. Thus in total there are 5 solutions that "follow" from the partial solution.
Combinatorics has always been my weakness, so I hope someone can help me.