,
(海軍潛艇學(xué)院,山東 青島 266071)
最佳航線選擇不僅是船舶駕駛員經(jīng)常關(guān)注的問題之一,而且還是船舶經(jīng)營(yíng)公司時(shí)常面臨的重要問題之一。船舶從起始地到目的地之間有多條航線可供選擇,由于自然條件、距離、船舶密度等多種因素的影響,各條航線所含的參數(shù)不同。在多條可供選擇的航線中,選擇出一條最佳航線,無(wú)疑將會(huì)對(duì)提高船舶經(jīng)營(yíng)公司的競(jìng)爭(zhēng)力起到至關(guān)重要的作用。
對(duì)于一個(gè)網(wǎng)絡(luò)簡(jiǎn)單的規(guī)劃來(lái)說(shuō),最短路徑算法具有良好的適用性;但是對(duì)于一個(gè)較為復(fù)雜的交通網(wǎng)絡(luò)來(lái)說(shuō),最短路徑算法在搜索效率上則會(huì)大打折扣,因此,需要更為高效的搜索算法。
船舶最佳航線選擇問題可以描述為:某船從起始港S出發(fā)前往目的港E,S、E兩港之間存在多條可供船舶航行的航線,并且這些航線和船舶在航線上的掛靠港或錨地組成了一個(gè)交通網(wǎng)絡(luò)圖。那么,從起始港S出發(fā)前往目的港E,存在一條最佳航線。這里,“最佳”包括有航程最短、時(shí)間最省、能耗最少、最安全等內(nèi)容。若要研究時(shí)間最省、能耗最少、最安全等內(nèi)容時(shí),只需將研究問題中的一些參數(shù)作一些必要的變換后,這些問題將會(huì)變成最短路徑問題。這里將航程最短作為目標(biāo),建立數(shù)學(xué)模型[2]。
起始港與目的港之間為一交通網(wǎng)絡(luò)。無(wú)向圖G=(V,E,L)。式中:V為m個(gè)節(jié)點(diǎn)構(gòu)成的點(diǎn)集;E為n條邊構(gòu)成的邊集;L為路權(quán)集。同時(shí)滿足:
1)G為一個(gè)簡(jiǎn)單圖,不含環(huán)和多重邊;
2) 路權(quán)具有可加性。若有路徑νi-νk-νj,則有
l(νi,νj)=l(νi,νk)+l(νk,νj)
求A,B間的最短路徑P*,滿足
目前最短路徑問題的最成熟算法是Dijkstra算法。先給賦權(quán)圖的每一頂點(diǎn)記一個(gè)數(shù)(稱標(biāo)號(hào)),臨時(shí)標(biāo)號(hào)(T標(biāo)號(hào))或固定標(biāo)號(hào)(P標(biāo)號(hào))。T標(biāo)號(hào)表示從始點(diǎn)到這一點(diǎn)還沒有尋找到最短路徑;P標(biāo)號(hào)則表示從始點(diǎn)到這一點(diǎn)已尋找到最短路徑。計(jì)算的每一步是把某個(gè)點(diǎn)的T標(biāo)號(hào)變成P標(biāo)號(hào)。這樣一旦終點(diǎn)得到P標(biāo)號(hào),計(jì)算就停止。若尋求從始點(diǎn)到每一點(diǎn)的最短路徑,則最多經(jīng)過(guò)N-1步計(jì)算,計(jì)算就要停止(N是G的頂點(diǎn)數(shù))。
步驟1:給始點(diǎn)v1標(biāo)上P標(biāo)號(hào)d(v1)=0,給其他各點(diǎn)標(biāo)上T標(biāo)號(hào)d(vj)=l1j(j=2,3,4,…,N);
步驟2:取所有T標(biāo)號(hào)中的最小者,如,d(vj0)=l1j0,則把該點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào);
步驟3:重新計(jì)算具有T標(biāo)號(hào)的其他各點(diǎn)T標(biāo)號(hào):選vj點(diǎn)的T標(biāo)號(hào)與d(vk)+lj中較小者作為vj的新標(biāo)號(hào)。
一般情況下,設(shè):
P={vj|vj具有P標(biāo)號(hào)}
T={vj|vj具有T標(biāo)號(hào)}
VP(V為圖G的頂點(diǎn)集合)
step4:重復(fù)上述步驟,直到vN∈P,這時(shí)d(vN)是從v1到vN的最短路徑。
最短路徑問題首先考慮是否將此問題分解多個(gè)子問題進(jìn)行求解。這樣可以降低問題復(fù)雜度,符合并行處理思想。Dijkstra最短路徑算法是從起點(diǎn)到終點(diǎn)求最短路徑,同樣也可以表述為從終點(diǎn)到起點(diǎn)求最短路徑。于是考慮最短路徑問題是否可以分解為由起點(diǎn)到終點(diǎn)求解最短路徑和由終點(diǎn)到起點(diǎn)求解最短路徑兩個(gè)子問題[3]。
步驟1:開始時(shí),P=?,Q=?,易知vm=v1,vn=vN。P,Q分別是由開始點(diǎn)v1、終點(diǎn)vN開始的擴(kuò)展點(diǎn)(固定標(biāo)號(hào))集合,vm,vn分別是集合P,Q的當(dāng)前擴(kuò)展點(diǎn);
式中:d(vm)、e(vn)——起點(diǎn)到vm、終點(diǎn)到vn的最短路徑。
P∪{vm}→P,Q∪{vn}→Q
步驟3:重復(fù)步驟2直到P∩Q={vm}且vm唯一時(shí)終止;
步驟4:計(jì)算最短路徑
l1=d(vm)+e(vn)
l2=d(vx)+e(vy)+l(vx,vy)
式中:l(vx,vy)——vx,vy相鄰兩點(diǎn)的路權(quán)值,
l(vx,vy)>0
vx∈P
vy∈Q
最短路徑lmin為:lmin{l1,l2}
算法程序框圖見圖1。
圖1 改進(jìn)算法程序框圖
如圖2所示,若船從起始港S港出發(fā)前往目的港E港執(zhí)行運(yùn)輸任務(wù),其間有多條航線以及掛靠港或錨地可供船舶駕駛員或船舶經(jīng)營(yíng)公司選擇,兩點(diǎn)之間的航線上的權(quán)值表示該航線的航程,權(quán)值越大,表示航程越大,反之,航程越小。作為船舶駕駛員或船舶經(jīng)營(yíng)公司,要在這些航線中選擇出航程最短的航線。
圖2 交通網(wǎng)絡(luò)圖
各航線的航程見表1。
表1 航線航程表 n mile
Dijkstra算法搜索過(guò)程及結(jié)果見表2。
表2 Dijkstra搜索過(guò)程
航程最短航線為S→D→C→B→A→E。
改進(jìn)算法搜索過(guò)程及結(jié)果見表3。
表3 改進(jìn)算法搜索過(guò)程 n mile
航程最短航線為S→D→C→B→A→E。
比較兩算法:搜索結(jié)果相同,但是顯然改進(jìn)后的算法在效率上較第一種有所提高。在節(jié)點(diǎn)較少、邊較少簡(jiǎn)單的交通網(wǎng)絡(luò)中兩種算法也許沒有太大的區(qū)別,但是對(duì)于一個(gè)較為復(fù)雜的交通網(wǎng)絡(luò)來(lái)說(shuō),改進(jìn)算法就能發(fā)揮出優(yōu)勢(shì)。
[1] 龍光正,楊建軍.改進(jìn)的最短算法[J].系統(tǒng)工程與電子技術(shù),2002(6):106-108.
[2] 鄧成梁.運(yùn)籌學(xué)(OR)的原理和方法[M].武漢:華中理工大學(xué)出版社,1996.
[3] 傅冬綿.交通問路系統(tǒng)中最短路徑的新算法[J].華僑大學(xué)學(xué)報(bào):自然科學(xué)版,2001(2):139-142.
收稿日期:2007-08-30
修回日期:2007-10-22
作者簡(jiǎn)介:蔡文學(xué)(1968-),男,博士,副教授。
研究方向:交通信息化與電子政務(wù)、交通地理信息
系統(tǒng)、物流信息系統(tǒng)等。E-mail:jzhf2605@yahoo.com.cn