New parallel randomized algorithms for the traveling salesman problem

We recently developed a new randomized optimization framework, the Nested P artitions (NP) method. This approach uses partitioning, global random sampl ing, and local search heuristics to create a Markov chain that has global o ptima as its absorbing states. This new method combines global and local se arch in a natural way and it is highly matched to emerging massively parall el processing capabilities. In this paper, we apply the NP method to the Tr avelling Salesman Problem. Preliminary numerical results show that the NP m ethod generates high-quality solutions compared to well-known heuristic met hods, and that it can be a very promising alternative for finding a solutio n to the TSP. (C) 1999 Elsevier Science Ltd. All rights reserved.