海上施工水域船舶航線規(guī)劃數(shù)學建模及求解

謝新連，劉 毅，何 傲

(大連海事大學 交通運輸工程學院 , 遼寧 大連 116026)

0 引 言

水上施工會給通行船舶帶來許多限制和安全風險，海上施工水域往往也是交通事故的高發(fā)區(qū)域。當施工環(huán)境比較復雜、通航限制較多時，船舶安全航線的設計就顯得格外重要，也具有難度。特殊水域上船舶航線自動規(guī)劃的發(fā)展將很大程度決定現(xiàn)代無人駕駛船舶技術的發(fā)展水平。早在現(xiàn)代智能化無人船出現(xiàn)之前，路徑規(guī)劃已經有大量的相關研究[1]

傳統(tǒng)的船舶航線規(guī)劃是指在靜態(tài)和動態(tài)障礙物并存的環(huán)境中，尋找一條從已知起點到終點的滿足一定評價標準的航行路徑，使得船舶在航行過程中能夠安全可靠地避開所有的障礙物[2]。常見的航線規(guī)劃方法有動態(tài)規(guī)劃法、最速下降法、最優(yōu)控制法、啟發(fā)式搜索法、神經網(wǎng)絡法、模擬退火法、遺傳算法等。由于每種航線規(guī)劃算法都或多或少存在一些缺陷，所以實際應用的方法大多數(shù)是基本算法的改進算法，或者融合了數(shù)種基本航線規(guī)劃算法的算法[3]。孟祥杜[4]做了無人船路徑規(guī)劃算法研究，針對無人船工作水域具有不規(guī)則邊界且常常存在障礙物的特點，也介紹了幾種常用的建立環(huán)境模型的方法。

環(huán)境建模也是智能駕駛技術研究最基本、最關鍵的環(huán)節(jié)之一，在環(huán)境建模方面的研究，王飛等[5-7]采用柵格法進行環(huán)境建模，提出了基于Maklink圖和遺傳算法的改航路徑規(guī)劃方法，并且利用遺傳算法對Maklink圖中的初始飛行器航線進行了改航規(guī)劃；李明富等[8]在Maklink圖的基礎上采用變參數(shù)螢火蟲算法對路徑進行優(yōu)化，實驗表明改進后的螢火蟲算法能夠較好的解決離散路徑規(guī)劃問題；孟祥杜[4]做了無人船路徑規(guī)劃算法研究，針對無人船工作水域具有不規(guī)則邊界且常常存在障礙物的特點，也介紹了幾種常用的建立環(huán)境模型的方法。

由以上的文獻可以發(fā)現(xiàn)，目前研究的問題主要集中在普通或正常環(huán)境下各種交通工具的路徑的規(guī)劃。然而在特殊環(huán)境下的路徑規(guī)劃研究則較為罕見。而且船舶的路徑規(guī)劃和航線設計有其自身的特殊性，船舶在水中的操作性能和陸上的交通工具或機器人也有較大差異，因此不能生搬硬套其它交通工具的路徑規(guī)劃的方法。船舶在海上航行時事故頻發(fā)的區(qū)域就是海上的施工區(qū)域，海上施工種類繁多，對其附近船舶的影響也各不相同，為了保證船舶能夠順利的通過施工水域，有必要對施工水域的船舶航線規(guī)劃進行相關的研究。

1 問題描述及環(huán)境模型的構建

船舶在海上航行時可能會經過某些施工水域，并且在有的水域中同時包含多個水面和水下施工地點，當在同一片施工水域中包含多個施工點時，船舶在其中的航行將變得極為復雜和危險，假設船舶在某施工水域中的環(huán)境示意如圖1。

圖1中，S為航線規(guī)劃的起點，T為航線規(guī)劃的終點，其中的陰影部分表示海上的施工區(qū)域。

為了方便施工水域的航線規(guī)劃數(shù)學模型的建立，首先利用Maklink圖論的方法來處理施工水域的危險區(qū)域，通過在施工水域中構造Maklink鏈接圖來構造施工水域中的可航行網(wǎng)絡圖，構造Maklink航線網(wǎng)絡圖的具體步驟可以參考文獻[5, 8]。由于船舶始終是處于海平面高度，因此筆者建立數(shù)學模型時不考慮海拔高度的影響，將環(huán)境模型的構建簡化為二維平面。另外對施工水域中所有的不可航行區(qū)域都采用凸多邊形或多個凸多邊形的組合來表示。在模型化表示不可航行區(qū)域的基礎上進一步構造可航行的自由空間，海上施工水域的可航行自由空間是由鏈接線構成的凸多邊形。在圖1的環(huán)境模型中構造的可航行自由空間如圖2。

圖1 施工水域環(huán)境示意Fig. 1 Schematic diagram for construction waters

圖2 可航行自由空間Fig. 2 Nautical free space map

構造可自由航行空間圖時主要需要遵循以下兩個基本準則：①所構造的鏈接線不能夠穿越施工水域中的危險區(qū)域；②鏈接線的一端是施工水域的危險區(qū)域所構成的凸多邊形的頂點，另一端是另一個施工危險區(qū)域構成的凸多邊形的頂點或者是施工水域的自由空間的邊界點。

在施工水域的自由空間中，將所有鏈接線的中點兩兩相連所形成的圖就是需要構造的可航行區(qū)域的Maklink航線網(wǎng)絡圖，如圖3。

圖3 施工水域的MaklinkFig. 3 Maklink diagram for construction waters

2 海上施工水域航線規(guī)劃的數(shù)學模型

將圖3中構造的Maklink航線圖，進一步表述為可求解的數(shù)學模型。假設由起點S到終點T的一條在施工水域中的航線是由點序列(S,p1,p2,…,pk,T)組成，數(shù)學建模時其目標方程就是點序列所構成的航線的距離最短。在點序列中，船舶在除了起點S和終點T以外的所有中間點處都有可能轉向，為此我們需要考慮轉向角對船舶航行的約束，船舶在一定的航行速度下，船舶在pi處的轉向角我們用θpi來表示，它不能超過其轉向角的極限角度，用φmax表示船舶在設計航速下的轉向極限角度。另一方面船舶的轉彎半徑也是航線設計中必須考慮的一個重要因素，船舶轉彎的轉彎半徑和船舶所處的航行速度有很大的關系，根據(jù)參考文獻[9-10]中指出船舶在沒有拖輪的輔助的情況下在10 kn的設計航速下船舶的最小轉彎半徑可按表1 的設計參數(shù)選取。

表1 航道轉彎半徑設計指標Table 1 Channelturning radius design index

根據(jù)十一五科技攻關項目“沿海深水港航道選線及設計主要研究”中[11]，對10萬噸級集裝箱船、15萬噸集裝箱船和10萬噸級LNG船舶在不同轉向和航速情況下的轉彎進行的模擬研究，得出了航道的轉彎半徑R也可按照公式(1)估算：

(1)

式中：R為航道設計的轉彎半徑,m；Vt為航道的設計行駛速度，kn;L為航道的通行船長,m；θ為船舶在某點需要轉向的角度,(°)。

研究發(fā)現(xiàn)航道的轉向角達到60°時，船舶的操縱出現(xiàn)操縱困難的現(xiàn)象，船舶操縱人員不易掌握船位、轉向角速率及在航道上的姿態(tài)；當轉向角達到90°時，操縱極為困難，對操作人員的壓力極大，特別是在風、浪、流等自然因素的共同作用下，過彎操作的失誤率明顯增加[12]。因此在進行航線規(guī)劃時，得到的航線必須滿足船舶在設計航速下在各個轉向點處的轉向角度小于等于90°。

考慮這些因素后，建立船舶在海上施工水域中航線規(guī)劃的數(shù)學模型如式(2)～式(6)。

(2)

s.t.

?l(pi，pi+1)∩Sj=?,i=1,2,3,…,n,j=1,2,3,…,m

(3)

?θPj∈(1,…,k)≤φmax

(4)

RPj∈(1,.…,k)≥λL

(5)

D≥Dmin

(6)

模型的解釋：公式(2)表示目標方程，其中(pi,pi+1)表示由pi和pi+1兩點構成的航段，d(pi,pi+1)表示航段(pi,pi+1)間的距離，式中k表示路徑終點T前的最后一個節(jié)點。目標方程由三部分組成，第一部分表示組成航線的中間航段的長度總和，后面兩部分表示連接起點和終點的航段長度。公式(3)表示構成航線的任意航段與施工水域的危險區(qū)域的交集為空集，其中l(wèi)(pi,pi+1)表示由pi和pi+1兩點連接形成的航段的點集；Sj表示施工水域中危險區(qū)域的點集。公式(4)表示船舶在第pj節(jié)點處的轉向角必須小于航線設計航速下船舶的最大安全轉向角φmax，由前面的研究結果可知一般情況下φmax≤90°。公式(5)表示的是在pj節(jié)點處船舶進行轉向時，航線必須滿足船舶最小轉彎半徑的要求，其中L表示船舶的長度,m；λ表示航道在不同設計航速下所取的最小轉彎半徑與船長的比值。公式(6)表示規(guī)劃航線與危險區(qū)域的最小距離的約束；D表示航線某處與危險區(qū)域的最小距離；Dmin表示船舶與危險區(qū)域的最小安全距離,m。

3 Dijkstra算法求解航線規(guī)劃數(shù)學模型

對建立的數(shù)學模型的求解，采用兩階段優(yōu)化求解的方法：第一階段采用Dijkstra算法，在建立的Maklink可航行航線網(wǎng)上搜尋經過網(wǎng)絡節(jié)點的最短航線；第二階段再利用蟻群算法對得到的初始解優(yōu)化，最終得到最優(yōu)的航線。

Dijkstra算法是用于解決非負權值網(wǎng)絡中尋找指定兩點間最短距離的最好的算法之一。Dijkstra算法的基本思想是采用標號法，給每個節(jié)點預先設置兩個標簽，其中一個用于標記路長，另一個是用于標記從起點到終點路徑的最后一條弧的起始點號。網(wǎng)絡節(jié)點的標號分為兩類，一類是永久標號，另一類是臨時標號。當?shù)恋趉步時，獲得永久標號的點意味著已經找到起點到該點的最短路徑，將獲得永久標號的點放在Sk集合中，獲得永久標號的點的路長d值和路徑標號ξ值不再修改。

在利用Dijkstra算法求解前，需要得到Maklink圖中網(wǎng)路節(jié)點各點間的鄰接距離矩陣，航線網(wǎng)絡圖的鄰接距離矩陣為一個19×19階的矩陣，即：

在鄰接距離矩陣中，∞表示兩個節(jié)點不連通，其距離為無窮大，其中的數(shù)字25則表示p1和p3是連通的，并且兩點間的距離為25 km。利用Dijkstra算法求解得到的結果的總距離為221.573 0 km，其路徑依次為S-p8-p9-p2-p1-p12-p13-T。航線規(guī)劃的結果如圖4。

圖4 Dijkstra算法求解路徑Fig. 4 Diagram for Dijkstra algorithm solution

4 蟻群算法對初始航線的優(yōu)化

在構造海上施工水域中的航線圖時，選擇的是可自由航行鏈接線的中點來構造Maklink航線網(wǎng)絡的節(jié)點，但是根據(jù)模型約束條件式(6)的實際要求，只要與施工水域中的危險區(qū)域的距離大于Dmin即可自由航行，因此最優(yōu)的航線不一定經過航線的網(wǎng)絡的中點。即節(jié)點pi的位置是可以在自由空間的鏈接線上進一步優(yōu)化的，因此下面就使用蟻群算法對初始航線進行進一步的優(yōu)化。

4.1 工作空間離散化處理

(7)

式中：pi(hi)為鏈接線上的任意一點；hi為一個0到1的隨機數(shù)，用它來表示當前點所處在兩端點間的比例參數(shù)；N為某鏈路所經過的節(jié)點的個數(shù)[13]。

在得到Dijkstra算法的解的基礎上，只要給出一組(h1,h2，…,hN)參數(shù)，就可以得到一組由起點到終點的新解。在采用蟻群算法優(yōu)化施工水域的船舶航線前，需要離散化工作空間，對鏈接線的劃分筆者采用固定長度劃分法。為了滿足模型約束條件距離危險區(qū)域的最小距離為Dmin的要求，采用的劃分長度ξ取Dmin，每條鏈接線L將劃分成的分數(shù)為

(8)

式中：Int()函數(shù)表示取整函數(shù)，當Int(Li/Dmin)為奇數(shù)時，為了保證鏈接線的中點也是一個等分點，將劃分的等分數(shù)加1，經過離散處理后那么從鏈接線Li-1到其相鄰的鏈接線Li將會有Ni+1條路徑可以選擇。

4.2 螞蟻路徑的搜索和信息素的更新

每一只螞蟻在完成從起點到終點的路徑搜索后都會產生一組與之相對應的路徑參數(shù)集合(h1，h2，…，hk)，在移動的過程中，一只螞蟻在鏈接線Li上時，選擇下一個鏈接線Li+1上的節(jié)點j的方法為，依次計算當前鏈接線節(jié)點i到下一條鏈接線節(jié)點j的選擇概率Pij，然后根據(jù)選擇概率Pij采用輪盤賭法找出下一個節(jié)點j，Pij的計算公式為[14]

(9)

式中：ηi,j為啟發(fā)值；τi,j為信息素，信息素的濃度越高，選擇概率Pij越大。當螞蟻在移動過程中選擇了某個節(jié)點，則在該節(jié)點處需要釋放信息素，則對該節(jié)點的信息素需要進行更新的公式為

τi,j=(1-ρ1)×τi,j+τ0

(10)

式中：τ0為信息素的初始值；ρ1為[0,1]區(qū)間的可調參數(shù)，文中ρ1取0.1。當所有的螞蟻都完成一次搜索，保存最短路徑的長度，同時再次更新每個點上的信息素。此次更新稱為信息素的揮發(fā)更新，信息素揮發(fā)的公式為

τi,j=τi,j(1-ρ2)

(11)

式中：ρ2為信息素揮發(fā)參數(shù)，文中ρ2的值取0.003。

4.3 蟻群算法對航線轉向角的優(yōu)化

圖5 轉向角優(yōu)化示意Fig. 5 Diagram for steering angle optimization

τi,j=λij×[(1-ρ1)×τi, j+τ0]

(12)

(13)

公式(12)為修正后的信息素更新公式，式中λij為新引進的信息素更新公式的修正系數(shù)；公式(13)為信息素的修正系數(shù)的計算公式，其中αij為當前位置和備選位置的連續(xù)與起點和終點位置連線的夾角，為了消除角度正負方向的影響，公式(13)中對夾角 取絕對值。另一方面因為船舶的最大安全轉向角度為90°，所以取π/2為參考基準，當αij絕對值大于90°時修正系數(shù)λij的值將小于1，將會使路徑所含有信息素濃度τi,j減少，從而達到迭代過程選中轉向角大于90°的概率不斷減小的目標。同時當夾角αij的絕對值越小時λij的值也將越大，當αij的絕對值取最小值0時，λij取得最大值2。

4.4 蟻群算法優(yōu)化求解最終結果

在利用蟻群算法進行優(yōu)化求解時，每次迭代產生10只螞蟻來搜索最優(yōu)路徑，在每一次迭代結束后都記錄下這10只螞蟻尋找到的最優(yōu)路徑和最優(yōu)路徑的長度，總共進行了500次迭代。最終通過蟻群算法求解的航線總長度為205.43 km，比Dijkstra算法求解的路徑總長度221.573 0 km減少了16.139 3 km，較初始解縮短了7.87%，最終的航線規(guī)劃結果如圖6。

圖6 蟻群算法最終結果Fig. 6 Final result for ant colony algorithm

圖6中虛線就是由蟻群算法求得的航線，它不僅在總距離上和初始解相比減少了7.87%，而且航線在轉向次數(shù)和轉向角上也得到了優(yōu)化。為了滿足數(shù)學模型約束條件公式(6)的約束，觀察圖6可以發(fā)現(xiàn)蟻群算法優(yōu)化得到的船舶航線與施工水域的危險水域都保持了一定安全距離，特別是圖中的A、B兩個地方，船舶航線與施工水域的危險區(qū)域的距離已經是算法設置的極限安全距離Dmin，本算法實驗中Dmin取值為0.2 km。

為了觀察蟻群算法在搜索最優(yōu)航線時的收斂過程，圖7是蟻群算法優(yōu)化初始解的收斂過程。

圖7 蟻群算法收斂過程Fig. 7 Ant colony algorithm convergence process

觀察圖7可以發(fā)現(xiàn)蟻群算法在迭代的初期航線總長度迅速收斂，當?shù)?00次以后算法收斂趨于平穩(wěn)，說明此時已經得到了較為優(yōu)秀的滿意解，但是為了減小陷入局部最優(yōu)解的概率，提升算法搜索全局最優(yōu)解的能力,可以發(fā)現(xiàn)蟻群算法在迭代的中后期出現(xiàn)了幾次明顯的波動。這是因為在利用蟻群算法求解模型時，螞蟻種群始終會以一個較小的概率去探索未知的領域，以便于發(fā)現(xiàn)全局最優(yōu)解。

5 結 論

1)為了解決船舶在施工水域中的船舶航線規(guī)劃問題，以圖論的相關理論為基礎，在海上施工水域中構建起了可自由航行網(wǎng)絡圖，利用Dijkstra算法求得了航線的初始可行解。

2)在得到初始可行解的基礎上，利用蟻群算法對初始解進行了智能優(yōu)化，使最終得到的海上施工水域的船舶航線得到了較大幅度的優(yōu)化。

3)通過兩階段的優(yōu)化求解求得了既滿足航線盡可能短又能夠避開海上施工水域危險區(qū)域的航線。