VRP of Drones Considering Power Consumption Rate and Wind Effects

Kim, Seongheon; Kim, Suhwan

doi:10.2478/logi-2022-0019

Abstract

The drone industry is one of the most important areas of the Fourth Industrial Revolution. In the drone industry, delivery systems using drones are now facing commercialization as they have undergone many experiments and discussions. The purpose of this study is to find the best route in a delivery system using a drone. In this study, we have developed the existing Vehicle Routing Problem (VRP) into a more realistic mathematical model considering the two differences between drones and vehicles; one is that power consumption varies with the weight of the loaded cargo and the other is that velocity is influenced by wind. This study also presents an Ant Colony System (ACS) algorithm to effectively solve VRP, a well-known NP-hard problem. The methodology of this study is quite successful and is expected to enable more realistic and effective routing decisions.

References

[1] Danzig, G.B. & Ramser, J.H. (1959). The truck dispatching problem. Management Science 6(1), 80-91. DOI: 10.1287/mnsc.6.1.80.
Open DOI Search in Google Scholar Back to article
[2] Braekers, K., Ramaekers, K. & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering 99, 300-313. DOI: 10.1016/j.cie.2015.12.007.
Open DOI Search in Google Scholar Back to article
[3] Otto, A., Agatz, N., Campbell, J., Golden, B. & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey. Networks 72 (4), 411–458. DOI: 10.1002/net.21818.
Open DOI Search in Google Scholar Back to article
[4] Amazon.com Inc. (2016). Amazon Prime Air. Retrieved August 25, 2021, from www.amazon.com/primeair
Back to article
[5] DHL International GmbH (2014). DHL Parcelcopter Launches Initial Operations for Research Purposes. Retrived August 25, 2021, from http://www.dhl.com/en/press/releases/releases_2014/group/dhl_parcelcopter_launches_initial_operations_for_research_purposes
Back to article
[6] Wing, P. (2018). Project wing. Retrieved September 5, 2021, from https://x.company/projects/wing/
Back to article
[7] UPS YouTube Channel. (2017). UPS tests residential delivery via drone. Retrived August 25, 2021, from https://www.youtube.com/watch?v=HEkHhZDuLhU
Back to article
[8] Aljazeera. (2014, Feburary). UAE to Use Drones for Citizen Services. Retrieved November 10, 2021, from http://www.aljazeera.com/news/middleeast/2014/02/uae-use-drones-government-services-20142121717319272.html
Back to article
[9] Murray, C.C. & Chu, A.G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies 54, 86-109. DOI: 10.1016/j.trc.2015.03.005.
Open DOI Search in Google Scholar Back to article
[10] Agatz, N., Bouman, P. & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science 52(4), 965-981. DOI: 10.1287/trsc.2017.0791.
Open DOI Search in Google Scholar Back to article
[11] Dayarian, I., Savelsbergh, M. & Clarke J.P. (2018). Same-day delivery with drone resupply. Tech. rep. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology
Search in Google Scholar Back to article
[12] Wang, X., Poikonen, S. & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters 11(4), 679-697. DOI: 10.1007/s11590-016-1035-3.
Open DOI Search in Google Scholar Back to article
[13] Poikonen, S., Wang, X. & Golden, B. (2017). The vehicle routing problem with drones: Extended models and connections. Networks 70(1), 34-43. DOI: 10.1002/net.21746.
Open DOI Search in Google Scholar Back to article
[14] Carlsson, J.G. & Song, S. (2017). Coordinated logistics with a truck and a drone. Management Science 64(9), 4052-4069. DOI: 10.1287/mnsc.2017.2824.
Open DOI Search in Google Scholar Back to article
[15] Ulmer, M.W. & Thomas, B.W. (2018). Same-day delivery with heterogeneous fleets of drones and vehicles. Networks 72(4), 475-505. DOI: 10.1002/net.21855.
Open DOI Search in Google Scholar Back to article
[16] Dorling, K., Heinrichs, J., Messier, G.G. & Magierowski, S. (2016). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(1), 70-85. DOI: 10.1109/TSMC.2016.2582745.
Open DOI Search in Google Scholar Back to article
[17] Poikonen, S. & Golden, B. (2020). Multi-visit drone routing problem. Computers & Operations Research 113, 104802. DOI: 10.1016/j.cor.2019.104802.
Open DOI Search in Google Scholar Back to article
[18] Sorbelli, F.B., Corò, F., Das, S.K. & Pinotti, C.M. (2020). Energy-constrained delivery of goods with drones under varying wind conditions. IEEE Transactions on Intelligent Transportation Systems, 22(9), 6048-6060. DOI: 10.1109/TITS.2020.3044420.
Open DOI Search in Google Scholar Back to article
[19] Palazzetti, L., Pinotti, C.M. & Rigoni, G. (2021). A run in the wind: favorable winds make the difference in drone delivery. In 2021 17th International Conference on Distributed Computing in Sensor Systems (DCOSS), 109-116. IEEE. DOI: 10.1109/DCOSS52077.2021.00031.
Open DOI Search in Google Scholar Back to article
[20] Hwang, M.H., Cha, H.R. & Jung, S.Y. (2018). Practical endurance estimation for minimizing energy consumption of multirotor unmanned aerial vehicles. Energies, 11(9), 2221. DOI: 10.3390/en11092221.
Open DOI Search in Google Scholar Back to article
[21] 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. DOI: 10.1287/opre.12.4.568.
Open DOI Search in Google Scholar Back to article

VRP of Drones Considering Power Consumption Rate and Wind Effects

Abstract

Paradigm

My account