Wasserstein Distance and the Distributionally Robust TSP
Wasserstein Distance and the Distributionally Robust TSP
复制标题
DOI：
10.1287/opre.2018.1746
复制
发表时间：
2018-11-01
影响因子：
2.7
通讯作者：
Mihic, Kresimir
中科院分区：
文献类型：
--
作者：
Carlsson, John Gunnar;Behroozi, Mehdi;Mihic, Kresimir
最近的鲁棒随机旅行商问题和车辆路径问题的研究已经使用了许多不同的方法来描述模糊区域，包括采取凸组合的观察到的需求向量或施加约束的时刻的空间需求分布。在运输部门之外使用的一种方法是使用描述两个概率分布之间的距离函数的统计度量。出于多车辆路由的分区问题，我们考虑一个分布鲁棒版本的欧几里德旅行推销员问题，在该问题中，我们计算最坏情况下的空间分布的需求对所有分布的Wasserstein距离所观察到的需求分布是有界的。这个约束使我们能够避免使用其他程序时出现的常见高估，例如固定质心和协方差矩阵。数值实验证实，我们的新方法是有用的，当有限的数据时，用于决策支持工具划分为车队的服务区的领土。
Recent research on the robust and stochastic traveling salesman problem and the vehicle routing problem has used many different approaches for describing the region of ambiguity including taking convex combinations of observed demand vectors or imposing constraints on the moments of the spatial demand distribution. One approach that has been used outside the transportation sector is the use of statistical metrics that describe a distance function between two probability distributions. Motivated by a districting problem in multivehicle routing, we consider a distributionally robust version of the Euclidean traveling salesman problem in which we compute the worst-case spatial distribution of demand against all distributions whose Wasserstein distance to an observed demand distribution is bounded from above. This constraint allows us to circumvent common overestimation that arises when other procedures are used, such as fixing the center of mass and the covariance matrix of the distribution. Numerical experiments confirm that our new approach is useful when used in a decision support tool for dividing a territory into service districts for a fleet of vehicles when limited data are available.