New parallel randomized algorithms for the traveling salesman problem

We recently developed a new randomized optimization framework, the Nested Partitions (NP) method. This approach uses partitioning, global random sampling, and local search heuristics to create a Markov chain that has global optima as its absorbing states. This new method combines global and local search in a natural way and it is highly matched to emerging massively parallel processing capabilities. In this paper, we apply the NP method to the Travelling Salesman Problem. Preliminary numerical results show that the NP method generates high-quality solutions compared to well-known heuristic methods, and that it can be a very promising alternative for finding a solution to the TSP.