Please use this identifier to cite or link to this item:
http://eztuir.ztu.edu.ua/123456789/3656
Title: | ДЕКОМПОЗИЦІЯ ЗАГАЛЬНОЇ ЗАДАЧІ КОМІВОЯЖЕРА ТА НАБЛИЖЕНИЙ МЕТОД ЇЇ РОЗВ’ЯЗКУ |
Other Titles: | Decomposition of the total traveling salesman problem and its solutions approximate method |
Authors: | Левченко, А.Ю. Levchenko, А.Yu. |
Keywords: | задача комівояжера комбінаторна оптимізація |
Issue Date: | 2011 |
Publisher: | ЖДТУ |
Series/Report no.: | Вісник ЖДТУ. Серія: Технічні науки;3(58) |
Abstract: | Запропоновано підхід до декомпозиції загальної задачі комівояжера (ЗЗК) на задачі меншої розмірності, що дозволяє суттєво прискорити процедуру пошуку розв’язку. Крім того, пропонується швидкодіючий наближений метод розв’язку ЗЗК, який полягає у послідовному виконанні двох відомих алгоритмів комбінаторної оптимізації. Спочатку ЗЗК зводиться до метричної симетричної задачі комівояжера (СЗК) поліноміальним перетворенням вихідного зваженого графа в повний метричний граф. Потім знаходиться наближене рішення метричної СЗК, що дозволяє визначити шуканий маршрут. |
URI: | http://eztuir.ztu.edu.ua/123456789/3656 |
Appears in Collections: | Вісник ЖДТУ. Серія: Технічні науки |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.