近年來，不時發生登山客因天災人禍等諸多因素受困途中，導致政府耗費不少人力物力搜救。由於搜救行動有其立即與危險性，搜救單位往往需要立即調派大量人力或直升機，在不易行走的地區沿路搜救，以期能盡快找到停留於某路段上的靜態標靶(譬如受傷無法行走的登山客)。即使目標可能在的路段與其存在機率為已知，為了在這些可能的路段上搜索，傳統只能以徒步方式沿路逐步前進，而直升機雖能快速抵達欲搜索之路段上方，但成本過高，且可能因障礙物遮蔽而難以貼近地面搜索。此時若使用無人機(Unmanned Aerial Vehicle，UAV)搜索，其較快的三維空間移動能力可跳脫傳統人力在二維網路上的路段移動限制，也較直升機有更低的成本與貼地搜索之優勢；只要續航力足夠，同時指派多架無人機分工協同搜索，應可更快完成搜索任務。為讓無人機群之搜索續航力無虞，本研究提議讓徒步的搜救隊攜帶無人機之充換電設備，權充類似地面載具 (Ground Vehicle，GV)之「動態充換電站」角色，讓無人機能在其電力耗盡前能與同步搜救的人員會合，以充換電池繼續搜救任務，形成一個「無人機-地面載具的二階層協同式路徑規劃問題」(Two-Echelon GV and UAV cooperated Routing Problem，2E-GU-RP)。本研究假設在欲搜索之網路上，某單一靜態標靶在其可能停留之各段節線上之存在機率、無人機之電量及其不同移動模式之電力消耗與速度、與搜救隊的移動速度皆為已知，以時空(time-space)網路為架構，建構「可共乘」和「非共乘」兩種整數規劃模式，來規劃多架無人機、多位搜救隊的最佳協同移動路線，以最短之總期望搜索時間來遍訪該標靶可能存在之所有節線，而在實際進行數值測試後，我們發現兩種數學模式皆需要花費大量的求解時間，且無法處理中大型網路，因此本研究再開發啟發式演算法以在短時間內獲得高品質的近似最佳解(nearly optimal solution)，參考過去針對多鄉村郵差問題(K-rural postman problem，KRPP)常使用的編碼方式，將需要尋訪的標靶節線分配給不同的無人機和搜救隊，形成一組編碼，設計概念類似於貪婪演算法的解碼演算法，先規劃無人機的移動路徑，並記錄其需要充換電的節點與時間，再規劃動態充換電站的移動路徑，以提供無人機電力和尋訪標靶節線，將編碼轉化為實際的移動路徑。最後再利用多種區域搜尋演算法交換迭代，以求解最小化期望搜尋時間。透過數值分析，可證明即使是不同的區域搜尋演算法組合，啟發式演算法在面對中大型網路時，皆可在短時間內求得近似最佳解。因此我們推薦使用本論文發展之數學模式處理規模較小的網路，而中大型的網路則可使用本研究開發之啟發式演算法處理之。

Unmanned Aerial Vehicles (UAVs) are mobile, faster, remotely controllable for search and rescue (SAR) missions. This thesis investigates a SAR mission by SAR teams and a fleet of UAVs to search over arcs of positive probability to identify an immobile target (e.g., an injured hiker) with minimum expected time. To deal with the range anxiety, we assume each SAR team serves as a mobile battery-swapping station, similar to the Ground Vehicle (GV) role in the 2-Echelon UAV & GV Routing Problem (2E-GU-RP). In particular, while a SAR team searches along hiking routes on foot, a UAV can be launched and retrieved at some nodes. A retrieved UAV will become fully charged right after its rendezvous with teams. Both teams and UAVs have two moving modes: a slower searching mode, and a faster passing mode. The searching mode searches the target along arcs, but a UAV on the passing mode might fly between nonadjacent nodes. Two integer programming formulations, carried model and non-carried model are proposed on a time-space network, which can only deal with smaller networks. A local search based heuristic algorithm (LS) is designed to calculate solutions of good qualities in a short time. Our computational experiments’ numerical results indicate that our heuristic with the 2-opt and cross-exchange LS mechanisms can get a nearly optimal solution in a short time.

呂昀軒. (2019). 以無人機群搜尋單一靜態標靶之最佳協同搜尋路徑規劃問題研究. 國立成功大學工業與資訊管理學系碩士論文, 台南市. Retrieved from https://hdl.handle.net/11296/58w5mx
馬哈曼. (2019). 執行區域覆蓋任務之可充換電無人機及其載具之最佳聯合路線規劃問題研究. 國立成功大學工業與資訊管理學系碩士論文, 台南市. Retrieved from https://hdl.handle.net/11296/4ukecq
Berger, J., Lo, N., & Noel, M. (2014). A new multi-target, multi-agent search-and-rescue path planning approach. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 8(6), 935-944.
Campbell, J. F., Corberán, Á., Plana, I., & Sanchis, J. M. (2018). Drone arc routing problems. Networks, 72(4), 543-559.
Dobbie, J. M. (1968). A survey of search theory. Operations Research, 16(3), 525-537.
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.
Forgy, E. W. (1965). Cluster analysis of multivariate data: efficiency versus interpretability of classifications. biometrics, 21, 768-769.
Garone, E., Naldi, R., Casavola, A., & Frazzoli, E. (2010). Cooperative mission planning for a class of carrier-vehicle systems. Paper presented at the 49th IEEE Conference on Decision and Control (CDC).
Groves, G., & Van Vuuren, J. (2005). Efficient heuristics for the rural postman problem. ORiON, 21(1), 33-51.
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.
Hà, M. H., Bostel, N., Langevin, A., & Rousseau, L. M. (2014). Solving the close‐enough arc routing problem. Networks, 63(1), 107-118.
Jotshi, A., & Batta, R. (2008). Search for an immobile entity on a network. European Journal of Operational Research, 191(2), 347-359.
Lenstra, J. K., & Kan, A. R. (1976). On general routing problems. Networks, 6(3), 273-280.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Luo, Z., Liu, Z., & Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors, 17(5), 1144.
MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Paper presented at the Proceedings of the fifth Berkeley symposium on mathematical statistics and probability.
Mathew, N., Smith, S. L., & Waslander, S. L. (2015). Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions on Automation Science and Engineering, 12(4), 1298-1308.
Orloff, C. (1974). A fundamental problem in vehicle routing. Networks, 4(1), 35-64.
Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E. (2018). Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4), 411-458.
Piacentini, C., Bernardini, S., & Beck, J. C. (2019). Autonomous target search with multiple coordinated UAVs. Journal of Artificial Intelligence Research, 65, 519-568.
Potvin, J.-Y., Kervahut, T., Garcia, B.-L., & Rousseau, J.-M. (1996). The vehicle routing problem with time windows part I: tabu search. INFORMS Journal on Computing, 8(2), 158-164.
Reiter, S., & Sherman, G. (1965). Discrete optimizing. Journal of the Society for Industrial and Applied Mathematics, 13(3), 864-889.
Savuran, H., & Karakaya, M. (2015). Route optimization method for unmanned air vehicle launched from a carrier. Lecture Notes on Software Engineering, 3(4), 279.
Stone, L. D. (1976). Theory of optimal search (Vol. 118): Elsevier.
Sujit, P., Sousa, J., & Pereira, F. L. (2009). UAV and AUVs coordination for ocean exploration. Paper presented at the Oceans 2009-Europe.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J.-Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science, 31(2), 170-186.
Tavana, M., Khalili-Damghani, K., Santos-Arteaga, F. J., & Zandi, M.-H. (2017). Drone shipping versus truck delivery in a cross-docking system with multiple fleets and products. Expert systems with applications, 72, 93-107.
Tokekar, P., Vander Hook, J., Mulla, D., & Isler, V. (2016). Sensor planning for a symbiotic UAV and UGV system for precision agriculture. IEEE Transactions on Robotics, 32(6), 1498-1511.
Xu, R., & Wunsch, D. (2005). Survey of clustering algorithms. IEEE Transactions on neural networks, 16(3), 645-678.
Yao, P., Xie, Z., & Ren, P. (2017). Optimal UAV route planning for coverage search of stationary target in river. IEEE Transactions on Control Systems Technology, 27(2), 822-829.
Yu, K., Budhiraja, A. K., & Tokekar, P. (2018). Algorithms for routing of unmanned aerial vehicles with mobile recharging stations. Paper presented at the 2018 IEEE International Conference on Robotics and Automation (ICRA).