Applied routing problem for a fleet of delivery drones using a modified parallel genetic algorithm
DOI:
https://doi.org/10.21638/11701/spbu10.2022.111Abstract
More and more experts agree that in the near future, most freight traffic will be carried out using automated systems, and of them drone delivery is considered to be the most promising. Drone delivery would benefit by independence from the limitations of transport infrastructure and road conditions and would ensure cargo delivery with rapid turnaround times, as well as a significant reduction of environmental impact. The technical capabilities of unmanned aerial vehicles improve year by year, so the task of coordinating drones and effectively planning routes is relevant and in great demand. The development of such technologies will help reduce transportation costs and improve customer service through faster delivery. This article discusses the applied routing problem for a fleet of drones with limited load capacity for the delivery of heterogeneous goods with the possibility of loading in multiple warehouses from an international optimization competition. The solution includes new approach based on a mixed dimensional parallel genetic algorithm (MDPGA) for finding rational routes for delivering goods to various customers and an assignment problem to reduce the dimension depending on the number of warehouses.
Keywords:
drone delivery, scheduling, genetic algorithm, vehicle routing problem, multidepot, multi-trip, multi-product, split-delivery
Downloads
References
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).
Downloads
Published
How to Cite
Issue
Section
License
Articles of "Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
