IJMEMES logo

International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749


Route Planning of Unmanned Aerial Vehicles under Recharging and Mission Time Constraints

Route Planning of Unmanned Aerial Vehicles under Recharging and Mission Time Constraints

Kriangsak Phalapanyakoon
Department of Computer Engineering, King Mongkut’s University of Technology, Thonburi, Bangkok, Thailand.

Peerapon Siripongwutikorn
Department of Computer Engineering, King Mongkut’s University of Technology, Thonburi, Bangkok, Thailand.

DOI https://doi.org/10.33889/IJMEMS.2021.6.5.087

Received on May 06, 2021
  ;
Accepted on September 27, 2021

Abstract

This paper investigates the problem of route planning for rechargeable unmanned aerial vehicles (UAV) under the mission time constraint in cases where more than one trip per round is required due to limited battery capacities. The goal is to determine the number of UAVs to be deployed and the flying paths that minimize the total mission cost. Unlike previous works, the electric cost incurred by UAV recharging proportional to actual flying distances is incorporated into our model. The problem is formulated as a mixed-integer programming model to minimize the sum of electric charging cost, the UAV usage cost, and the penalty cost from the violation of the mission time constraint. Extensive numerical experiments are conducted to examine the integrity and performance of the proposed model under various model parameters and deployment scenarios in grid areas and a real terrain area. The optimal solutions can be obtained for small-scale problem instances in a reasonable runtime. For large-scale problems, only feasible solutions can be obtained due to limited computational resources.

Keywords- Unmanned aerial vehicle (UAV), Route planning, Rechargeable unmanned aerial vehicles, Mission time constraint, Mixed-integer programming (MIP).

Citation

Phalapanyakoon, K., & Siripongwutikorn, P. (2021). Route Planning of Unmanned Aerial Vehicles under Recharging and Mission Time Constraints. International Journal of Mathematical, Engineering and Management Sciences, 6(5), 1439-1459. https://doi.org/10.33889/IJMEMS.2021.6.5.087.

Conflict of Interest

The authors confirm that there is no conflict of interest to declare for this publication.

Acknowledgements

This research is supported by the Petchra Pra Jom scholarship from King Mongkut’s University of Technology Thonburi.

References

Alonso, F., Alvarez, M.J., & Beasley, J.E. (2008). A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society, 59, 963-976. https://doi.org/10.1057/palgrave.jors.2602405.

Aurambout, J.P., Gkoumas, K., & Ciuffo, B. (2019). Last mile delivery by drones: an estimation of viable market potential and access to citizens across European cities. European Transport Research Review, 11(30), 1-21. https://doi.org/10.1186/s12544-019-0368-2.

Authority, M.E. (2020). Energy charge of residential. URL: https://www.mea.or.th/en/profile/109/111.

Ayadi, R., & Benadada, Y. (2013). Memetic algorithm for a multi-objective vehicle routing problem with multiple trips. International Journal of Computer Science and Applications, 10(2), 72-91.

Choi, Y., Robertson, B., Choi, Y., & Mavris, D. (2019). A multi-trip vehicle routing problem for small unmanned aircraft systems-based urban delivery. Journal of Aircraft, 56(6), 2309-2323. https://doi.org/10.2514/1.C035473

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(1), 306-315. https://doi.org/10.1016/j.cor.2017.04.011.

Conrad, R.G., & Figliozzi, M.A. (2011, May). The recharging vehicle routing problem. In Proceedings of the 2011 Industrial Engineering Research Conference, (pp. 8). IISE Norcross, GA.

Dantzig, G.B., & Ramser, J.H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. https://doi.org/10.1287/mnsc.6.1.80.

DJI. (2020). Spark specs. URL: https://www.dji.com/spark/info#specs.

Dorling, K., Heinrichs, J., Messier, G.G., & Magierowski, S. (2017). Vehicle routing problems for drone delivery. In IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85. https://doi.org/10.1109/TSMC.2016.2582745.

Han, Y.Q., Li, J.Q., Liu, Z., Liu, C., & Tian, J. (2020). Metaheuristic algorithm for solving the multi-objective vehicle routing problem with time window and drones. International Journal of Advanced Robotic Systems, 17(2). https://doi.org/10.1177/1729881420920031.

Hiermann, G., Puchinger, J., Ropke, S., & Hartl, R.F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252(3), 995-1018. https://doi.org/10.1016/j.ejor.2016.01.038.

International Business Machines Corporation. (2021, December). IBM ilog cplex optimization studio (Version 12.10.0.0). URL: https://www.ibm.com/products/ ilog-cplex-optimization-studio.

Joshi, D. (2019). Drone technology uses and applications for commercial, industrial and military drones in 2020 and the future. URL: https://www.businessinsider.com/drone-technology-uses-applications.

Kabcome, P., & Mouktonglang, T. (2015). Vehicle routing problem for multiple product types, compartments, and trips with soft time windows. International Journal of Mathematics and Mathematical Sciences, 2015, 1-9. https://doi.org/10.1155/2015/126754.

Kitjacharoenchai, P., & Lee, S. (2019). Vehicle routing problem with drones for last mile delivery. Procedia Manufacturing, 39, 314-324. https://doi.org/10.1016/j.promfg.2020.01.338.

Miller, C.E., Tucker, A.W., & Zemlin, R.A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326-329. https://doi.org/10.1145/321043.321046.

Penna, P.H.V., Afsar, H.M., Prins, C., & Prodhon, C. (2016). A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. IFAC-PapersOnLine, 49(12), 955-960. https: //doi.org/10.1016/j.ifacol.2016.07.899.

Thailand, D.R. (2020). Spark drone for rent. URL: https://www.facebook.com/dronerobotics.in.th/.

Troudi, A., Addouche, S.A., Dellagi, S., & Mhamedi, A.E. (2018). Sizing of the drone delivery fleet considering energy autonomy. Sustainability, 10(9), 1-17. https://doi.org/10.3390/su10093344.

Yu, K., Budhiraja, A.K., Buebel, S., & Tokekar, P. (2019). Algorithms and experiments on routing of unmanned aerial vehicles with mobile recharging stations. Journal of Field Robotics, 36(3), 602-616. https://doi.org/10.1002/rob.21856.

Zhen, L., Ma, C., Wang, K., Xiao, L., & Zhang, W. (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E: Logistics and Transportation Review, 135(1), 1-21. https://doi.org/10.1016/j.tre.2020.101866.

Zmazek, B., Taranenko, A., & Smid, M. (2005). Capacitated VRP with time windows and multiple trips within working day. In 27th International Conference on Information Technology Interfaces, (pp. 104-109). IEEE. Cavtat, Croatia. https://doi.org/10.1109/ITI.2005.1491105.