Розв’язання задачі комівояжера на основі методу відпалу з урахуванням нечіткості сприйняття плину часу
Тип публікації :
Стаття
Дата випуску :
23 грудня 2023 р.
Автор(и) :
Рець, В. О.
Мова основного тексту :
Англійська
eKNUTSHIR URL :
Випуск :
2
ISSN :
1812-5409
Початкова сторінка :
226
Кінцева сторінка :
231
Цитування :
[APA 7] Рець, В. О. (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
[ДСТУ] Рець В. О. 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. 2023. no. 2. P. 226—231. DOI: 10.17721/1812-5409.2023/2.39 (date of access: 25.07.2026).
У статті досліджується використання нечітких чисел і методу відпалу для пошуку розв’язків задачі комівояжера з урахуванням суб’єктивного сприйняття плину часу в реальних умовах руху, що дозволяє сформулювати нечітку оптимізаційну задачу для знаходження найкращого значення цільової функції, яка визначається величиною необхідного для подорожі між містами часу. Задача комівояжера (traveling salesman problem, TSP) — це класична задача комбінаторної оптимізації, яка передбачає пошук найкоротшого або найбільш швидкого маршруту між набором міст. Для формалізації невизначеності та неточності вхідних даних, пов’язаної з впливом суб’єктивності в оцінках тривалості необхідних проміжків часу, використовуються нечіткі числа. Їх застосування обумовлено можливістю конструктивного формулювання обмежень реального світу та факторів, які можуть вплинути на результат розв’язування задачі. Розглянуто метод відпалу для оптимізації розв’язків задачі комівояжера шляхом поступового зниження енергії системи, що дозволяє досліджувати різні розв’язки та уникати локальних мінімумів. Отримано результати, які підтвердили ефективність цього підходу. Розроблено програму, яка використовувалася для порівняння результатів задачі комівояжера з використанням чітких і нечітких чисел на основі методу відпалу. Отримано висновок, який свідчить, що використання нечітких чисел, зокрема трикутних та параболічних, із методом відпалу призводить до покращення результатів задачі порівняно з використанням чітких чисел за умов припущення реалістичності моделі з можливими відхиленнями від очікуваного фіксованого середнього. Представлено та проаналізовано результати обчислень програми, що демонструє потенціал цього підходу для реальних оптимізаційних процесів з використанням неточних або невизначених даних та врахуванням суб’єктивних оцінок в параметрах, зокрема, при вимірюванні швидкості плину часу.
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
695.27 KB
Контрольна сума :
(MD5):ad02f9c0c9dc719eb79d72e0d62f1458
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International