Wasserstein Distance and the Distributionally Robust TSP
John Gunnar Carlsson, Mehdi Behroozi, Kresimir Mihic
Operations Research · 2018 · Volume 66 · Issue 6
Abstract
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. The online appendix is available at https://doi.org/10.1287/opre.2018.1746 .
Keywords
traveling salesman, distributionally robust optimization, continuous approximation models, districting
Enable JavaScript for citation tools and additional paper interactions.