Shi, Leyuan; Ólafsson, Sigurdur; Sun, Ning New parallel randomized algorithms for the traveling salesman problem. (English) Zbl 0940.90063 Comput. Oper. Res. 26, No. 4, 371-394 (1999). 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. Cited in 6 Documents MSC: 90B99 Operations research and management science 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut Keywords:optimization; randomized algorithm; parallel algorithm; traveling salesman problem PDFBibTeX XMLCite \textit{L. Shi} et al., Comput. Oper. Res. 26, No. 4, 371--394 (1999; Zbl 0940.90063) Full Text: DOI