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

Abstract

В статті на основі методу гілок і границь запропоновано алгоритм оптимізації маршрутів автомобільних перевезень вантажів за критерієм мінімізації транспортної роботи з їх доставки, коли відстані та обсяги доставки для кожного пункту і між пунктами є заданими. В даному дослідженні в якості критерія оптимізації застосовується мінімізація транспортної роботи перевезення вантажів із відповідного транспортно-логістичного центру до визначених пунктів доставки та одноразовість проходження місць їх розташування. Особливість запропонованого підходу полягає в тому, що вся множина можливих варіантів перевезення вантажу описується матрицею транспортної роботи доставки елементи якої обчислюються динамічно на кожному кроці алгоритму, на відміну від класичного застосування методу гілок і границь при мінімізації довжини маршруту перевезень, коли елементи матриці відстаней перевезень є сталими. Для підвищення ефективності пошуку оптимального маршруту проведено модифікацію методу гілок і границь (TBM) на випадок динамічного визначення елементів матриці транспортної роботи доставки вантажів. В роботі наведено алгоритм застосування запропонованого варіанту методу TBM для побудови оптимального автомобільного маршруту з мінімізацією транспортної роботи перевезення вантажів із логістичного центру в мережі із п’яти пунктів доставки. Аналіз результатів проведених розрахунків підтверджує ефективність запропонованого підходу і показує, що його застосування дозволяє зменшити обчислювальну складність завдяки використанню покращених стратегій відсікання нерелевантних рішень та адаптивного розгалуження можливих варіантів доставки вантажів. Запропонований підхід дозволяє підвищити точність результатів розрахунків та зменшити час пошуку оптимального маршруту за критерієм мінімізації транспортної роботи доставки вантажів до пунктів призначення. Отримані результати можуть бути використані для оптимізації логістичних процесів та зниження витрат на транспортні перевезення.