Wasserstein Distance and the Distributionally Robust TSP

• 成果类型: Article
• 署名作者: Carlsson, John Gunnar; Behroozi, Mehdi; Mihic, Kresimir
• 署名单位: University of Southern California; Northeastern University; Oracle
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1746
• 发表日期: 2018
• 页码: 1603-1624
• 关键词: vehicle-routing problem; optimization; uncertainty

摘要

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.