Abstract

We propose and analyze new policies for the traveling salesman problem in a dynamic and stochastic environment (DTSP). The DTSP is defined as follows: demands for service arrive in time according to a Poisson process, are independent and uniformly distributed in a Euclidean region of bounded area, and the time service is zero; the objective is to reduce the time the
server takes to visit to all the present demands for the first time. We start by analyzing the nearest neighbour (NN) policy since it has the best performance for the dynamic vehicle routing problem (DTRP), a closely related problem to the DTSP. We next introduce the random start policy whose efficiency is similar to that of the NN, and we observe that when the random start policy is delayed, it behaves like the DTRP with the NN policy. Finally, we introduce the partitioning policy, and show that, relative to other policies, it reduces the expected time that demands are swept from the region for the first time.