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

Анотація

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