We give the first probabilistic analysis of the Multiple Depot Vehicle Routing Problem(MDVRP) where we are given k depots and n customers in [0,1]~2. The optimization problem is to find a collection of disjoint TSP tours with minimum total length such that all customers are served and each tour contains exactly one depot (not all depots have to be used). In the random setting the depots as well as the customers are given by independently and uniformly distributed random variables in [0,1]~2. We show that the asymptotic tour length is α_k n~(1/2) for some constant α_k depending on the number of depots. If k = o(n), α_k is the constant α(TSP) of the TSP problem. Beardwood, Halton, and Ham-mersley(1959) showed 0.62 ≤ α(TSP) ≤ 0.93. For k = λn, λ > 0, one expects that with increasing A the MDVRP tour length decreases. We prove that this is true exhibiting lower and upper bounds on α_k, which decay as fast as (1+ λ)~(-1/2). A heuristics which first clusters customers around the nearest depot and then does the TSP routing is shown to find an optimal tour almost surely.
展开▼
