Особливості застосування алгоритму Clarke–Wright у задачах multi-depot кластеризації

Abstract

The paper proposes a methodology for studying the efficiency of the Clarke–Wright algorithm in multi-depot clustering problems with different spatial data structures. Three test datasets (uniform, clustered, and combined) with weighted vertices were generated. The influence of cluster capacity constraints and the choice of the initial depot on the cluster structure and route lengths was analyzed. Experimental results demonstrate that the structure of input data can significantly affect the efficiency of the algorithm and opens prospects for further research in optimal routing problems.

У роботі запропоновано методику дослідження ефективності алгоритму Clarke–Wright у задачах multi-depot кластеризації з різною просторовою структурою даних. Сформовано три тестові датасети (рівномірний, кластеризований та комбінований) з ваговими характеристиками вершин. Проведено аналіз впливу обмеження сумарної потужності кластерів та вибору початкового депо на форму кластерів і довжину маршрутів. Результати експериментів демонструють, що структура вхідних даних може суттєво впливати на ефективність алгоритму та відкриває перспективи для подальших досліджень задач оптимальної маршрутизації.