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

Рець, В. О. (2023). Solution of the traveling salesman problem based on the annealing method with the fuzziness of the time perception. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics(2), 226–231. https://doi.org/10.17721/1812-5409.2023/2.39

У статті досліджується використання нечітких чисел і методу відпалу для пошуку розв’язків задачі комівояжера з урахуванням суб’єктивного сприйняття плину часу в реальних умовах руху, що дозволяє сформулювати нечітку оптимізаційну задачу для знаходження найкращого значення цільової функції, яка визначається величиною необхідного для подорожі між містами часу. Задача комівояжера (traveling salesman problem, TSP) — це класична задача комбінаторної оптимізації, яка передбачає пошук найкоротшого або найбільш швидкого маршруту між набором міст. Для формалізації невизначеності та неточності вхідних даних, пов’язаної з впливом суб’єктивності в оцінках тривалості необхідних проміжків часу, використовуються нечіткі числа. Їх застосування обумовлено можливістю конструктивного формулювання обмежень реального світу та факторів, які можуть вплинути на результат розв’язування задачі. Розглянуто метод відпалу для оптимізації розв’язків задачі комівояжера шляхом поступового зниження енергії системи, що дозволяє досліджувати різні розв’язки та уникати локальних мінімумів. Отримано результати, які підтвердили ефективність цього підходу. Розроблено програму, яка використовувалася для порівняння результатів задачі комівояжера з використанням чітких і нечітких чисел на основі методу відпалу. Отримано висновок, який свідчить, що використання нечітких чисел, зокрема трикутних та параболічних, із методом відпалу призводить до покращення результатів задачі порівняно з використанням чітких чисел за умов припущення реалістичності моделі з можливими відхиленнями від очікуваного фіксованого середнього. Представлено та проаналізовано результати обчислень програми, що демонструє потенціал цього підходу для реальних оптимізаційних процесів з використанням неточних або невизначених даних та врахуванням суб’єктивних оцінок в параметрах, зокрема, при вимірюванні швидкості плину часу.