Euclidean Traveling Salesman Tours through Stochastic Neighborhoods

摘要

We consider the problem of planning a shortest tour through a collection of neighborhoods in the plane, where each neighborhood is a disk whose radius is an i.i.d. random variable drawn from a known probability distribution. This is a stochastic version of the classic traveling salesman problem with neighborhoods (TSPN). Planning such tours under uncertainty, a fundamental problem in its own right, is motivated by a number of applications including the following data gathering problem in sensor networks: a robotic data mule needs to collect data from n geographically distributed wireless sensor nodes whose communication range r is a random variable influenced by environmental factors. We propose a polynomial-time algorithm that achieves a factor O(log log n) approximation of the expected length of an optimal tour. In data mule applications, the problem has an additional complexity: the radii of the disks are only revealed when the robot reaches the disk boundary (transmission success). For this online version of the stochastic TSPN, we achieve an approximation ratio of O(log n). In the special case, where the disks with their mean radii are disjoint, we achieve an O(1) approximation even for the online case.