Алгоритм приєднання часткових розв’язків у підмножинах при декомпозиції задачі комівояжера

2009;
: сс. 3 – 12
Автори: 
Базилевич Р.П., Кутельмах Р.К.

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

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

1. Reinelt, Gerhard (1994), The Traveling Salesman: Computational Solutions for TSP Applications. Lecture Notes in Computer Science 840, Springer–Verlag, Berlin. 2. Reinelt, Gerhard (1992), Fast heuristics for large geometric traveling salesman problems. ORSA Journal on computing, 4:206-217 3. David S. Johnson and Lyle A. McGeoch. Experimental Analysis of Heuristics for the STSP. In Gutin and Punnen, editors, The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, 2002. 4. Lin S. and Kernighan B. W. An effective heuristic algorithm for the Traveling salesman problern. Operations Research, 21:498–516. 1973. 5. Lin S. Computer solutions of the travelling salesman problem. Bell System Technical Journal 44, pages 2245–2269, 1965. 6. K. Helsgaun, “An effective implementation of the Lin–Kernighan Traveling Salesman Heuristic”, 2002. 7. Reinelt, Gerhard(1991) TSPLIB – A traveling salesman problem library, ORSA Journal on Computing 3, 376–384. 8. http://www.research.att.com/~dsj/chtsp/ 9. Applegate D., Bixby R.E., Chvátal V. and Cook W. On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume ICM III:645–656, 1998. 10. Applegate D., Cook W., Rohe A.. Chained Lin–Kernighan for large traveling salesman problems. INFORMS J. Computing, to appear. 11. Applegate D., Bixby R.E., Chvátal V. and Cook W. Findong tours in the TSP.1998. 12. Applegate D., Bixby R. E., Chvátal V., and Cook W. Findong cuts in the TSP.1995 13. http://www.tsp.gatech.edu/concorde.html. 14. Neto D. Efficient cluster compensation for Lin–Kernighan Heuristics. PhD thesis, Department of Computer Science, University of Toronto, 1999. 15. Laporte G., Potvin J-Y., Quilleret F. A Tabu Search using Genetic Diversification for the Clustered Traveling Salesman Problem // Journal of Heuristics, Vol 2 (3), p. 187-200, 1996. 16. Базилевич Р. П., Кутельмах Р. К. Алгоритми динамічного формування моделі робочого поля для задачі комівояжера з кластерним розподілом точок // Вісник Нац. ун-ту “Львівська політехніка”, Львів, 2006. 17. Базилевич Р. П., Ремі Дюпа, Кутельмах Р. К. Використання алгоритмів локальної оптимізації для розв’язування задачі комівояжера з кластерним розподілом точок // Вісник Нац. ун-ту “Львівська політехніка”. – Львів, 2006. 18. Bazylevych R., Dupas R, Kutelmakh R. Scanning-area algorithms for clustered TSP // Proceedings of International conference “Comp. science and Information Technologies”, Lviv, Polytechnic University, 2006, pp. 148–152. 19. Bazylevych R., Prasad B., Kutelmakh R., L.Bazylevych. Decomposition and Scanning Optimization Algorithms for TSP, Proceedings of the International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS- 08), pp. 110–116, Florida, USA, 2008.