近年來，無人機相關議題受到越來越多關注。隨著功能、穩定性和成本效益的提升，無人機的使用也逐漸普遍、在多個領域都能看見其應用。其中使用者透過無人機，可以有效率地將貨物安全交付給客戶，完成運輸服務，而不用顧慮平面道路上的阻礙。於是在各式使用情境中，本研究著重於災難救濟的應用。
在災難發生後，救援的相關物資需求突然大量的出現，與此同時，有些道路及橋樑損壞坍塌因而一般車輛無法通行、使得物流工作難上加難。針對此痛點，本研究提出透過車輛與無人機的共同交付，來克服災後運輸的困難並提升其效率。
在本研究中，提出了數學模型以及具無人機的旅行商問題作為解決方案。數學模型基於過去相關研究，並加入服務時間的考量。應用於災難救援的具無人機的旅行商問題 (TSP-D) 則是透過基因演算法結合區域搜尋法首先規劃卡車的行進路線，進而使用無人機來考量賑災情境所需的協同交付工作。
提出的TSP-D問題也在小型、中型和大型不同規模的實例中進行測試。將TSP-D與TSP的解答進行比較，實驗結果顯示所提出之TSP-D問題既可以節省整體運輸時間，又可以符合成本考量地實現救災。

Peoples are attending to the issues of drone these years. The use of drones is getting more due to the improved capability, reliability, and cost-effectiveness. Drones can rapidly deliver parcels to customers, finish transportation services without the limits of obstacles on the route. Among the several applications, this study focuses on the application of disaster relief.
When disasters occur, we can maximize the effect of logistics in disaster relief by collaborating with drones. Especially after the disaster, the sudden increase in the need for rescue. Even some roads or bridges damage so that unable to pass. By the proposed method in disaster relief, increase the efficiency and the range of transportation. In this study, the problem is formulated mathematically and the Traveling Salesman Problem with Drone in Disaster Relief (TSP-D) is proposed for the solution. The TSP-D is based on the Genetic Algorithm with Local Search to solve the routing problem first, considers the situation of disaster relief by assigning drone deliveries afterward.
The proposed TSP-D is tested in small, medium, and large instances. The experimental result performed to be effective by comparing them with the TSP solution. The TSP-D in disaster relief can save delivery time but also achieve disaster relief economically.

Altay, N., & Green III, W. G. (2006). OR/MS research in disaster operations management. European journal of operational research, 175(1), 475-493.
Balcik, B., & Beamon, B. M. (2008). Facility location in humanitarian relief. International Journal of Logistics, 11(2), 101-121.
Balcik, B., Beamon, B. M., & Smilowitz, K. (2008). Last mile distribution in humanitarian relief. Journal of Intelligent Transportation Systems, 12(2), 51-63.
Ballou, R. H. (2004). Business logistics/supply chain management 5th edn, pp. 35-37.
Beamon, B. M., & Balcik, B. (2008). Performance measurement in humanitarian relief chains. International Journal of Public Sector Management, 21(1), 4-25.
Bianchi, L., Knowles, J., & Bowler, N. (2005). Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms. European Journal of Operational Research, 162(1), 206-219.
Carson, Y., & Maria, A. (1997, December). Simulation optimization: methods and applications. In Proceedings of the 29th conference on Winter simulation (pp. 118-126). IEEE Computer Society.
Cerny V. (1982). A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm, Report, Comenius University, Bratislava, Czechoslovakia.
Chauhan, D., Unnikrishnan, A., & Figliozzi, M. (2019). Maximum coverage capacitated facility location problem with range constrained drones. Transportation Research Part C: Emerging Technologies, 99, 1-18.
Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G., & Bian, L. (2017). Drones for disaster response and relief operations: A continuous approximation model. International Journal of Production Economics, 188, 167-184.
Crişan, G. C., & Nechita, E. (2019). On a cooperative truck-and-drone delivery system. Procedia Computer Science, 159, 38-47.
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.
Doerner, K. F., & Hartl, R. F. (2008). Health care logistics, emergency preparedness, and disaster relief: new challenges for routing problems with a focus on the Austrian situation. In The vehicle routing problem: latest advances and new challenges (pp. 527-550). Springer, Boston, MA.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.
Eberhart R. C. & Kennedy J., “A new optimizer using particle swarm theory,” in Proceedings of the Sixth International Symposium on Micro Machine and Human Science, (Nagoya, Japan), pp. 39–43, IEEE Service Center, 1995.
Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science (pp. 39-43). IEEE.
Elloumi, W., El Abed, H., Abraham, A., & Alimi, A. M. (2014). A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP. Applied Soft Computing, 25, 234-241.
Estrada, M. A. R., & Ndoma, A. (2019). The uses of unmanned aerial vehicles–UAV’s-(or drones) in social logistic: Natural disasters response and humanitarian relief aid. Procedia Computer Science, 149, 375-383.
Freisleben, B., & Merz, P. (1996). A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In Proceedings of IEEE international conference on evolutionary computation (pp. 616-621). IEEE.
Freisleben, B., & Merz, P. (1996). New genetic local search operators for the traveling salesman problem. In International Conference on Parallel Problem Solving from Nature (pp. 890-899). Springer, Berlin, Heidelberg.
Golden B. L., Kovacs A. A., & Wasil E. A. (2014). Vehicle Routing Applications in Disaster Relief. In P. Toth et al. (Eds.), Vehicle Routing Problems, Methods, and Applications (2^nded., pp. 409-436). Bologna, Italy: SIAM.
Hacizade, U., & Kaya, I. (2018). GA Based Traveling Salesman Problem Solution and its Application to Transport Routes Optimization. IFAC-PapersOnLine, 51(30), 620-625.
Ingber, L. (1993). Simulated annealing: Practice versus theory. Mathematical and computer modelling, 18(11), 29-57.
Karak, A., & Abdelghany, K. (2019). The hybrid vehicle-drone routing problem for pick-up and delivery services. Transportation Research Part C: Emerging Technologies, 102, 427-449.
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.
Kilci, F., Kara, B. Y., & Bozkaya, B. (2015). Locating temporary shelter areas after an earthquake: A case for Turkey. European Journal of Operational Research, 243(1), 323-332.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
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.
Kureichick, V. M., Miagkikh, V. V., & Topchy, A. P. (1996). Genetic algorithm for solution of the traveling salesman problem with new features against premature convergence. Proc. of GA+ SE, 96.
Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231-247.
Luis, E., Dolinskaya, I. S., & Smilowitz, K. R. (2012). Disaster relief routing: Integrating research and practice. Socio-economic planning sciences, 46(1), 88-97.
Mirjalili, S. (2016). SCA: a sine cosine algorithm for solving optimization problems. Knowledge-Based Systems, 96, 120-133.
Oruc, B. E., & Kara, B. Y. (2018). Post-disaster assessment routing problem. Transportation research part B: methodological, 116, 76-102.
Schmitt, L. J., & Amini, M. M. (1998). Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study. European Journal of Operational Research, 108(3), 551-570.
Shi, Y., & Eberhart, R. (1998). A modified particle swarm optimizer. In 1998 IEEE international conference on evolutionary computation proceedings. IEEE world congress on computational intelligence (Cat. No. 98TH8360) (pp. 69-73). IEEE.
Stephenson R. (1993). Logistics (1^sted.). UNDP/UNDRO Disaster Management Training Programme.
Suzuki, Y. (2019). Impact of material convergence on last-mile distribution in humanitarian logistics. International Journal of Production Economics, 107515.
Tomasini, R. M., & Van Wassenhove, L. N. (2009). From preparedness to partnerships: case study research on humanitarian logistics. International Transactions in Operational Research, 16(5), 549-559.
Van den Bergh, F., & Engelbrecht, A. P. (2004). A cooperative approach to particle swarm optimization. IEEE transactions on evolutionary computation, 8(3), 225-239.
Van Wassenhove, L. N. (2006). Humanitarian aid logistics: supply chain management in high gear. Journal of the Operational research Society, 57(5), 475-489.
Verhoeven, M. G. A., Aarts, E. H., & Swinkels, P. C. J. (1995). A parallel 2-opt algorithm for the traveling salesman problem. Future Generation Computer Systems, 11(2), 175-182.
Wang, Y. (2014). The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Computers & Industrial Engineering, 70, 124-133.
Whitley D., Starkweather T., & Fuquay D., “Scheduling problems and travelling salesman: the genetic edge recombination operator,” in Proc. the 3rd Int. Conf. Genetic Algorithms. Palo Alto, CA: Morgan Kaufmann, 1989, pp. 133–140.