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

О. Ф. Шевчук, А. В. Козловський, Ю. М. Паночишин et al. · Repository of Vinnytsia National Technical University (Vinnytsia National Technical University) · 2026

Статтю присвячено порівняльному аналізу найвідоміших методів кластеризації маршрутів доставки (K-means, Sweep та Clarke–Wright) з обмеженою вантажопідйомністю транспортних засобів на основі імітаційних сценарних датасетів: Uniform (рівномірний розподіл пунктів доставки), Clustered (мережа, що імітує скупченість торговельних точок у спальних районах міста), Mixture (комбінована мережа з кластерами та окремими віддаленими пунктами доставки). Для маршрутизації усередині кластерів малої розмірності застосовано точний алгоритм динамічного програмування Held–Karp та евристичний алгоритм найближчого сусіда з подальшою оптимізацією 2-opt для великих наборів даних. Результати числових експериментів показали, що для Uniform-датасету всі алгоритми демонструють порівнянні показники щодо приросту довжини маршруту після кластеризації. Для Clustered- та Mixture-датасетів виявлено значні відмінності: алгоритм Clarke–Wright забезпечує мінімальний приріст довжини маршруту та високий рівень завантаження транспортних засобів, метод Sweep демонструє помірну ефективність, а K-means у складних сценаріях призводить до істотного збільшення довжини маршрутів і кількості задіяних транспортних засобів. Час виконання алгоритмів залишається прийнятним для задач середньої розмірності, при цьому K-means забезпечує найвищу швидкодію, але ціною втрати контролю над балансом навантаження. Проведене дослідження підтверджує, що запропонована методика є ефективним інструментом оцінювання алгоритмів кластеризації маршрутів доставки в умовах обмеженої вантажопідйомності та різної просторової структури пунктів доставки. Вона дозволяє не лише порівнювати продуктивність алгоритмів, а й обґрунтовано обирати найбільш доцільні методи для конкретних логістичних сценаріїв. Подальші дослідження можуть бути спрямовані на удосконалення наявних алгоритмів шляхом інтеграції динамічних обмежень, аналізу великих та географічно складних мереж, а також застосування гібридних методів, що комбінують переваги кількох кластеризаційних підходів для підвищення економічної ефективності та зменшення операційних витрат.

Cited by 0 works. Open-access PDF

Authors