臺灣博碩士論文加值系統

長久以來，每當在深山或偏遠地區發生搜索與救援等服務需求任務時，搜救單位必須立即調派大量人力於事故地區沿路徒步搜索，期能儘快找到停留於某路段上的靜態標靶（譬如受傷的登山客）。由於欲搜尋之範圍廣大且路況不明，此種搜尋方式受制於平面路網的連結，即便事先已得知該靜態標靶較可能的位置，仍需沿路逐段徒步跋涉探索；相對而言，無人機具有較快的三維空間移動能力，可跳脫二維路網的路段連結限制；只要續航力足夠，同時指派多架無人機分工協同搜尋，應可更快完成搜尋任務，同時也能減少搜救團隊發生人身意外。本研究欲探討下述之搜救路線規劃問題：給定一網路（譬如某區域的諸多登山步道路線），假設單一靜態標靶僅會停留在某段節線上，且各節線上可尋獲該標靶的機率、可供無人機充換電的節點位址等資訊皆為已知，我們將規劃K架無人機的最佳移動路線，尋訪該標靶可能存在（即機率為正值）之所有節線，以使總期望搜尋時間能最短。
先前探討使用人力徒步沿路搜尋的相關文獻，大多僅能處理特殊的「單位節線長度網路」(unit graph，亦即所有節線的長度皆為單位長度)，本研究則首度提出可以處理一般節線長度的數學規劃模式。我們參考過去文獻針對目標式之期望搜尋時間的處理方式，將目標式由非線性改為線性，並利用層空網路(Level-Space Network)為基礎以建構數學規劃模式。而無人機必須尋訪所有之標靶存在機率為正值的節線（但不見得為所有節線），此與文獻中的鄉村多郵差問題(K Rural Postmen Problem，KRPP)類似；然而本研究之目標式為最小化總期望搜尋時間，與KRPP僅將最長的車輛移動時間最小化相比，本研究的目標式更為複雜。為能善用無人機的移動機動彈性，本研究假設無人機在節點間有兩種移動模式：(1)慢速的「沿路搜尋模式」，及(2)快速的「節點移動模式」，前者與人員徒步沿路移動方式相同，僅能在原節線路段連續進行；而後者則可在續航力允許下自由地在任兩節點間移動。為簡化問題，我們亦假設無人機除充電（耗費固定時間，且充完必滿電）與結束任務外，必須一直保持移動。基於無人機續航力限制的現實考量，本研究亦假設充換電站位址皆在某些已知的節點上，且無人機在電力耗盡前可自行前往充換電站。上述諸項設定，除讓本研究問題更符合現實外，也大幅提高其困難度與挑戰性。
在實際進行數值測試後，我們發現數學規劃模型的作法將耗時過長，無法處理規模為中或大型之網路，因此本研究再發展數種啟發式演算法，將需要進行搜尋的節線編碼為一組解，設計結合動態規劃法與回溯法之解碼演算法，將該解再轉變為實際之飛行路徑，最後再利用基因演算法與區域搜尋法以求解最小之總期望搜尋時間。為加速求解，我們將無人機之電量限制視為軟性限制處理，數值測試結果顯示數學規劃模型雖可得到理論最佳解，但僅可求解小規模的網路；而區域搜尋法則皆可在短時間內求得近似最佳解。最後，我們推薦使用本論文發展之數學規劃法建模處理規模較小的搜救服務需求，而大規模的搜救服務作業則可使用本論文設計之區域搜尋法處理之。

Unmanned Aerial Vehicles (UAVs) are very useful for search and rescue missions, since they are more mobile, faster, remotely controllable, and can cover wider range in shorter time. In this thesis, we focus on the application of locating a single immobile target on a general network by a fleet of UAVs. Assuming the probability of finding the target on each arc is estimated beforehand, we seek optimal UAV routings so that the target can be located in a minimum expected time, whereas the UAV routings also consider the necessary battery swapping or recharging at specific nodes. Our settings are more realistic since we consider two UAV moving modes: a slower searching mode along arcs, and a faster moving mode between possibly nonadjacent nodes. A mixed integer programming formulation is proposed on a level-space network, which can only deal with networks of smaller sizes. Two heuristic algorithms, genetic algorithm (GA) and local search algorithm (LS), are designed to calculate solutions of good qualities in short time. The numerical results of our computational experiments indicate that LS can calculate high-quality solutions within limited time among all cases.

摘要 I
誌謝 VII
目錄 VIII
圖目錄 X
表目錄 XI
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 3
1.4 研究範圍 4
1.5 論文架構 5
第二章 文獻回顧 6
2.1 傳統人力徒步搜救路線規劃相關研究 6
2.1.1 搜尋動態標靶 7
2.1.2 搜尋靜態標靶 7
2.2 無人機搜救路線規劃相關研究 10
2.3 節線排程問題相關文獻 12
2.4 小結 14
第三章 無人機群搜尋路徑之數學規劃模型 15
3.1 問題描述 15
3.2 問題假設 16
3.3 網路結構 17
3.4 固定充定站位置之數學模式 17
3.4.1 符號定義 18
3.4.2 期望搜尋時間 19
3.4.3 數學模式 21
3.4.4 考慮無人機群起訖組合模式 24
3.5 最佳階層數 25
3.6 小結 25
第四章 無人機群搜尋路徑規劃之求解演算法設計 26
4.1 編碼方式(Encode) 26
4.2 解碼演算法(Decoding Algorithm，DA) 27
4.2.1 演算法步驟 28
4.2.2 範例說明 32
4.3 基因演算法 (Genetic Algorithm，GA) 34
4.4 區域搜尋法 (Local Search，LS) 38
4.5 小結 44
第五章 數值分析 45
5.1 測試資料參數設定 45
5.2 測式網路圖設定 46
5.3 固定充換電站點之無人機群路徑規劃問題之測試 46
5.3.1 整數規劃模式比較 46
5.3.2 數學演算法測試 49
5.4 使用無人機之效益比較 50
5.5 小結 51
第六章 結論與未來研究議題建議 52
6.1 結論 52
6.2 未來研究 53
附錄 55
參考文獻 58

[1]Ahr, D., ＆ Reinelt, G. (2002, September). New heuristics and lower bounds for the min-max k-Chinese postman problem. In European symposium on algorithms (pp. 64-74). Springer, Berlin, Heidelberg.
[2]Aráoz, J., Fernández, E., ＆ Zoltan, C. (2006). Privatized rural postman problems. Computers ＆ operations research, 33(12), 3432-3449.
[3]Benavent, E., Corberán, Á., ＆ Sanchis, J. M. (2010). A metaheuristic for the min–max windy rural postman problem with K vehicles. Computational Management Science, 7(3), 269-287.
[4]Berger, J., ＆ Lo, N. (2015). An innovative multi-agent search-and-rescue path planning approach. Computers ＆ Operations Research, 53, 24-31.
[5]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.
[6]Campbell, J. F., Corberán, Á., Plana, I., ＆ Sanchis, J. M. (2018). Drone arc routing problems. Networks.
[7]Forsmo, E. J., Grøtli, E. I., Fossen, T. I., ＆ Johansen, T. A. (2013, May). Optimal search mission with unmanned aerial vehicles using mixed integer linear programming. In Unmanned Aircraft Systems (ICUAS), 2013 International Conference on (pp. 253-259). IEEE.
[8]Hashimoto, H., ＆ Yagiura, M. (2008, March). A path relinking approach with an adaptive mechanism to control parameters for the vehicle routing problem with time windows. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 254-265). Springer, Berlin, Heidelberg.
[9]Jotshi, A., ＆ Batta, R. (2008). Search for an immobile entity on a network. European Journal of Operational Research, 191(2), 347-359.
[10]Kang, M. J., ＆ Han, C. G. (1998, February). Solving the rural postman problem using a genetic algorithm with a graph transformation. In SAC (Vol. 98, pp. 356-360).
[11]Karakatič, S., ＆ Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.
[12]Kemper, F. P., Suzuki, K. A., ＆ Morrison, J. R. (2011). UAV consumable replenishment: design concepts for automated service stations. Journal of Intelligent ＆ Robotic Systems, 61(1-4), 369-397.
[13]Lenstra, J. K., ＆ Kan, A. R. (1976). On general routing problems. Networks, 6(3), 273-280.
[14]Li, B., Patankar, S., Moridian, B., ＆ Mahmoudian, N. (2018, August). Planning Large-Scale Search and Rescue using Team of UAVs and Charging Stations. In 2018 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR) (pp. 1-8). IEEE.
[15]Li, S., ＆ Huang, S. (2018). Multiple searchers searching for a randomly distributed immobile target on a unit network. Networks, 71(1), 60-80.
[16]Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
[17]Lo, K. M., Yi, W. Y., Wong, P. K., Leung, K. S., Leung, Y., ＆ Mak, S. T. (2018). A genetic algorithm with new local operators for multiple traveling salesman problems. International Journal of Computational Intelligence Systems, 11(1), 692-705.
[18]Moskal II, M. D. (2013). A Mathematical Programming Approach to Immobile Entity Search. State University of New York at Buffalo.
[19]Muyldermans, L., Beullens, P., Cattrysse, D., ＆ Van Oudheusden, D. (2005). Exploring variants of 2-opt and 3-opt for the general routing problem. Operations research, 53(6), 982-995.
[20]Orloff, C. S. (1974). A fundamental problem in vehicle routing. Networks, 4(1), 35-64.
[21]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.
[22]Raap, M., Meyer-Nieberg, S., Pickl, S., ＆ Zsifkovits, M. (2017). Aerial vehicle search-path optimization: a novel method for emergency operations. Journal of Optimization Theory and Applications, 172(3), 965-983.
[23]Reiter, S., ＆ Sherman, G. (1965). Discrete optimizing. Journal of the Society for Industrial and Applied Mathematics, 13(3), 864-889.
[24]Royset, J. O., ＆ Sato, H. (2010). Route optimization for multiple searchers. Naval Research Logistics (NRL), 57(8), 701-717.
[25]Stone, L. D. (1976). Theory of optimal search (Vol. 118). Elsevier.
[26]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.
[27]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.
[28]Yu, W., ＆ Batta, R. (2010). Search for an Immobile Entity on a Unit Graph: A Mathematical Programming Approach.