DATA-STRUCTURES FOR TRAVELING SALESMEN

The choice of data structure for tour representation plays a critical role in the efficiency of local improvement heuristics for the traveli ng salesman problem. The tour data structure must permit queries about the relative order of cities in the current tour and must allow secti ons of the tour to be reversed. The traditional array-based representa tion of a tour permits the relative order of cities to be determined i n small constant time, but requires worst-case Omega(N) time (where N is the number of cities) to implement a reversal, which renders it imp ractical for large instances. This paper considers alternative tour da ta structures, examining them from both a theoretical and experimental point of view. The first alternative we consider is a data structure based on splay trees, where all queries and updates take amortized tim e O(log N). We show that this is close to the best possible, because i n the cell probe model of computation any data structure must take wor st-case amortized time Omega(log N/log log N) per operation. Empirical ly (for random Euclidean instances), splay trees overcome their large constant-factor overhead and catch up to arrays by N = 10,000, pulling ahead by a factor of 4-10 (depending on machine) when N = 100,000. Tw o alternative tree-based data structures do even better in this range, however. Although both are asymptotically inferior to the splay tree representations, the latter does not appear to pull even with them unt il N similar to 1,000,000. (C) 1995 Academic Press, Inc.