Розв'язування задачі комівояжера великих розмірностей методом спільних ребер
Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Розв'язування задачі комівояжера великих розмірностей методом спільних ребер
|
|
| Creator |
Базилевич, Р.
Кутельмах, Р. Томчук, А. |
|
| Subject |
задача комівояжерaа
NN 2-Opt 3-Opt алгоритм Ліна-Кернігана алгоритм Ліна-Кернігана-Гельсгауна евристика велика розмірність traveling salesman problem NN 2-Opt 3-Opt Lin-Kernighan LKH heuristics large-scale |
|
| Description |
Досліджено евристичні алгоритми розв'язання задачі комівояжера: найближчого сусіда, 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.
|
|
| Date |
2015-01-15T11:17:50Z
2015-01-15T11:17:50Z 2014 |
|
| Type |
Article
|
|
| Identifier |
Базилевич Р. Розв'язування задачі комівояжера великих розмірностей методом спільних ребер / Р. Базилевич, Р. Кутельмах, А. Томчук // Вісник Національного університету "Львівська політехніка". – 2014. – № 800 : Комп’ютерні науки та інформаційні технології. – С. 278–285. – Бібліографія: 10 назв.
http://ena.lp.edu.ua:8080/handle/ntb/25947 |
|
| Language |
ua
|
|
| Publisher |
Видавництво Львівської політехніки
|
|