Решение задачи маршрутизации транспорта с чередованием объектов с определением местоположения центров на основе алгоритмов кластеризации
Ключевые слова:
задача маршрутизации транспорта, кластеризация, муравьиный алгоритм, задача коммивояжера
Аннотация
В статье рассматривается задача маршрутизации транспорта с несколькими центрами и чередованием объектов двух видов, особенностью которой является отсутствие исходной информации о местоположении центров. Задача состоит в поиске координат центров и в определении порядка посещения объектов с целью минимизации общей длины маршрута. Предложены математическая модель задачи с разными типами переменных и алгоритм решения поставленной задачи. Его основная идея состоит в кластеризации объектов для нахождения координат центров и последующем определении порядка посещения кластеров. В статье рассматриваются два алгоритма кластеризации: k-means и подход, основанный на применении муравьиных стратегий. Объекты типа центр предлагается располагать в центры масс полученных кластеров. Далее предлагается способ задания матрицы расстояний между кластерами, что позволяет перейти к решению задачи коммивояжера для формирования искомого маршрута. В заключении проведен анализ применяемых алгоритмов кластеризации и сделаны выводы по целесообразности их использования в рамках поставленной задачи. Также проведено сравнение предложенного в статье алгоритма с точным методом решения. Оценена эффективность процедуры поиска местоположения центров.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Grangeon N., Mbiadou Saleu R. G., Deroussi L., Feillet D. and Quilliot A. (2021) The parallel drone scheduling problem with multiple drones and vehicles. European Journal of Operational Research. 300(2). P. 571-589. DOI
2. Bouyahyiouy K. EL and Bellabdaoui A. (2022) The selective full truckload multi-depot vehicle routing problem with time windows: formulation and a genetic algorithm. // International Journal of Supply and Operations Management. 9(3). P. 299–320. DOI
3. Amini A. and Haughton M. (2023) A mathematical optimization model for cluster-based single-depot location-routing e-commerce logistics problems. Supply Chain Analytics. 3(100019). P. 14. DOI
4. Karels V. C. G., Rei W., Veelenturf L. P. and Woensel T. V. (2024) A vehicle routing problem with multiple service agreements. European Journal of Operational Research. 313(1). P. 129–145. DOI
5. Su J., Fu Ya., Gao K., Dong H. and Mou J. (2023) Integrated scheduling problems of open shop and vehicle routing using an ensemble of group teaching optimization and simulated annealing. Swarm and Evolutionary Computation. 83(101373). P. 17. DOI
6. Zhang L., Ding P. and Thompson R. G. (2023) A stochastic formulation of the two-echelon vehicle routing and loading bay reservation problem. Transportation Research Part E. 177(103252). P. 21. DOI
7. Lenstra J. K. and Kan A. H. G. (1981) Complexity of vehicle routing and scheduling problems. Networks. 11(2). P. 221–227. DOI
8. Chen B., Li Ch., Zeng S., Yang S. and Mavrovouniotis M. (2021) An adaptive evolutionary algorithm for bi-level multi-objective VRPs with real-time traffic conditions. IEEE Symposium Series on Computational Intelligence (IEEE SSCI), Orlando, FL, USA. P. 1–8. DOI
9. Posada A., Rivera J. C. and Palacio J. D. (2020) Selective vehicle routing problem: a hybrid genetic algorithm approach. International Conference on Artificial Evolution (Evolution Artificielle), Springer, Cham. 12052. P. 148–161. DOI
10. Medvedev S., Sorokina A. and Medvedeva O. (2019) The vehicle routing problem for several agents among the objects of two types. XXI International Conference Complex Systems: Control and Modeling Problems (CSCMP), Samara. P. 535–540. DOI
11. Medvedev S. N., Medvedeva O. A., Zueva Y. R. and Chernyshova G. D. (2019) Formulation and algorithmization of the interleaved vehicle routing problem. Journal of Physics: Conference Series. 1203(012053). P. 15. DOI
12. Hollo-Szabo A. and Botzheim J. (2022) Bacterial memetic algorithm for asymmetric capacitated vehicle-routing problem. Electronics. 11(3758). P. 27. DOI
13. Bolaji A. L., Okwonu F. Z., Shola P. B., Balogun B. S. and Adubisi Bolaji O. D. (2020) A modified binary pigeon-inspired algorithm for solving the multi-dimensional knapsack problem. Journal of Intelligent Systems. 30(1). P. 90–103. DOI
14. Zhou Y., Hao J., Fu Z., Wang Z. and Lai X. (2021) Variable population memetic search: A case study on the critical node problem. IEEE Transactions on evolutionary computation. 25(1). P. 187–200. DOI
15. Vlasov A. and Stanovskikh A. (2022) The vehicle routing problem in urban road networks. Norwegian Journal of development of the International Science. 82. P. 30–35.
16. Kozlova M. G., Lukianenko V. A. and Makarov O. O. (2023) Multi-agent route planning in hierarchical networks. Proceedings of Voronezh state university. Series: systems analysis and information technologies. 3. P. 32–50. DOI
17. Medvedev S. N. (2021) Mathematical model and exact algorithm for solving the vehicle routing problem with multiple centers with an alternate and a single gathering place. Proceedings of Voronezh state university. Series: systems analysis and information technologies. 1. P. 21–32. DOI
18. Medvedev S. N. (2019) Greedy and adaptive algorithms for multi-depot vehicle routing with object alternation. Automation and Remote Control. 84(3). P. 341–364. DOI
19. Medvedev S. N. (2021) About the optimal solution of the vehicle routing problem with alternation and a single collection point. Modern methods of applied mathematics, control theory and computer technologies (PMTUKT-2021), Voronezh. P. 97–101. (In Russian)
20. Ding Ch. and He X. (2004) K-means clustering via principal component analysis.ICML ‘04: Proceedings of the twenty-first international conference on Machine learning, Berkeley. P. 225–232. DOI
21. Rodzin S., Rodzina O. and El-Khatib S. (2017) Hybrid segmentation ant algorithms of medical images. Bulletin of Chuvash University. 3. P. 262–272. (In Russian)
22. Korbut A. A. and Finkelstein Yu. Yu. (1969) Discrete programming, ed. D. B. Yudin. Moscow, Nauka. 368 p. (In Russian)
23. Medvedev S. N. (2021) A special computational experiment for one vehicle routing problem with object alternation // Information technologies in modeling and control: approaches, methods, solutions: IV All-Russian scientific conference with international participation, Tolyatti. P. 277–284. (In Russian)
2. Bouyahyiouy K. EL and Bellabdaoui A. (2022) The selective full truckload multi-depot vehicle routing problem with time windows: formulation and a genetic algorithm. // International Journal of Supply and Operations Management. 9(3). P. 299–320. DOI
3. Amini A. and Haughton M. (2023) A mathematical optimization model for cluster-based single-depot location-routing e-commerce logistics problems. Supply Chain Analytics. 3(100019). P. 14. DOI
4. Karels V. C. G., Rei W., Veelenturf L. P. and Woensel T. V. (2024) A vehicle routing problem with multiple service agreements. European Journal of Operational Research. 313(1). P. 129–145. DOI
5. Su J., Fu Ya., Gao K., Dong H. and Mou J. (2023) Integrated scheduling problems of open shop and vehicle routing using an ensemble of group teaching optimization and simulated annealing. Swarm and Evolutionary Computation. 83(101373). P. 17. DOI
6. Zhang L., Ding P. and Thompson R. G. (2023) A stochastic formulation of the two-echelon vehicle routing and loading bay reservation problem. Transportation Research Part E. 177(103252). P. 21. DOI
7. Lenstra J. K. and Kan A. H. G. (1981) Complexity of vehicle routing and scheduling problems. Networks. 11(2). P. 221–227. DOI
8. Chen B., Li Ch., Zeng S., Yang S. and Mavrovouniotis M. (2021) An adaptive evolutionary algorithm for bi-level multi-objective VRPs with real-time traffic conditions. IEEE Symposium Series on Computational Intelligence (IEEE SSCI), Orlando, FL, USA. P. 1–8. DOI
9. Posada A., Rivera J. C. and Palacio J. D. (2020) Selective vehicle routing problem: a hybrid genetic algorithm approach. International Conference on Artificial Evolution (Evolution Artificielle), Springer, Cham. 12052. P. 148–161. DOI
10. Medvedev S., Sorokina A. and Medvedeva O. (2019) The vehicle routing problem for several agents among the objects of two types. XXI International Conference Complex Systems: Control and Modeling Problems (CSCMP), Samara. P. 535–540. DOI
11. Medvedev S. N., Medvedeva O. A., Zueva Y. R. and Chernyshova G. D. (2019) Formulation and algorithmization of the interleaved vehicle routing problem. Journal of Physics: Conference Series. 1203(012053). P. 15. DOI
12. Hollo-Szabo A. and Botzheim J. (2022) Bacterial memetic algorithm for asymmetric capacitated vehicle-routing problem. Electronics. 11(3758). P. 27. DOI
13. Bolaji A. L., Okwonu F. Z., Shola P. B., Balogun B. S. and Adubisi Bolaji O. D. (2020) A modified binary pigeon-inspired algorithm for solving the multi-dimensional knapsack problem. Journal of Intelligent Systems. 30(1). P. 90–103. DOI
14. Zhou Y., Hao J., Fu Z., Wang Z. and Lai X. (2021) Variable population memetic search: A case study on the critical node problem. IEEE Transactions on evolutionary computation. 25(1). P. 187–200. DOI
15. Vlasov A. and Stanovskikh A. (2022) The vehicle routing problem in urban road networks. Norwegian Journal of development of the International Science. 82. P. 30–35.
16. Kozlova M. G., Lukianenko V. A. and Makarov O. O. (2023) Multi-agent route planning in hierarchical networks. Proceedings of Voronezh state university. Series: systems analysis and information technologies. 3. P. 32–50. DOI
17. Medvedev S. N. (2021) Mathematical model and exact algorithm for solving the vehicle routing problem with multiple centers with an alternate and a single gathering place. Proceedings of Voronezh state university. Series: systems analysis and information technologies. 1. P. 21–32. DOI
18. Medvedev S. N. (2019) Greedy and adaptive algorithms for multi-depot vehicle routing with object alternation. Automation and Remote Control. 84(3). P. 341–364. DOI
19. Medvedev S. N. (2021) About the optimal solution of the vehicle routing problem with alternation and a single collection point. Modern methods of applied mathematics, control theory and computer technologies (PMTUKT-2021), Voronezh. P. 97–101. (In Russian)
20. Ding Ch. and He X. (2004) K-means clustering via principal component analysis.ICML ‘04: Proceedings of the twenty-first international conference on Machine learning, Berkeley. P. 225–232. DOI
21. Rodzin S., Rodzina O. and El-Khatib S. (2017) Hybrid segmentation ant algorithms of medical images. Bulletin of Chuvash University. 3. P. 262–272. (In Russian)
22. Korbut A. A. and Finkelstein Yu. Yu. (1969) Discrete programming, ed. D. B. Yudin. Moscow, Nauka. 368 p. (In Russian)
23. Medvedev S. N. (2021) A special computational experiment for one vehicle routing problem with object alternation // Information technologies in modeling and control: approaches, methods, solutions: IV All-Russian scientific conference with international participation, Tolyatti. P. 277–284. (In Russian)
Опубликован
2024-02-05
Как цитировать
Медведева, О. А., Пономарев, Д. И., & Медведев, С. Н. (2024). Решение задачи маршрутизации транспорта с чередованием объектов с определением местоположения центров на основе алгоритмов кластеризации. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 58-72. https://doi.org/10.17308/sait/1995-5499/2023/4/58-72
Раздел
Математические методы системного анализа, управления и моделирования
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
