# What is the size of the search space of a vehicle routing problem?

 4 Presume we have a normal Vehicle Routing Problem (VRP) with n customers (= locations) and v vehicles. Each vehicle has 1 route. In how many different ways can we assign those n customers to the v routes? What's the formula? For example. If we have 2 customers (A, B) and 2 vehicles (1, 2), this is a list of all possible combinations: 1AB - 2 1BA - 2 1A - 2B 1B - 2A 1 - 2AB 1 - 2BA So the formula with n=2 and v=2 should return 6. asked 25 Mar '14, 08:08 Geoffrey De ... ♦ 3.6k●3●27●64 accept rate: 6% If your performance measure is to minimize the total traveled distance and the distance matrix is symmetric, then 1AB will the same as 1BA (i.e., reverse permutations yield similar costs). Therefore, you would have four distinct solutions. I guess you should define your underlying assumptions more clearly before moving on to finding the formula. (25 Mar '14, 08:52) Ehsan ♦ @Ehsan I am interested in both formula's (including and excluding of those duplicate symmetric routes). But mainly including, because in time windowed cases they are not duplicates. (25 Mar '14, 09:03) Geoffrey De ... ♦

 6 I'd go for (n + v -1)!/(v-1)! Indeed, one can represent the routes by listing all customers for the first vehicle, in the order in which they are visited, then a separator, then the customers for the second vehicle, and so on. This sequence is built from n customers and v-1 separators. For the example in the question, the sequences are (- stands for the separator): AB- BA- A-B B-A -AB -BA  There are (n + v -1)! such sequences. However, permuting the separators does not change the actual assignment of customers to vehicles, hence we must divide by (v - 1)! For the example, n = v = 2, and the number of sequences is 3!/1! = 6 answered 25 Mar '14, 12:54 jfpuget 2.5k●3●10 accept rate: 8% Nice reasoning. This implies: n customers and 1 vehicle (=TSP): n! 2 customers and 2 vehicles: 6 3 customers and 2 vehicles: 24 4 customers and 2 vehicles: 120 ... 2 customers and 3 vehicles: 12 3 customers and 3 vehicles: 60 4 customers and 3 vehicles: 360 5 customers and 3 vehicles: 2520 ... @fbahr Do your baby step methods come to the same result? (25 Mar '14, 13:53) Geoffrey De ... ♦ 1 for v=2 it does, both methods say it is (n+1)! (25 Mar '14, 15:01) jfpuget for v=3 it also does, both methods say it's (n+2)!/2 (26 Mar '14, 02:52) Geoffrey De ... ♦
 3 Some "baby steps" (towards a closed-form expression [over n and v]): for v=2: $\begin{array}{l} \sum_{i=0}^n {n \choose i} i! (n-i)! = \sum_{i=0}^n n!\\ = n! ( \sum_{i=0}^n 1 ) = n!(n+1) = (n+1)! \end{array}$ for v=3: $\begin{array}{l} \sum_{i=0}^n \sum_{j=0}^{n-i} {n \choose i} i! {n-i \choose j} j! (n-i-j)! = \sum_{i=0}^n \sum_{j=0}^{n-i} n!\\ = n! ( \sum_{i=0}^n \sum_{j=0}^{n-i} 1 ) = n! ( \sum_{i=0}^n (n-i+1) )\\ = \frac{1}{2}n!(n+1)(n+2) = \frac{1}{2}(n+2)! \end{array}$ for v=4: $\begin{array}{l} \sum_{i=0}^n \sum_{j=0}^{n-i} \sum_{k=0}^{n-i-j} {n \choose i} i! {n-i \choose j} j! {n-i-j \choose k} k! (n-i-j-k)! = \sum_{i=0}^n \sum_{j=0}^{n-i} \sum_{k=0}^{n-i-j} n!\\ = n! ( \sum_{i=0}^n \sum_{j=0}^{n-i} \sum_{k=0}^{n-i-j} 1 ) = n! ( \sum_{i=0}^n \sum_{j=0}^{n-i} (n-i-j+1) ) = n! ( \sum_{i=0}^n \frac{1}{2}(n-i+1)(n-i+2) )\\ = \frac{1}{2}\frac{1}{3}n!(n+1)(n+2)(n+3) = \frac{1}{6}(n+3)! \end{array}$ ...and, finally, "we" [~royal] are getting somewhere – with $\sum_{i_1=0}^n ~~\cdots \sum_{i_{v-1}=0}^{n-\cdots-i_{v-2}} 1 = \frac{1}{(v-1)!} \prod_{j=1}^{v-1} (n+j)$ $\Rightarrow \frac{1}{(v-1)!} \prod_{j=1}^{v-1} (n+j) * n! ~=~ \frac{(n+v-1)!}{(v-1)!}$ yields exactly the expression @jfpuget came up with (just by looking at the problem). Since I obviously lack his intuition (or experience ...or: both), it took me "some" more iterations, though. The basic principle is rather straightforward: if vehicle 1 serves $$i$$ customers, vehicle 2 can serve up to $$(n-i)$$ customers, and so on (the last vehicle has to pick all customers which haven't yet been scheduled). Then, vehicle 1 can choose from $$i!$$ different routes to visit its customers, vehicle 2 from [up to] $$(n-i)!$$, and so on. Multiplying the numbers of different routes for each vehicle gives the number of possible configurations for a fixed setting. If vehicle is assigned to pick $$i$$ customers, there a $${n \choose i}$$ ways to do so (, $${n-i \choose j}$$ ways for vehicle 2, and so on). Again, multiply (number of homogenous settings). And finally, sum over all possible (different) settings (= number of customers per vehicles). answered 25 Mar '14, 10:51 fbahr ♦ 4.6k●7●16 accept rate: 13% If 2 experts come to the same conclusion in a totally different manner, that raises the confidence in both their answers :) (26 Mar '14, 02:57) Geoffrey De ... ♦ @Geoffrey: I think I've basically demonstrated that my mathematical analysis skills have gotten a bit rusty over the years. (26 Mar '14, 09:39) fbahr ♦
 1 Some rough lower and upper bounds: Lower bound: The number of TSP tours is on the order of $$n!$$. This provides a lower bound of $$\Omega (n!)$$. Upper bound: You can think of the collection of VRP routes as being performed by a single vehicle in a particular order. This will give rise to an order of the cities. There are $$n \choose v$$ ways of dividing a particular order into v routes. This gives an upper bound of $$O( n! {n \choose v})$$. If the number of vehicles is a fixed constant, then the factorial term dominates and the number of solutions is $$\Theta^* ( n! )$$. (The star notation ignores polynomial factors.) answered 25 Mar '14, 10:12 Austin Buchanan 1.3k●3●13 accept rate: 42%
 1 If the vehicules are identical, i.e. if they are interchangeable, then you may want to divide further by v! In that case we are computing the number of ways of visiting the n customers with at most v routes: (n + v -1)!/v!(v-1)! answered 26 Mar '14, 04:57 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: