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:

  1. 1AB - 2
  2. 1BA - 2
  3. 1A - 2B
  4. 1B - 2A
  5. 1 - 2AB
  6. 1 - 2BA

So the formula with n=2 and v=2 should return 6.

asked 25 Mar '14, 08:08

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
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 ... ♦

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

link

answered 25 Mar '14, 12:54

jfpuget's gravatar image

jfpuget
2.5k310
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 ... ♦

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

link

answered 25 Mar '14, 10:51

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 26 Mar '14, 09:47

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 ♦

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

link

answered 25 Mar '14, 10:12

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 25 Mar '14, 10:14

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

link

answered 26 Mar '14, 04:57

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×10

Asked: 25 Mar '14, 08:08

Seen: 19,833 times

Last updated: 26 Mar '14, 11:52

OR-Exchange! Your site for questions, answers, and announcements about operations research.