ФОРМИРОВАНИЕ РАЗВОЗОЧНЫХ МАРШРУТОВ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ
Ключевые слова:
кластеризация, развозочные маршруты, алгоритм k-means, алгоритм DBSCAN, зона транспортного обслуживания, «метод ветвей и границ»Аннотация
Кластеризация представляет собой процесс предварительного объединения точек доставки в группы (кластеры), путём группировки точек по определённым признакам, основываясь на их характеристиках. В результате, маршрут планируется не по всей совокупности точек, а отдельно внутри каждого кластера, что существенно снижает сложность задачи. Целью исследования является определение оптимального метода кластеризации объектов доставки и разработка с его помощью развозочных маршрутов при обслуживании торговой сети города. В данной статье рассмотрена работа алгоритмов DBSCAN и k-means. Сравнительный анализ показал, что DBSCAN не обеспечивает устойчивого результата при высокой плотности точек, тогда как метод k-means формирует четкие кластеры. Оптимальное количество кластеров определено методами «локтя» и «силуэта». Реализация алгоритмов на языке программирования Python и последующее использование «метода ветвей и границ» позволят сократить пробег автомобилей на маршрутах и снизить транспортные расходы на доставку готовой продукции.
Использованные источники
- Бочкарев, А.А., & Клочков, В.Н. (2008). Методология планирования доставки мелкопартионных грузов в условиях крупного города. Вестник СГТУ, 5–15. // Bochkarev, A. A., & Klochkov, V. N. (2008). Metodologiya planirovaniya dostavki melkopartionnykh gruzov v usloviyakh krupnogo goroda. Vestnik SGTU, 5–15. [Methodology for planning small-lot cargo delivery in a large city] (In Russ.)
- Овсянникова, Г.Л., & Шошин, Д.А. (2014). Организация автомобильных перевозок мелких партий груза на предприятии молокозавода. Молодой ученый, 11, 87–90. // Ovsyannikova, G.L., & Shoshin, D.A. (2014). Organizatsiya avtomobilnykh perevozok melkikh partiy gruza na predpriyatii molokozavoda. Molodoy uchenyy, 11, 87–90. [Organization of road transportation of small cargo lots at a dairy plant] (In Russ.)
- Aravind, C. R. (2023). Exploring clustering algorithms: Explanation and use cases. Neptune.ai. https://neptune.ai/blog/clustering-algorithms
- Mokhammad, R., & Indratno, S. W. (2021). Dynamic items delivery network: Prediction and clustering. Heliyon, 7(8), e07640. https://doi.org/10.1016/j.heliyon.2021.e07640
- Тюрин, А. Г., & Зуев, И. О. (2014). Кластерный анализ: методы и алгоритмы кластеризации. Вестник МГТУ МИРЭА, 2, 86–97. // Tyurin, A.G., & Zuev, I.O. (2014). Klasternyy analiz: metody i algoritmy klasterizatsii. Vestnik MGTU MIREA, 2, 86–97. [Cluster analysis: methods and clustering algorithms] (In Russ.)
- Семенов, Ю. Н., & Семенова, О. С. (2016). Применение методов кластеризации при организации междугородных перевозок грузов. Вестник КузГТУ, 6, 201–204. // Semenov, Yu. N., & Semenova, O. S. (2016). Primenenie metodov klasterizatsii pri organizatsii mezhdugorodnykh perevozok gruzov. Vestnik KuzGTU, 6, 201–204. [Application of clustering methods in organizing intercity freight transportation] (In Russ.)
- Апельцин, Л. (2023). Data Science в действии. Санкт-Петербург: Питер. // Apeltsin, L. (2023). Data Science v deystvii. Saint Petersburg: Piter. [Data Science in action] (In Russ.)
- IT-ресурс Хабр. (2023). Кластеризация в ML: от теоретических основ популярных алгоритмов к их реализации с нуля на Python. https://habr.com/ru/articles/798331/ // IT-resurs Khabr. (2023). Klasterizatsiya v ML: ot teoreticheskikh osnov populyarnykh algoritmov k ikh realizatsii s nulya na Python. [Clustering in ML: from theoretical foundations of popular algorithms to their implementation from scratch in Python] (In Russ.)
- Кугаевских, А. В., Муромцев, Д. И., & Кирсанова, О. В. (2022). Классические методы машинного обучения: учебное пособие. Санкт-Петербург: НИУ ИТМО. // Kugaevskikh, A. V., Muromtsev, D. I., & Kirsanova, O. V. (2022). Klassicheskie metody mashinnogo obucheniya: uchebnoe posobie. Saint Petersburg: NRU ITMO. [Classical machine learning methods: study guide] (In Russ.)
- Duran, B., & Odell, P. (1977). Cluster analysis. New York: Springer. // Duran, B., & Odell, P. (1977). Klasternyy analiz. Moscow: Statistika. [Cluster analysis] (In Russ.)
- Ершов, К. С., & Романова, Т. Н. (2016). Анализ и классификация алгоритмов кластеризации. Новые информационные технологии в автоматизированных системах. // Ershov, K. S., & Romanova, T. N. (2016). Analiz i klassifikatsiya algoritmov klasterizatsii. Novye informatsionnye tekhnologii v avtomatizirovannykh sistemakh. [Analysis and classification of clustering algorithms] (In Russ.)
- IT-resource GeeksforGeeks. (2025). Elbow method vs. silhouette score: Which is better? https://www.geeksforgeeks.org/machine-learning/elbow-method-vs-silhouette-score-which-is-better/
- Домке, Э. Р., & Жесткова, С. А. (2014). Методы оптимизации маршрутных схем развозки грузов автомобильным транспортом: учебное пособие. Пенза: ПГУАС. // Domke, E. R., & Zhestkova, S. A. (2014). Metody optimizatsii marshrutnykh skhem razvozki gruzov avtomobilnym transportom. Penza: PGUAS. [Methods for optimizing road freight distribution routes] (In Russ.)
- Павлов, Л. А., & Первова, Н. В. (2020). Структуры и алгоритмы обработки данных (2-е изд.). Санкт-Петербург: Лань. // Pavlov, L. A., & Pervova, N. V. (2020). Struktury i algoritmy obrabotki dannykh (2nd ed.). Saint Petersburg: Lan. [Data structures and processing algorithms] (In Russ.)
- Галяутдинов, Р. Р. (2023). Задача коммивояжера — метод ветвей и границ. https://galyautdinov.ru/post/zadacha-kommivoyazhera // Galyautdinov, R. R. (2023). Zadacha kommivoyazhera — metod vetvey i granits. [The traveling salesman problem — branch and bound method] (In Russ.)
Vdovin, V., Mashekenova, А., Duisen, А., & Suresh, А.
(2026).
CREATING DELIVERY ROUTES USING CLUSTERING ALGORITHMS.
EKTU Journal of Engineering Sciences,
1(1),
17-29.
https://doi.org/10.51885/3134-8009_JES_2026_1_2