A. Baltz, Devdatt Dubhashi, A. Srivastav, Libertad Tansini, S. Werth

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 [1]

Publikationslänkar:

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

Sourcepages:

206-225