Оптимізація розв’язку задачі комівояжера методом парних заміщень

Authors:

Р. Базилевич, Б. Кузь

Національний університет «Львівська політехніка», кафедра програмного забезпечення

Досліджено алгоритм для оптимізації розв’язання задачі комівояжера. Зменшення довжини шляху забезпечується обміном ребер, які відповідають умові оптимізації.

The algorithm for TSP solution optimization is investigated. Tour minimization is performed by swapping of edges, which satisfy optimization criteria.

задача комівояжера

комбінаторна оптимізація

NP-важкі задачі

Bazylevych R., Kutelmakh R., Prasad B., Bazylevych L. Decomposition and Scanning Optimization algorithms for TSP // Proceedings of the International Conference on Theoretical and Mathematical Foundations of Computer Science, Orlando, 2008, pp. 110-116.
Concorde: http://www.tsp.gatech.edu/concorde.html.
Delaunay B. Sur la sphère vide // Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, No 7, 1934, pp. 793–800.
DIMACS TSP Challenge Results: http://www.akira.ruc.dk/~keld/research/LKH/DIMACS_results.html.
Helsgaun K. An Effective Implementation of k-Opt Moves for the Lin–Kernighan TSP Heuristic // Datalogiske Skrifter, Writings on Computer Science, No. 109, Roskilde University, 2006.
TSP Art Instances: http://www.tsp.gatech.edu/data/art/index.html.
Базилевич Р. П., Кутельмах Р. К., Кузь Б. О. Алгоритм розв’язання задачі комівояжера великої розмірності методом «тора» // Вісник Нац. ун- ту «Львівська політехніка». – 2010. – № 686. – С. 179–182.