Applied routing problem for a fleet of delivery drones using a modified parallel genetic algorithm
Прикладная задача маршрутизации для парка беспилотных летательных аппаратов с использованием модифицированного параллельного генетического алгоритма
DOI:
https://doi.org/10.21638/11701/spbu10.2022.111Аннотация
Все больше экспертов сходятся во мнении, что в ближайшем будущем большая часть грузовых перевозок будет осуществляться с использованием автоматизированных систем, и из них наиболее перспективной считается доставка с помощью дронов. Такая доставка выиграла бы благодаря независимости от ограничений транспортной инфраструктуры и дорожных условий и обеспечила бы более быструю развозку грузов, а также значительное снижение вредного воздействия на окружающую среду. Технические возможности беспилотных летательных аппаратов улучшаются, поэтому задача их координации и эффективного планирования маршрутов актуальна и пользуется большим спросом. Развитие таких технологий поможет снизить транспортные расходы и улучшить обслуживание клиентов за счет более быстрой доставки. В статье рассматривается прикладная задача маршрутизации для парка беспилотных летательных аппаратов с ограниченной грузоподъемностью для доставки разнородных товаров с возможностью загрузки на нескольких складах. Решение включает в себя новый подход, основанный на смешанном размерном параллельном генетическом алгоритме для поиска рациональных маршрутов доставки товаров различным клиентам, и задачу назначения для уменьшения размера в зависимости от количества складов.
Ключевые слова:
доставка дронами, теория расписания, генетический алгоритм, задача маршрутизации транспорта, несколько депо, несколько продуктов, разделенная доставка
Скачивания
Библиографические ссылки
Poikonen S., Wang X., Golden B. The vehicle routing problem with drones: Extended models and connections. Networks, 2017, no. 70(1), pp. 34–43. https://doi.org/10.1002/net.21746
Theverge.com. Theverge Official Website, Drones could make Amazon’s dream of free delivery profitable — The Verge. 2015. Available at: https://www.theverge.com/2015/6/3/8719659/amazon-prime-air-drone-delivery-profit-free-shipping-small-items (accessed: June 20, 2021).
Radzki G., Thebbotuwawa A., Bocewick G. Uavs flight routes optimization in changing weather conditions — constraint programming approach. Applied Computer Science, 2019, vol. 15, no. 3, pp. 5–20. https://doi.org/10.23743/acs-2019-17
Kaggle.com. Kaggle Official Website, Hash Code Archive — Drone Delivery Homepage, 2021. Available at: https://www.kaggle.com/c/hashcode-drone-delivery (accessed: June 20, 2021).
Euchi J. Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem. J. of Modelling in Management, 2017, vol. 12(1), pp. 2–18. https://doi.org/10.1108/JM2-10-2015-0077
Euchi J., Sadok A. Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones. Physical Communication, 2021, vol. 44. https://doi.org/10.1016/j.phycom.2020.101236
Erdogan S., Miller-Hooks E. A Green Vehicle Routing Problem. Transportation Research. Pt E. Logistics and Transportation Review, 2012, vol. 48(1), pp. 100–114. https://doi.org/10.1016/j.tre.2011.08.001
Fleischmann B. The vehicle routing problem with multiple use of vehicles. Technical report. Hamburg, Universitat Press, 1990.
Azi N., Gendreau M., Potvin J.-V. An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Computers and Operations Research, 2014, vol. 41, pp. 167–173. https://doi.org/10.1016/j.cor.2013.08.016
Cattaruzza D., Absi N., Feillet D., Vidal T. A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Research, 2014, vol. 236(3), pp. 833–848. https://doi.org/10.1016/j.ejor.2013.06.012
Cheikh M., Jarbou B. A variable neighborhood search algorithm for the vehicle routing problem with multiple trips. Electronic Notes in Discrete Mathematics, 2015, vol. 47, pp. 277–284. https://doi.org/10.1016/j.endm.2014.11.036
Ovsyannikov D. A., Mizintseva M. A., Balabanov M. Yu., Durkin A. P., Edamenko N. S., Kotina E. D. Optimization of dynamics of trajectory bundles using smooth and nonsmooth functionals. Pt 1. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2020, vol. 16, iss. 1, pp. 73–84. https://doi.org/10.21638/11701/spbu10.2020.107 (In Russian)
Popkov A. S. Optimal program control in the class of quadratic splines for linear systems. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2020, vol. 16, iss. 4, pp. 462–470. https://doi.org/10.21638/11701/spbu10.2020.411
Drivotin O. I. On numerical solution of the optimal control problem based on a method using the second variation of a trajectory. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2019, vol. 15, iss. 2, pp. 283–295. https://doi.org/10.21638/11701/spbu10.2019.211
Github.com. Github Official Website. Implementation of the MDPGA. Available at: https://github.com/LaLa-Lisa/Drones_delivery_compet (accessed: June 20, 2021).
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
