李延武，蘇國鋒，袁宏永

（清華大學(xué)工程物理系公共安全研究院，北京100084）

低空安全監(jiān)測飛艇介紹及其行駛路線問題研究*

李延武，蘇國鋒，袁宏永

（清華大學(xué)工程物理系公共安全研究院，北京100084）

在地震救災(zāi)中，利用低空安全監(jiān)測飛艇進行災(zāi)情監(jiān)測是了解災(zāi)情的有效手段。由于飛艇信號傳輸具有距離限制，如何結(jié)合救災(zāi)需要和飛艇技術(shù)參數(shù)提前設(shè)計飛艇的行駛路線是一個急需解決的問題，同時也是飛艇救援指揮系統(tǒng)的重要組成部分。該文首先介紹了低空安全監(jiān)測飛艇的優(yōu)勢和功能，然后結(jié)合應(yīng)急救災(zāi)實際情況，將低空安全監(jiān)測飛艇的路線問題轉(zhuǎn)化為帶條件的旅行商問題，并通過仿真實驗詳細(xì)分析比較了蟻群算法、“最近鄰居”算法、模擬退火算法、遺傳算法四種算法在解決該問題時的效果。結(jié)果表明，蟻群算法得到的最優(yōu)解次數(shù)最多、計算時間最穩(wěn)定，于是將蟻群算作為原問題的核心算法，提出了該問題的解決方案。

地震救援；災(zāi)情監(jiān)測；安全監(jiān)測；飛艇；行駛路線；旅行商問題

在地震救災(zāi)中，如何盡快了解災(zāi)區(qū)損失情況，從而合理、有效地分配救災(zāi)力量是一大難題。在2008年汶川8.0級大地震中，交通網(wǎng)、通信網(wǎng)等被破壞，直升飛機不能得到清晰、穩(wěn)定的路面圖象，衛(wèi)星的實時操作性較差，使得決策者不能根據(jù)損失情況進行資源調(diào)度、分配救援力量。缺少實時有效的監(jiān)測手段，已經(jīng)成為地震應(yīng)急的瓶頸問題。

為了解決這一問題，清華大學(xué)研制了低空安全監(jiān)測飛艇（圖1），將3S技術(shù)（GIS、GPS和RS技術(shù)）［1］和飛行控制技術(shù)相融合，利用飛艇將地震災(zāi)區(qū)低空區(qū)域的圖像、相關(guān)環(huán)境參數(shù)和災(zāi)害產(chǎn)物參量和參數(shù)進行多維自動采集、處理后，通過無線方式將采集各種參數(shù)傳輸?shù)奖O(jiān)測中心。該系統(tǒng)同時適用于地震災(zāi)害監(jiān)測評估、環(huán)境監(jiān)測評估、火情監(jiān)測評估、通信中繼、集會監(jiān)測、日常和應(yīng)急巡查、應(yīng)急物資投運等應(yīng)急情況，具有廣泛的應(yīng)用性。

圖1 低空安全監(jiān)測飛艇系統(tǒng)（待起飛狀態(tài)）

低空安全監(jiān)測飛艇屬于無人操作系統(tǒng)，需要通過航線設(shè)置系統(tǒng)在二維GIS地圖設(shè)置航線，飛艇將自動按照預(yù)設(shè)航線執(zhí)行飛行任務(wù)。由于應(yīng)急過程時間緊、任務(wù)重，如何盡快選擇合適的路線是直接影響到應(yīng)急效果的重要問題。同時，為了提升飛艇的智能化設(shè)計，路線算法應(yīng)該盡量快速，且便捷、所耗資源要少，為飛艇飛行過程中的路線自動計算與調(diào)整提供技術(shù)可能性。

1 低空安全監(jiān)測飛艇介紹

低空飛艇安全監(jiān)測技術(shù)已廣泛應(yīng)用于電力巡線、人員搜救、災(zāi)害監(jiān)測、環(huán)境監(jiān)測等方面［2］，相比于衛(wèi)星遙感、航空遙感和無人機遙感等技術(shù)而言，飛艇監(jiān)測技術(shù)具有以下幾點優(yōu)勢［3］。

（1）覆蓋范圍大。覆蓋最長距離為10～100 km，接近衛(wèi)星、航空遙感的覆蓋范圍，高于無人機的監(jiān)測范圍，特別適合于造成現(xiàn)場道路和交通遭到破壞的區(qū)域以及人員無法進入的高危險區(qū)域的安全監(jiān)測，如地震災(zāi)區(qū)的監(jiān)測任務(wù)。

（2）高空間觀測精度和分辨率高。隨著視頻跟蹤［4］和穩(wěn)像技術(shù)［5］的發(fā)展，飛艇監(jiān)測的分辨率可以達到厘米量級，高于衛(wèi)星遙感，其穩(wěn)定性高于一般的航空遙感，能夠滿足安全監(jiān)測的需求。

（3）可擴展性強。由于低空飛艇有較強的載重能力，可以根據(jù)災(zāi)害應(yīng)急的需要搭載輻射監(jiān)測、空氣監(jiān)測等各類專業(yè)監(jiān)測裝置，甚至進行應(yīng)急物資的投放，其應(yīng)急可擴展性是無人機等輕型設(shè)備所無法比擬的。

（4）成本較低。相比于衛(wèi)星遙感和航空遙感而言，低空安全監(jiān)測飛艇的數(shù)據(jù)成本和系統(tǒng)建設(shè)成本較低，易于保養(yǎng)、修復(fù)，適合復(fù)雜環(huán)境使用。

清華大學(xué)研制的低空安全監(jiān)測飛艇包括動力飛行部分、視頻監(jiān)測與投擲系統(tǒng)部分以及無線傳輸部分三個部分，可以在事件發(fā)生后快速抵達現(xiàn)場，完成現(xiàn)場信息（圖像、地理信息、環(huán)境參數(shù)等）采集、傳輸處理，實現(xiàn)事發(fā)現(xiàn)場空地立體監(jiān)測。其主要功能模塊包括有4種。①自動導(dǎo)航與預(yù)先設(shè)置功能：可自動定位導(dǎo)航飛行到制定地點，指揮人員可通過PDA、PC等多種手段進行遙控指揮，可根據(jù)設(shè)置的任務(wù)點自動執(zhí)行預(yù)先設(shè)置的任務(wù)。②智能掃描與遠(yuǎn)程監(jiān)測功能：能利用GIS、GPS、RS、電子羅盤定位、航空攝影空間解析模型實現(xiàn)地物目標(biāo)監(jiān)控圖像與地物GIS位置的雙向智能自動掃描，將高空采集的現(xiàn)場圖像和高清晰照片傳送回指揮中心。③遠(yuǎn)程投擲功能：可遠(yuǎn)程定點投擲多參數(shù)傳感器，進行現(xiàn)場采集，可以實現(xiàn)溫度、濕度、環(huán)境氣壓、風(fēng)向、風(fēng)速等環(huán)境參數(shù)和硫化氫、氫氰酸、氨氣等有毒氣體的信息采集，亦可以投擲少量應(yīng)急物資。④中繼功能，可對現(xiàn)場圖像、語音、數(shù)據(jù)進行中繼傳輸，保證遠(yuǎn)端指揮中心實現(xiàn)接收現(xiàn)場采集的各種參數(shù)。

2 問題描述

結(jié)合飛艇的實際技術(shù)參數(shù)，低空安全監(jiān)測飛艇其路線選擇問題描述如下。

（1）路線要求：飛艇必須從起飛點起飛，巡航完畢后到起飛點降落補充燃料；應(yīng)急監(jiān)測情況下，需要首先探測一些重點地域（交通樞紐、供電站、核電站、居民密集區(qū)等），飛艇需不重復(fù)地經(jīng)過每一個重點領(lǐng)域進行巡航，同時為了巡航到更多的地域，飛艇需要走最短的路線；飛艇的起飛點必須是正常交通工具可以達到的，因此可能與探測點有較遠(yuǎn)的距離，如果存在不能覆蓋所有重點區(qū)域的情況，需要另選起飛點進行。

（2）飛行控制要求：飛艇可遙控距離僅1.5 km，1.5 km外靠飛艇GPS路線自動識別系統(tǒng)完成，在地面形式惡劣的情況下無法人工更改預(yù)設(shè)路線。

（3）相關(guān)參數(shù)計算：飛艇飛行相對高度1 000 m，抗風(fēng)等級5級，可以認(rèn)為是直線運行。飛艇攝影偏角平均值5°，以高度1 000 m計算得單次攝影范圍半徑87.48 m，按照技術(shù)標(biāo)準(zhǔn)，地圖150 m距離內(nèi)的測試點可認(rèn)為是一個點，即地圖分辨率為150 m；飛艇發(fā)動機總功率20×2 hp（雙發(fā)動機），續(xù)航時間4 h，巡航速度45 km／h，最大飛行速度72 km／h?？紤]每次上升、下降時間，一次巡航最大距離不超過150 km。

3 問題分析與模型建立

3.1 旅行商問題簡介

旅行商問題（Traveling Salesman Problem，TSP）是最基本的路線問題。其簡單表述如下：一個商人欲到n個城市推銷商品，每兩個城市i和j之間的距離為dij，需要選擇一條最短路線，使得商人在每個城市走完一遍后回到起點［6］。

3.2 問題分析與轉(zhuǎn)化

原問題在形式上近似TSP問題，屬于NPH問題，可以先向TSP問題轉(zhuǎn)化，再利用啟發(fā)式算法求解。原問題中有三點與傳統(tǒng)TSP問題的不同之處進行分析處理。

（1）多個起飛點的可能：考慮到現(xiàn)實情況下基本上是進行城區(qū)或縣域的監(jiān)測，北京五環(huán)全長約為99 km，已經(jīng)遠(yuǎn)遠(yuǎn)大于一般的縣城區(qū)，因此可知150 km的巡航距離基本能夠滿足巡航的要求。如果出現(xiàn)極個別的區(qū)域覆蓋需要（例如核電站經(jīng)常放在偏遠(yuǎn)區(qū)域），可以單獨考慮。這里，可以在GIS上根據(jù)起飛點和主要的探測區(qū)域畫一個邊長為10 km的正方形作為主要研究區(qū)域，在正方形外的點基本可以作為第二點選擇。

（2）總長度的限制：在起飛點最佳的基礎(chǔ)上，如果總長度超出，可以去掉與起始點最近的點進行計算（去掉的點數(shù)從1到n依次遞增），直至出現(xiàn)符合總長度的路線。剩下的點進行同樣方法的二次迭代。

（3）地圖分辨率：將距離為150 m的點取其重心作為一個點進行分析。

經(jīng)過以上的處理，該問題就可以簡化成有限制的TSP問題［7］，數(shù)學(xué)模型如下所示。其中xij＝1表示商人行走路線包含從城市i到城市j的路徑，反之xij＝0表示沒有包含。dij為城市i和城市j之間的距離，S為滿足要求的任意集合，｜S｜表示集合S元素的個數(shù)，T為最長路徑限制。

4 算法設(shè)計與實現(xiàn)

4.1 算例估算

首先進行數(shù)據(jù)估算。以北京市海淀區(qū)為例，海淀區(qū)共有人口密集區(qū)22個（西苑、羊坊店、六郎莊、中關(guān)村、唐家?guī)X、肖家河、萬壽路、八大處、14所密集的大學(xué)），能源供應(yīng)地點3個（供電、供水、暖氣），其他重要交通樞紐3個（西直門、車公莊、甘家口），一共28個觀測點，大學(xué)占了很大的部分。一般的城市大學(xué)這種特殊密集區(qū)較少，因此這里取20個觀測點為一般的城區(qū)觀測對象是合適的。

假設(shè)已經(jīng)進行了前期的數(shù)據(jù)處理（分辨率和區(qū)域劃分處理），還剩20個觀測點，問題屬于傳統(tǒng)TSP問題，這里隨機生成10個算例，保證其兩點距離大于150 m，進行計算。

4.2 算法設(shè)計

本問題中，20個觀測點路線選擇有（N-1）?。?＝6.08×1016種方法，使用枚舉方法計算量巨大，不適合應(yīng)急救災(zāi)的突發(fā)情況，需要采用啟發(fā)式算法進行計算。以下將采用常用的蟻群算法、“最近鄰居”算法、模擬退火算法、遺傳算法四種啟發(fā)式算法進行計算，均使用最佳參數(shù)設(shè)計，并比較其計算結(jié)果。

4.2.1 蟻群算法設(shè)計與參數(shù)選擇

蟻群算法（ASA）由意大利學(xué)者M.Dorigo等人首先提出，是一種基于群體智能的算法，模擬螞蟻在尋找食物過程中依靠信息素來進行通信的行為［6］。不同的地區(qū)分布著不同的螞蟻，每個螞蟻的位置構(gòu)成一個解集。在每條路徑上設(shè)置初始的信息量，當(dāng)螞蟻按照一定概率轉(zhuǎn)移時，計算螞蟻走過的路程并改變軌跡的強度，當(dāng)循環(huán)計數(shù)小于預(yù)定的最大迭代次數(shù)且不退化時，則得到最優(yōu)結(jié)果。［8-9］。

用蟻群算法求解TSP問題的運行效果受到信息素重要程度參數(shù)α、啟發(fā)式因子重要程度參數(shù)β等參數(shù)的影響，其合理取值范圍為［0，5］。參數(shù)ρ的影響在于其體現(xiàn)的螞蟻留在其通過路徑上信息素的揮發(fā)性，一般取0.1～0.2比較合適。信息素增強強度系數(shù)Q對結(jié)果影響不大［10-11］。基于對蟻群算法參數(shù)最優(yōu)化的比較分析，最終取最大迭代次數(shù)NC＿max＝200，螞蟻數(shù)為30，信息素重要程度的參數(shù)α＝1，啟發(fā)式因子重要程度的參數(shù)β＝5，信息素蒸發(fā)系數(shù)ρ＝0.1，信息素增加強度系數(shù)Q＝100。計算打印出最優(yōu)路線、L-best（各代最優(yōu)路線長度）和L-ave（各代路線的平均長度）。計算結(jié)果如圖2所示。

4.2.2 “最近鄰居”算法設(shè)計與參數(shù)選擇

最近鄰居搜索算法（NNS）的定義是：有一個待查詢的點q，在點集P上構(gòu)造一個數(shù)據(jù)結(jié)構(gòu)，利用該結(jié)構(gòu)可以在一個已定義好的距離向量上找到距離q點最近的點p［6］。最近鄰居搜索算法是基于分割原則實現(xiàn)的，其首要是要選擇分隔空間的參考點，可以很容易地構(gòu)造一個平衡二叉樹，它以參考點為結(jié)點，以數(shù)據(jù)為葉結(jié)點。此后的算法遵循“單個碰撞原則”［12］，即假定：如果兩條記錄數(shù)據(jù)是相同的，那么它們獲得至少一次碰撞相同數(shù)據(jù)段的機會就會相對高很多［13］。

根據(jù)“最近鄰居”算法的定義，設(shè)置參數(shù)：人口規(guī)模pop＿size＝20，地區(qū)規(guī)模N＝20，判斷是否畫迭代次數(shù)圖的邏輯函數(shù)show＿prog＝1，判斷是否輸出最短路線圖的邏輯函數(shù)show＿res＝1。計算結(jié)果見圖3。

4.2.3 模擬退火算法設(shè)計與參數(shù)選擇

模擬退火算法（SA）的思想最早由Metropolis等提出的，其出發(fā)點是基于物理中固體物質(zhì)的退火過程［6］。先根據(jù)各地區(qū)距離矩陣計算出一個初始溫度，在內(nèi)循環(huán)中隨機選擇一個路徑，計算新舊路徑的長度差，在外循環(huán)中計算下降后的溫度，當(dāng)?shù)竭_“零度”時結(jié)束計算，否則一直重復(fù)。模擬退火算法尋找的最優(yōu)解與初始點的選擇無關(guān)［14］。

基于對模擬退火算法參數(shù)最優(yōu)化的分析，本案例中地區(qū)數(shù)N＝20，對應(yīng)MAPKOB鏈長度為100N＝2 000，對應(yīng)的最優(yōu)參數(shù)［15］如下：溫度下降參數(shù)K＝0.95，地區(qū)數(shù)N＝20，零度標(biāo)準(zhǔn)T（K）＝0.01。在計算結(jié)果中用*標(biāo)示初始地區(qū)，途經(jīng)地區(qū)依次用方塊標(biāo)示。計算結(jié)果見圖4。

圖2 蟻群算法計算結(jié)果

4.2.4 遺傳算法設(shè)計與參數(shù)選擇

遺傳算法（GA）是由生物界的進化規(guī)律演化而來的算法［6］。其對算法所產(chǎn)生的每個染色體進行評價，計算每個個體的適應(yīng)度，并由此選擇染色體，在選擇計算中保證適應(yīng)性好的染色體有更多的繁殖機會。將地區(qū)之間的距離記錄，進行迭代計算，每一代用輪盤賭的方式競爭選擇染色體，通過交叉計算實現(xiàn)繼承，用基因的隨機排序?qū)崿F(xiàn)染色體的變異，當(dāng)?shù)螖?shù)大于迭代總代數(shù)時停止運算。［6］

遺傳算法的主要參數(shù)為截止代數(shù)［16］。經(jīng)過試驗，取截止代數(shù)為5 000即可得到最優(yōu)解，同樣，設(shè)置地區(qū)數(shù)N＝20。在計算結(jié)果中用*標(biāo)示初始地區(qū)，途經(jīng)地區(qū)依次用方塊標(biāo)示。計算結(jié)果見圖5。

圖4 模擬退火算法計算結(jié)果

5 計算效果比較

實際救災(zāi)中使用的算法，需滿足準(zhǔn)確度高、耗時少的要求，才能適應(yīng)應(yīng)急救災(zāi)的需要。十個案例的計算結(jié)果（近似到整數(shù)，單位為m）比較如表1所示，相對最優(yōu)解已經(jīng)用黑體標(biāo)出。可見ACA算法得到最優(yōu)解的次數(shù)最多，之后依次是GA算法、NNS算法和SA算法。為了模擬實際情況，四種算法均在家用筆記本電腦上進行計算（主頻2.5GHz，內(nèi)存4G），盡量保證計算環(huán)境相似，計算所需時間比較見表2（單位為s）。四種算法在家用筆記本電腦上計算所需時間均在10s以內(nèi)，既能滿足在飛艇出發(fā)前計算預(yù)設(shè)路線的時間要求，也能節(jié)省飛艇在高空進行飛行路線計算和調(diào)整的時間成本。計算其標(biāo)準(zhǔn)差、平均值及變異系數(shù)見表3，得知變異系數(shù)ACA＜NNS＜SA＜GA，因此ACA算法計算所需時間最穩(wěn)定。

圖5 遺傳退火算法計算結(jié)果

綜上比較，結(jié)合算法穩(wěn)定性需要和最優(yōu)解結(jié)果，ACA算法最適合做低空安全監(jiān)測飛艇行駛路線的算法。

6 算法總結(jié)

經(jīng)過前面的比較，證明ACA算法適合解決本問題，因此，原問題處理流程設(shè)計如圖6所示。

圖6 低空安全監(jiān)測飛艇行駛路線解決方案

表1 四種算法計算10個案例結(jié)果比較

表2 四種算法計算10個案例所用時間比較

表3 四種算法計算10個案例所用時間比較分析

7 結(jié)語

本文首先介紹了低空安全監(jiān)測飛艇的優(yōu)勢和功能，然后結(jié)合應(yīng)急救災(zāi)實際情況，將低空安全監(jiān)測飛艇行駛路線問題轉(zhuǎn)化為總路程限制的旅行商問題，再詳細(xì)討論了蟻群算法、“最近鄰居”算法、模擬退火算法、遺傳算法四種算法對原問題處理結(jié)果的比較，最終確定蟻群算法作為解決問題的核心算法，從而提出了原問題的解決方案并得到應(yīng)用。

［1］ 李劍萍.3S技術(shù)在災(zāi)害監(jiān)測預(yù)測中的應(yīng)用及展望［J］.災(zāi)害學(xué)，2004，19（Supp.1）：83-87.

［2］ Hain JHW.Lighter-than-air platforms（blimpsand aerostats）for oceanographic and atmospheric research and monitoring［C］／／OCEANS 2000 MTS／IEEE Conference and Exhibition.IEEE，2000，3：1933-1936.

［3］ 李云，徐偉，吳瑋.災(zāi)害監(jiān)測無人機技術(shù)應(yīng)用與研究［J］.災(zāi)害學(xué)，2011，26（1）：138-143.

［4］ 馬偉，陳建國，張毛磊.基于尺度自適應(yīng)和跟蹤框自轉(zhuǎn)的視頻目標(biāo)跟蹤［J］.清華大學(xué)學(xué)報：自然科學(xué)版，2012，52（1）：92-95.

［5］ 張毛磊，陳濤，楊銳，等.基于穩(wěn)像技術(shù)的飛艇監(jiān)控視頻目標(biāo)追蹤［J］.清華大學(xué)學(xué)報：自然科學(xué)版，2011，51（6）：809-813.

［6］ 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京：清華大學(xué)出版社，2005.

［7］董萍.基于蟻群算法求解TSP［J］.無錫職業(yè)技術(shù)學(xué)院學(xué)報，2008（5）：34-36.

［8］ 王果，戴冬.基于蟻群算法的TSP問題的求解［J］.河南機電高等?？茖W(xué)校學(xué)報，2008，5（9）：42-43.

［9］ 董萍.基于蟻群算法求解TSP［J］.無錫職業(yè)技術(shù)學(xué)院學(xué)報，2008（5）：34-36.

［10］馬良，朱剛，寧愛兵等.蟻群優(yōu)化算法［M］.北京：科學(xué)出版社，2008

［11］王玥，陶洪久.蟻群優(yōu)化算法在TSP問題中的應(yīng)用［J］.武漢理工大學(xué)學(xué)報，2006，11（11）：24-26

［12］Hao F，Daugman J.A fast search for a large fuzzy database［J］. IEEE Transacrionson Information Forensicsand Security，2008，2（3）：204-206.

［13］劉輝.最近鄰居搜索的模糊實現(xiàn)［J］.上海電力學(xué)院學(xué)報，2011（2）：160-162.

［14］馮劍，岳琪.模擬退火算法求解TSP問題［J］.森林工程，2008（1）：94-96.

［15］康立山，謝云.非數(shù)值并行算法［M］.北京：科學(xué)出版社，1994：2-129

［16］穆艷玲.遺傳算法在TSP問題中的應(yīng)用［D］.天津：天津師范大學(xué)，2004.

Introduction of the Low-altitude Safety M onitoring Airship and Study on its Driving Route Problem

Li Yanwu，Su Guofeng and Yuan Hongyong
（Institute of Public Safety Research，Department of Engineering Physics，Tsinghua University，Beijing 100084，China）

In the earthquake disaster rescue，using Low-altitude Safety Monitoring Airship is an effective method to know more about the disaster situation.Due to the limitof signal transmission distance，how to design the driving route，considering the needs of disaster rescue and technical parameters of the airship，is a big problem needed to be resolved，and also an important part of airship command system.At first，we introduce advantages and functions of the low-altitude safetymonitoring airship.Then to solve the problem，considering the practical situation of disaster rescue，we transform the problem to the TSP problem and compare the effect of the ASA，NNS，SA and GA through simulation experiments.As the effectof ASA arithmetic is stable and takes less time，we finally decide to adopt the ASA algorithm as the core algorithm，and put forward the solutions to the driving route problem.

earthquake rescue；disaster monitoring；safety monitoring；airship；driving route；traveling salesman problem

X43；TP311

A

1000-811X（2015）04-0135-09

10.3969／j.issn.1000-811X.2015.04.026

李延武，蘇國鋒，袁宏永.低空安全監(jiān)測飛艇介紹及其行駛路線問題研究［J］.災(zāi)害學(xué)，2015，30（4）：135-142.［Li Yanwu，Su Guofeng and Yuan Hongyong.Introduction of the Low-altitude Safety Monitoring Airship and Study on its driving route problem-Li Yanwu，Su Guofeng and Yuan Hongyong［J］.Journal of Catastrophology，2015，30（4）：135-142.］*

2015-04-21 修改日期：2015-06-08

國家“十二五”科技支撐項目（2015BAK10B00）

李延武（1988-），男，安徽安慶人，博士研究生，主要從事應(yīng)急救災(zāi)管理方面的研究.

E-mail：liyw11＠m(xù)ails.tsinghua.edu.cn