無人駕駛飛行器，也被簡稱為無人機，是一種可以遠端操控或通過自己內部飛行路徑進行控制的小型自主機器人，此技術在近年來蓬勃發展。使用者能夠藉由多種方式運用無人機，例如通信廣播、運送救災物資、區域性消毒及測量體溫。而在不同使用情境中，本研究將著重於新冠肺炎疫情救援的應用。
目前為了應對新冠肺炎（COVID-19）疫情的爆發，世界各國政府已頒布許多防疫政策如封城、居家隔離、保持社交距離，並利用無人機協助執行物流配送的工作，避免人們近距離接觸，以盡可能地減少發生群聚感染與病毒擴散的機會。
在本研究中，提出了數學模型以及具多台無人機的旅行商人問題（Traveling Salesman Problem with Drones, TSP-D）。數學模型基於過去相關研究，應用於新冠肺炎救援的具多台無人機的旅行商人問題 (TSP-D)是透過限制分群演算法與基因演算法，將被感染或被隔離的客戶先進行分群，規劃卡車的行車路線，並使用無人機協助完成賑災的工作。
小型、中型和大型不同的實例都將在我們提出的TSP-D中進行測試，並且計算出卡車平均完成運輸的時間、無人機平均完成運輸的時間以及無人機平均最長的使用時間。實驗結果顯示本研究應用之限制分群演算法與基因演算法，在小型問題中可以找到最佳解證明其有效性，在大型問題中能夠尋找近似解。所提出之TSP-D問題可以幫助節省整體運輸的時間，及時將物資送達，有效率地完成賑災。

Drones, known more formally as Unmanned Aerial Vehicles (UAV), are small and autonomous robots controlled either remotely or by following an internal flight path on its own. Moreover, they are able to be deployed in a variety of situations, such as facilitating communication, delivering supplies, disinfecting areas, and measuring temperatures. This paper proceeds the application of drones on the situation of pandemic.
In response to the global outbreak of coronavirus (COVID-19), many governments have been prompted to issue lockdowns, stay-at-home orders and social-distancing guidelines. Amid this, we can turn to drones for job functions once performed by humans, in the interest of minimizing infections. In this paper, we introduce a new type of Traveling Salesman Problem with Drones (TSP-D) in COVID-19 relief defined by a mathematical model and applications of Constrained K-means Algorithm and Genetic Algorithm is our proposed solution. The solution is initially based on Constrained K-means Algorithm to cluster infected or quarantined individuals into groups, finding centroids from each group. Then, Genetic Algorithm is used to solve the routing problem. Drones are also considered to help complete the rescue work in this disaster relief.
Small, medium, and large instances are tested in our proposed TSP-D. Moreover, average delivery completion time of truck, average delivery completion time of drones, and average max usage time of drones are measured. The experimental result shows that applying Constrained K-means Algorithm and Genetic Algorithm in this study can help us find the optimal solution to prove its effectiveness in small scale problems. Additionally, through this method, it is able to find approximate solution in large size problems. The TSP-D in contagious disease relief helps reduce delivery completion time, which allows us to deliver critical supplies in time and make our rescue work efficiently.

Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.
Angurala, M., Bala, M., Bamber, S. S., Kaur, R., & Singh, P. (2020). An internet of things assisted drone based approach to reduce rapid spread of COVID-19. Journal of Safety Science and Resilience, 1(1), 31-35.
Baykasoğlu, A., & Özbel, B. K. (2016, December). Multiple traveling salesman game for cost allocation: a case problem for school bus services. In LM-SCM 2016 XIV. INTERNATIONAL LOGISTICS AND SUPPLY CHAIN CONGRESS, 64.
Boone, N., Sathyan, A., & Cohen, K. (2015). Enhanced approaches to solving the multiple traveling salesman problem. In AIAA Infotech@ Aerospace, 889.
Bradley, P. S., Bennett, K. P., & Demiriz, A. (2000). Constrained k-means clustering. Microsoft Research, Redmond, 20(0), 0.
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts. Transportation Science, 42(2), 127-145.
Chamola, V., Hassija, V., Gupta, V., & Guizani, M. (2020). A comprehensive review of the COVID-19 pandemic and the role of IoT, drones, AI, blockchain, and 5G in managing its impact. IEEE Access, 8, 90225-90265.
Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4), 393-410.
Dasaklis, T. K., Pappis, C. P., & Rachaniotis, N. P. (2012). Epidemics control and logistics operations: A review. International Journal of Production Economics, 139(2), 393-410.
Davendra, D. (Ed.). (2010). Traveling Salesman Problem: Theory and Applications. BoD–Books on Demand.
de Freitas, J. C., & Penna, P. H. V. (2020). A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 27(1), 267-290.
Dell’Amico, M., Montemanni, R., & Novellani, S. (2019). Drone-assisted deliveries: new formulations for the flying sidekick traveling salesman problem. Optimization Letters, 1-32.
Ding, J., Tang, W., & Wang, L. (2006, August). Parallel combination of genetic algorithm and ant algorithm based on dynamic K-means cluster. In International Conference on Intelligent Computing, 825-830. Springer, Berlin, Heidelberg.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. biosystems, 43(2), 73-81.
El-Samak, A. F., & Ashour, W. (2015). Optimization of traveling salesman problem using affinity propagation clustering and genetic algorithm. Journal of Artificial Intelligence and Soft Computing Research, 5(4), 239-245.
Farag, M. A., El-Shorbagy, M. A., El-Desoky, I. M., El-Sawy, A. A., & Mousa, A. A. (2015). Genetic algorithm based on k-means-clustering technique for multi-objective resource allocation problems. Current Journal of Applied Science and Technology, 80-96.
Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management (JIEM), 9(2), 374-388.
Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management (JIEM), 9(2), 374-388.
Ghaziri, H., & Osman, I. H. (2003). A neural network algorithm for the traveling salesman problem with backhauls. Computers & Industrial Engineering, 44(2), 267-281.
Govindan, K., Mina, H., & Alavi, B. (2020). A decision support system for demand management in healthcare supply chains considering the epidemic outbreaks: A case study of coronavirus disease 2019 (COVID-19). Transportation Research Part E: Logistics and Transportation Review, 138, 101967.
Graboyes, R. F., & Skorup, B. (2020). Medical drones in the United States and a survey of technical and policy challenges. Mercatus Center Policy Brief.
Ha, Q. M., Deville, Y., Pham, Q. D., & Ha, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
Hacizade, U., & Kaya, I. (2018). Ga based traveling salesman problem solution and its application to transport routes optimization. IFAC-PapersOnLine, 51(30), 620-625.
Jahre, M., Persson, G., Kovács, G., & Spens, K. M. (2007). Humanitarian logistics in disaster relief operations. International Journal of Physical Distribution & Logistics Management.
Joborn, M., Crainic, T. G., Gendreau, M., Holmberg, K., & Lundgren, J. T. (2004). Economies of scale in empty freight car distribution in scheduled railways. Transportation Science, 38(2), 121-134.
Junius, K. (1997). Economies of scale: A survey of the empirical literature. Available at SSRN 8713.
Khoufi, I., Laouiti, A., & Adjih, C. (2019). A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones, 3(3), 66.
Khoufi, I., Laouiti, A., & Adjih, C. (2019). A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones, 3(3), 66.
Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., & Brunese, P. A. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14-30.
Kumar, A., Sharma, K., Singh, H., Naugriya, S. G., Gill, S. S., & Buyya, R. (2020). A drone-based networked system and methods for combating coronavirus disease (COVID-19) pandemic. Future Generation Computer Systems, 115, 1-19.
Kumar, M., Husain, M., Upreti, N., & Gupta, D. (2010). Genetic algorithm: Review and application. Available at SSRN 3529843.
Kumaranayake, L. (2008). The economics of scaling up: cost estimation for HIV/AIDS interventions. Aids, 22, S23-S33.
Liu, D., Deng, Z., Sun, Q., Wang, Y., & Wang, Y. (2019). Design and freight corridor-fleet size choice in collaborative intermodal transportation network considering economies of scale. Sustainability, 11(4), 990.
Liu, M., Cao, J., Liang, J., & Chen, M. (2020). Epidemic-Logistics Modeling: A New Perspective on Operations Research, 1-12. Singapore:: Springer.
Lu, Z., Zhang, K., He, J., & Niu, Y. (2016, October). Applying k-means clustering and genetic algorithm for solving mtsp. In International Conference on Bio-Inspired Computing: Theories and Applications, 278-284. Springer, Singapore.
Moshref-Javadi, M., Hemmati, A., & Winkenbach, M. (2020). A truck and drones model for last-mile delivery: A mathematical model and heuristic approach. Applied Mathematical Modelling, 80, 290-318.
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.
Nallusamy, R., Duraiswamy, K., Dhanalaksmi, R., & Parthiban, P. (2010). Optimization of non-linear multiple traveling salesman problem using k-means clustering, shrink wrap algorithm and meta-heuristics. International Journal of Nonlinear Science, 9(2), 171-177.
Necula, R., Breaban, M., & Raschip, M. (2015, June). Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem. In International Conference on Hybrid Artificial Intelligence Systems, 257-268. Springer, Cham.
Oruc, B. E., & Kara, B. Y. (2018). Post-disaster assessment routing problem. Transportation research part B: methodological, 116, 76-102.
Osterholm, M. T. (2001). How to vaccinate 30,000 people in three days: realities of outbreak management. Public Health Reports, 116(Suppl 2), 74.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(2), 81-117.
Ruiz Estrada, M. A. (2020). The uses of drones in case of massive epidemics contagious diseases relief humanitarian aid: Wuhan-COVID-19 crisis. Available at SSRN 3546547.
Saleh, H. A., & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, 17(1), 111-122.
Saputra, M. Y. D., Huda, S. N., & Rani, S. (2020). Travel itinerary planning using traveling salesman problem, K-Means clustering, and multithreading Approach. AUTOMATA, 1(1).
Sathya, N., & Muthukumaravel, A. (2015). A review of the optimization algorithms on traveling salesman problem. Indian Journal of Science and Technology, 8(1).
Schermer, D., Moeini, M., & Wendt, O. (2018, March). Algorithms for solving the vehicle routing problem with drones. In Asian Conference on Intelligent Information and Database Systems, 352-361. Springer, Cham.
Silberholz, J., & Golden, B. (2007). The generalized traveling salesman problem: A new genetic algorithm approach. In Extending the horizons: advances in computing, optimization, and decision technologies, 165-181. Springer, Boston, MA.
Singh, S., Kumar, R., Panchal, R., & Tiwari, M. K. (2020). Impact of COVID-19 on logistics systems and disruptions in food supply chain. International Journal of Production Research, 1-16.
Snyder, L. V., & Daskin, M. S. (2006). A random-key genetic algorithm for the generalized traveling salesman problem. European journal of operational research, 174(1), 38-53.
Svestka, J. A., & Huckfeldt, V. E. (1973). Computational experience with an m-salesman traveling salesman algorithm. Management Science, 19(7), 790-799.
Tamir, A. (1989). On the core of a traveling salesman cost allocation game. Operations Research Letters, 8(1), 31-34. Multiple traveling salesman game for cost allocation: a case problem for school bus services.
Tan, L. Z., Tan, Y. Y., Yun, G. X., & Zhang, C. (2017). An improved genetic algorithm based on k-means clustering for solving traveling salesman problem. In Computer Science, Technology and Application: Proceedings of the 2016 International Conference on Computer Science, Technology and Application (CSTA2016), 334-343.
Van Essen, G. A., Palache, A. M., Forleo, E., & Fedson, D. S. (2003). Influenza vaccination in 2000: recommendations and vaccine use in 50 developed and rapidly developing countries. Vaccine, 21(16), 1780-1785.
Wagstaff, K., Cardie, C., Rogers, S., & Schrödl, S. (2001, June). Constrained k-means clustering with background knowledge. In Icml, 577-584.
Wang, C., & Lan, H. (2019, October). An expressway based TSP Model for vehicle delivery service coordinated with truck+ UAV. In 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC), 307-311. IEEE
Webby, R. J., & Webster, R. G. (2003). Are we ready for pandemic influenza?. Science, 302(5650), 1519-1522.
Wu, T., Shen, H., & Zhu, C. (2015). A multi-period location model with transportation economies-of-scale and perishable inventory. International Journal of Production Economics, 169, 343-349.
Yadav, J., & Sharma, M. (2013). A Review of K-means Algorithm. International journal of engineering trends and technology, 4(7), 2972-2976.
Yadav, R., & Sharma, A. (2012). Advanced methods to improve performance of k-means algorithm: A review. Global Journal of Computer Science and Technology, 12(9), 47-52.
Yedla, M., Pathakota, S. R., & Srinivasa, T. M. (2010). Enhancing K-means clustering algorithm with improved initial center. International Journal of computer science and information technologies, 1(2), 121-125.
Zeng, Z., Chen, P. J., & Lew, A. A. (2020). From high-touch to high-tech: COVID-19 drives robotics adoption. Tourism Geographies, 1-11.