無人機(jī)在搶險(xiǎn)救災(zāi)中的數(shù)量與路徑優(yōu)化

黃麥

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

關(guān)鍵詞：無人機(jī)；搶險(xiǎn)救災(zāi)；數(shù)量與路徑優(yōu)化；旅行商問題；遺傳算法

中圖分類號：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1671-2064（2018）15-0240-02

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

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

1 地形圖及重災(zāi)區(qū)相對位置

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

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

2 目標(biāo)區(qū)域選擇

通過過濾3000m以下的災(zāi)區(qū)數(shù)據(jù)，可得到目標(biāo)范圍區(qū)域，將這些范圍的面積納入重要性比例系數(shù)。設(shè)重要性比例系數(shù)為目標(biāo)范圍面積與重災(zāi)區(qū)總面積的比，即，其中總面積，目標(biāo)范圍面積由軟件計(jì)算得出。計(jì)算得出各重災(zāi)區(qū)域的重要性比例系數(shù)如表1所示。

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

3 無人機(jī)數(shù)量及飛行路線優(yōu)化

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

行駛問題抽象為TSP問題，選用遺傳算法。根據(jù)上一步得出的結(jié)論進(jìn)一步簡化問題為4小時(shí)內(nèi)，用最少的無人機(jī)巡查6個(gè)重災(zāi)區(qū)，利用matlab進(jìn)行最優(yōu)化路徑規(guī)劃。通過計(jì)算得知，選用4架無人機(jī)的時(shí)候雖然飛行的總距離為最短，但是無人機(jī)數(shù)量是最多的，且飛行時(shí)間超過4小時(shí)，因此舍棄該路徑。當(dāng)無人機(jī)數(shù)量為2架時(shí)，每架飛機(jī)任務(wù)量很重，飛行的距離也遠(yuǎn)，飛行時(shí)間也超過了4小時(shí)。因此，3架無人機(jī)的數(shù)量，飛行距離居中，時(shí)間在4小時(shí)以內(nèi)，基本符合各項(xiàng)約束條件，且與其他規(guī)劃路徑相比為最優(yōu)解。無人機(jī)最優(yōu)飛行路徑如圖5所示。

4 結(jié)語

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

參考文獻(xiàn)

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

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

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

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