Drone pick-up and delivery path planning problem considering charging facilities

Abstract

Drone delivery has been widely used in various areas of e-commerce, such as delivering packages, takeaways, etc. For the problem of logistic package delivery in remote rural areas, a drone only delivery system which considers integrating mixed sequences of pick-up and delivery is designed. In this system, the drone range limit, energy consumption constraint, weight constraint, pick-up and delivery mode are comprehensively considered. A three stage planning model is proposed to solve this problem, which is solved by SCIP and Advanced Clark and Wright Saving-Improved and Repaired Crow Search Algorithm (ACWS-IRCSA). In numerical experiments and analyses, the case of Hongergole town, Xilingole prefecture, Abaga county, Inner Mongolia Autonomous Region, China is designed for analysis. The parameters and algorithms are compared and analyzed. The experiments show that adding charging facilities triples the drone’s service radius, significantly improving coverage. Additionally, for reverse logistics with 100% higher pickup demand, energy consumption only rises by ~50%. Extensive studies are conducted based on the characteristics of the problem, such as changes in drone delivery coverage before and after the addition of charging facilities; the impact of reverse logistics services on energy consumption; the influence of cargo weight on the number of paths, charging times and the remaining power before charging.

Graphical abstract

Keywords

drone / pick-up and delivery / path planning problem / charging facility

References

[1] Amazon (2021). Amazon.com: Prime air. Available at the website of amazon.com

[2] Bi H L, Gu Y Y, Lu F Q, Mahreen S, (2025). Site selection of electric vehicle charging station expansion based on GIS-FAHP-MABAC. Journal of Cleaner Production, 507: 145557

[3] Bi H L, Zhu X, Lu F Q, Huang M, (2023). The meal delivery routing problem in e-commerce platforms under the shared logistics mode. Journal of Theoretical and Applied Electronic Commerce Research, 18( 4): 1799–1819

[4] Chai H (2018). First drone delivery license issued. Available at the website of chinadaily.com

[5] Chauhan D, Unnikrishnan A, Figliozzi M, (2019). Maximum coverage capacitated facility location problem with range constrained drones. Transportation Research Part C, Emerging Technologies, 99: 1–18

[6] Cheng C, Adulyasak Y, Rousseau L, (2020). Drone routing with energy function: Formulation and exact algorithm. Transportation Research, Part B: Methodological, 139: 364–387

[7] Clarke G, Wright J W, (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12( 4): 568–581

[8] Coelho B N, Coelho V N, Coelho I M, Ochi L S, Haghnazar K R, Zuidema D, Lima M S F, da Costa A R, (2017). A multi-objective green UAV routing problem. Computers & Operations Research, 88: 306–315

[9] Cokyasar T, Dong W, Jin M, Verbas İ Ö, (2021). Designing a drone delivery network with automated battery swapping machines. Computers & Operations Research, 129: 105177

[10] Dorling K, Heinrichs J, Messier G G, Magierowski S, (2017). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics:. Systems, 47( 1): 70–85

[11] Figliozzi M A, (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO₂e emissions. Transportation Research Part D, Transport and Environment, 57: 251–261

[12] Gamrath GAnderson DBestuzheva K (2020). The SCIP Optimization Suite 7.0. ZIB-Report 20–10. Available at the website of optimization-online.org

[13] Ghelichi Z, Gentili M, Mirchandani P B, (2021). Logistics for a fleet of drones for medical item delivery: A case study for Louisville, KY. Computers & Operations Research, 135: 105443

[14] Hong IKuby MMurray A T (2017). A deviation flow refueling location model for continuous space: A commercial drone delivery system for urban areas. In: Griffith D. Chun Y. Dean D. eds. Advances in Geocomputation. Cham: Springer. pp. 199–212

[15] Hong I, Kuby M, Murray A T, (2018). A range-restricted recharging station coverage model for drone delivery service planning. Transportation Research Part C, Emerging Technologies, 90: 198–212

[16] Jeon A, Kang J, Choi B, Kim N, Eun J, Cheong T, (2021). Unmanned aerial vehicle last-mile delivery considering backhauls. IEEE Access: Practical Innovations, Open Solutions, 9: 85017–85033

[17] Kim S J, Lim G J, Cho J, Côté M J, (2017). Drone-aided healthcare services for patients with chronic diseases in rural areas. Journal of Intelligent & Robotic Systems, 88( 1): 163–180

[18] Liu C, Chen H, Li X, Liu Z, (2021). A scheduling decision support model for minimizing the number of drones with dynamic package arrivals and personalized deadlines. Expert Systems with Applications, 167: 114157

[19] Liu Y, (2019). An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research, 111: 1–20

[20] Lu F Q, Chen W, Feng W, Bi H L, (2023). 4PL routing problem using hybrid beetle swarm optimization. Soft Computing, 27( 22): 17011–17024

[21] Lu F Q, Du Z C, Wang Z T, Wang L, Wang S Y, (2025a). Towards enhancing the crowdsourcing door-to-door delivery: An effective model in Beijing. Journal of Industrial and Management Optimization, 21( 3): 2371–2395

[22] Lu F Q, Meng F, Bi H L, (2025b). Scenario deduction of explosion accident based on Fuzzy Dynamic Bayesian Network. Journal of Loss Prevention in the Process Industries, 96: 105613

[23] Lu F Q, Jiang R, Bi H L, Gao Z Y, (2024). Order distribution and routing optimization for takeout delivery under drone–rider joint delivery mode. Journal of Theoretical and Applied Electronic Commerce Research, 19( 2): 774–796

[24] Luo Q, Wu G H, Ji B, Wang L, Suganthan P N, (2022). Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time windows. IEEE Transactions on Intelligent Transportation Systems, 23( 8): 13011–13025

[25] Pachayappan M, Sudhakar V, (2021). A solution to drone routing problems using docking stations for pickup and delivery services. Transportation Research Record: Journal of the Transportation Research Board, 2675( 12): 1056–1074

[26] Parragh S N, Doerner K F, Hartl R F, (2008a). A survey on pickup and delivery problems Part I: Transportation between customers and depot. J Betriebswirtsch, 58( 1): 21–51

[27] Parragh S N, Doerner K F, Hartl R F, (2008b). A survey on pickup and delivery problems Part II: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft, 58( 2): 81–117

[28] People's Daily Online (2018). Drones become standard vehicles in China’s logistics industry. Available at the website of people.com

[29] Rave A, Fontaine P, Kuhn H, (2023). Drone location and vehicle fleet planning with trucks and aerial drones. European Journal of Operational Research, 308( 1): 113–130

[30] Salama M R, Srinivas S, (2022). Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites. Transportation Research Part E, Logistics and Transportation Review, 164: 102788

[31] Shavarani S M, Mosallaeipour S, Golabi M, İzbirak G, (2019). A congested capacitated multi-level fuzzy facility location problem: An efficient drone delivery system. Computers & Operations Research, 108: 57–68

[32] Torabbeigi M, Lim G J, Kim S J, (2020). Drone delivery scheduling optimization considering payload-induced battery consumption rates. Journal of Intelligent & Robotic Systems, 97( 3–4): 471–487

[33] Wong R (2019). FAA approves Google's drone delivery service for commercial use in the U.S. Available at the website of mashable.com

[34] Yin Y, Li D, Wang D, Yu Y, Cheng T C E, (2025). Truck‐drone pickup and delivery service optimization with availability profiles. Naval Research Logistics, 72( 4): 534–565

RIGHTS & PERMISSIONS

Higher Education Press