無人機在搶險救災中的數量與路徑優化

黃麥

摘 要：無人機作為一種抗震救災的新型運載工具，能夠快速有效地巡查災區，將信息反饋到救援基地，以便及時制定出合適的救援方案。本文以某受災區的實際情況為基礎，假定無人機飛行速度一定，飛行高度一定，巡查到目標災區范圍盡量最大，在該情況下所需要的無人機最少架數及行駛路線。本文將問題抽象為多旅行商問題，根據實際數據繪制出災區的地形圖并確定救援范圍，設置約束條件和目標函數，通過遺傳算法計算出無人機的最優情況下的數量和行駛時間，并基于此給出關于行駛軌跡的最優解。

關鍵詞：無人機；搶險救災；數量與路徑優化；旅行商問題；遺傳算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1671-2064（2018）15-0240-02

隨著現代科技的發展，無人機的應用越來越廣泛，不僅適用于傳統的偵查監視、目標轟炸等軍用領域范疇，且同樣適用于航拍、監測、森林防火、抗震救災等領域。由于預測地震比較困難，及時高效的災后救援是減少地震損失的重要措施。無人機作為一種新型運載工具，能夠在救援行動中發揮重要作用，為提高其使用效率，那么解決無人機優化運用問題顯得尤為重要。無人機的行駛路線可看做旅行商問題TSP（Traveling Salesman Problem，TSP），有關TSP問題的研究在現實問題中有很大的使用價值。諸如：交通運輸、管道鋪設、路線的選擇、計算機網絡的拓撲設計、郵遞員送信等，都可抽象成TSP或MTSP（Multiple Traveling Salesman Problem）問題，而對于TSP問題有多重解法[1-4]。

本文以某地發生的實際地震為研究對象，使用無人機巡查災區，其中有數個重點區域即以確定點為中心半徑為10公里以內的受災區。無人機要盡可能多地巡查到重災區內海拔3000米以下的地方，以便于在地震發生后及時了解災區情況，從而制訂救援方案。模型可抽象為，多架無人機從同一地點出發，到不同的受災區域進行巡查，最后選擇一個所用時間最短、無人機數量最少（降低成本）的路線，其對應數學模型可抽象為多旅行商問題，旅行商問題是一個典型的組合優化難題，它在許多領域都有著廣泛的應用，已被證明屬于NP問題。本文選用遺傳算法來解決多旅行商問題。

1 地形圖及重災區相對位置

根據已有災區地形的數據，運用matlab軟件建立地形圖如圖1所示，并繪制出重災區與基地的相對位置如圖2所示，當所有無人機均從基地出發時，要求在4小時內使區域S內海拔3000米以下的地方盡可能多地被巡查到，理解為，無人機數量越多，一方面覆蓋率會增加，巡查范圍變大；另一方面，無人機投入越多則成本越大，且花費時間越多，飛行路徑也將隨著無人機數量的增加而增加。

根據實際情況設置約束條件及目標函數分別為：無人機飛行高度恒定為4200米，飛行速度恒定為55km/h。若所有無人機均同時從某基地出發，巡查完成后即刻返回基地，執行任務的總時間不超過4小時。

2 目標區域選擇

通過過濾3000m以下的災區數據，可得到目標范圍區域，將這些范圍的面積納入重要性比例系數。設重要性比例系數為目標范圍面積與重災區總面積的比，即，其中總面積，目標范圍面積由軟件計算得出。計算得出各重災區域的重要性比例系數如表1所示。

從表1可看出各重災區的重要性比例系數中A區域最小，根據資料分析，為了在4小時內，使區域S內海拔3000米以下的地方盡可能多地被巡查到，就必須做舍棄A區域的決定，進一步來優化規劃無人機飛行路徑的安排。

3 無人機數量及飛行路線優化

在考慮無人機的巡查范圍時，已知無人機以恒定高度Hf=4200米飛行，地面某點看見無人機的仰角大于60°且視線不被山體阻隔。則根據公式L=2Hf×tan（30°）=4850米，得到無人機的巡查帶寬如圖3，若忽略無人機進入重災區的轉彎半徑對行駛過程的影響，無人機從進入重災區后，以巡查帶的寬度繞重災區巡查，假設無人機以最短時間巡查一圈，圖中陰影面積為巡查覆蓋面積，其示意圖如圖4。

行駛問題抽象為TSP問題，選用遺傳算法。根據上一步得出的結論進一步簡化問題為4小時內，用最少的無人機巡查6個重災區，利用matlab進行最優化路徑規劃。通過計算得知，選用4架無人機的時候雖然飛行的總距離為最短，但是無人機數量是最多的，且飛行時間超過4小時，因此舍棄該路徑。當無人機數量為2架時，每架飛機任務量很重，飛行的距離也遠，飛行時間也超過了4小時。因此，3架無人機的數量，飛行距離居中，時間在4小時以內，基本符合各項約束條件，且與其他規劃路徑相比為最優解。無人機最優飛行路徑如圖5所示。

4 結語

本文對某實際受災地區建立了三維模型，對比了各重災區與救援基地的相對位置，通過權重系數衡量了一定時間內救援的有效性。并將無人機行駛問題簡化為旅行商問題，對在一定約束條件下的無人機行駛數量及路線進行了研究，通過設置約束條件和目標函數，運用Matlab軟件實現改進的遺傳算法，比較分析了3種不同數量無人機行駛的飛行總路程和總時間，綜合得出最優解即使用3架無人機執行救援任務，并給出了無人機的最優飛行線路。

參考文獻

[1]李敏，吳浪，張開碧.求解旅行商問題幾種算法的比較研究[J].重慶郵電大學學報，2008，20（5）：624-626.

[2]程畢蕓，魯海燕，徐向平等.求解旅行商問題的改進局部搜索混沌離散粒子群優化算法[J].計算機應用，2016，36（1）：138-142.

[3]何慶，吳意樂，徐同偉.改進遺傳模擬退火算法在TSP優化中的應用[J].控制與決策，2018，33（2）：219-225.

[4]張鑫龍，陳秀萬，肖漢，等.一種求解旅行商問題的新型帝國競爭算法[J].控制與決策，2016，31（4）：586-592.