×

New parallel randomized algorithms for the traveling salesman problem. (English) Zbl 0940.90063

Summary: 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.

MSC:

90B99 Operations research and management science
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI