田茹會(huì)
(陜西能源職業(yè)技術(shù)學(xué)院 咸陽(yáng) 712000)
艦船作為一個(gè)危險(xiǎn)的工作場(chǎng)所,一旦出現(xiàn)不規(guī)范作業(yè)或受海上因素的影響便可能造成無(wú)法挽回的巨大損失[1~4]。如果現(xiàn)場(chǎng)人員能夠在遇到災(zāi)害時(shí)快速選擇最優(yōu)路徑導(dǎo)航,則可以顯著提升生還概率[5]。由此可見(jiàn),采用合適的方法來(lái)求解得到最佳路線已經(jīng)成為一項(xiàng)具有重大現(xiàn)實(shí)意義的課題。
采用傳統(tǒng)Dijkstra算法來(lái)搜索最佳路徑存在較大的盲目性,王玉琨[6]等利用經(jīng)過(guò)扇形優(yōu)化的Dijkstra算法來(lái)求解路線,使搜索速度獲得顯著提高;同時(shí),楊林[7]在研究煤礦瓦斯事故的應(yīng)對(duì)方案過(guò)程中,對(duì)導(dǎo)航實(shí)施“當(dāng)量計(jì)算”并采用Dijkstra最佳路徑算法求出最佳導(dǎo)航路徑。王磊等采用Dijsktra算法來(lái)完成對(duì)路徑的導(dǎo)航分析功能,同時(shí)粒子群算法來(lái)規(guī)劃真實(shí)路徑的選擇過(guò)程,通過(guò)為指定節(jié)點(diǎn)區(qū)域確定較優(yōu)路徑來(lái)實(shí)現(xiàn)路徑規(guī)劃的目的。薛峰會(huì)等研究了對(duì)船舶導(dǎo)航路徑計(jì)算過(guò)程進(jìn)行優(yōu)化的方法,以Dijkstra算法優(yōu)化了航行規(guī)劃圖上所有節(jié)點(diǎn)之間的航行路徑。本文根據(jù)以上研究結(jié)果,對(duì)導(dǎo)航當(dāng)量長(zhǎng)度以及導(dǎo)航速度進(jìn)行了深入探討,并通過(guò)Dijkstra算法構(gòu)建得到了選擇艦船最佳導(dǎo)航路線的模型。
對(duì)導(dǎo)航當(dāng)量長(zhǎng)度以及導(dǎo)航速度進(jìn)行了深入探討,給出了扇形優(yōu)化Dijkstra算法進(jìn)行分析流程,并進(jìn)行了應(yīng)用示例。
選擇Dijkstra算法來(lái)求解最佳導(dǎo)航之前,應(yīng)先把所有導(dǎo)航表示成統(tǒng)一的當(dāng)量長(zhǎng)度。先根據(jù)艦船導(dǎo)航中的實(shí)際網(wǎng)絡(luò)狀態(tài)及其影響程度來(lái)得到各個(gè)導(dǎo)航對(duì)應(yīng)的影響因子。之后,考慮到海上作業(yè)環(huán)境具有較大的復(fù)雜性與特殊性,因此實(shí)際導(dǎo)航影響因子會(huì)受到多種因素的共同影響,本文將從以下各個(gè)角度對(duì)導(dǎo)航速度進(jìn)行分析,包括導(dǎo)航有效寬度、高度、風(fēng)向、風(fēng)速及其水流速程度。針對(duì)上述各項(xiàng)影響因素,依次采用系數(shù)α1、α2、α3、α4、α5進(jìn)行表示,并得到下述表達(dá)式[8]
在式(1)中,Eij代表連接節(jié)點(diǎn) i與 j的導(dǎo)航;α(Eij)是導(dǎo)航Eij中包含的影響因子系數(shù);T(Eij)是包含此該影響因子的情況下經(jīng)過(guò)導(dǎo)航Eij所需的時(shí)間,單位s;t(Eij)是不包含此影響因子時(shí)經(jīng)過(guò)導(dǎo)航Eij所需的時(shí)間,單位s。
導(dǎo)航Eij綜合影響程度系數(shù)α(Eij)取決于所有因子影響程度系數(shù)進(jìn)行加和所得的結(jié)果,表示為如下的形式:
采用統(tǒng)一測(cè)試條件完成現(xiàn)場(chǎng)模擬與實(shí)測(cè)過(guò)程,并對(duì)T(Eij)與t(Eij)測(cè)試結(jié)果進(jìn)行取平均,結(jié)合式(1)求解出對(duì)導(dǎo)航具有影響的各個(gè)因子系數(shù),之后計(jì)算得到影響因素的系數(shù)之和,再通過(guò)式(2)求解得到導(dǎo)航的綜合影響程度系數(shù)。
當(dāng)導(dǎo)航的影響因子被確定之后,則可以根據(jù)導(dǎo)航真實(shí)長(zhǎng)度與總影響程度系數(shù)來(lái)獲得當(dāng)量長(zhǎng)度,表達(dá)式如下:
從上式中可以看到,Ls是對(duì)導(dǎo)航進(jìn)行實(shí)際測(cè)試所得的長(zhǎng)度,單位m;Ld代表導(dǎo)航當(dāng)量長(zhǎng)度,單位m;α( )
Eij代表導(dǎo)航總影響程度系數(shù)。以同樣的條件進(jìn)行現(xiàn)場(chǎng)模擬測(cè)試與仿真,經(jīng)多次測(cè)試得到的Ls平均值,再通過(guò)式(3)計(jì)算導(dǎo)航當(dāng)量長(zhǎng)度。計(jì)算連接受災(zāi)地點(diǎn)與避難地點(diǎn)之間的各個(gè)可通行導(dǎo)航對(duì)應(yīng)的當(dāng)量長(zhǎng)度,并尋找具有最小當(dāng)量長(zhǎng)度的路徑,再以此路徑作為最佳導(dǎo)航路徑。
采用傳統(tǒng)Dijkstra算法進(jìn)行處理時(shí),是先選擇一個(gè)中心位置再通過(guò)不斷增加節(jié)點(diǎn)距離的方式得到最佳路徑的搜索算法,需完成各個(gè)標(biāo)定路線的搜索之后才可以進(jìn)行統(tǒng)計(jì)運(yùn)算,實(shí)際計(jì)算量非常大,因此導(dǎo)致搜索速度明顯變慢,同時(shí)也使得搜索過(guò)程變得更加盲目。為了克服Dijkstra算法的以上缺陷,本文選擇經(jīng)過(guò)扇形優(yōu)化的Dijkstra算法進(jìn)行分析,經(jīng)過(guò)優(yōu)化后的Dijkstra算法所采用的核心處理思想是按照人員定位結(jié)果來(lái)得到艦船導(dǎo)航的源點(diǎn),根據(jù)設(shè)定的導(dǎo)航目標(biāo)點(diǎn)以直線連接的方式得到由軸線組成的扇形區(qū),再對(duì)該區(qū)域進(jìn)行搜索得到最佳路徑。由此實(shí)現(xiàn)穩(wěn)定運(yùn)行與快速搜索的目的,可以更好地適應(yīng)艦船導(dǎo)航中的復(fù)雜網(wǎng)絡(luò)環(huán)境。
圖1 Dijkstra算法流程圖
從圖1中可以看到采用扇形優(yōu)化Dijkstra算法進(jìn)行分析的流程,具體步驟如下:
1)從艦船導(dǎo)航網(wǎng)絡(luò)內(nèi)選擇出起點(diǎn)V1以及終點(diǎn)Vn,在此基礎(chǔ)上求得最佳扇形區(qū);
2)臨時(shí)標(biāo)記圖中的各個(gè)起點(diǎn)Vi,分別以二個(gè)坐標(biāo)來(lái)表示各節(jié)點(diǎn),其中,第一個(gè)坐標(biāo)是節(jié)點(diǎn)對(duì)應(yīng)的母節(jié)點(diǎn),即與最佳路徑相鄰的之前節(jié)點(diǎn),第二個(gè)坐標(biāo)對(duì)應(yīng)的是此節(jié)點(diǎn)與起點(diǎn)V1之間的距離權(quán)值;把V1標(biāo)記成(1,0),再以(1,D1i)來(lái)表示其它節(jié)點(diǎn)Vi,若果Vi與V1之間是保持直接相連的狀態(tài),則可以得到D1i=L1i,如果Vi與V1之間不是保持直接相連的狀態(tài),則此時(shí)D1i=∞,同時(shí)將V1歸入永久標(biāo)記點(diǎn)組成的集合S={V1};
3)對(duì)比分析集合T=V-S內(nèi)各個(gè)沒(méi)有被標(biāo)記的點(diǎn)對(duì)應(yīng)的權(quán)值選,從中選出具有最小權(quán)值的點(diǎn)Vk作為永久標(biāo)記點(diǎn),此時(shí)可以得到S={V1,Vk},和永久標(biāo)記點(diǎn)Vk之間保持直接相鄰狀態(tài)的各個(gè)點(diǎn)Vi,當(dāng)滿足條件 D1k+Lki<D1i時(shí),存在 D1i=D1k+Lki,此時(shí)母節(jié)點(diǎn)將轉(zhuǎn)變成Vk;
4)重復(fù)執(zhí)行以上各個(gè)步驟到終點(diǎn)Vn為止,得到的D1n是最優(yōu)路徑權(quán)值和,由終點(diǎn)母節(jié)點(diǎn)往回追溯,便可得到這一最優(yōu)路徑。
從圖2中可以看到對(duì)艦船的局部導(dǎo)航進(jìn)行模擬所得的網(wǎng)絡(luò),可以發(fā)現(xiàn)節(jié)點(diǎn)①代表航船的實(shí)際位置,節(jié)點(diǎn)⑨是導(dǎo)航目標(biāo)位置。求解由節(jié)點(diǎn)①與節(jié)點(diǎn)⑨之間的最佳路徑,確保這一路徑是各個(gè)可行路徑中能夠?qū)崿F(xiàn)最佳通行時(shí)間的導(dǎo)航。
圖2 艦船局部導(dǎo)航模擬網(wǎng)絡(luò)圖
為海上作業(yè)人員提供的啟動(dòng)后根據(jù)實(shí)際型號(hào)的差異實(shí)際可用時(shí)間介于25min~40min范圍內(nèi)。因此,海上作業(yè)人員需確保能在的有效工作時(shí)間中導(dǎo)航到安全的避難位置。根據(jù)以上分析,本文將有效時(shí)間設(shè)定為25min,相當(dāng)于所有作業(yè)人員到達(dá)最近安全區(qū)域的時(shí)間不能超過(guò)25min。
針對(duì)本模型艦船的真實(shí)情況,分別為節(jié)點(diǎn)3與節(jié)點(diǎn)6,并以此作為人員導(dǎo)航的安全目標(biāo)位置。而且給其他各個(gè)節(jié)點(diǎn)人員到節(jié)點(diǎn)13需要的時(shí)間都大于25min,所以其他各節(jié)點(diǎn)的海上作業(yè)人員應(yīng)在限定時(shí)間內(nèi)轉(zhuǎn)移至別的安全位置點(diǎn)。
可以作為導(dǎo)航安全位置的節(jié)點(diǎn)包括節(jié)點(diǎn)3、6、13與17,之后再通過(guò)Dijkstra算法求解出從艦船模型內(nèi)的各節(jié)點(diǎn)導(dǎo)航至上述安全位置點(diǎn)需要消耗的時(shí)間以及尋找最佳導(dǎo)航路徑。從表1中可以看到由本文艦船模型的20個(gè)節(jié)點(diǎn)導(dǎo)航至節(jié)點(diǎn)3、6、13與17對(duì)應(yīng)的時(shí)間。
表2是根據(jù)海上局部導(dǎo)航圖各參數(shù)進(jìn)行計(jì)算所得的結(jié)果,可以看到每次搜素時(shí)得到的最小導(dǎo)航當(dāng)量。其中,最佳導(dǎo)航路徑是①②⑤⑧⑨。
表1 節(jié)點(diǎn)導(dǎo)航時(shí)間表
表2 導(dǎo)航參數(shù)表
基于Dijkstra算法得到的K則最優(yōu)路徑雙向搜索算法可以得到多條最佳導(dǎo)航路徑,本文選擇其中的兩種最佳導(dǎo)航路徑,結(jié)果見(jiàn)表3。
根據(jù)表3可知,當(dāng)出現(xiàn)安全事故時(shí),作業(yè)人員可通過(guò)最近安全避難點(diǎn)進(jìn)行導(dǎo)航。
選擇VSL進(jìn)行最佳路徑編程并演示海上導(dǎo)航培訓(xùn)系統(tǒng)運(yùn)行過(guò)程,其中該程序的腳本圖可以讀取導(dǎo)航當(dāng)量長(zhǎng)度與人員導(dǎo)航速度,同時(shí)根據(jù)Dijkstra算法求出最佳導(dǎo)航路徑,形象展示導(dǎo)航過(guò)程。
表3 最佳導(dǎo)航路徑表
先在Virtools內(nèi)創(chuàng)建VSL腳本程序,如果發(fā)現(xiàn)腳本圖內(nèi)存在不同的VSL腳本程序時(shí)則對(duì)其進(jìn)行更名,從而準(zhǔn)確分辨各VSL腳本程序的功能。再結(jié)合實(shí)際需求設(shè)定bIn/bOut端口與pIn/pOut參數(shù)的種類與數(shù)量。
先通過(guò)VSL腳本程序創(chuàng)建得到一個(gè)存儲(chǔ)表來(lái)保存當(dāng)量長(zhǎng)度與導(dǎo)航速度。創(chuàng)建Run VSL并將其更名為L(zhǎng)aneway Data Array,再把存儲(chǔ)導(dǎo)航參數(shù)的代碼輸入編程欄進(jìn)行調(diào)試。
之后,以VSL腳本程序進(jìn)行編程并求解出最佳路徑,構(gòu)建一個(gè)Run VSL并將其更名為Get Shortest Path。選擇VSL來(lái)編寫Dijkstra算法時(shí),通過(guò)優(yōu)化改進(jìn)處理可以降低搜索過(guò)程的遍歷節(jié)點(diǎn)個(gè)數(shù),使程序高效運(yùn)行。
最后,以系統(tǒng)BB模塊依次和通過(guò)VSL腳本程序編譯的Laneway Data Array模塊以及Get Shortest Path模塊進(jìn)行連線得到腳本圖。
在系統(tǒng)的操作界面中,點(diǎn)擊選擇系統(tǒng)的演示功能,從圖2選擇節(jié)點(diǎn)①作為受災(zāi)位置,再點(diǎn)擊系統(tǒng)的演示按鈕,可以看到此時(shí)系統(tǒng)的人物開(kāi)始演示導(dǎo)航的過(guò)程,并可以得到導(dǎo)航所需的最佳路徑及時(shí)間。
根據(jù)本實(shí)驗(yàn)測(cè)試結(jié)果可知,利用VSL編程以及把Dijkstra算法應(yīng)用于海上導(dǎo)航模擬系統(tǒng)是完全可行的。
對(duì)導(dǎo)航當(dāng)量長(zhǎng)度以及導(dǎo)航速度進(jìn)行了深入探討,給出了扇形優(yōu)化Dijkstra算法進(jìn)行分析流程,并進(jìn)行了應(yīng)用示例。研究結(jié)果得到:
1)基于Dijkstra算法得到的K則最優(yōu)路徑雙向搜索算法可以得到多條最佳導(dǎo)航路徑,本文選擇其中的兩種最佳導(dǎo)航路徑,完全滿足避難需求。
2)選擇VSL進(jìn)行最佳路徑編程并演示海上導(dǎo)航培訓(xùn)系統(tǒng)運(yùn)行過(guò)程,根據(jù)Dijkstra算法求出最佳導(dǎo)航路徑,形象展示導(dǎo)航過(guò)程。利用VSL編程以及把Dijkstra算法應(yīng)用于海上導(dǎo)航模擬系統(tǒng)是完全可行的。