https://oldena.lpnu.ua/handle/ntb/25947| Title: | Розв'язування задачі комівояжера великих розмірностей методом спільних ребер |
| Authors: | Базилевич, Р. Кутельмах, Р. Томчук, А. |
| Bibliographic description (Ukraine): | Базилевич Р. Розв'язування задачі комівояжера великих розмірностей методом спільних ребер / Р. Базилевич, Р. Кутельмах, А. Томчук // Вісник Національного університету "Львівська політехніка". – 2014. – № 800 : Комп’ютерні науки та інформаційні технології. – С. 278–285. – Бібліографія: 10 назв. |
| Issue Date: | 2014 |
| Publisher: | Видавництво Львівської політехніки |
| Keywords: | задача комівояжерaа NN 2-Opt 3-Opt алгоритм Ліна-Кернігана алгоритм Ліна-Кернігана-Гельсгауна евристика велика розмірність traveling salesman problem NN 2-Opt 3-Opt Lin-Kernighan LKH heuristics large-scale |
| Abstract: | Досліджено евристичні алгоритми розв'язання задачі комівояжера: найближчого сусіда, 2-Opt, 3-Opt, Ліна-Кернігана та Ліна-Кернігана-Гельсгауна. Здійснено порівняльний аналіз часу роботи алгоритмів та якості отриманих розв'язків. Запропоновано декомпозиційний метод знаходження розв’язків задачі комівояжера на основі спільних ребер. Existing heuristic algorithms for solving traveling salesman problem, such as Nearest Neighbor, 2-Opt, 3-Opt, Lin-Kernighan and Lin-Kernighan-Helsgaun have been investigated in this work. The algorithms have been compared in terms of running time and solution quality. Decomposition approach, based on using common edges in multiple solutions, has been proposed. |
| URI: | https://ena.lpnu.ua/handle/ntb/25947 |
| Content type: | Article |
| Appears in Collections: | Комп'ютерні науки та інформаційні технології. – 2014. – №800 |
| File | Description | Size | Format | |
|---|---|---|---|---|
| 39-278-285.pdf | 860.34 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.