|
Presume we have a normal Vehicle Routing Problem (VRP) with For example. If we have 2 customers (A, B) and 2 vehicles (1, 2), this is a list of all possible combinations:
So the formula with |
|
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): 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 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 ... ♦
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
\[ \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} \]
\[ \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} \]
\[ \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). 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 ... ♦
|
|
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.) |
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.
@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.