Track: Operations Research

Abstract

Recent research on the robust and stochastic travelling salesman problem
and the vehicle routing problem has seen many different approaches
for describing the region of uncertainty, such as 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.
In this paper, we consider a distributionally robust version of the
Euclidean travelling 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.