基于遍歷算法的無人機救援模型研究

黃敬 王志堅

摘 要：本文研究了救援響應系統的開發需面臨裝箱問題。將無人機與自身攜帶的外部貨艙、運輸集裝箱和醫療包組合放入標準ISO集裝箱內，采用非線性規劃模型，根據三個港口的地理位置采用遍歷法找出三個港口到救援地點的最短路徑，并給出了無人機的有效載荷包裝方案、交付路線和時間表。確立飛行路徑最小化目標，根據醫療包數量需求做出相應約束，結合港口與無人機分配情況，使用遍歷方法求出救援最佳方案。

關鍵詞：非線性規劃；遍歷；禁忌；搜索

2017年，史上最嚴重颶風襲擊美國波多黎各領土，使多黎各受到嚴重破壞，并造成多人因此死亡。非政府組織-HELP，Inc-設計了一種名為“DroneGo”的可移動災難響應系統，本文則是為該系統提供救援方案來提高其響應能力。同時根據各營救點的需求以及救援路線和偵查路線為HELP，Inc制定營救計劃。

針對以上問題，雖然以前的學者都有研究過貨物裝配問題及配送問題，但本文的背景是救援，因此要綜合考慮救援效率以及救援成本的問題，選出合適港口再制定救援路線。鑒于此，本文采用非線性規劃、遍歷方法、禁忌搜索等方法制定的救援計劃，比前人的研究更具有科學性和合理性。

1 問題分析

ISO集裝箱停靠港口后，提供無人機的有效載荷包裝方案，交付路線和時間表。首先，確立飛行路徑最小化的目標，根據各個交貨地點對醫療包的數量需求。結合3個港口分配方案，賦予每個方案1-3臺無人機，計算每種分配方案的飛行總距離，運用遍歷方法求出最佳方案。還要結合當地人口分布，優先配送傷亡人數多的地點。綜合考慮波多黎各的多方面因素，提出假設，得出配送路線，無人機的飛行速度，飛行路徑和飛行時間。第二步，為了提供無人機飛行計劃，使DroneGo車隊能夠使用車載攝像機評估主要高速公路和道路，從GoogleMap獲取波多黎各的主要道路的交叉點，定義這些交叉點為偵察對象，采用禁忌搜索算法得到最佳偵察路線。

2 符號意義

3 模型的建立

3.1 無人機有效載荷包裝配置、交付路線和時間表

若某個港口被選擇，就為該港口配置一臺H Tethered無人機。在考慮最短路徑時，還要結合當地人口分布，優先考慮配送傷亡人數多的地點。綜合考慮波多黎各的受災情況和地理因素，得出配送路線。根據所選中的無人機的飛行速度和飛行路徑，獲得相應的飛行時間。

3.2 評估主要高速公路和道路的搜索模型

為了提供無人機飛行計劃，使DroneGo車隊能夠使用車載攝像機評估主要的高速公路和道路。我們通過網絡數據獲取波多黎各的主要道路的交叉點，定義這些交叉點為無人機主要的偵察對象。采用禁忌搜索算法：

從一個初始可行解出發，選擇一系列的特定搜索方向作為試探，選擇實現讓特定的目標函數值變化最多的移動。建立Tabu表，對已經優化的過程進行記錄和選擇，指導下一步的搜索方向，避免陷入局部最優解。

第一步：令禁忌表H=空集，并選定一個初始解xnow；

第二步：滿足停止規則時，停止計算，輸出結果；否則，在xnow的鄰域N（xnow）中選擇不受禁忌的候選集Can_N（xnow）；在Can_N（xnow）中選一個評價值最佳的解xnext，xnow=xnext；更新歷史記錄H，保存f（xnow），重復step2；

第三步：在保存的眾多f中，挑選最小（大）值作為解。

4 主要結果

當停靠Arecibo，Fajardo，San Juan這三個港口時，每個港口各配置1架無人機。結合交貨地點與港口的距離以及醫療包的需求，得出以下結果：

（1）港口Arecibo配置一臺E型無人機，負責的救援點：Hospital Pavia Arecibo，飛行路線是由Arecibo飛到Hospital Pavia Arecibo，飛行時間是5.43分鐘（設開始飛行時間為0）。

（2）港口Fajardo配置一臺無人機E，負責救援點：Caribbean Medical Center，飛行路線為由Fajardo飛到Caribbean Medical Center，飛行時間2.41分鐘。

（3）港口San Juan配置一臺無人機B，負責救援點：Hospital HIMA、Hospital Pavia Santurce、Puerto Rico Children's Hospital。考慮到無人機B的配送能力以及為了縮短飛行時間，該無人機的配送方案為：無人機先攜帶救援點Hospital Pavia Santurce、Puerto Rico Children's Hospital所需的總救援物資，然后先飛往Hospital Pavia Santurce，飛行時間為10.45分鐘；再飛往Puerto Rico Children's Hospital，飛行時間為10.91分鐘，總飛行時間21.36分鐘。在無人機B離開港口的同時，派出一輛營救車帶著1個H Tethered平臺直接沿著救援點Hospital HIMA的方向駛去。當到達無人機B可以把醫療包帶往的救援點Hospital HIMA時，并在能夠返回的范圍內，等待無人機的到來，再進行充電以及對醫療包進行裝配，最后飛往Hospital HIMA，飛行時間為20分鐘（重新飛行時，開始飛行時間為0）。通過禁忌搜索算法使用python求得的飛行最短路徑結果如下圖所示：

5 結語

在保證合理的情況下，運用了遍歷算法，在假設條件下考慮了所有可能的情況，減少了誤差的產生。在確定最佳飛行路線時，綜合考慮了當地人口密集地，海拔和施工地點等因素，增加了模型的可靠性。

參考文獻：

[1]王帥.智能輪式機器人在養殖場中路徑規劃的研究[D].長春大學，2017.

[2]張雪婷，陳英武，王琦，周浩，葛冰峰.整車物流的任務規劃模型和算法[J].中國管理科學，2015，23（S1）：624-629.

[3]蘇迎迎.果蔬農產品物流運輸路徑優化研究[D].中國石油大學（華東），2016.

[4]江偉，秦翠蘭，康順光.整車物流運輸計劃優化模型研究[J].物流工程與管理，2014，36（11）：69-71.

作者簡介：黃敬（1996-），男，廣東清城人，2016級本科生，研究方向：應用統計學；王志堅（1982-），江西余干人，博士，講師，研究方向：管理統計方法。