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

(loglog

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.