基于Maklink圖和布谷鳥搜索算法的施工水域路徑規(guī)劃

張波菲　謝新連　何傲

摘要：為提高船舶在復(fù)雜施工水域通行的安全性，提出一種基于Maklink圖和布谷鳥搜索（cuckoo search， CS）算法的船舶路徑規(guī)劃方法。利用改進(jìn)的Maklink圖構(gòu)建施工水域環(huán)境模型;設(shè)置變量參數(shù)并用改進(jìn)的CS算法對模型進(jìn)行求解，其中采用基于Dijkstra算法得到的最短路徑長度作為種群個體的適應(yīng)度值;采用3個衡量算法性能的指標(biāo)——優(yōu)化性能指標(biāo)、時間性能指標(biāo)和動態(tài)性能指標(biāo)，對多種算法進(jìn)行分析比較。結(jié)果表明，采用指數(shù)型自適應(yīng)步長和線性自適應(yīng)發(fā)現(xiàn)概率對CS算法進(jìn)行改進(jìn)，能提高其在路徑規(guī)劃中的搜索效率和迭代速度，并可以保證求出一定精度內(nèi)的近似最優(yōu)解，顯示出該算法的優(yōu)越性。

關(guān)鍵詞：船舶避障; 智能交通; 布谷鳥搜索（CS）算法; 性能指標(biāo); 施工水域; Maklink圖

中圖分類號：? U675.73

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

Path planning? in construction waters based on Maklink

graph and cuckoo search algorithm

ZHANG Bofei， XIE Xinlian， HE Ao

（Logistics Research Institute， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In order to improve the navigation safety of ships in complex construction waters，? a ship path planning method based on the Maklink graph and the cuckoo search （CS） algorithm is proposed. The construction waters environment model is constructed by the improved Maklink graph; the variable parameters are set and the model is solved by the improved CS algorithm. The shortest path length calculated by the Dijkstra algorithm is used as the fitness value of the population individual. Three performance indexes for measuring the algorithm performance are used to analyze and compare many algorithms， where three performance indexes are the optimization performance index， the time performance index and the dynamic performance index， respectively. The results show that the improvement of the CS algorithm by the exponential adaptive step size and the linear adaptive discovery probability can improve its search efficiency and iteration speed in path planning， and can guarantee to obtain the approximate optimal solution within a certain precision， which shows the superiority of the algorithm.

Key words：

ship obstacle avoidance; intelligent transportation; cuckoo search （CS） algorithm; performance index; construction waters; Maklink graph

0 引 言

隨著港口和航道的通航密度迅速增加，船舶呈現(xiàn)大型化、專業(yè)化、高速化的發(fā)展趨勢，海上交通環(huán)境越來越復(fù)雜。同時，由于需求的增加和沿海城市經(jīng)濟(jì)的快速發(fā)展，海上和沿海區(qū)域的開發(fā)利用（如跨海大橋、海底隧道、海上鉆井平臺、各類水工設(shè)施等）越來越頻繁，這就對船舶通行安全產(chǎn)生了一定的影響。為提高船舶在施工水域通行的安全性，對通行船舶進(jìn)行智能誘導(dǎo)，使船舶安全地避開施工區(qū)域的障礙物顯得尤為重要。

路徑規(guī)劃是船舶智能誘導(dǎo)系統(tǒng)的重要組成部分，其主要目的是在已知船舶準(zhǔn)確位置和周圍環(huán)境信息的情況下，尋找出一條從起點(diǎn)到終點(diǎn)的滿足一定要求的航行路徑，使船舶在通行過程中能夠安全可靠地避開所有障礙物并且使路徑盡可能地短?！?br>