海上施工水域船舶航線規劃數學建模及求解

謝新連，劉 毅，何 傲

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

0 引 言

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

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

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

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

1 問題描述及環境模型的構建

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

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

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

圖1 施工水域環境示意Fig. 1 Schematic diagram for construction waters

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

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

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

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

2 海上施工水域航線規劃的數學模型

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

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

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

(1)

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

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

考慮這些因素后，建立船舶在海上施工水域中航線規劃的數學模型如式(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前的最后一個節點。目標方程由三部分組成，第一部分表示組成航線的中間航段的長度總和，后面兩部分表示連接起點和終點的航段長度。公式(3)表示構成航線的任意航段與施工水域的危險區域的交集為空集，其中l(pi,pi+1)表示由pi和pi+1兩點連接形成的航段的點集；Sj表示施工水域中危險區域的點集。公式(4)表示船舶在第pj節點處的轉向角必須小于航線設計航速下船舶的最大安全轉向角φmax，由前面的研究結果可知一般情況下φmax≤90°。公式(5)表示的是在pj節點處船舶進行轉向時，航線必須滿足船舶最小轉彎半徑的要求，其中L表示船舶的長度,m；λ表示航道在不同設計航速下所取的最小轉彎半徑與船長的比值。公式(6)表示規劃航線與危險區域的最小距離的約束；D表示航線某處與危險區域的最小距離；Dmin表示船舶與危險區域的最小安全距離,m。

3 Dijkstra算法求解航線規劃數學模型

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

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

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

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

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

4 蟻群算法對初始航線的優化

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

4.1 工作空間離散化處理

(7)

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

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

(8)

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

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

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

(9)

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

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

(10)

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

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

(11)

式中：ρ2為信息素揮發參數，文中ρ2的值取0.003。

4.3 蟻群算法對航線轉向角的優化

圖5 轉向角優化示意Fig. 5 Diagram for steering angle optimization

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

(12)

(13)

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

4.4 蟻群算法優化求解最終結果

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

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

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

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

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

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

5 結 論

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

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

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