• Home
  • Probabilistic analysis for a multiple depot vehicle routing problem

Probabilistic analysis for a multiple depot vehicle routing problem

Sourcetitle: 
Random structures & algorithms
Year of publication: 
2007
PublicationType: 
Scientific journal article - peer reviewed

We give a probabilistic analysis of the Multiple Depot Vehicle Routing Problem (MDVRP) where k depots and it customers are given by i.i.d. random variables in [0, 1](d), d >= 2. The tour length divided by n((d-1)/d) tends to a integral([0,1]d) f(x)((d-1)/d) dx, where,f is the density of the absolutely continuous part of the law of the random variables giving the depots and customers and where the constant alpha depends on the number of depots. If k = o(n), alpha is the constant of the TSP problem. For k = lambda n, lambda > 0, we prove lower and upper bounds on alpha, which decrease as fast as (1 + lambda)(-1/d).

http://dx.doi.org/10.1002/rsa.20156

Sourcepages: 
206-225
To the top

Page updated: 2013-02-07 14:51

Send as email
Print page
Show as pdf

X
Loading