Масштабована модель для проблеми маршрутизації транспортних засобів із обмеженнями в динамічних умовах з використанням адаптивної оптимізації колонії мурах на основі евристики

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2025.319733

Ключові слова:

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

Анотація

У цьому дослідженні розглядається проблема маршрутизації ємного транспортного засобу з прийомом і доставкою (CVRPPD), яка є основною проблемою міської логістики, яка передбачає оптимізацію маршрутів транспортних засобів за динамічних обмежень. Традиційні алгоритми здебільшого зосереджуються на статичних змінних, таких як відстань, не враховуючи чинники реального світу, такі як затори, несприятлива погода та обмеження місткості транспортних засобів. Щоб вирішити цю проблему, був розроблений алгоритм адаптивної евристичної оптимізації мурашиної колонії (AЕА-ОМК), який включає ці динамічні обмеження в процес оптимізації маршрутизації. Алгоритм AЕА-ОМК мінімізує загальні витрати на подорож, забезпечуючи дотримання обмежень щодо місткості транспортного засобу та покращуючи безпеку маршруту. Тести моделювання проводилися на наборах даних із 50, 100 і 200 клієнтами, щоб оцінити продуктивність на різних рівнях складності. Результати демонструють, що AЕА-ОМК перевершує традиційний ОМК, особливо в динамічних сценаріях, досягаючи загальної вартості 4155,82 із часом виконання 1639,68 секунди для набору даних із 200 клієнтів. Адаптивна евристична формула алгоритму об’єднує відстань, затори та погодні умови, що дозволяє створювати безпечніші та реалістичніші маршрути. Ці результати пояснюються здатністю алгоритму динамічно адаптуватися до обмежень, забезпечуючи надійну роботу в складних середовищах. Отримані дані підкреслюють практичну застосовність AЕА-ОМК в міській логістиці, пропонуючи масштабованість і адаптивність для реальних завдань доставки та самовивозу, особливо в районах, на які впливають коливання трафіку та погодні умови

Біографії авторів

Imam Muslem R, Universitas Sumatera Utara

Doctoral Student

Department of Computer Science

Mahyuddin K. M. Nasution, Universitas Sumatera Utara

Professor

Department of Computer Science

Sutarman Sutarman, Universitas Sumatera Utara

Doctor

Department of Mathematics

Suherman Suherman, Universitas Sumatera Utara

Head of Department

Department of Electrical Engineering

Посилання

  1. Song, M., Li, J., Li, L., Yong, W., Duan, P. (2018). Application of Ant Colony Algorithms to Solve the Vehicle Routing Problem. Intelligent Computing Theories and Application, 831–840. https://doi.org/10.1007/978-3-319-95930-6_83
  2. Yu, W., Liu, Z., Bao, X. (2019). Distance Constrained Vehicle Routing Problem to Minimize the Total Cost. Computing and Combinatorics, 639–650. https://doi.org/10.1007/978-3-030-26176-4_53
  3. Akkerman, F., Mes, M. (2022). Distance approximation to support customer selection in vehicle routing problems. Annals of Operations Research. https://doi.org/10.1007/s10479-022-04674-8
  4. Zhu, Z., Qian, Y., Zhang, W. (2021). Research on UAV Searching Path Planning Based on Improved Ant Colony Optimization Algorithm. 2021 IEEE 3rd International Conference on Civil Aviation Safety and Information Technology (ICCASIT), 1319–1323. https://doi.org/10.1109/iccasit53235.2021.9633591
  5. Xiang, A., Wang, L. (2021). Research on Path Planning of UAV Forest Fire Fighting Based on Improved Ant Colony Algorithm. 2021 7th International Conference on Computing and Artificial Intelligence, 289–295. https://doi.org/10.1145/3467707.3467751
  6. Jang, J., Kim, M., Lee, J. (2019). Improvement of Ant Colony Optimization Algorithm to Solve Traveling Salesman Problem. Journal of Society of Korea Industrial and Systems Engineering, 42 (3), 1–7. https://doi.org/10.11627/jkise.2019.42.3.001
  7. Frías, N., Johnson, F., Valle, C. (2023). Hybrid Algorithms for Energy Minimizing Vehicle Routing Problem: Integrating Clusterization and Ant Colony Optimization. IEEE Access, 11, 125800–125821. https://doi.org/10.1109/access.2023.3325787
  8. Ky Phuc, P. N., Phuong Thao, N. L. (2021). Ant Colony Optimization for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window and Heterogeneous Fleets. Logistics, 5 (2), 28. https://doi.org/10.3390/logistics5020028
  9. Pan, T., Pan, H., Gao, J. (2015). An improved ant colony algorithm based on vehicle routing problem. 2015 34th Chinese Control Conference (CCC), 2747–2752. https://doi.org/10.1109/chicc.2015.7260059
  10. Ren, T., Luo, T., Jia, B., Yang, B., Wang, L., Xing, L. (2023). Improved ant colony optimization for the vehicle routing problem with split pickup and split delivery. Swarm and Evolutionary Computation, 77, 101228. https://doi.org/10.1016/j.swevo.2023.101228
  11. Huang, Y.-H., Blazquez, C. A., Huang, S.-H., Paredes-Belmar, G., Latorre-Nuñez, G. (2019). Solving the Feeder Vehicle Routing Problem using ant colony optimization. Computers & Industrial Engineering, 127, 520–535. https://doi.org/10.1016/j.cie.2018.10.037
  12. Peng, Y., Pan, Y., Qin, Z., Li, D. (2015). An adaptive hybrid ant colony optimization algorithm for solving Capacitated Vehicle Routing. Proceedings of the 2015 International Industrial Informatics and Computer Engineering Conference. https://doi.org/10.2991/iiicec-15.2015.132
  13. Dhanya, K. M., Kanmani, S. (2017). Dynamic Vehicle Routing Problem: Solution by Ant Colony Optimization with Hybrid Immigrant Schemes. International Journal of Intelligent Systems and Applications, 9 (7), 52–60. https://doi.org/10.5815/ijisa.2017.07.06
  14. Fatimah Mohamad Ayop, S., Shahizan Othman, M., Mi Yusuf, L. (2020). Ant Colony Optimization Using Different Heuristic Strategies for Capacitated Vehicle Routing Problem. IOP Conference Series: Materials Science and Engineering, 864 (1), 012082. https://doi.org/10.1088/1757-899x/864/1/012082
  15. Guo, N., Qian, B., Na, J., Hu, R., Mao, J.-L. (2022). A three-dimensional ant colony optimization algorithm for multi-compartment vehicle routing problem considering carbon emissions. Applied Soft Computing, 127, 109326. https://doi.org/10.1016/j.asoc.2022.109326
  16. Thymianis, M., Tzanetos, A., Osaba, E., Dounias, G., Del Ser, J. (2022). Electric Vehicle Routing Problem: Literature Review, Instances and Results with a Novel Ant Colony Optimization Method. 2022 IEEE Congress on Evolutionary Computation (CEC), 1–8. https://doi.org/10.1109/cec55065.2022.9870373
  17. Wu, H., Gao, Y. (2023). An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup–delivery and time window. Applied Soft Computing, 139, 110203. https://doi.org/10.1016/j.asoc.2023.110203
  18. Siddalingappa, P., Basavaraj, P., Basavaraj, P., Gowramma, P. (2023). Route optimization via improved ant colony algorithm with graph network. International Journal of Reconfigurable and Embedded Systems (IJRES), 12 (3), 403. https://doi.org/10.11591/ijres.v12.i3.pp403-413
  19. Setyati, E., Juniwati, I. (2022). Ant Colony Optimization Ant Colony Optimization untuk menyelesaikan perutean distribusi Snack dengan Vehicle Routing Problem. Jurnal Teknologi Informasi Dan Terapan, 9 (2), 111–117. https://doi.org/10.25047/jtit.v9i2.296
  20. Alwabli, A., Kostanic, I., Malky, S. (2020). Dynamic Route Optimization For Waste Collection and Monitering smart bins Using Ant colony Algorithm. 2020 IEEE 2nd International Conference on Electronics, Control, Optimization and Computer Science (ICECOCS), 1–7. https://doi.org/10.1109/icecocs50124.2020.9314571
  21. Han, J., Mozhdehi, A., Wang, Y., Sun, S., Wang, X. (2022). Solving a multi-trip VRP with real heterogeneous fleet and time windows based on ant colony optimization. Proceedings of the 15th ACM SIGSPATIAL International Workshop on Computational Transportation Science, 1–4. https://doi.org/10.1145/3557991.3567776
  22. Kyriakakis, N. A., Marinaki, M., Marinakis, Y. (2021). A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 134, 105397. https://doi.org/10.1016/j.cor.2021.105397
Масштабована модель для проблеми маршрутизації транспортних засобів із обмеженнями в динамічних умовах з використанням адаптивної оптимізації колонії мурах на основі евристики

##submission.downloads##

Опубліковано

2025-02-21

Як цитувати

Muslem R, I., Nasution, M. K. M., Sutarman, S., & Suherman, S. (2025). Масштабована модель для проблеми маршрутизації транспортних засобів із обмеженнями в динамічних умовах з використанням адаптивної оптимізації колонії мурах на основі евристики. Eastern-European Journal of Enterprise Technologies, 1(3 (133), 57–65. https://doi.org/10.15587/1729-4061.2025.319733

Номер

Том 1 № 3 (133) (2025): Процеси управління

Розділ

Процеси управління

Ліцензія

Авторське право (c) 2025 Imam Muslem R, Mahyuddin K. M. Nasution, Sutarman Sutarman, Suherman Suherman

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.