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

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

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

Посилання:

1. Зайченко Ю. П. Дослідження операцій / Ю. П. Зайченко. – К.: «Слово», 2006. – 815 с.
2. Ajay D. Kshemkalyani, Mukesh Singhal. Distributed Computing: Principles, Algorithms, and Systems. - Cambridge University Press, 2011. DOI: 10.1017/CBO9780511805318
3. Vanderbei R. J. Linear programming: Foundations and extensions. - Springer, 2014. – 414 р.
4. Golden B., Raghavan S., Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges. – Springer New York, 2008. DOI: 10.1007/978-0-387-77778-8
5. Hamdy A. Taha. Operations Research: An Introduction (10th Edition). – Pearson Education Limited, 2017. – 849 p.
6. Seth Pettie, Vijaya Ramachandran An optimal minimum spanning tree algorithm // Journal of ACM, 2002. – V.49. – Iss. 1. – P.16-34. DOI: 10.1145/505241.50524
7. Зайченко Ю. П. Нечіткі моделі та методи в інтелектуальних системах, Київ: «Слово», 2008. – 344с.
8. 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.
9. Гавриленко В. В., Івохін Є. В., Івохіна К. Є., Юштін К. Е. Моделі оптимізації транспортних та мережевих потоків в задачах підтримки прийняття рішень в інформаційних управляючих системах/ Розділ монографії «Інноваційні тенденції розвитку інформаційних управляючих систем і технологій» за загальною редакцією Устенко С. В. - Київ, КНЕУ, 2023.
10. Van Broekhoven, E., De Baets, B. Fast and accurate center of gravity defuzzification of fuzzy system outputs defined on trapezoidal fuzzy partitions// Fuzzy Sets and Systems, 2006. - V. 157. - Iss. 7. – P. 904-918.
11. Syswerda, G., Schedule Optimization Using Genetic Algorithms// in book “Yandbook of Genetic Algorithms”, Van Nostran Reynolds, NY, 1991, pp.332-349.
12. Barraq Subhi Kaml, Mohamed Saad Ibrahim. Solving the Multi-Objective Travelling Salesman Problem with Real Data Application // Journal of Al-Nahrain University, 2018. - Vol.21 (3). – Pp. 146-161. DOI: 10.22401/JNUS.21.3.18