ЗАСТОСУВАННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ ДЛЯ РОЗВ'ЯЗАННЯ ТРАНСПОРТНИХ ЗАДАЧ
DOI:
https://doi.org/10.31319/2519-8106.2(49)2023.293181Ключові слова:
транспортна задача, генетичний алгоритм, математична модель, оператор кросинговера, хромосомиАнотація
У роботі представлено метод розв’язання задачі маршрутизації транспортних засобів, заснований на використанні адаптивного генетичного алгоритму. Було досліджено можливість та ефективність використання генетичних алгоритмів для розв'язання специфічних транспортних задач, а також визначено оптимальні параметри та методи кодування для підвищення точності і швидкості отримання розв’язків. Розроблено дві стратегії кодування окремих елементів популяції та алгоритм визначення ймовірностей, які формують хромосому в адаптивному генетичному алгоритмі. Надано практичні рекомендації щодо впровадження та налаштування генетичних алгоритмів для конкретних транспортних завдань. Результати роботи описують переваги та можливі обмеження запропонованого підходу.
Посилання
Македон В.В., Чабаненко А.В. Факторні складові цифровізації глобальної економіки та макроекономічних систем країн світу. Ефективна економіка. 2022. № 1. URL: http://www.economy.nayka.com.ua/?op=1&z=9875. DOI: 10.32702/2307-2105-2022.1.11
Івохін Є.В. Про багатоіндексні транспортні задачі та способи їх фазифікації. Вісник Київського національного університету імені Тараса Шевченка. Серія фізико-математичні науки. 2014. Вип. 2. С. 147–150. URL: http://www.library.univ.kiev.ua/ukr/host/10.23.10.100/db/ftp/visnyk/fiz_mat_2_2014.pdf
Ільченко Н.Б., Кулік А.В. Розвиток транспортно-логістичної системи в Україні. Вчені записки ТНУ імені В. І. Вернадського. Серія: Економіка і управління. 2019. № 5(30). С. 42–50. https://doi.org/10.32838/2523-4803/69-5-36.
Романюк О.Н., Снігур А.В., Куклій Д.В. Оптимізація профорієнтаційних маршрутів на основі задачі комівояжера. Вчені записки ТНУ імені В.І. Вернадського. Серія: Технічні науки. 2021. № 2(32). С. 221-228. https://doi.org/10.32838/2663-5941/2021.2-1/35.
Шейко М.В. Застосування генетичних алгоритмів для вирішення задачі транспортних перевезень. Новітні інформаційні системи та технології. Полтава: ПНТУ, 2014. Т. (1). URL: http://journals.nupp.edu.ua/mist/article/view/472
Makedon V., Mykhailenko O., Dzyad O. Modification of Value Management of International Corporate Structures in the Digital Economy. European Journal of Management Issues. 2023. № 31(1). pp. 50–62. https://doi.org/10.15421/192305
Stutzle T., Hoos H. The Max-Min ANT System and Local Search for Combinatorial Optimization Problems. Future Generation Computer Systems. 2000. Vol. 16. pp. 889–914.
Leno J., Sankar S., Raj V., Ponnambalam S. An elitist strategy genetic algorithm for integrated layout design. International Journal of Advanced Manufacturing Technology. 2013. Vol. 66. Issue 9–12. pp. 1573–1589. DOI: 10.1007/s00170-012-4441-4
Gottlieb J., Paulmann L. Genetic algorithms for the fixed charge transportation problem. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. IEEE Press. 1998. pp. 330–335.
Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), Springer. New York, 2018. 455 p.
Hong Haoyuan, Panahi Mahdi, Shirzadi Ataollah, Ma Tianwu, Liu Junzhi, Zhu A-Xing, Chen Wei, Kougias Ioannis, Kazakis Nerantzis. Flood susceptibil- ity assessment in Hengfeng area coupling adaptive neuro-fuzzy inference system with genetic algorithm and differential evolution. Science of The Total Environment. 2018. № 621. pp. 1124–1141. 10.1016/j.scitotenv.2017.10.114.
Худов Г., Хижняк І., Марченко В., Горошко О. Метод визначення маршруту руху транспортних засобів з використанням модифікованого алгоритму мурашиної колонії. Системи обробки інформації. 2022. С. 58–66. 10.30748/soi.2022.170.08.
Jiang H. Solving Traveling Salesman Problem Using Artificial Bee Colony Algorithm. Computer Science and Technology. 2017. pp. 989-995. https://doi.org/10.1142/9789813146426_0110.
Makedon, V. & Chabanenko, A. (2022). Factor components of digitalization of the global economy and macroeconomic systems of countries. Efektyvna ekonomika, [Online], vol. 1, available at: http://www.economy.nayka.com.ua/?op=1&z=9875. DOI:10.32702/2307-2105-2022.1.11 [in Ukrainian].
Ivokhin, Ye. V. (2014). Pro bahatoindeksni transportni zadachi ta sposoby yikh fazyfikatsii [On multi-index transport problems and ways of their phasing]. Visnyk Kyivskoho natsionalnoho universytetu imeni Tarasa Shevchenka. Seriia: Fizyko-matematychni nauky. Retrieved from http://www.library.univ.kiev.ua/ukr/host/10.23.10.100/db/ftp/visnyk/fiz_mat_2_2014.pdf
[in Ukrainian].
Ilchenko, N. B. & Kulik, A. V. (2019). Rozvytok transportno-lohistychnoyi systemy v Ukrayini” [Development of the transport and logistics system in Ukraine], Academic notes of TNU named after V.I. Vernadskyi. Series: Economics and man-agement, No. 5(30), 42–50. https://doi.org/10.32838/2523-4803/69-5-36. [in Ukrainian].
Romanyuk, O. N., Snigur, A. V. & Kuklii, D. V. (2021). Optymizatsiia proforiientatsiinykh marshrutiv na osnovi zadachi komivoiazhera [Optimization of career guidance routes based on the traveling salesman problem]. Academic notes of TNU named after V.I. Vernadskyi. Series: Technical sciences, No. 2(32), 221–228. https://doi.org/10.32838/2663-5941/2021.2-1/35.
[in Ukrainian].
Sheiko, M. V. (2014). Zastosuvannya henetychnykh alhorytmiv dlya vyrishennya zadachi transportnykh perevezen’ [Application of genetic algorithms to solve the problem of transportation]. The latest information systems and technologies. Poltava: PNTU, Vol. (1). Retrieved from http://journals.nupp.edu.ua/mist/article/view/472 [in Ukrainian].
Makedon, V., Mykhailenko, O., & Dzyad, O. (2023). Modification of Value Management of International Corporate Structures in the Digital Economy. European Journal of Management Issues, 31(1), 50-62. https://doi.org/10.15421/192305.
Stutzle, T. & Hoos, H. (2000). The Max-Min ANT System and Local Search for Combinatorial Optimization Prob-lems. Future Generation Computer Systems, Vol. 16, 889–914.
Leno, J. (2013). An elitist strategy genetic algorithm for integrated layout design. International Journal of Advanced Manufacturing Technology, vol. 66, no. 9–12 (2013): 1573-1589. DOI: 10.1007/s00170-012-4441-4
Gottlieb, J., & Paulmann, L. (1998). Genetic algorithms for the fixed charge transportation problem. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, IEEE Press, 330–335.
Korte, B., & Vygen, J. (2018). Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), Springer, New York, 455 p.
Hong, Haoyuan & Panahi, Mahdi & Shirzadi, Ataollah & Ma, Tianwu & Liu, Junzhi & Zhu, A-Xing & Chen, Wei & Kougias, Ioannis & Kazakis, Nerantzis. (2018). Flood susceptibil - ity assessment in Hengfeng area coupling adaptive neuro-fuzzy inference system with genetic algorithm and differential evolution. Science of The Total Environment, 621, 1124–1141. 10.1016/j.scitotenv.2017.10.114.
Khudov, H., Khizhnyak, I., Marchenko, V., & Horoshko, O. (2022). Metod vyznachennya marshrutu rukhu transportnykh zasobiv z vykorystannyam modyfikovanoho alhorytmu murashynoyi koloniyi [The method of determining the route of vehicles using a modified ant colony algorithm]. Information processing systems, 58–66. 10.30748/soi.2022.170.08
[in Ukrainian].
Jiang, H. (2017). Solving Traveling Salesman Problem Using Artificial Bee Colony Algorithm. Computer Science and Technology, 989–995. https://doi.org/10.1142/9789813146426_0110.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
a. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
b. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
c. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
