ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ КЛАСТЕРИЗАЦІЇ ДЛЯ ЗАДАЧІ МАРШРУТИЗАЦІЇ ТРАНСПОРТНИХ ЗАСОБІВ

Анотація

Задача маршрутизації транспортних засобів (Vehicle Routing Problem, VRP) є однією з ключових задач операційної логістики підприємств харчової промисловості, де логістичні витрати можуть сягати третини собівартості продукції. Зниження цих витрат досягається насамперед через оптимізацію маршрутів доставки. Підхід «спочатку кластеризація – потім маршрутизація» (cluster-first route-second, CFRS) дозволяє декомпозувати задачу VRP на два послідовні етапи: географічний розподіл точок доставки на зони відповідальності та побудову маршруту всередині кожної зони. Якість першого етапу безпосередньо визначає ефективність всього рішення. Незважаючи на широке застосування підходу CFRS, порівняльний аналіз алгоритмів кластеризації для задач VRP із використанням комплексу метрик на реальних даних залишається недостатньо дослідженим: більшість робіт обмежуються коефіцієнтом силуету як єдиним критерієм оцінки. У даній роботі проведено порівняльний аналіз п'яти алгоритмів кластеризації двох класів – розподільчих (K-Means, K-Medoids, Bisecting K-Means) та агломеративних (Ward, Complete Linkage) – на реальних даних мережі доставки хлібобулочних виробів одного з підприємств харчової промисловості м. Одеса. Нижня межа кількості кластерів визначена обґрунтованим методом, що враховує максимальну кількість точок на маршрут із операційних обмежень за часом доставки. Для оцінки якості кластеризації було застосовано сім внутрішніх метрик трьох груп: статистичної якості кластерів (Silhouette Score, Davies-Bouldin Index, Calinski-Harabasz Index), балансу навантаження між зонами (коефіцієнт варіації CV та різниця максимального і мінімального розмірів кластерів Δn) та географічної зв'язності (внутрішньокластерна відстань ICD та індекс просторової автокореляції Moran's I). Для агрегованого порівняння застосовано метод суми місць. Встановлено, що оцінка за єдиним коефіцієнтом силуету є недостатньою для вибору алгоритму кластеризації у задачах CFRS-VRP: алгоритми з близькими значеннями силуету суттєво відрізняються за балансом навантаження та географічною зв'язністю зон доставки, що безпосередньо впливає на ефективність маршрутних рішень на другому етапі CFRS. Отримані результати становлять практичний інтерес для розробки системи підтримки прийняття рішень автоматизованого управління доставкою в частині географічного розбиття на зони доставки.