АЛГОРИТМ ОПТИМІЗАЦІЇ МАРШРУТІВ АВТОМОБІЛЬНИХ ПЕРЕВЕЗЕНЬ ВАНТАЖІВ НА ОСНОВІ ДИНАМІЧНОЇ МОДИФІКАЦІЇ МЕТОДУ ГІЛОК І ГРАНИЦЬ
Анотація
В статті на основі методу гілок і границь запропоновано алгоритм оптимізації маршрутів автомобільних перевезень вантажів за критерієм мінімізації транспортної роботи з їх доставки, коли відстані та обсяги доставки для кожного пункту і між пунктами є заданими. В даному дослідженні в якості критерія оптимізації застосовується мінімізація транспортної роботи перевезення вантажів із відповідного транспортно-логістичного центру до визначених пунктів доставки та одноразовість проходження місць їх розташування. Особливість запропонованого підходу полягає в тому, що вся множина можливих варіантів перевезення вантажу описується матрицею транспортної роботи доставки елементи якої обчислюються динамічно на кожному кроці алгоритму, на відміну від класичного застосування методу гілок і границь при мінімізації довжини маршруту перевезень, коли елементи матриці відстаней перевезень є сталими. Для підвищення ефективності пошуку оптимального маршруту проведено модифікацію методу гілок і границь (TBM) на випадок динамічного визначення елементів матриці транспортної роботи доставки вантажів. В роботі наведено алгоритм застосування запропонованого варіанту методу TBM для побудови оптимального автомобільного маршруту з мінімізацією транспортної роботи перевезення вантажів із логістичного центру в мережі із п’яти пунктів доставки. Аналіз результатів проведених розрахунків підтверджує ефективність запропонованого підходу і показує, що його застосування дозволяє зменшити обчислювальну складність завдяки використанню покращених стратегій відсікання нерелевантних рішень та адаптивного розгалуження можливих варіантів доставки вантажів. Запропонований підхід дозволяє підвищити точність результатів розрахунків та зменшити час пошуку оптимального маршруту за критерієм мінімізації транспортної роботи доставки вантажів до пунктів призначення. Отримані результати можуть бути використані для оптимізації логістичних процесів та зниження витрат на транспортні перевезення.
Посилання
2. Little J. D. C., Murty K. G., Sweeney D. W., Karel C. An Algorithm for the Traveling Salesman Problem. Operations Research. 1963. Vol. 11, № 6. P.972–989.
3. Munapo E. A Return to the traveling salesman model: a network branch and bound approach. South African Journal of Economic and Management Sciences. 2013. Vol 16, № 1. P.52–63.
4. Walton P. C., do Nascimento R. Q., Pessoa A.A., Subramanian A.A. Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem. Inform Journal on Computing. 2016. Vol 28, № 4. P.752–765.
5. Rastogi A., Shrivastava A. Kumar, Payal N., Singh R. A Proposed Solution to Travelling Salesman Problem using Branch and Bound. International Journal of Computer Applications. 2013. Vol 65, № 5. NY, USA. P.44–49.
6. Suyudi M., Sukono S., Mamat M., Bon A.T. Solving Traveling Salesman Problems Using Branch and Bound Methods. Proceedings of the International Conference on Industrial Engineering and Operations Management. Pilsen, Czech Republic. 2019. P.1606–1614.
7. Markevich E., Trushechkin A. Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem. Mathematical Sciences. Springer Science and Business Media LLC. 2019. № 2. P.168–184.
8. Wiener R. Branch and Bound Implementations for the Traveling Salesperson Problem. Object Technology. 2003. Vol. 2, № 2. P.65–86.
9. Ropke S., Cordeau J.-F., Laporte G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks. 2007. Vol 49, № 4. Р.258–272.
10. Inayatullah S., Riaz W., Jafree H.A., Siddiqi T.A., Imtiaz M., Naz S., Hassan S.A. A Note on Branch and Bound Algorithm for Integer Linear Programming. Current Journal of Applied Science and Technology. 2019. Vol 34, № 6. Р.1–6.
11. Крижанівський Б. Використання методу гілок і меж при розв’язанні задач лінійного цілочислового програмування. Матеріали науково-технічної конференції «Наука. Освіта. Молодь». Умань. 2016. URL: https://library.udpu.edu. ua/library_files/stud_konferenzia/2016_1/85.pdf.
12. Мельник І.М., Піднебесна Г.А. Особливості застосування методу гілок і границь для розв’язання задачі вибору оптимальної регресійної моделі. Індуктивне моделювання складних систем. 2012. № 4. С. 128–135.
13. Козар Л. М., Романович Є. В., Афанасов Г. М. Методи транспортної логістики : навчальний посібник. Харків: УкрДАЗТ. 2015. 175 с.
14. Пасічник А.М., Худа Ж.В., Циба В.В. Метод оптимізації роботизованої транспортної системи портової переробки вантажопотоку. Системи та технології. 2023. В.66, № 2. С. 5–12.
15. Пасічник А.М., Худа Ж.В., Циба В.В. Оптимізація маршрутів автомобільних перевезень вантажів із застосуванням методу гілок і границь. Мат. III міжн. наук.-практ. конф. «Сучасні дослідження: транспортна інфраструктура та інноваційні технології». Київ: ДУІТ. 2024. Ч.2. С. 280–283.
ISSN 
