1. SCSIT
  2. All Volumes and Issues
  3. Volume 751, 2013
  4. Оптимізація розв’язку задачі комівояжера методом парних заміщень

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

SCSIT.
2013;
Volume 751
: pp. 392 - 395
Authors: 

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

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

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

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

traveling salesman problem
combinatorial optimization
NP-hard problems
  1. 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.
  2. Concorde: http://www.tsp.gatech.edu/concorde.html.
  3. Delaunay B. Sur la sphère vide // Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, No 7, 1934, pp. 793–800.
  4. DIMACS TSP Challenge Results: http://www.akira.ruc.dk/~keld/research/LKH/DIMACS_results.html.
  5. 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.
  6. TSP Art Instances: http://www.tsp.gatech.edu/data/art/index.html.
  7. Базилевич Р. П., Кутельмах Р. К., Кузь Б. О. Алгоритм розв’язання задачі комівояжера великої розмірності методом «тора» // Вісник Нац. ун- ту «Львівська політехніка». – 2010. – № 686. – С. 179–182.