陳立家+黃立文+崔梅

摘要：為提高船舶航線經(jīng)濟(jì)性，基于電子海圖顯示與信息系統(tǒng)（electronic chart display and information system，ECDIS），分析影響航線設(shè)計(jì)的各種因素，建立航線設(shè)計(jì)網(wǎng)絡(luò)模型。將改進(jìn)蟻群算法的基本原理應(yīng)用于船舶航行路徑搜索中，提出一種多約束條件下航行綜合成本最低的最優(yōu)航線生成算法。仿真試驗(yàn)證明，該算法是可行的，且具有動(dòng)態(tài)尋優(yōu)的特點(diǎn)，將其應(yīng)用于多約束條件下的最優(yōu)航線設(shè)計(jì)是合理的。

關(guān)鍵詞： 電子海圖顯示與信息系統(tǒng)（ECDIS）； 多約束； 船舶航線設(shè)計(jì)； 蟻群算法

中圖分類號(hào)： U692.33 文獻(xiàn)標(biāo)志碼： A

Abstract： In order to improve the economy of ship route， based on the electronic chart display and information system （ECDIS）， the various factors influencing route planning are analyzed， and a route planning network model is established. The basic principle of the improved ant colony algorithm is applied to ship path search. An optimal route generation algorithm under multiple constraints is proposed for the minimum integrated navigation cost. The simulation test shows that， the algorithm is feasible and of the characteristic of dynamic optimization， and it is reasonable to apply the algorithm to the optimal route planning under multiple constraints.

Key words： electronic chart display and information system （ECDIS）； multi-constraint； ship route planning； ant colony algorithm

0 引 言

隨著智能航海技術(shù)的發(fā)展，實(shí)時(shí)航路規(guī)劃已成為利用電子海圖顯示與信息系統(tǒng)（electronic chart display and information system，ECDIS）進(jìn)行研究的最新方向之一。李源惠等[1]根據(jù)電子海圖數(shù)據(jù)庫(kù)特有的性質(zhì)，結(jié)合礙航物的判別標(biāo)準(zhǔn)和船舶的航行狀態(tài)，提出了基于電子海圖的自動(dòng)判別計(jì)劃航線可行性的方法。CHANG等[2]依靠柵格電子海圖平臺(tái)，對(duì)迷宮算法進(jìn)行適當(dāng)改進(jìn)，提出了解決最短航線距離問(wèn)題的方法。RAFAL[3]采用分析避碰和轉(zhuǎn)向條件的策略優(yōu)化航線。葉清等[4]利用某個(gè)港口與多個(gè)港口之間的船舶交通網(wǎng)絡(luò)圖，提出了找到一條最佳航線的方法。王德春等[5]通過(guò)構(gòu)建航運(yùn)網(wǎng)絡(luò)圖，利用A*啟發(fā)式搜索算法，提出了找到船舶最佳航線的方法。此外，王科[6]依據(jù)Dijkstra算法的基本思想對(duì)軍事航線的最優(yōu)化問(wèn)題進(jìn)行了研究。

蟻群算法具有很好的魯棒性，被廣泛地應(yīng)用于求解船舶航行的最短路徑問(wèn)題。聶皓冰等[7]引入空間數(shù)據(jù)索引結(jié)構(gòu)來(lái)實(shí)現(xiàn)航行信息的快速檢索，提出了基于航行信息空間連通矩陣的改進(jìn)蟻群算法。陳寶文[8]根據(jù)艦船路徑規(guī)劃的技術(shù)特點(diǎn)，提出了一種基于鄰域變異的改進(jìn)微分進(jìn)化算法。朱青[9]針對(duì)船舶航行環(huán)境的特點(diǎn)，采用MAKLINK法建立海洋環(huán)境模型，提出了基于蟻群算法的全局路線搜索模型。何立居等[10]基于蟻群算法進(jìn)行了航線自動(dòng)生成的研究，在電子海圖中通過(guò)案例證明了蟻群算法用于航線自動(dòng)生成的可行性。然而，這些研究都主要集中在算法改良上，路徑選擇主要滿足路徑最短這一目標(biāo)，即在一個(gè)約束條件下的最優(yōu)路徑問(wèn)題。

在水上交通中，在多約束條件下的最優(yōu)航線設(shè)計(jì)問(wèn)題是在給定的帶有多個(gè)約束的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中尋找一條或多條滿足限定條件的路徑的問(wèn)題，其約束條件可以為水深、路徑長(zhǎng)度、與障礙物距離等。本文以電子海圖為基礎(chǔ)，對(duì)多約束條件下船舶航行路徑最短問(wèn)題進(jìn)行研究。

1 航線設(shè)計(jì)問(wèn)題描述

在多約束條件下船舶最優(yōu)航線選擇是，某船舶在滿足給定的約束條件的情況下，在起始港口與目的港口之間找到一條成本最小或者達(dá)到特定的服務(wù)水平的航線。兩個(gè)港口之間有任意多條可供船舶航行的航線，它們經(jīng)過(guò)不同的港口和錨地，同時(shí)存在多種約束和一些點(diǎn)、線、面的礙航物，這組成了一張航線網(wǎng)絡(luò)圖。在電子海圖中根據(jù)相關(guān)約束條件來(lái)確定礙航區(qū)，在起始港口與目的港口之間的可航區(qū)域內(nèi)，按照一定間隔依次遍歷每一個(gè)水深點(diǎn)，若符合預(yù)先規(guī)定的約束條件要求，則將該航路點(diǎn)抽象為一個(gè)節(jié)點(diǎn)，同時(shí)將要經(jīng)過(guò)的港口也當(dāng)作節(jié)點(diǎn)抽象出來(lái)，節(jié)點(diǎn)之間的距離為廣義上的航行距離，這樣就抽象出一張帶權(quán)網(wǎng)絡(luò)圖[9，11]。

尋找從起始港口到目的港口的最短路徑問(wèn)題[12-14]，可以轉(zhuǎn)化成在帶權(quán)網(wǎng)絡(luò)圖中對(duì)單源節(jié)點(diǎn)最短路徑問(wèn)題的分析，故在航線網(wǎng)絡(luò)圖上尋找最短路徑問(wèn)題就轉(zhuǎn)化為圖論中的最短路徑問(wèn)題。節(jié)點(diǎn)、弧、權(quán)值三要素組成了帶權(quán)網(wǎng)絡(luò)圖。節(jié)點(diǎn)為航路點(diǎn)、港口、交叉點(diǎn)以及斷點(diǎn)；弧為兩節(jié)點(diǎn)間的有向弧段；權(quán)值為航段某個(gè)或者某些特性的量化值。因此，帶權(quán)航線網(wǎng)絡(luò)圖就轉(zhuǎn)化為一個(gè)帶權(quán)有向圖，并且權(quán)值的獲取是基于時(shí)間段的。假設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，船舶可通過(guò)第i個(gè)節(jié)點(diǎn)的時(shí)間段為[til，tir]，實(shí)際通過(guò)該節(jié)點(diǎn)的時(shí)刻為ti。這樣，節(jié)點(diǎn)就增加了時(shí)間約束：til≤ti≤tir（1≤i≤N）。設(shè)置約束函數(shù)Qi（ti）來(lái)體現(xiàn)這個(gè)時(shí)間約束對(duì)最優(yōu)航線設(shè)計(jì)的影響：endprint

2 多元約束及其參數(shù)

按照航線影響因素的不同，有靜態(tài)權(quán)值和動(dòng)態(tài)權(quán)值。靜態(tài)權(quán)值是用船舶航行距離衡量航線權(quán)重以達(dá)到最短距離的目標(biāo)，動(dòng)態(tài)權(quán)值是用經(jīng)濟(jì)效益衡量航線權(quán)重以獲得航行時(shí)燃料消耗最少的目標(biāo)。

航行費(fèi)用E=E1+E2+E3，其中E1表示燃料消耗所產(chǎn)生的費(fèi)用，E2表示航行時(shí)間價(jià)值所產(chǎn)生的費(fèi)用（隱形的費(fèi)用），E3表示航行過(guò)程中所繳納的費(fèi)用。這很明顯地體現(xiàn)出一些經(jīng)濟(jì)因素，比如將航行距離和航行時(shí)間都折算為費(fèi)用。

航行質(zhì)量指航線能滿足人們需求的程度。對(duì)影響航行質(zhì)量的一切性能指標(biāo)進(jìn)行綜合評(píng)價(jià)，得到航線質(zhì)量權(quán)值：M=σ1T+σ2D+σ3Q，σ1+σ2+σ3=1

（3）式中：T是船舶在航線上的平均行程時(shí)間；D是航行過(guò)程中所消耗的燃料；Q是航線的舒適度；σ1，σ2和σ3為權(quán)重因數(shù)，分別體現(xiàn)了T，D和Q在航線質(zhì)量中所占的權(quán)重。

在多約束條件下的航線權(quán)值計(jì)算方法：根據(jù)水文氣象資料，得知在某時(shí)間段內(nèi)船舶在可航區(qū)域各航段的海況信息、風(fēng)浪信息和水深信息，以及船舶在風(fēng)浪中的臨界速度。

V=1T+2W+3S， 1+2+3=1

（4）

式中：T是基于靜態(tài)因素的船舶在航線上的平均行程時(shí)間（=航程/基本航行速度）；W是關(guān)于風(fēng)的信息值，包含風(fēng)的大小和方向；S是關(guān)于浪的信息值；1，2和3分別表示T，W和S所占的權(quán)重。另外，當(dāng)風(fēng)浪超過(guò)一定級(jí)別時(shí)，船舶航速會(huì)發(fā)生變化，此時(shí)用確定好的臨界速度來(lái)計(jì)算T。

3 在多約束條件下最優(yōu)航線設(shè)計(jì)算法

3.1 基本思想

本文提出一種在多約束條件下航行綜合成本最低的最優(yōu)航線生成算法（an optimal route generation algorithm based on the minimum integrated navigation cost under multiple constraints，ORGA）。當(dāng)兩港口之間有多條航線可供選擇時(shí)，可應(yīng)用Dijkstra算法求得最短航線。根據(jù)各種環(huán)境因素對(duì)航線的影響，用改進(jìn)的蟻群算法使生成的航線達(dá)到最優(yōu)。改進(jìn)的蟻群算法的基本思想為：（1）在每只螞蟻完成一遍搜索后，在信息素濃度更新之前，對(duì)所有螞蟻按照其所走過(guò)的路徑的長(zhǎng)度由短到長(zhǎng)進(jìn)行排序；在信息素濃度更新時(shí)，對(duì)挑選出來(lái)的前h只螞蟻，適當(dāng)增加其所走過(guò)的路徑的信息素量，對(duì)后面的m-h只螞蟻，適當(dāng)減少其所走過(guò)的路徑的信息素量，這樣就拉開了優(yōu)、劣螞蟻所走過(guò)的路徑之間的差距，從而提高找到最優(yōu)路徑的速度。（2）為削弱上述策略引起的蟻群陷入早熟的局限，采用MMAX優(yōu)化思想，將各路徑上的信息素濃度限制在[τmin，τmax]內(nèi)，若某路徑上的信息素濃度超過(guò)這個(gè)范圍，則按就近原則將其設(shè)為τmin或τmax，這就避免了算法過(guò)早收斂并陷入局部最優(yōu)解的問(wèn)題，也避免了搜索過(guò)程中的停滯現(xiàn)象。（3）因?yàn)樵贠RGA中對(duì)路徑上的信息素濃度進(jìn)行了人為控制，導(dǎo)致了各路徑上的信息素濃度兩級(jí)分化比較嚴(yán)重，所以將路徑上信息素的殘留系數(shù)設(shè)得較低。為有助于增加初始階段螞蟻的搜索能力，將各路徑上的信息素濃度初始值設(shè)為τmax。

3.2 算法實(shí)現(xiàn)

通過(guò)釋放人工螞蟻來(lái)創(chuàng)建基于螞蟻算法的網(wǎng)絡(luò)模型。

算法涉及的函數(shù)和變量如下：ηij=1/（dij（1+Rij（1+Wij）+Cij））

（5）式中：ηij為啟發(fā)函數(shù)；dij為相鄰兩節(jié)點(diǎn)間的距離；Rij為風(fēng)浪狀況因子；Wij為天氣情況因子；Cij為海況因子。各因子都是非負(fù)的。對(duì)螞蟻k而言，該啟發(fā)函數(shù)表示它從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的期望程度。各因子都是通過(guò)觀測(cè)得到的。

τij（t）為t時(shí)刻在邊（i，j）上的信息素濃度；tij為船舶從i行駛到j(luò)的時(shí)間，用權(quán)值cij表示；tij，l=til+tij，tij，r=tir+tij；α為期望啟發(fā)因子，表示軌跡的相對(duì)重要度；β為能見度的相對(duì)重要度；ψ為時(shí)間約束因子，表示時(shí)間約束的相對(duì)重要度；q為一個(gè)取值范圍為[0，1]的變量，它決定選擇下一個(gè)城市的概率；q0為一個(gè)給定的[0，1]間的常數(shù)，其值越小表示螞蟻隨機(jī)選擇下一個(gè)節(jié)點(diǎn)的概率越大；Ak（k=1，2，…，m）為螞蟻k已走過(guò)的節(jié)點(diǎn)集合，即為禁忌表；m為螞蟻的數(shù)量；Bk為允許螞蟻k下一步選擇的節(jié)點(diǎn)集合；Q為每只螞蟻所持有的信息素總量；Lk為節(jié)點(diǎn)i與j之間的路徑長(zhǎng)度。

3.3 算法具體步驟

ORGA的具體步驟如下：

步驟1 將各控制參數(shù)初始化：時(shí)間t=0；循環(huán)次數(shù)Nc=0；每條航段（i，j）的初始化信息素濃度τij（0）=τmax；最大循環(huán)次數(shù)為Nc，max；全局最優(yōu)解為L(zhǎng)g。

步驟2 將m只螞蟻置于起點(diǎn)，建立候選節(jié)點(diǎn)列表M。

步驟3 對(duì)螞蟻k（k=1，2，…，m），在候選節(jié)點(diǎn)列表中找出其未走過(guò)的節(jié)點(diǎn)（M-Ak），并在這些節(jié)點(diǎn)中根據(jù)式（6）（狀態(tài)轉(zhuǎn)移規(guī)則）選擇該螞蟻訪問(wèn)的下一個(gè)節(jié)點(diǎn)，直到所有的節(jié)點(diǎn)都被訪問(wèn)為止。

步驟4 判斷已完成搜索的螞蟻數(shù)量是否為m，是則執(zhí)行步驟5，否（即還有螞蟻未完成搜索）則返回步驟3，直到所有螞蟻都完成搜索為止。

步驟5 計(jì)算每只螞蟻的搜索路徑長(zhǎng)度Lk（k=1，2，…，m），并且對(duì)螞蟻按照其所走過(guò)的路徑長(zhǎng)度由短到長(zhǎng)的順序進(jìn)行排序。對(duì)于排名前h的螞蟻，設(shè)置本次路徑Llocal為本次最優(yōu)路徑，Llocal=hk=1Lk，同時(shí)保存最優(yōu)路徑表。

步驟6 對(duì)所有路徑上的信息素濃度按式（8）進(jìn)行全局更新，在本次循環(huán)中對(duì)排名前h的螞蟻所經(jīng)過(guò)的路徑上的信息素濃度按該螞蟻所在的名次進(jìn)行增加。信息素濃度更新的同時(shí)，按照式（7）來(lái)優(yōu)化替換，以便螞蟻產(chǎn)生新的搜索路線。

步驟7 將本次最優(yōu)路徑Llocal與全局最優(yōu)解Lg比較，較小的值存入Lg，并更新全局最優(yōu)路徑表。endprint

步驟8 若每只螞蟻的路徑都收斂于同一條路徑，則算法結(jié)束。判斷Nc與Nc，max是否相等，若相等，則流程結(jié)束；否則，清空禁忌表Ak，轉(zhuǎn)至步驟3。4 算法檢驗(yàn)

4.1 復(fù)雜度分析

假設(shè)航線網(wǎng)絡(luò)結(jié)構(gòu)中有N個(gè)節(jié)點(diǎn)，采用傳統(tǒng)的Dijkstra算法，需要的時(shí)間為N（N-1）=N2-N，該算法的時(shí)間復(fù)雜度為O（N2）。ORGA是針對(duì)傳統(tǒng)Dijkstra算法搜索時(shí)間過(guò)長(zhǎng)和基本的蟻群算法存在早熟和停滯現(xiàn)象而提出來(lái)的，它適當(dāng)?shù)馗倪M(jìn)蟻群算法，對(duì)一次循環(huán)完成后的所有螞蟻按照路徑長(zhǎng)短排序，雖然增加了空間復(fù)雜度，但讓螞蟻能夠更快地找到最優(yōu)路徑，從而提高了算法的執(zhí)行效率。

4.2 收斂性分析

ORGA是以航線網(wǎng)絡(luò)圖為基礎(chǔ)，并以蟻群算法為基本思想的最優(yōu)航線生成算法。Gutjahr W J已經(jīng)在理論上對(duì)圖搜素螞蟻系統(tǒng)（graph-based ant system，GBAS）的收斂性進(jìn)行了證明，在符合一些前提條件時(shí)，GBAS可以以接近于1的概率收斂于最優(yōu)解，而ORGA也滿足GBAS的4個(gè)條件：

（1）經(jīng)過(guò)仿真試驗(yàn)并按照經(jīng)驗(yàn)，可以將參數(shù)α取值為1。

（2）設(shè)計(jì)航線時(shí)，一般從起點(diǎn)到終點(diǎn)的最優(yōu)航線與從終點(diǎn)到起點(diǎn)的最優(yōu)航線是不一致的，這是因?yàn)楦鞣N環(huán)境因素的影響等都不盡相同，并且還伴隨著順流逆流問(wèn)題的存在，所以最優(yōu)路徑也是唯一的。

（3）根據(jù)式（5），期望因子ηij>0。

（4）信息素濃度更新使用的是全局更新策略，只是對(duì)前h只螞蟻所走過(guò)的路徑適當(dāng)增加額外的信息素量。

5 仿真試驗(yàn)

5.1 仿真環(huán)境

實(shí)驗(yàn)采用OpenCPNSDK，它是對(duì)OpenCPN進(jìn)行封裝后，提供給電子海圖應(yīng)用系統(tǒng)開發(fā)商進(jìn)行二次開發(fā)的組件包，可提供COM組件和C+ +動(dòng)態(tài)庫(kù)兩種形式封裝，支持WINDOWS，WINCE和LINUX平臺(tái)。利用OpenCPNSDK，用戶可開發(fā)出自己的支持S57和S52標(biāo)準(zhǔn)的電子海圖系統(tǒng)，并與雷達(dá)、AIS等系統(tǒng)結(jié)合，開發(fā)出多種船用或岸上應(yīng)用系統(tǒng)。OpenCPNSDK可根據(jù)用戶的應(yīng)用需求提供靈活的、有針對(duì)性的封裝，從而最大程度地幫助用戶增強(qiáng)系統(tǒng)功能，提高系統(tǒng)性能，縮短開發(fā)周期和減少開發(fā)成本。在Visual Studio 2008平臺(tái)下，基于組件包OpenCPNSDK采用VC+ +語(yǔ)言進(jìn)行系統(tǒng)開發(fā)。

5.2 結(jié)果

Dijkstra算法中兩節(jié)點(diǎn)之間的權(quán)值大小按照式（4）進(jìn)行設(shè)置，設(shè)定1=0.4，2=0.3，3=0.3。ORGA中的各參數(shù)設(shè)置如下：α=1，β=5，ρ=0.2，m=60，w=m/2。式（5）中：dij和Rij范圍均為[0，10]；Wij的范圍為[0，5]（陰晴用0表示；小雨或小雪在[0.1，0.2）內(nèi)取值；中雨或中雪在[0.2，0.5）內(nèi)取值；大雨或大雪在[0.5，1）內(nèi)取值；暴風(fēng)雨在[1，3）內(nèi)取值；大霧在[3，5]內(nèi)取值）；Cij，海況正常用0表示，有暴浪致使不能航行的情況用∞表示。以下是航行起點(diǎn)為寧波-舟山港蝦峙門的進(jìn)口燈船，終點(diǎn)為金塘港，航線規(guī)劃經(jīng)過(guò)蝦峙門航道和螺頭航道，使用Dijkstra算法和ORGA生成的最短距離航線分別見圖1和2。圖1中所得最優(yōu)航線的里程為45.6 n mile，轉(zhuǎn)向點(diǎn)數(shù)為18；圖2中所得最優(yōu)航線的里程為42.8 n mile，轉(zhuǎn)向點(diǎn)數(shù)為6。

由試驗(yàn)可知：ORGA克服了Dijkstra算法對(duì)復(fù)雜礙航區(qū)處理不完備的問(wèn)題，進(jìn)一步優(yōu)化了航線繞行礙航區(qū)的策略；ORGA耗時(shí)2.450 s，而Dijkstra算法耗時(shí)4.556 s，故ORGA相對(duì)Dijkstra算法在時(shí)間上有明顯優(yōu)勢(shì)。

6 結(jié)束語(yǔ)

分析了各種環(huán)境因素對(duì)航線設(shè)計(jì)的影響，簡(jiǎn)述了各種影響因素的來(lái)源和確定方法，提出了在電子海圖顯示與信息系統(tǒng)（ECDIS）中以航行綜合成本最低為目標(biāo)的航線設(shè)計(jì)算法。重點(diǎn)討論了基于電子海圖的最優(yōu)航線算法的設(shè)計(jì)，并且對(duì)所提出的算法進(jìn)行了仿真試驗(yàn)分析，達(dá)到了預(yù)期的效果。

參考文獻(xiàn)：

[1] 李源惠， 孫少鵬. 電子海圖中計(jì)劃航線可行性的自動(dòng)判別[J]. 大連海事大學(xué)學(xué)報(bào)， 2000， 26（2）： 40-43.

[2] CHANG K Y， JAN G E， PARBERRY I. A method for searching optimal routes with collision avoidance on raster charts[J]. The Journal of Navigation， 2003， 56（3）： 371-384.

[3] RAFAL S. A new method of ship routing on raster grids， with turn penalties and collision avoidance[J]. The Journal of Navigation， 2006， 59（1）： 371-384.

[4] 葉清， 郁振偉. 改進(jìn)最短路徑算法在最佳航線選擇中的應(yīng)用[J]. 中國(guó)航海， 2003， 55（2）： 15-17.

[5] 王德春， 陳利敏， 張孝芳. 基于A*算法的艦船最佳選擇[J]. 青島大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2005， 18（4）： 10-13.

[6] 王科. 基于電子海圖的航線設(shè)計(jì)研究[D]. 大連： 海軍大連艦艇學(xué)院， 2004.

[7] 聶皓冰， 王勝正， 胡志武， 等. 航線動(dòng)態(tài)優(yōu)化算法在海上搜救中的應(yīng)用[J]. 上海海事大學(xué)學(xué)報(bào)， 2011， 32（4）： 1-6.

[8] 陳寶文. 蟻群優(yōu)化算法在車輛路徑問(wèn)題中的應(yīng)用研究[D]. 哈爾濱： 哈爾濱工業(yè)大學(xué)， 2009.

[9] 朱青. 基于蟻群算法的船舶航行設(shè)計(jì)方法的研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 2011.

[10] 何立居， 李啟華. 基于蟻群算法的航線自動(dòng)生成研究[J]. 中國(guó)航海， 2009， 32（3）： 71-75.

[11] BIJLSMA S J. On the applications of the principle of optimal evolution in ship routing[J]. Journal of the Institute of Navigation， 2004， 51（2）： 93-100.

[12] 馬榮貴， 崔華， 薛世焦. 改進(jìn)蟻群算法的多約束質(zhì)量最優(yōu)路徑選擇[J]. 西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2016， 43（3）： 185-189.

[13] 湯青慧， 唐旭， 崔曉暉. 基于動(dòng)態(tài)通達(dá)網(wǎng)絡(luò)模型的最優(yōu)航程規(guī)劃方法[J]. 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）， 2015， 40（4）： 521-526.

[14] 李松江， 張異， 龔躍.基于蟻群算法的智能交通最優(yōu)路徑研究[J]. 長(zhǎng)春理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015， 38（4）： 122-126.

（編輯 趙勉）endprint