Probabilistic analysis for a multiple depot vehicle routing problem
Probabilistic analysis for a multiple depot vehicle routing problem
复制标题
多站点车辆路径问题的概率分析
DOI：
10.1002/rsa.20156
复制
发表时间：
2005
影响因子：
1
通讯作者：
Sören Werth
中科院分区：
文献类型：
--
作者：
Andreas Baltz;Devdatt P. Dubhashi;Anand Srivastav;Libertad Tansini;Sören Werth
本文给出了一个多仓库车辆路径问题的概率分析，其中k个仓库和n个客户由独立同分布给出。[0，1]d中的随机变量，d ≥ 2。行程长度除以n（d−1）/d趋于α <$[0，1] df（x）（d−1）/d dx，其中f是给出站点和客户的随机变量定律的绝对连续部分的密度，常数α取决于站点的数量。如果k = o（n），则α是TSP问题的常数。对于k = λn，λ > 0，我们证明了α的上下界，它们以（1 + λ）−1/d的速度递减。随机结构算法，2007
We give a probabilistic analysis of the Multiple Depot Vehicle Routing Problem (MDVRP) where k depots and n 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 α∫ [0,1] df(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 α depends on the number of depots. If k = o(n), α is the constant of the TSP problem. For k = λn, λ > 0, we prove lower and upper bounds on α, which decrease as fast as (1 + λ)−1/d.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007