задача комівояжера

КОМБІНОВАНИЙ ПІДХІД ДЛЯ ПОБУДОВИ ОПТИМАЛЬНОГО ІНДИВІДУАЛЬНОГО ТУРИСТИЧНОГО МАРШРУТУ У МОБІЛЬНОМУ ЗАСТОСУНКУ

Стаття присвячена вирішенню задачі побудови оптимальних маршрутів при плануванні індивідуальних подорожей в умовах впливу багатьох факторів і можливих змін вхідних параметрів (погодних умов, заторів на дорогах тощо). Проаналізовано чотири класи алгоритмів для розв'язання задачі комівояжера та оцінено їхню доцільність для використання у мобільному туристичному застосунку. Форма мобільного застосунку продиктована тим, що туристи переважно не беруть у мандри техніку, важчу за смартфон.

ОЦІНКА ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ ГЕНЕТИЧНОГО АЛГОРИТМУ

Стаття присвячена оцінці обчислювальної складності генетичного алгоритму як одного із ключових засобів для розв’язання оптимізаційних задач. Розглянуто теоретичні аспекти обчислювальної складності алгоритмів та взаємозв'язок елементів генетичного алгоритму. Описано основні види обчислювальної складності алгоритмів: часову, просторову та асимптотичну. Наведено п’ять основних правил для розрахунку асимптотичної складності.

Оптимізація розв’язку задачі комівояжера методом парних заміщень

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

The algorithm for TSP solution optimization is investigated. Tour minimization is performed by swapping of edges, which satisfy optimization criteria.

Алгоритм розв’язання задачі комівояжера великої розмірності методом «Тора»

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

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

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

Article describes three approaches to clustering set of points of TSP into subsets with given constraints. One of the well-known basic algorithms is used for solutions at every cluster with further joining of partial solutions.

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

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

Модифікація методу мурашиної колонії для розв'язання задачі комівояжера колективом автономних агентів

Розглянуто можливість використання колективу автономних агентів для розв’я- зання задач комбінаторної оптимізації на прикладі розв’язання задачі комівояжера.