Route Optimization for Medication Delivery of Covid-19 Patients with Drones

Abstract

With the developments in information technologies and the intense use of online commerce, the use of drones in distribution process has gained importance. In order to transport products to more than one location, drones can perform the distribution by following a specific route, as in the traveling salesman problem. Drones provide advantages over land transportation since they are not affected by the traffic congestion and can be used autonomously. However, the limited battery durations increase the importance of using the optimum route in distribution processes. In this study, it is aimed to use drones in drug distribution. Nowadays, due to the Covid-19 pandemic, it is aimed to distribute the drugs for the patients in an optimum way with drones. In this study, it is aimed to find the optimized routes for drones in drug distribution since Covid-19 medicine distribution is a time-critic mission. Since the number of patients in a certain area may increase very quickly, it is ensured that the patients are divided into clusters and the optimum route is determined for each cluster. We propose a hybrid model consisting of a combination of K-means clustering and Ant Colony algorithms. In particular, Covid-19 patients use the mobile part of the developed application on their smartphones and transmit their medication requests to our central server. We have compared the performance of Ant Colony, Artificial Bee and Genetic algorithm metaheuristics at the stage of determining the most suitable route according to the demands collected dynamically on the central server. In the process of determining the most suitable route, Ant Colony algorithm yields the closest to optimum results for different location groups. We have developed the mobile and web site of the application to validate the proposed drug delivery model.

Keywords

• Metaheuristics
• TSP
• K-means
• Drone
• Drone Delivery
• Optimization
• Medication Delivery

Kaynakça

1. [1] Z., Tang, W. J., van Hoeve, P., Shaw, “A Study on the Traveling Salesman Problem with a Drone.” In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Thessaloniki, Greece, 557-564, June, 2019.
2. [2] D., Rojas Viloria, E. L., Solano‐Charris, A., Muñoz‐Villamizar, J. R., Montoya‐Torres, “Unmanned Aerial Vehicles/Drones In Vehicle Routing Problems: A Literature Review”, International Transactions in Operational Research, 28(4), 1626-1657, 2021.
3. [3] S., Kim, I, Moon. “Traveling Salesman Problem With A Drone Station”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49(1), 42-52, 2018.
4. [4] M. Y., Özsağlam, M., Çunkaş, “Optimizasyon Problemlerinin Çözümü İçin Parçaçık Sürü Optimizasyonu Algoritması”, Politeknik Dergisi, 11(4), 299-305, 2008.
5. [5] Internet: E. Adams. DHL’s Tilt-Rotor ‘Parcelcopter’ is Both Awesome and Actually Useful, https://www.wired.com/2016/05/dhls-new-drone-can-ship-packages-around-alps/, 16.04.2021
6. [6] E. E., Yurek, H. C., Ozmutlu, “A Decomposition-Based Iterative Optimization Algorithm for Traveling Salesman Problem with Drone”, Transportation Research Part C: Emerging Technologies, 91, 249-262, 2018.
7. [7] C., Ercan, C. Gencer, “A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets” Gazi University Journal of Science, 31(3), 863-877, 2018.
8. [8] D., Karaboga, B., Gorkemli, “A Combinatorial Artificial Bee Colony Algorithm For Traveling Salesman Problem”, International Symposium on Innovations in Intelligent Systems and Applications, Istanbul, Turkey, 50-53, June, 2011.

9. [9] A.P. Adewole, K. Otubamowo, T.O. Egunjobi, K.M. Ng, “A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving The Travelling Salesman Problem”, Int. J. Appl. Inf. Syst. (IJAIS), 4 (4), 6-12, 2012.
10. [10] S., Kuzu, O. Önay, U. Şen, M., Tunçer, B., Yıldırım, T., Keskintürk, “Gezgin Satıcı Problemlerinin Metasezgiseller ile Çözümü”, İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 1-27, 2014.
11. [11] S. A., Haroun, B., Jamal, E. H., Hicham, “A Performance Comparison of GA and ACO Applied to TSP”, International Journal of Computer Applications, 117(19), 28-35, 2015.
12. [12] Makuchowski, M. “Effective Algorithm Of Simulated Annealing For The Symmetric Traveling Salesman Problem”, International Conference on Dependability and Complex Systems, Brunów, Poland, 348–359, July, 2018.
13. [13] K., Chaudhari, A., Thakkar, “Travelling Salesman Problem: An Empirical Comparison Between ACO, PSO, ABC, FA and GA”, Advances in Intelligent Systems and Computing, 397-405, 2019.
14. [14] A. S., Bhagade, P. V., Puranik, “Artificial Bee Colony (ABC) Algorithm for Vehicle Routing Optimization Problem”, International Journal of Soft Computing and Engineering (IJSCE), 2012.
15. [15] F., Valdez, F., Moreno, P., Melin, “A Comparison of ACO, GA and SA for Solving the TSP Problem”, Hybrid Intelligent Systems in Control, Pattern Recognition and Medicine, Volume:827, Editors: Castillo, O., Melin, P., Springer, Cham, 181-189, 2020.
16. [16] A., Yılmaz Yalçıner, “Tavlama Benzetimi Temelli Yaklaşım ile Kapasite Kısıtlı Araç Rotalama Optimizasyonu: Karadeniz Bölgesi Örneği”, European Journal of Science and Technology, (22), 239- 248, 2021.
17. [17] D. Karaboga, An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report TR06, Erciyes University, Turkey, 2005.
18. [18] D., Karaboga, B. Akay, “A Comparative Study of Artificial Bee Colony Algorithm”, Applied Mathematics and Computation. 214(1), 108-132, 2009.
19. [19] Y. Torun, Z. Ergül, A. Aksöz, “Optimum Enerji Verimliliğini Hedefleyen Rastgele Ağaçlar ve Yapay Arı Kolonisi Yöntemi ile Otonom Robotlarda Yol Planlama Algoritması”, Gazi University Journal of Science Part C: Design and Technology, 7(4), 903-915, 2019.
20. [20] C., Öztürk, E., Hançer, D., Karaboğa, “Küresel En İyi Yapay Arı Koloni Algoritması ile Otomatik Kümeleme”, Journal of the Faculty of Engineering and Architecture of Gazi University, 29(4), 677-687, 2014.
21. [21] F. Xu , C. Pun , H. Li, Y. Zhang , Y. Song, H. Gao, “Training Feed-Forward Artificial Neural Networks With A Modified Artificial Bee Colony Algorithm”, Neurocomputing, 416, 69-84., 2019.
22. [22] Y. Cao, S. Ji, Y. Lu, “An Improved Support Vector Machine Classifier Based On Artificial Bee Colony Algorithm”, Journal of Physics Conference Series, 1550(4), 042073, 2020.
23. [23] M., Mitchell, “Genetic Algorithms: An Overview”, Complexity, 1(1), 31–39, 1995.
24. [24] M., İlkuçar, İ., Güngör, “Hekim Atama Probleminin Genetik Algoritma ile Optimizasyonu”, Mehmet Akif Ersoy Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 10(24), 236-261, 2019.
25. [25] C., Aktürk, “Genetik Algoritma ve Pikselizasyon Yöntemi ile Mayın Tarlası Oyununun Zorluk Seviyesini Belirleme”, Uluslararası Yönetim Bilişim Sistemleri ve Bilgisayar Bilimleri Dergisi, 2(2), 105-113, 2018.
26. [26] C., Guo, L., Li, Y., Hu, J., Yan, “A Deep Learning Based Fault Diagnosis Method with Hyperparameter Optimization by Using Parallel Computing”, IEEE Access, 8, 131248-131256, 2020.
27. [27] A., Özgür, H., Erdem, “Saldırı Tespit Sistemlerinde Genetik Algoritma Kullanarak Nitelik Seçimi ve Çoklu Sınıflandırıcı Füzyonu”, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 33(1), 75- 87, 2018.
28. [28] J., Tarigan, R., Diedan, Y., Suryana, “Plate Recognition Using Backpropagation Neural Network and Genetic Algorithm”, Procedia Computer Science, 116, 365-372, 2017.
29. [29] M., Dorigo, M., Birattari, T., Stutzle, “Ant Colony Optimization”. IEEE Computational Intelligence Magazine, 1(4), 28-39, 2006.
30. [30] S., Kuzu, O., Önay, U., Şen, M., Tunçer, B., Yıldırım, T., Keskintürk, “Gezgin Satıcı Problemlerinin Metasezgiseller ile Çözümü”, İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(1), 1- 27, 2014.
31. [31] H., Dikmen, H., Dikmen, A., Elbir, Z., Eksi, F., Çelik, “Gezgin Satıcı Probleminin Karınca Kolonisi ve Genetik Algoritmalarla En İyilemesi ve Karşılaştırılması”, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 18(1), 8-13, 2014.
32. [32] S., Kılıç, C., Kahraman, “Bulanık Karar Ortamında Karınca Kolonisi Optimizasyonu Yöntemiyle Araç Rotalama”. İTÜdergisi/d . 8(4), 160-172, 2009.