Abstract
Given is a production system in which material handling operations are carried out by a fleet of UAVs. A problem has been formulated for this case of cyclic multi-product batch production flow, which combines the problems of split delivery-vehicle routing with time windows and deployment of battery swapping depots. It is assumed that the times of execution of pickup and delivery operations are known. During these operations, workpieces following different production routes reach and leave workstations cyclically. Given is the number of battery swapping depots and their potential arrangement. Given is also the rate of power consumption by an UAV in hovering mode or flying at a constant speed as well as during take-off and landing. The goal is to find the number of UAVs and the routes they fly to serve all the workstations periodically, within a given takt time, without violating constraints imposed by the due-time pickup/delivery operations and collision-free movement of UAVs. A declarative model of the analysed case allows to view the problem under consideration as a constraint satisfaction problem and solve it in the Oz Mozart programming environment.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bocewicz, G., Nielsen P., Banaszak, Z., Thibbotuwawa, A.: Routing and scheduling of unmanned aerial vehicles subject to cyclic production flow constraints. In: Proceedings of 15th International Conference on Distributed Computing and Artificial Intelligence (2018, in print)
Gino, J.L., Seonjin, K., Jaeyoung, C., Yibin, G., Amin, K.: Multi-UAV pre-positioning and routing for power network damage assessment. IEEE Trans. Smart Grid PP(99), 1 (2016)
Gorecki, T., Piet-Lahanier, H., Marzat, J., Balesdent, M.: Cooperative guidance of UAVs for area exploration with final target allocation. IFAC Proc. Vol. 46(19), 260–265 (2013)
Guettier, C., Lucas, F.: A constraint-based approach for planning unmanned aerial vehicle activities. Constraint Satisfaction Plan. Sched. 31(5), 486–497 (2017)
Guerriero, F., Surace, R., Loscri, V., Natalizio, E.: A multi-objective approach for unmanned aerial vehicle routing problem with soft time windows constraints. Appl. Math. Model. 38(3), 839–852 (2014)
Hayat, S., Yanmaz, E., Muzaffar, R.: Survey on unmanned aerial vehicle networks for civil applications: a communications Viewpoint. IEEE Commun. Surv. Tutorials 18, 1 (2016). https://doi.org/10.1109/COMST.2016.2560343
Ho, H.-M., Ouaknine, J.: The cyclic-routing UAV problem is PSPACE-complete. In: Pitts, A. (ed.) FoSSaCS 2015. LNCS, vol. 9034, pp. 328–342. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46678-0_21
Suzuki, K.A.O., Kemper Filho, P., Morrison, J.R.: Automatic battery replacement system for UAVs: analysis and design. J. Intell. Robot Syst. 65, 563–586 (2012). https://doi.org/10.1007/s10846-011-9616-y
Manyam, S.G., Rasmussen, S., Casbeer, D.W., Kalyanam, K., Manickam, S.: Multi-UAV routing for persistent intelligence surveillance and reconnaissance missions. In: 2017 International Conference on Unmanned Aircraft Systems (ICUAS), USA, pp. 573–580 (2017)
Michini, B., et al.: Automated battery swap and recharge to enable persistent UAV missions. In: Infotech@Aerospace 2011, American Institute of Aeronautics and Astronautics (2011)
Myers, D., Batta, R., Karwan, M.: A real-time network approach for including obstacles and fight dynamics in UAV route planning. J. Defense Model. Simul. Appl. Methodol. Technol. 13, 291–306 (2016)
Nikhil, N.: The multiple unmanned air vehicle persistent surveillance problem: a review. Machines 2, 13–72 (2014). https://doi.org/10.3390/machines2010013
Park, Y., Khosiawan, Y., Moon, I., Janardhanan, M.N., Nielsen, I.: Scheduling system for multiple unmanned aerial vehicles in indoor environments using the CSP approach. In: Czarnowski, I., Caballero, A.M., Howlett, Robert J., Jain, Lakhmi C. (eds.) Intelligent Decision Technologies 2016. SIST, vol. 56, pp. 77–87. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39630-9_7
Sitek, P., Wikarek, J.: A hybrid approach to the optimization of multiechelon systems. Math. Prob. Eng. 2015, Article ID 925675, 12 pages (2015)
Shao, S., Guo, S., Qiu, X.: A mobile battery swapping service for electric vehicles based on a battery swapping van. Energies 10, 1667 (2017). https://doi.org/10.3390/en10101667
Tan, K.C., Lee, L.H., Zhu, Q.L., Ou, K.: Heuristic methods for vehicle routing problem with time windows. Artif. Intell. Eng. 15, 281–295 (2001)
Thibbotuwawa, A., Nielsen, P.: Unmanned aerial vehicle routing problems: a literature review (in print)
Zhihao, L., Zhong, L., Jianmai, S.: A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors 17, 1144 (2017)
Acknowledgements
The work was carried out as part of the POIR.01.01.01-00-0485/17 project, “Development of a new type of logistic trolley and methods of collision-free and deadlock-free implementation of intralogistics processes”, financed by NCBiR.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Bocewicz, G., Nielsen, P., Banaszak, Z., Thibbotuwawa, A. (2018). Deployment of Battery Swapping Stations for Unmanned Aerial Vehicles Subject to Cyclic Production Flow Constraints. In: Damaševičius, R., Vasiljevienė, G. (eds) Information and Software Technologies. ICIST 2018. Communications in Computer and Information Science, vol 920. Springer, Cham. https://doi.org/10.1007/978-3-319-99972-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-99972-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99971-5
Online ISBN: 978-3-319-99972-2
eBook Packages: Computer ScienceComputer Science (R0)