An Integer Programming Based Approach to Delivery Drone Routing under Load-Dependent Flight Speed

  1. Nishira, Mao 1
  2. Ito, Satoshi 1
  3. Nishikawa, Hiroki 2
  4. Kong, Xiangbo 3
  5. Tomiyama, Hiroyuki 1
  6. González Aguilera, Diego 4
  1. 1 Graduate School of Science and Engineering, Ritsumeikan University, Kusatsu 525-8577, Shiga, Japan
  2. 2 Graduate School of Information Science and Technology, Osaka University, Suita 565-0871, Osaka, Japan
  3. 3 Department of Intelligent Robotics, Faculty of Engineering, Toyama Prefectural University, Imizu 939-0398, Toyama, Japan
  4. 4 Universidad de Salamanca
    info

    Universidad de Salamanca

    Salamanca, España

    ROR https://ror.org/02f40zc51

Mostrar afiliaciones +
Revista:
Drones

ISSN: 2504-446X

Año de publicación: 2023

Volumen: 7

Número: 5

Páginas: 320

Tipo: Artículo

DOI: 10.3390/DRONES7050320 GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Drones

Resumen

Delivery drones have been attracting attention as a means of solving recent logistics issues, and many companies are focusing on their practical applications. Many research studies on delivery drones have been active for several decades. Among them, extended routing problems for drones have been proposed based on the Traveling Salesman Problem (TSP), which is used, for example, in truck vehicle routing problems. In parcel delivery by drones, additional constraints such as battery capacity, payload, and weather conditions need to be considered. This study addresses the routing problem for delivery drones. Most existing studies assume that the drone’s flight speed is constant regardless of the load. On the other hand, some studies assume that the flight speed varies with the load. This routing problem is called the Flight Speed-Aware Traveling Salesman Problem (FSTSP). The complexity of the drone flight speed function in this problem makes it difficult to solve the routing problem using general-purpose mathematical optimization solvers. In this study, the routing problem is reduced to an integer programming problem by using linear and quadratic approximations of the flight speed function. This enables us to solve the problem using general-purpose mathematical optimization solvers. In experiments, we compared the existing and proposed methods in terms of solving time and total flight time. The experimental results show that the proposed method with multiple threads has a shorter solving time than the state-of-the-art method when the number of customers is 17 or more. In terms of total flight time, the proposed methods deteriorate by an average of 0.4% for integer quadratic programming and an average of 1.9% for integer cubic programming compared to state-of-the-art methods. These experimental results show that the quadratic and cubic approximations of the problem have almost no degradation of the solution.

€ Ver financiación

Información de financiación

Financiadores

  • JSPS Kakenhi
    • 20H04160
  • NEDO
    • JPNP22006

Referencias bibliográficas

  • Lu, (2020), J. Adv. Transp., 2020, pp. 8831746, 10.1155/2020/8831746
  • Reiko, S. (2022, November 11). Japan’s Logistics Crisis. Available online: https://www3.nhk.or.jp/nhkworld/en/news/backstories/1771/.
  • Takashima, K. (2022, November 11). Decarbonization in Japan’s Trucking Industry—A Turning Point for Labor and Environmental Solutions. Available online: https://www.mitsui.com/mgssi/en/report/detail/__icsFiles/afieldfile/2022/07/22/2205i_takashima_e.pdf.
  • Hoffman, (2013), Encycl. Oper. Res. Manag. Sci., 1, pp. 1573
  • Funabashi, Y., Taniguchi, I., and Tomiyama, H. (2019, January 3–6). Work-in-progress: Routing of Delivery Drones with Load-dependent Flight Speed. Proceedings of the 2019 IEEE Real-Time Systems Symposium (RTSS), Hong Kong, China.
  • Jeong, (2019), Int. J. Prod. Econ., 214, pp. 220, 10.1016/j.ijpe.2019.01.010
  • Wen, (2022), J. Supercomput., 78, pp. 6567, 10.1007/s11227-021-04127-2
  • Lu, (2022), Knowl.-Based Syst., 235, pp. 107600, 10.1016/j.knosys.2021.107600
  • Yan, (2023), J. Ind. Manag. Optim., 19, pp. 4663, 10.3934/jimo.2022145
  • Wang, (2019), Transp. Res. Part B Methodol., 122, pp. 350, 10.1016/j.trb.2019.03.005
  • Cheng, (2020), Transp. Res. Part B Methodol., 139, pp. 364, 10.1016/j.trb.2020.06.011
  • Masone, (2022), Networks, 80, pp. 193, 10.1002/net.22087
  • Poikonen, (2017), Networks, 70, pp. 34, 10.1002/net.21746
  • (2014), IEEE Trans. Autom. Sci. Eng., 11, pp. 647, 10.1109/TASE.2014.2326952
  • Stolaroff, (2018), Nat. Commun., 9, pp. 409, 10.1038/s41467-017-02411-5
  • Kirschstein, (2020), Transp. Res. Part D Transp. Environ., 78, pp. 102209, 10.1016/j.trd.2019.102209
  • Tseng, C.-M., Chau, C.-K., Elbassioni, K., and Khonji, M. (2017). Flight Tour Planning with Recharging Optimization for Battery-operated Autonomous Drones. CoRR.
  • Muli, C., Park, S., and Liu, M. (2022, January 20–23). A Comparative Study on Energy Consumption Models for Drones. Proceedings of the Global IoT Summit 2022 Conference, Dublin, Ireland.
  • Fontaine, (2022), Eur. J. Oper. Res., 300, pp. 1005, 10.1016/j.ejor.2021.09.009
  • Qian, (2016), Eur. J. Oper. Res., 248, pp. 840, 10.1016/j.ejor.2015.09.009
  • Rosati, S., Krużelecki, K., Traynard, L., and Mobile, B.R. (2013, January 9–13). Speed-aware Routing for UAV Ad-hoc Networks. Proceedings of the IEEE Globecom Workshops (GC Wkshps), Atlanta, GA, USA.
  • Amazon.com Inc (2022, January 01). Amazon Prime Air. Available online: www.amazon.com/primeair.
  • The Irish News (2022, January 01). Google’s Project Wing is Testing Food Delivery Drones in Australia. Available online: https://www.irishnews.com/magazine/technology/2017/11/06/news/google-s-project-wing-is-testing-food-delivery-drones-in-australia-1180920/.
  • Join TechCrunch+ (2022, January 01). How Meituan Is Redefining Food Delivery in China with Drones. Available online: https://techcrunch.com/2021/12/29/meituan-food-drone-delivery-china/.
  • Walmart (2022, January 01). Walmart Invests in DroneUp, the Nationwide On-Demand Drone Delivery Provider. Available online: https://corporate.walmart.com/newsroom/2021/06/17/walmart-invests-in-droneup-the-nationwide-on-demand-drone-delivery-provider.
  • Reinelt, (1995), Handb. Oper. Res. Manag. Sci., 7, pp. 225
  • Bellman, (1962), J. ACM, 9, pp. 61, 10.1145/321105.321111
  • Held, (1962), J. Soc. Ind. Appl. Math., 10, pp. 196, 10.1137/0110015
  • Nuzhet, A., and Burchan, B. (2006). All Computer Science and Engineering Research, Washington University in St. Louis. Report Number: WUCSE-2006-54.
  • Krajník, T., Vonásek, V., Fišer, D., and Faigl, J. (2011, January 15–17). AR-Drone as a Platform for Robotic Research and Educaton. Proceedings of the International Conference on Research and Education in Robotics, Prague, Czech Republic.
  • SkyDrive Inc (2022, June 01). SkyLift Transports Your Payload to Wherever You Need It Most. Available online: https://skydrive2020.com/eng/cargo-drone/spec.html#spec-04.