Comparative analysis of the clusterization methods of the delivery routes with limited carrying capacity, based on simulation datasets

Abstract

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

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

Проведене дослідження підтверджує, що запропонована методика є ефективним інструментом оцінювання алгоритмів кластеризації маршрутів доставки в умовах обмеженої вантажопідйомності та різної просторової структури пунктів доставки. Вона дозволяє не лише порівнювати продуктивність алгоритмів, а й обґрунтовано обирати найбільш доцільні методи для конкретних логістичних сценаріїв. Подальші дослідження можуть бути спрямовані на удосконалення наявних алгоритмів шляхом інтеграції динамічних обмежень, аналізу великих та географічно складних мереж, а також застосування гібридних методів, що комбінують переваги кількох кластеризаційних підходів для підвищення економічної ефективності та зменшення операційних витрат.