,

(海軍潛艇學(xué)院，山東 青島 266071)

最佳航線選擇不僅是船舶駕駛員經(jīng)常關(guān)注的問題之一，而且還是船舶經(jīng)營公司時常面臨的重要問題之一。船舶從起始地到目的地之間有多條航線可供選擇，由于自然條件、距離、船舶密度等多種因素的影響，各條航線所含的參數(shù)不同。在多條可供選擇的航線中，選擇出一條最佳航線，無疑將會對提高船舶經(jīng)營公司的競爭力起到至關(guān)重要的作用。

對于一個網(wǎng)絡(luò)簡單的規(guī)劃來說，最短路徑算法具有良好的適用性；但是對于一個較為復(fù)雜的交通網(wǎng)絡(luò)來說，最短路徑算法在搜索效率上則會大打折扣，因此，需要更為高效的搜索算法。

1 數(shù)學(xué)模型的建立

船舶最佳航線選擇問題可以描述為：某船從起始港S出發(fā)前往目的港E，S、E兩港之間存在多條可供船舶航行的航線，并且這些航線和船舶在航線上的掛靠港或錨地組成了一個交通網(wǎng)絡(luò)圖。那么，從起始港S出發(fā)前往目的港E，存在一條最佳航線。這里，“最佳”包括有航程最短、時間最省、能耗最少、最安全等內(nèi)容。若要研究時間最省、能耗最少、最安全等內(nèi)容時，只需將研究問題中的一些參數(shù)作一些必要的變換后，這些問題將會變成最短路徑問題。這里將航程最短作為目標(biāo)，建立數(shù)學(xué)模型[2]。

起始港與目的港之間為一交通網(wǎng)絡(luò)。無向圖G=(V，E，L)。式中：V為m個節(jié)點構(gòu)成的點集；E為n條邊構(gòu)成的邊集；L為路權(quán)集。同時滿足：

1)G為一個簡單圖，不含環(huán)和多重邊；

2) 路權(quán)具有可加性。若有路徑νi-νk-νj，則有

l(νi,νj)=l(νi,νk)+l(νk,νj)

求A，B間的最短路徑P*，滿足

2 最短路徑算法

目前最短路徑問題的最成熟算法是Dijkstra算法。先給賦權(quán)圖的每一頂點記一個數(shù)(稱標(biāo)號)，臨時標(biāo)號(T標(biāo)號)或固定標(biāo)號(P標(biāo)號)。T標(biāo)號表示從始點到這一點還沒有尋找到最短路徑；P標(biāo)號則表示從始點到這一點已尋找到最短路徑。計算的每一步是把某個點的T標(biāo)號變成P標(biāo)號。這樣一旦終點得到P標(biāo)號，計算就停止。若尋求從始點到每一點的最短路徑，則最多經(jīng)過N-1步計算，計算就要停止(N是G的頂點數(shù))。

步驟1：給始點v1標(biāo)上P標(biāo)號d(v1)=0，給其他各點標(biāo)上T標(biāo)號d(vj)=l1j(j=2，3，4，…，N)；

步驟2：取所有T標(biāo)號中的最小者，如，d(vj0)=l1j0，則把該點的T標(biāo)號改為P標(biāo)號；

步驟3：重新計算具有T標(biāo)號的其他各點T標(biāo)號：選vj點的T標(biāo)號與d(vk)+lj中較小者作為vj的新標(biāo)號。

一般情況下，設(shè)：

P={vj|vj具有P標(biāo)號}

T={vj|vj具有T標(biāo)號}

VP(V為圖G的頂點集合)

step4：重復(fù)上述步驟，直到vN∈P，這時d(vN)是從v1到vN的最短路徑。

3 改進(jìn)算法

最短路徑問題首先考慮是否將此問題分解多個子問題進(jìn)行求解。這樣可以降低問題復(fù)雜度，符合并行處理思想。Dijkstra最短路徑算法是從起點到終點求最短路徑，同樣也可以表述為從終點到起點求最短路徑。于是考慮最短路徑問題是否可以分解為由起點到終點求解最短路徑和由終點到起點求解最短路徑兩個子問題[3]。

步驟1：開始時，P=?，Q=?，易知vm=v1，vn=vN。P，Q分別是由開始點v1、終點vN開始的擴(kuò)展點(固定標(biāo)號)集合，vm,vn分別是集合P，Q的當(dāng)前擴(kuò)展點；

式中：d(vm)、e(vn)——起點到vm、終點到vn的最短路徑。

P∪{vm}→P，Q∪{vn}→Q

步驟3：重復(fù)步驟2直到P∩Q={vm}且vm唯一時終止；

步驟4：計算最短路徑

l1=d(vm)+e(vn)

l2=d(vx)+e(vy)+l(vx,vy)

式中：l(vx,vy)——vx，vy相鄰兩點的路權(quán)值，

l(vx,vy)>0

vx∈P

vy∈Q

最短路徑lmin為：lmin{l1,l2}

算法程序框圖見圖1。

圖1 改進(jìn)算法程序框圖

4 實例

如圖2所示，若船從起始港S港出發(fā)前往目的港E港執(zhí)行運(yùn)輸任務(wù)，其間有多條航線以及掛靠港或錨地可供船舶駕駛員或船舶經(jīng)營公司選擇，兩點之間的航線上的權(quán)值表示該航線的航程，權(quán)值越大，表示航程越大，反之，航程越小。作為船舶駕駛員或船舶經(jīng)營公司，要在這些航線中選擇出航程最短的航線。

圖2 交通網(wǎng)絡(luò)圖

各航線的航程見表1。

表1 航線航程表 n mile

Dijkstra算法搜索過程及結(jié)果見表2。

表2 Dijkstra搜索過程

航程最短航線為S→D→C→B→A→E。

改進(jìn)算法搜索過程及結(jié)果見表3。

表3 改進(jìn)算法搜索過程 n mile

航程最短航線為S→D→C→B→A→E。

比較兩算法：搜索結(jié)果相同，但是顯然改進(jìn)后的算法在效率上較第一種有所提高。在節(jié)點較少、邊較少簡單的交通網(wǎng)絡(luò)中兩種算法也許沒有太大的區(qū)別，但是對于一個較為復(fù)雜的交通網(wǎng)絡(luò)來說，改進(jìn)算法就能發(fā)揮出優(yōu)勢。

[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é)報:自然科學(xué)版，2001(2)：139-142.

收稿日期：2007-08-30

修回日期：2007-10-22

作者簡介：蔡文學(xué)(1968-)，男，博士，副教授。

研究方向：交通信息化與電子政務(wù)、交通地理信息

系統(tǒng)、物流信息系統(tǒng)等。E-mail：jzhf2605@yahoo.com.cn