Штучний інтелект

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

Ключові слова: задача комівояжера, нечіткі числа, метод динамічного програмування, дефазифікація, нечітке представлення часу, неточність, невизначеність

Посилання:

1. Zadeh. L.A., Fuzzy sets, Information and Control, 8, 338-353 (1965).
2. Kumar, A.; Gupta, A. 2011. Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions, Fuzzy Information and Engineering 3(1): 3–21.
3. Bellman, R.E. and L.A. Zadeh (1970), Decision making in fuzzy environment, Management science 17, 144-164.
4. Zimmermann, H.-J. 1978. Fuzzy programming and linear programming with several objective functions, Fuzzy Sets and Systems 1(1): 45-55.
5. N. Christofides (1985). Vehicle Routing, in The Traveling Salesman Problem, Lawler, Lenstra, RinooyKan and Shmoys, eds., John Wiley, 431- 448.
6. Dantzig GB, Fulkerson DR, Johnson SM (1954). Solution of a Large-scale Traveling Salesman Problem. Operations Research, 2, 393410.
7. R.R. Yager, A procedure for ordering fuzzy subsets of the unit interval. Information Sciences, 1981, 24, 143-161.
8. Тien Fuling. Applying interactive fuzzy multi-objective Linear programming to transportation planning decisions//Journal of information and optimization sciences.–2006.–V.27. – №1.– P.107-126.
9. Bablu Jana, Tapan Kumar Roy. Multi-Objective Fuzzy Linear Programming and Its Application in Transportation Model//Tamsui Oxford Journal of Mathematical Sciences. – 2005. – V.21. – No.2. – P.243-268.
10. Kaufman A., Gupta M.M. Introduction to Fuzzy Arithmetic, Theory and applications /Van Nostrand Reinhold Co. Inc.,Workingham, Berkshire, 2003. 361р.