THE RELATIVE PERFORMANCE OF HEURISTICS FOR THE DYNAMIC TRAVELING SALESMAN PROBLEM
Amelia Regan, J Hermann, Xin Lu · 2002
In this working paper the authors investigate the convergence of an asymptotically optimal algorithm for the M/G/1 queueing model with switchover costs, when applied to the related dynamic traveling salesman problem (TSP). In this paper they present simulation based analysis of heuristics for the dynamic traveling salesman problem in which a mobile server provides service to customers whose positions are known. Service requests are generated according to a Poisson process which is uniform across customer locations. In the general case they assume that the mean service time is known and its variance is bounded. Service time is independent of customer location. They first examine a special case of the problem in which the optimal TSP tour and minimum spanning tree involves only links of equal length and then discuss the case for a general graph. The goal of this work is to examine the relative performance of algorithms intended to minimize the average waiting time of each customer. They show that the simple cyclic polling algorithm in which customers are visited in order of the optimal TSP tour has surprising robust performance.