白響恩　周俊杰　肖英杰　徐笑鋒　戚玉玲　沈建華　徐元　任鴻翔　曾建峰

摘要：

針對滴水湖新建無人船測試場的應(yīng)急保障問題，建立基于Maklink圖論和Dijkstra算法的多終點航道規(guī)劃模型。通過環(huán)境建模確定障礙物大小和位置;受PNPoly算法啟發(fā)，引入剔除函數(shù)進(jìn)行模型改進(jìn);利用Dijkstra算法在無向網(wǎng)絡(luò)圖中搜索從起點至終點的最短應(yīng)急航道，并利用蟻群算法對最短應(yīng)急航道集合進(jìn)行優(yōu)化。結(jié)果分析顯示，最終規(guī)劃的航道高效、安全，規(guī)劃結(jié)果可以為滴水湖管理工作和無人船測試場應(yīng)急保障提供參考。

關(guān)鍵詞：

滴水湖; 無人船測試場; 應(yīng)急保障; 航道規(guī)劃; Maklink圖論; Dijkstra算法

中圖分類號：? U612.1; U697.1

文獻(xiàn)標(biāo)志碼：? A

收稿日期： 2020-09-08

修回日期： 2020-11-22

基金項目：

國家自然科學(xué)基金（51909155）;上海市科學(xué)技術(shù)委員會項目（14170501600）

作者簡介：

白響恩（1984—），女，上海人，副教授，博士，研究方向為船舶交通管理，（E-mail）xebai@shmtu.edu.cn

Emergency support channel planning for unmanned ship

test site in Dishui Lake

BAI Xiangen1a，1b， ZHOU Junjie1a，1b， XIAO Yingjie1a，1b， XU Xiaofeng1a，1b，

QI Yuling1a，1b， SHEN Jianhua2， XU Yuan3， REN Hongxiang4， ZENG Jianfeng3

（1.a.Merchant Marine College; b.Engineering Research Center of Shipping Simulation， Ministry of Education，

Shanghai Maritime University， Shanghai 201306， China; 2.Shanghai Pilot Station， Shanghai 200080， China;

3.Shanghai Waterway Engineering Design and Consulting Co.， Ltd.， Shanghai 200120， China;

4.Navigation College， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In view of the problem of emergency support for the new built unmanned ship test site in Dishui Lake， a multi terminal channel planning model is established based on Maklink graph theory and Dijkstra algorithm. The size and location of obstacles are determined by environmental modeling. The model is improved by introducing the elimination function inspired by PNPoly algorithm. Dijkstra algorithm is used to search the shortest emergency channels from the starting point to the terminals in the undirected network diagram， and the ant colony algorithm is used to optimize the set of the shortest emergency channels. The analysis of the result shows that the final planned channel is of high efficiency and safety， and the planning result can provide reference for the management of Dishui Lake and the emergency support of the unmanned ship test site.

Key words：

Dishui Lake; unmanned ship test site; emergency support; channel planning; Maklink graph theory; Dijkstra algorithm

0 引 言

隨著近年來物聯(lián)網(wǎng)、大數(shù)據(jù)、云計算、人工智能等新理念、新技術(shù)的發(fā)展，無人船開始興起，船舶不斷向智能化過渡。相較于陸地環(huán)境和空中環(huán)境，水域環(huán)境的限制條件更多、安全風(fēng)險更大，因此對水域進(jìn)行航道規(guī)劃十分必要。水域環(huán)境尤其是具備一定觀光旅游條件的湖區(qū)，具有自身的獨特性，為保障觀光旅游的安全和可持續(xù)發(fā)展，在航道規(guī)劃中需要納入應(yīng)急保障因素。航道規(guī)劃的本質(zhì)是路徑規(guī)劃，其實現(xiàn)離不開算法的支持。這些算法根據(jù)其實現(xiàn)原理可分為非進(jìn)化型算法（如A*算法、人工勢場法、Floyd算法等）和進(jìn)化型算法（如TS算法、粒子群算法、遺傳算法等）兩類[1]。

傳統(tǒng)的路徑規(guī)劃模型的構(gòu)建較少結(jié)合具體情況改進(jìn)，所采用的算法比較單一，容易出現(xiàn)運算結(jié)果較差、易陷入局部最優(yōu)的情況，對復(fù)雜環(huán)境、特殊環(huán)境中的路徑規(guī)劃不夠有效。劉云翔等[2]通過實驗比較了A*算法與Dijkstra算法的搜索速度和搜索效率，以及在障礙物較多情況下的搜索效果;仝佳璐等[3]為解決空中航班流的運行問題，采用改進(jìn)的雙向Dijkstra算法求解多條改航路徑;朱小林等[4]在綜合各項因素的基礎(chǔ)上，針對海上應(yīng)急救援系統(tǒng)中應(yīng)急資源的決策問題建立了基于事件類型的應(yīng)急物資和船舶分配模型;余夢珺等[5]選取海洋相關(guān)指標(biāo)構(gòu)建出環(huán)境威脅場，利用蟻群算法對各目標(biāo)在不同救援時段具有不同權(quán)重的情況展開西北航道海上救援路徑規(guī)劃;謝新連等[6]根據(jù)海上施工水域的航道規(guī)劃問題，建立了以航線總長度最短為目標(biāo)函數(shù)、不可航行區(qū)域為約束條件的航線規(guī)劃數(shù)學(xué)模型。

為處置無人船在滴水湖新建無人船測試場測試期間發(fā)生的失控、碰撞或泄漏，甚至燃爆等危險情況，需要在測試場周圍設(shè)置多個應(yīng)急保障點，以確保意外事件發(fā)生后應(yīng)急救援迅速，因此規(guī)劃的航道應(yīng)該滿足高效性、安全性和易管理性。本文根據(jù)滴水湖實際環(huán)境，將剔除函數(shù)引入Maklink圖論中對環(huán)境模型進(jìn)行改進(jìn);考慮滴水湖地理環(huán)境的獨特

性、無人船測試場的影響及應(yīng)急保障等因素，選取3個目標(biāo)終點，利用Dijkstra算法進(jìn)行多終點航道規(guī)劃;結(jié)合蟻群算法

對規(guī)劃的航道進(jìn)行優(yōu)化，為滴水湖管理工作和無人船測試場應(yīng)急保障提供參考。

1 滴水湖無人船測試場現(xiàn)狀

1.1 背景概況

滴水湖位于上海市浦東新區(qū)南匯新城鎮(zhèn)，整個湖呈圓形，直徑約2 660 m，湖中心建有水滴雕塑，岸邊連接北島、西島和南島。隨著上海自貿(mào)試驗區(qū)臨港新片區(qū)的經(jīng)濟發(fā)展，滴水湖成為該地區(qū)的旅游中心，涉及游船、快艇等多種船舶航行活動。

“滴水湖無人船測試場項目”是由包括上海臨港海洋高新技術(shù)產(chǎn)業(yè)發(fā)展有限公司在內(nèi)的多家單位和組織共同參與的新興項目，旨在建立多功能前沿性無人船測試場。為保障無人船測試期間的安全，需要根據(jù)無人船測試場的布局對可能的突發(fā)情況制定應(yīng)急物資輸送、應(yīng)急救援實施的交通組織規(guī)劃尤其是航道規(guī)劃。目前滴水湖一號碼頭具備充足的配套資源和應(yīng)急保障能力。

1.2 通航環(huán)境

在建設(shè)無人船測試場前，滴水湖主要營運的船舶基本按照固定航線逆時針方向航行（見圖1），沒有一條真正意義上規(guī)范的航道。

無規(guī)范航道的現(xiàn)狀及無人船測試場的介入，勢必會對滴水湖內(nèi)通航環(huán)境造成很大影響。無人船在

滴水湖進(jìn)行測試時會占據(jù)很大一片水域，湖內(nèi)其他船舶活動水域?qū)⒋蠓s減，因此應(yīng)急保障航道規(guī)劃應(yīng)考慮這些實際情況，以確保應(yīng)急保障的快速、及時以及通航安全。

1.3 問題描述

船舶在滴水湖內(nèi)航行時會經(jīng)過在建的無人船測試場（見圖2中的扇形區(qū)域，其在建設(shè)完成前被定

義為施工障礙物，在建設(shè)完成后則被定義為一般障礙物）以及中心雕塑、北島、西島和南島等4個靜態(tài)障礙物。應(yīng)急保障船舶在水域內(nèi)航行應(yīng)避開這些障礙物，同時為保證應(yīng)急保障的全面性和及時性，需要根據(jù)無人船測試場地理位置為應(yīng)急保障船舶設(shè)置多個終點。本文結(jié)合相關(guān)圖論和算法設(shè)計出應(yīng)急保障船舶從起點到多個終點的多條合理路徑，實現(xiàn)滴水湖無人船測試場應(yīng)急保障航道規(guī)劃。

所有障礙物區(qū)域均需拓寬安全距離[7]。由于中心雕塑位于滴水湖正中位置，無論如何規(guī)劃應(yīng)急保障船舶均需經(jīng)過此處，所以中心雕塑對航道影響較大;無人船測試場作為應(yīng)急保障區(qū)域，在終點的數(shù)量和位置選取上要仔細(xì)斟酌。針對該情況，在中心雕塑處將安全距離拓寬60 m;把以無人船測試場外側(cè)的兩個端點為圓心、半徑為100 m的兩個圓形區(qū)

域作為終點選址區(qū)域（見圖2中虛線圓）;其余障礙

物處適當(dāng)拓寬安全距離。

最終選取1個起點S和3個終點T1、T2和T3。

2 應(yīng)急航道規(guī)劃總體流程

基于Maklink圖論和Dijkstra算法進(jìn)行應(yīng)急保障航道規(guī)劃，需要結(jié)合滴水湖的獨特環(huán)境進(jìn)行合理、有效的創(chuàng)新，使規(guī)劃出的航道安全且易于管理。應(yīng)急保障航道規(guī)劃主要包括坐標(biāo)系的繪制、障礙物的膨化處理、二維路徑規(guī)劃模型的建立與改進(jìn)以及算法的實現(xiàn)，具體流程見圖3。

3 環(huán)境模型

3.1 環(huán)境建模

由于滴水湖內(nèi)船舶所處位置海拔高度基本相同，所以環(huán)境模型建為二維模型。環(huán)境建模基于Maklink圖論[8-9]，考慮到其復(fù)雜性并涉及多圖展

示，作如下說明：①環(huán)境模型規(guī)格為3 000 m×

3 000 m。②自由鏈接線（采用虛線段表示）被定義為兩個障礙物之間不與障礙物相交的端點之間的連

線，以及障礙物端點到環(huán)境模型邊界線的垂直線段;省略個別鄰近的不具顯著實際效果的自由鏈接線;vi表示自由鏈接線

Li的中點

（以下簡稱“節(jié)點”），i∈N*。③障礙物并非全部為規(guī)則形狀，如北島、南島均為極不規(guī)則形狀，中心雕塑為圓形形狀，無人船測試場為近似扇形形狀。這類障礙物需要進(jìn)行“膨化處理”[10]，膨化處理后的障礙物由凸多邊形替代。④可行路徑（采用實線段表示）為每兩個節(jié)點有效相連的結(jié)果，其中“有效”指線段不可與其端點外的虛線線段相交，且線段不可穿越障礙物。經(jīng)拓寬安全距離和膨化處理后的障礙物見圖2。

構(gòu)建出的滴水湖無人船測試場的具體環(huán)境模型無向網(wǎng)絡(luò)圖見圖4。

3.2 模型改進(jìn)

基于Maklink圖論構(gòu)建的滴水湖無人船測試場環(huán)境模型，能夠完整包含在3 000 m×3 000 m的范圍內(nèi)。所規(guī)劃出的應(yīng)急航道不能超出滴水湖水域，因此需要將環(huán)境模型進(jìn)行改進(jìn)。

受PNPoly算法啟發(fā)，構(gòu)造剔除函數(shù)，對環(huán)境模型進(jìn)行改進(jìn)。

對待測點vi的坐標(biāo)（xvi， yvi）與多邊形頂點坐標(biāo)（設(shè)任一頂點e的坐標(biāo)（xe， ye），與e相鄰的另一個頂點r的坐標(biāo)（xr， yr））進(jìn)行相關(guān)運算，判斷vi是否處于多邊形內(nèi)部，核心公式為

xvi<（xr-xe）（yvi-ye）yr-ye+xe

如果上式成立，則節(jié)點vi位于多邊形頂點e與r之間邊的左側(cè)。依次對節(jié)點vi與多邊形其他邊的關(guān)系進(jìn)行判斷，若該節(jié)點位于多邊形邊的左側(cè)的情況總共有偶數(shù)次，則保留該節(jié)點，否則剔除該節(jié)點。

將PNPoly算法與Maklink圖論結(jié)合，并根據(jù)滴水湖的具體情況對環(huán)境模型進(jìn)行改進(jìn)，將環(huán)境模型從“多邊形”改為“圓形”，進(jìn)一步進(jìn)行篩選。先在模型中給出直徑為2 660 m的圓形界限，圓心坐標(biāo)為（1 330，1 330）m，與縱軸和橫軸分別相切于（0，1 330）m和（1 330，0）m;再將所有節(jié)點組成一個節(jié)點集合V;然后引入剔除函數(shù)f（vj），保留界限內(nèi)的節(jié)點，剔除界限外的節(jié)點;最后對變化后的自由鏈接線進(jìn)行處理。剔除函數(shù)構(gòu)造流程見圖5。

f（vj）=1， （xvj-xo）2+（yvj-yo）2≤1 3302

0， （xvj-xo）2+（yvj-yo）2>1 3302

式中：o表示圓心。

如圖6所示，給出圓形界限后，無效的自由鏈接線和節(jié)點均被剔除，Maklink圖中保留的自由鏈接線和節(jié)點在該界限內(nèi)，環(huán)境模型改進(jìn)后較改進(jìn)前更簡潔明了，保證了模型符合實際，也將有助于改善后續(xù)應(yīng)急保障航道規(guī)劃的效率。環(huán)境模型改進(jìn)結(jié)果見表1。

4 Dijkstra算法航道規(guī)劃

4.1 Dijkstra算法介紹

Dijkstra算法[11]是一種單源路徑算法，也是一種貪心算法，它以起始點為中心向外層層擴展直至終點，用來求解一個頂點到其余各頂點的最短路徑問題。Dijkstra算法十分簡潔，能夠有效地找到最優(yōu)解。基于Dijkstra路徑規(guī)劃的優(yōu)勢，對滴水湖應(yīng)急保障航道進(jìn)行規(guī)劃。在圖6的無向網(wǎng)絡(luò)內(nèi)從起點

到終點進(jìn)行路徑規(guī)劃，Dijkstra算法實現(xiàn)步驟[12]如下：

步驟1 對未確定最短路徑的節(jié)點集合Vk和已確定最短路徑的節(jié)點集合V′k進(jìn)行初始化操作（其中k為迭代次數(shù)），根據(jù)無向網(wǎng)絡(luò)圖的可行路徑計算各節(jié)點間的距離，同時建立帶權(quán)圖的鄰接矩陣M，相鄰節(jié)點間的權(quán)值即為距離對應(yīng)數(shù)值

，不相鄰節(jié)點間的權(quán)值賦值為∞，從起點S到相應(yīng)節(jié)點的最短路徑長度用數(shù)組D表示。

步驟2 選擇數(shù)組D中的最小值Di，將Di對應(yīng)的節(jié)點vi從集合Vk中取出，存入集合

V′k內(nèi)。

步驟3 根據(jù)節(jié)點vi修改更新Di中從起點S到集合Vk中其余節(jié)點的路徑長度。

步驟4 循環(huán)步驟2和步驟3的操作，重復(fù)迭代，直至尋找出從起點S到無向網(wǎng)絡(luò)圖中所有節(jié)點的最短路徑為止，并最終到達(dá)終點T。

4.2 應(yīng)急保障航道規(guī)劃

假設(shè)用Dijkstra算法規(guī)劃出的最短路徑經(jīng)過d個節(jié)點（起點和終點除外），

用

p（0）m和p（1）m分別表示以原點為起點、Lm（m=1，2，…，d）的兩個端點

為終點的向量，則Lm上其他點的表示方法為

式中：pm（χm）表示以原點為起點、Lm上任意一點為終點的向量;χm為0與1之間的隨機數(shù)，表示自由鏈接線比例參數(shù)。

求解數(shù)組D和矩陣M均需要知道各節(jié)點vi的坐標(biāo)，vi的坐標(biāo)應(yīng)根據(jù)各障礙物端點坐標(biāo)進(jìn)行計算，端點坐標(biāo)測量通過

AutoCAD 2020實現(xiàn)。利用Dijkstra算法得到從起點S至終點T1、T2和T3的3個22×

22階的鄰接矩陣M1、M2和M3：

Dijkstra算法求解通過MATLAB R2016a實現(xiàn)。得到的多終點應(yīng)急保障航道規(guī)劃結(jié)果（見圖7）分別為：S→v4→v5→v6→v9→v10→v18→v20→T1，距離為3 319.65m;S→v4→v8→v14→v13→v12→v11→T2，距離為2 829.27m;S→v4→v8→v14→T3，距離為1 696.09m。

5 蟻群算法航道優(yōu)化

5.1 優(yōu)化原理

蟻群算法是一種新型進(jìn)化算法，通過模擬螞蟻的行為規(guī)律（螞蟻在走過的路徑上會釋放一種信息素，后面的螞蟻會優(yōu)先選擇信息素濃度較高的路徑），根據(jù)正反饋機制尋找出最優(yōu)的路徑[13]。采用蟻群算法時需要離散化工作空間，由于最初選擇的自由鏈接線長短不一，需要采用固定距離劃分法。假設(shè)

ζ為劃分出的每段短線段的長度，每條自由鏈接線Lm的劃分段數(shù)為

Qm=int（Lm/ζ），int（Lm/ζ）為偶數(shù)

int（Lm/ζ）+1，int（Lm/ζ）為奇數(shù)

式中：當(dāng)int（Lm/ζ）為奇數(shù)時，因為路徑中點也是一個等分點，所以劃分段數(shù)需加1。經(jīng)過離散處理后，從自由鏈接線Lm-1到其相鄰的自由鏈接線Lm將有Qm+1條路徑可以選擇。

通過Dijkstra算法求得路徑后，只要給定一組參數(shù)（χ1，χ2，…，χd），就可以得到一條從起點到終點的新蟻群算法路徑。

設(shè)定q0為螞蟻對信息素感知的閾值（q0∈[0，1]），q為[0，1]內(nèi)的

一個隨機數(shù)，某只螞蟻在Lm+1上未走過的等分點集合為A，h∈A。當(dāng)該螞蟻到達(dá)Lm上某個等分點g時，采用輪盤賭法選擇Lm+1上的等分點：當(dāng)q≤q0時，以