1. SCSIT
  2. All Volumes and Issues
  3. Volume 638, 2009
  4. Оптимізація розв’язків задачі комівояжера методом послідовного сканування

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

SCSIT.
2009;
Volume 638
: pp. 254 - 260
Authors: 

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

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

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

New approach for Traveling Salesman Problem (TSP) solutions optimization is proposed. Approach can be applied for initial solution optimization, calculated with the help of decomposition algorithm or for route optimization, calculated by any classic algorithm. Route to be improved is an input data for algorithm.

  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. S. Lin and B. W. Kernighan. An effective heuristic algorithm for the Traveling salesman problern. Operations Research, 21:498–516. 1973.
  5. S. Lin. 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. D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook. On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume ICM III: 645–656, 1998.
  10. D. Applegate, W. Cook, A. Rohe. Chained Lin–Kernighan for large traveling salesman problems. INFORMS J. Computing, to appear.
  11. D. Applegate, R.E. Bixby, V. Chvätal, and W. Cook. Findong tours in the TSP.1998.
  12. D. Applegate, R.E. Bixby, V. Chvätal, and W. Cook. Findong cuts in the TSP.1995 
  13. http://www.tsp.gatech.edu/concorde.html
  14. D. Neto. Efficient cluster compensation for Lin–Kernighan Heuristics. PhD thesis, Department of Computer Science, University of Toronto, 1999.
  15. G. Laporte, J-Y. Potvin, F. Quilleret, «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. Held, M., and Karp, R. M. (1970), «The Traveling Salesman Problem and Minimum Spanning Trees», Operations Research. 18:1138–1162.