王廣生，孫祎崢，孫海軍，魚 童，張 鋮，周云鵬

（1.中國(guó)港灣工程有限責(zé)任公司，北京 100027；2.河海大學(xué)港口海岸與近海工程學(xué)院，江蘇南京 210098）

引言

近年來，盡管國(guó)際海事組織（IMO）及各國(guó)政府通過降低船用燃料油中的硫含量來控制船舶大氣污染物排放，但由于高、低硫油價(jià)格存在較大差距，低硫油高昂的使用成本使得高硫燃油使用的違規(guī)率依然較高。為解決此問題，已有眾多研究嘗試通過移動(dòng)式監(jiān)測(cè)系統(tǒng)[1]、岸基遙感監(jiān)測(cè)[2]、無人機(jī)嗅探檢測(cè)[3]等方式開展船舶尾氣污染防治工作。其中，無人機(jī)嗅探檢測(cè)方式憑借在機(jī)動(dòng)性強(qiáng)和執(zhí)法效率高等優(yōu)勢(shì)，受到了行業(yè)內(nèi)學(xué)者的廣泛關(guān)注，在海事管理領(lǐng)域的可行性得到了充分的證明[4-6]。

然而，在船舶流量密度較大的情況下，僅依靠人工操控?zé)o人機(jī)完成檢測(cè)工作效率低、危險(xiǎn)性也較高，因此研究續(xù)航時(shí)間有限的條件下，多無人機(jī)協(xié)同是實(shí)現(xiàn)無人機(jī)自動(dòng)化監(jiān)測(cè)的關(guān)鍵問題。

多無人機(jī)協(xié)同類屬于任務(wù)分配問題[7]，即在已知無人機(jī)數(shù)量和任務(wù)數(shù)量的條件下，考慮到環(huán)境威脅、無人機(jī)的續(xù)航能力、載荷能力約束以及任務(wù)的特殊需求，進(jìn)行合理的任務(wù)分配，使得各無人機(jī)均能夠以最優(yōu)效率協(xié)同完成工作。路徑尋優(yōu)問題一般可將其歸為經(jīng)典的旅行商問題[8]，多無人機(jī)協(xié)同的情景涉及到多旅行商問題（Multiple Traveling Salesman Problem,MTSP）和移動(dòng)目標(biāo)旅行商問題（Moving Target Traveling Salesman Problem,MTTSP）。針對(duì)MTSP 問題，目前主要采用啟發(fā)式算法進(jìn)行求解，如雜草入侵算法[9]、人工蜂群算 法[10]、遺傳算法[11]、粒子群算法[12]等。例如，Bourjolly等[13]建立了具有時(shí)間相關(guān)性的MTTSP 問題模型，并使用禁忌搜索算法求解航天器在軌服務(wù)問題；Moraes 等[14]通過對(duì)比遺傳算法、蟻群算法、模擬退火算法在解決MTTSP 時(shí)的表現(xiàn)，得出遺傳算法在求解質(zhì)量和求解效率等方面表現(xiàn)最佳。

本文基于MTTSP 和MTSP 模型，構(gòu)建了多無人機(jī)巡檢路徑規(guī)劃模型（Multiple UAVs’ Path Planning,MUPP）。針對(duì)多無人機(jī)巡檢任務(wù)分配的需求，提出兩階段算法（Two Phase Algorithm,TPA）以提升算法的求解性能，并以長(zhǎng)江干線航道斷面為例進(jìn)行仿真，驗(yàn)證模型的科學(xué)性和算法的有效性。

1 模型構(gòu)建

1.1 模型假設(shè)

為了將實(shí)際問題理論化，便于模型構(gòu)建，需對(duì)模型做出以下假設(shè)：

1）無人機(jī)前往檢測(cè)時(shí)的速度恒定且快于船舶；在檢測(cè)時(shí)間內(nèi)，船舶按當(dāng)前速度和航向行駛；無人機(jī)到達(dá)目標(biāo)點(diǎn)后能夠完成船舶燃油品質(zhì)的檢測(cè)；

2）無人機(jī)跟隨檢測(cè)時(shí)的速度與被檢測(cè)船舶速度一致，檢測(cè)所需時(shí)間不隨船舶變化；

3）旋翼無人機(jī)不同于固定翼無人機(jī)，其轉(zhuǎn)彎半徑較小，故不考慮最小轉(zhuǎn)彎半徑約束；不考慮飛行過程中威脅、地形和氣候等因素的影響。

1.2 模型建立

基于上述假設(shè)，多無人機(jī)巡檢路徑規(guī)劃（Multiple UAVs’ Path Planning,MUPP）問題的表達(dá)如下：

式中：

L—巡航路徑總長(zhǎng)度；

K—無人機(jī)的集合；

M—無人機(jī)的數(shù)量；

dij—船舶si與船舶sj的距離；

T—檢測(cè)總時(shí)間；

Q—無人機(jī)續(xù)航能力；

式（1）為目標(biāo)函數(shù)，表示優(yōu)化的目的為多無人機(jī)總飛行長(zhǎng)度最小。約束條件（2）表示對(duì)巡檢總時(shí)間T 進(jìn)行限制。約束條件（3）表示每艘船舶僅能被一架無人機(jī)檢測(cè)一次。約束條件（4）、（5）表示路徑中每個(gè)船舶只能分別與兩個(gè)船舶相連，保證路徑的連續(xù)性。

1.3 數(shù)據(jù)準(zhǔn)備

MUPP 模型中的L、T值按照?qǐng)D1 方法計(jì)算，圖中tr、dr為無人機(jī)返回基站的時(shí)間和距離；tj為無人機(jī)飛往船舶的時(shí)間；td為無人機(jī)跟隨檢測(cè)的時(shí)間；vd為無人機(jī)速度；vH(i)為船舶H(i)的速度；tH(i)為檢測(cè)時(shí)間；dH(i)為飛行距離。

圖1 無人機(jī)飛行總長(zhǎng)度和時(shí)間的計(jì)算方法Fig.1 Calculation method of total flight length and time of UAVs

其中，飛行時(shí)間tf的計(jì)算原理為：已知無人機(jī)檢測(cè)完H(i)船后的位置D 點(diǎn)坐標(biāo)為(x1,y1)，待檢船舶H(j)位置O 點(diǎn)坐標(biāo)為(x2,y2)。以(x2,y2)為原點(diǎn)，H(j)船舶航行方向?yàn)閥 軸建立直角坐標(biāo)系，船舶H(j)勻速前行至檢測(cè)點(diǎn)M 后，無人機(jī)飛行方向與y 軸夾角為θ，得到方程式（6），化簡(jiǎn)可得飛行時(shí)間tf的計(jì)算式（7）。計(jì)算簡(jiǎn)圖如圖2 所示。

圖2 飛行時(shí)間計(jì)算示意圖Fig.2 Schematic diagram of flight time calculation

1.4 模型求解

MUPP 模型中的路徑規(guī)劃問題屬于NP-hard 問題，本文采用融合了遺傳算法（GA）和模擬退火算法（SA）兩種算法的混合模擬退火遺傳算法[15]（Simulated Annealing Genetic Algorithm,SAGA）作為基本算法。該改進(jìn)遺傳算法同時(shí)具有遺傳算法的全局搜索特性和模擬退火算法的局部搜索特性。

此外，由于MUPP 模型需要多無人機(jī)協(xié)同完成巡檢任務(wù)，故涉及到任務(wù)分配的問題?；诟倪M(jìn)的聚類算法，將該任務(wù)分配問題抽象為MTSP 后，再將MTSP 轉(zhuǎn)化為多個(gè)TSP 進(jìn)行求解。

考慮到船舶運(yùn)動(dòng)特點(diǎn)及無人機(jī)任務(wù)分配的均衡，在上下行船舶數(shù)量較為接近的條件下，提出一種基于上下行船舶分組和任務(wù)均分的K-means++算法。其主要思想為將船舶數(shù)據(jù)集分為上下行兩組數(shù)據(jù)集，再引入容量限制要求，使得聚類形成的集合中船舶數(shù)量較為均勻。GT-K-means++算法的具體步驟如下：

設(shè)V=｛v1|i=1,2,…,n｝表示待檢測(cè)船舶節(jié)點(diǎn)集，初始簇集為s=(c1,c2,…,cj,…,ck)，k 為類簇?cái)?shù)量。初始類簇cj的中心為μj,j=1,2,…,k，每個(gè)類簇中節(jié)點(diǎn)的個(gè)數(shù)qj=0。

1）根據(jù)船舶航向數(shù)據(jù)，將船舶節(jié)點(diǎn)集分為上行船舶節(jié)點(diǎn)集Vup和下行船舶節(jié)點(diǎn)集Vdown；接著初始化類簇容量，即每個(gè)類簇中船舶數(shù)量上限為Q=ceil(n/k)。

2）對(duì)上行船舶節(jié)點(diǎn)集Vup，初始聚類中心是該集合中隨機(jī)選取的一個(gè)船舶點(diǎn)；用最短距離D(x)表示每個(gè)船舶點(diǎn)與已有聚類中心之間的距離，然后用輪盤賭法選出下個(gè)聚類中心點(diǎn)；重復(fù)以上操作，直到選出上行船舶的kup個(gè)聚類中心點(diǎn)。

3）對(duì)下行船舶節(jié)點(diǎn)集Vdown，按照步驟2 中的方法選出下行船舶的kdown個(gè)聚類中心點(diǎn)。

4）針對(duì)各上行船舶點(diǎn)vi?Vup，按照公式（8）計(jì)算各船舶點(diǎn)vi到其類簇中心μj的歐幾里得距離ρ(vi,μj)。

接著將所有船舶點(diǎn)按照距離值從小到大排序。

5）聚類。取到類簇中心μj距離值最小的船舶點(diǎn)vi，并令qj=qj+1，判斷類簇cj當(dāng)前船舶點(diǎn)個(gè)數(shù)是否滿足qj≤Q。若滿足，則將該船舶點(diǎn)vi分配給類簇cj；若不滿足，則將該船舶點(diǎn)vi到類簇cj的距離值設(shè)為無窮大，重新排序并分配下一船舶點(diǎn)，直到分配完所有船舶點(diǎn)。

6）根據(jù)公式更新聚類中心點(diǎn)jμ的坐標(biāo)，類簇cj中船舶點(diǎn)數(shù)量是，若其中心點(diǎn)坐標(biāo)沒有發(fā)生變化，則聚類完成收斂，輸出聚類結(jié)果；否則，轉(zhuǎn)4）。

7）針對(duì)各下行船舶點(diǎn)vi?Vdown，按照4）至 6）的方法完成聚類，并輸出聚類結(jié)果。

綜上，本文采用了GT-K-means++算法對(duì)水域內(nèi)待檢測(cè)船舶點(diǎn)進(jìn)行聚類，將船舶分成多個(gè)子集后，運(yùn)用SAGA 對(duì)每一個(gè)船舶子集進(jìn)行無人機(jī)巡檢路徑規(guī)劃，從而構(gòu)成“GT-K-means++”+“SAGA”的二階段算法（Two Phase Algorithm,TPA），以此來分段求解MUPP。

2 實(shí)驗(yàn)分析

2.1 研究范圍

本文選擇中國(guó)長(zhǎng)三角船舶排放控制區(qū)范圍內(nèi)長(zhǎng)江干線航道南京段進(jìn)行仿真實(shí)驗(yàn)（如圖3 所示），并作參數(shù)影響分析。研究范圍中頂點(diǎn)經(jīng)緯度為：32.25241 °N，119.156 °E；32.23642 °N，119.22114 °E；32.21797 °N，119.21249 °E；32.2372 °N，119.15147 °E。研究范圍的斷面長(zhǎng)度約4 km，寬度約1.3 km。船舶航行數(shù)據(jù)均源自中國(guó)交通運(yùn)輸部海事局的AIS 信息服務(wù)平臺(tái)。圖中圓形點(diǎn)表示設(shè)定的無人機(jī)基站位置，黑色線段為航道邊界線，船形標(biāo)志表示船舶分布位置。

圖3 基于AIS 的研究范圍和船舶實(shí)時(shí)位置Fig.3 The research scope based on AIS and the real-time positions of the ships

2.2 仿真結(jié)果分析

算法采用Python 語言編寫，相關(guān)參數(shù)與模型參數(shù)設(shè)置如表1 所示，結(jié)合船舶AIS 航行數(shù)據(jù)，給范圍內(nèi)所有船舶設(shè)定相應(yīng)的編號(hào)、速度以及坐標(biāo)。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter settings

TPA 算法迭代收斂圖如圖4 所示，從迭代結(jié)果可知，約350 次后收斂，表2 為使用TPA 算法運(yùn)算得到的各無人機(jī)的巡檢路徑及所需時(shí)間。計(jì)算結(jié)果顯示，各無人機(jī)的任務(wù)量均為9，各無人機(jī)巡檢時(shí)間平均值19.5 min，方差為1.57，任務(wù)量較為接近，且滿足無人機(jī)的續(xù)航時(shí)間要求，四架無人機(jī)可均衡、高效地完成巡檢工作。

表2 巡航路徑和時(shí)間Tab.2 Cruise path and tim

圖4 TPA 迭代結(jié)果Fig.4 TPA iteration results

2.3 模型參數(shù)影響分析

1）船舶數(shù)量及無人機(jī)數(shù)量對(duì)TPA 結(jié)果的影響

假設(shè)各無人機(jī)速度vd均為20 m/s，單船檢測(cè)時(shí)間td為3 s。分別在不同場(chǎng)景下運(yùn)行10 次程序，得到最優(yōu)的路徑總時(shí)間T，如表3 所示。結(jié)果顯示當(dāng)船舶數(shù)量大于60 艘時(shí)，出現(xiàn)2 艘無人機(jī)無法滿足巡檢要求的情況，并隨著船舶數(shù)量的增加，所需無人機(jī)數(shù)量不斷增加，當(dāng)船舶數(shù)量達(dá)到100 艘時(shí)，需4 臺(tái)無人機(jī)才能完成巡檢任務(wù)。

表3 16 種場(chǎng)景下的最優(yōu)路徑時(shí)間Tab.3 Optimal path time under 16 scenarios

可以發(fā)現(xiàn)，隨著船舶數(shù)量的增加，無人機(jī)巡檢總時(shí)間T 也呈增長(zhǎng)趨勢(shì)。雖然場(chǎng)景15 中船舶數(shù)量比場(chǎng)景11 中多20 艘，其總時(shí)間T 卻比場(chǎng)景11 少3.7 min，表明船舶數(shù)量是影響巡檢路徑時(shí)間的主要因素。當(dāng)航道中船舶數(shù)量為40 艘時(shí)，配備兩架續(xù)航時(shí)間為40 min 的無人機(jī)即可滿足巡檢要求；當(dāng)船舶數(shù)量為60 艘時(shí)，應(yīng)配備3 架續(xù)航時(shí)間為40 min的無人機(jī)或2 架續(xù)航時(shí)間為60 min 的無人機(jī)；而對(duì)于待檢測(cè)船舶數(shù)量較多的情況（80 艘、100 艘），則需要配備4 臺(tái)續(xù)航時(shí)間為40 min 的無人機(jī)才能夠順利完成巡檢任務(wù)。

當(dāng)船舶數(shù)量為60 和船舶數(shù)量為100 時(shí)，無人機(jī)數(shù)量對(duì)巡檢時(shí)間如圖5 所示。圖中方形、圓形線段為兩種場(chǎng)景下T 值的變化曲線，三角形線段為每增加一架無人機(jī)時(shí)T 值下降率的變化曲線。

圖5 不同無人機(jī)數(shù)量下的總巡檢時(shí)間Fig.5 Total inspection time under different numbers of UAVs

從圖5 可以看出，無人機(jī)數(shù)量的增加會(huì)減少巡檢路徑總時(shí)間，當(dāng)無人機(jī)數(shù)量由3 增加至4 時(shí)，T值下降率約51 %，變化最為顯著，而在無人機(jī)數(shù)量由4 增加至8 時(shí)，T 值下降率保持在14 %左右，巡檢效率提升不算明顯。由于內(nèi)河航道中船舶流量有明顯的高峰期與低谷期，配備2 架或3 架無人機(jī)不能夠滿足較多船舶數(shù)量情況的巡檢需求，故每個(gè)無人機(jī)基站配備4 臺(tái)無人機(jī)最為合理。

2）船舶速度和無人機(jī)速度對(duì)TPA 計(jì)算結(jié)果的影響

以場(chǎng)景15 為例，在vd為14、18、22、26、30 m/s的五種情景下，分別求出td為3、6、9、12 s 時(shí)的路徑總時(shí)間T，實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 不同飛行速度下的總檢測(cè)時(shí)間Fig.6 Total detection time at different flight speeds

圖6 顯示，在vd相同的情況下，td每增加3秒，T 值也隨之增長(zhǎng)，從3 s 增長(zhǎng)至6 s 時(shí)，T 值增長(zhǎng)量較小，約6 分鐘；從6 s 增長(zhǎng)至9 s 時(shí)，T 值的增長(zhǎng)量約23 分鐘；從9 s 增長(zhǎng)至12 s 時(shí)，T 值的增長(zhǎng)量更多，約42 分鐘?？梢妕d的增加表示無人機(jī)跟隨檢測(cè)所需長(zhǎng)時(shí)間的增加，同時(shí)由于其他船舶行駛得更遠(yuǎn)，也會(huì)導(dǎo)致巡檢時(shí)間的延長(zhǎng)。當(dāng)td保持不變時(shí)，隨著vd的增加，T 值逐漸減小，這是由于飛行速度提高導(dǎo)致檢測(cè)間隙時(shí)間縮短所致；此外，在vd由14 m/s 增加至22 m/s 的過程中T 值縮減幅度較大，但隨著vd值的繼續(xù)增加，T 值縮減幅度呈現(xiàn)逐漸減小趨勢(shì)。綜上分析，為提高巡檢效率，建議執(zhí)法部門選用速度22 m/s 的無人機(jī)，并選配檢測(cè)設(shè)備響應(yīng)時(shí)間小于6 s 的檢測(cè)儀來完成巡檢工作。

3 結(jié)語

為解決內(nèi)河船舶尾氣排放監(jiān)測(cè)工作中無人機(jī)自動(dòng)化巡檢的部署方案問題，本文以無人機(jī)總飛行長(zhǎng)度最小化為目標(biāo)函數(shù)，提出了一種多無人機(jī)動(dòng)態(tài)路徑規(guī)劃模型（MUPP），并采用“GT-K-means++” +“SAGA”的二階段算法（TPA）對(duì)這一NP-hard 問題進(jìn)行求解。以長(zhǎng)三角船舶排放控制區(qū)范圍內(nèi)長(zhǎng)江干線航道南京段為例，基于實(shí)時(shí)AIS 船舶航行數(shù)據(jù)，利用TPA 算法進(jìn)行實(shí)例分析，結(jié)果顯示：待檢船舶數(shù)量的增多會(huì)對(duì)無人機(jī)的數(shù)量及續(xù)航時(shí)長(zhǎng)有更高的要求，考慮到航道巡檢需求、無人機(jī)的巡檢效率，每個(gè)基站配備4 臺(tái)速度為22 m/s 的無人機(jī)，搭載檢測(cè)耗時(shí)少于6 s 的高性能檢測(cè)儀器較為合理。