區(qū)間數(shù)型多式聯(lián)運(yùn)路線優(yōu)化問題的混合遺傳算法

摘 要：多式聯(lián)運(yùn)路線優(yōu)化問題直接關(guān)系到貨物運(yùn)輸?shù)馁M(fèi)用、時(shí)間和運(yùn)輸質(zhì)量。首先分析了多式聯(lián)運(yùn)路線優(yōu)化問題的數(shù)學(xué)模型及虛擬運(yùn)輸網(wǎng)絡(luò)圖；其次，將區(qū)間數(shù)排序的思想引入適應(yīng)度函數(shù)的設(shè)計(jì)中，提出了一種求解區(qū)間數(shù)型多式聯(lián)運(yùn)路線優(yōu)化問題的混合型遺傳算法，給出了染色體編碼、遺傳算子設(shè)計(jì)、約束判斷與調(diào)整及群體多樣性控制的方法；最后用示例對算法的有效性進(jìn)行了驗(yàn)證，算法的提出可為多式聯(lián)運(yùn)經(jīng)營者的決策提供數(shù)據(jù)參考。

關(guān)鍵詞：多式聯(lián)運(yùn);路線優(yōu)化;混合遺傳算法;區(qū)間數(shù)

中圖分類號：TP301.6； U116文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2062-04

doi:10.3969/j.issn.1001-3695.2009.06.019

Hybrid genetic algorithm for interval route optimization problem in multimodal transport

JING Xiang-he1， SHANG Wen-zhong1， HE Jing1， YAN Zhen-ni2

（1.Dept. of Anti-craft Missile， Air Defense Command College， Zhengzhou 450052， China；2.School of Information Control Engineering， Xi’an University of Architecture Technology， Xi’an 710000， China）

Abstract:Route optimization problem in multimodal transport directly influences the freightage cost， freightage time and freightage quality. Firstly，analyzed the mathematics model and virtual transport network for interval route optimization problem in multimodal transport.Secondly，introduced the sequencing method for interval data into the design of fitness function， and presented a hybrid genetic algorithm for solving interval route optimization problem in multimodal transport.It also proposed the design of chromosome coding， genetic operators， restriction controlling method and population diversity controlling method.Finally，convinced the effectiveness of the hybrid genetic algorithm by the computational results of an example. The algorithm is valuable for multimodal transport.

Key words:multimodal transport; route optimization problem; hybrid genetic algorithm; interval data

0 引言

多式聯(lián)運(yùn)^[1]是現(xiàn)代物流系統(tǒng)中競爭協(xié)作的最佳方式，研究多式聯(lián)運(yùn)的路線優(yōu)化問題，以實(shí)現(xiàn)費(fèi)用的節(jié)約或時(shí)間的節(jié)省，對于提高交通運(yùn)輸?shù)姆?wù)水平、競爭能力以及其社會(huì)綜合效益或效率，具有重要的現(xiàn)實(shí)意義。受交通、氣候等因素的影響，在實(shí)際多式聯(lián)運(yùn)路線優(yōu)化問題中，決策信息經(jīng)常是不確定的，如某兩城市間的運(yùn)輸時(shí)間通常是一個(gè)區(qū)間數(shù)，而不是一個(gè)確定的實(shí)數(shù)，對于這種區(qū)間數(shù)型的優(yōu)化問題也就不能直接用求解確定性問題的方法來求解。因此，研究區(qū)間型的多式聯(lián)運(yùn)路線優(yōu)化問題具有更重要的現(xiàn)實(shí)意義。

從目前公開發(fā)表的文獻(xiàn)來看，對確定性的多式聯(lián)運(yùn)優(yōu)化問題研究較多，而研究區(qū)間數(shù)型多式聯(lián)運(yùn)優(yōu)化問題的文獻(xiàn)尚不多見。文獻(xiàn)[2~9]分別從不同的角度對確定性的多式聯(lián)運(yùn)的運(yùn)輸優(yōu)化問題進(jìn)行了探討，為我國多式聯(lián)運(yùn)的組織提供了一定的科學(xué)依據(jù)。

文獻(xiàn)[2]利用層次分析法和決策論的知識，對多式聯(lián)運(yùn)線路選擇問題進(jìn)行了研究；文獻(xiàn)[3]提出運(yùn)輸網(wǎng)絡(luò)的分層結(jié)構(gòu)和多式聯(lián)運(yùn)網(wǎng)絡(luò)的構(gòu)造方法，設(shè)計(jì)了多式聯(lián)運(yùn)路徑?jīng)Q策系統(tǒng)框架；文獻(xiàn)[4]提出了一種求解最佳運(yùn)輸路線的廣義最短路法；文獻(xiàn)[5]將多種運(yùn)輸方式的組合優(yōu)化問題轉(zhuǎn)換為一個(gè)帶時(shí)間約束和能力約束的最短路問題，并且給出一種基于最短路的啟發(fā)式算法；文獻(xiàn)[6]從實(shí)現(xiàn)總成本最小化的原則出發(fā)，建立了一種多式聯(lián)運(yùn)網(wǎng)絡(luò)的最優(yōu)分配模型，從定量角度分析了多式聯(lián)運(yùn)系統(tǒng)的合理組織；文獻(xiàn)[7]建立了多式聯(lián)運(yùn)虛擬運(yùn)輸網(wǎng)絡(luò)，并在運(yùn)輸方式選擇依據(jù)和運(yùn)輸網(wǎng)絡(luò)的基礎(chǔ)上給出了多種運(yùn)輸方式組合優(yōu)化模型及求解算法；文獻(xiàn)[8]建立了基于多維權(quán)有向圖的多式聯(lián)運(yùn)運(yùn)輸方式選擇模型；文獻(xiàn)[9]提出了一種求解多式聯(lián)運(yùn)運(yùn)輸方式選擇多目標(biāo)優(yōu)化問題的混合遺傳算法。

本文主要研究用遺傳算法(genetic algorithm，GA)^[10]來求解區(qū)間數(shù)型多式聯(lián)運(yùn)路線優(yōu)化問題。

1 區(qū)間數(shù)的比較與排序^[11]

記=[aL，aU]={x|aL≤x≤aU}，稱為一個(gè)區(qū)間數(shù)。特別地，若aL=aU，則退化為一個(gè)實(shí)數(shù)。

定義1 當(dāng)和b~均為實(shí)數(shù)時(shí)，則稱

p(＞b~)=1當(dāng)＞b~時(shí)

1/2當(dāng)=b~時(shí)

0當(dāng)＜b~時(shí)(1)

為＞b~的可能度。

定義2 當(dāng)和b~同時(shí)為區(qū)間數(shù)或者其中有一個(gè)為區(qū)間數(shù)時(shí)，設(shè)=[aL，aU]，b~=[bL，bU]，且記l=aU-aL，lb~=bU-bL，則稱

p(≥b~)=min{l+lb~，max(aU-bL，0)}/(l+l)（2）

為≥b~的可能度，且記和b~的次序關(guān)系為≥b~p。

對于給定的一組區(qū)間數(shù)i=[aLi，aUi](i=1，2，…，n)，把它們進(jìn)行兩兩比較。利用可能度公式求得相應(yīng)的可能度p(i≥j)，簡記為pij(i， j=1，2，…，n)，并建立可能度矩陣P=(pij)n×n。該矩陣包含了所有方案相互比較的全部可能度信息，因此，對區(qū)間數(shù)的排序問題，就轉(zhuǎn)換為求解可能度矩陣的排序向量的問題。矩陣P=(pij)n×n是一個(gè)模糊互補(bǔ)判斷矩陣，根據(jù)模糊互補(bǔ)判斷矩陣排序的中轉(zhuǎn)法可以得到可能度矩陣P=(pij)n×n的排序向量v=(v1，v2，…，vn)。其中

vi=1/[n(n-1)](nj=1pij+n/2-1)；i=1，2，…，n（3）

利用vi(i=1，2，…，n)可以對區(qū)間數(shù)i(i=1，2，…，n)進(jìn)行排序。

2 問題描述

區(qū)間數(shù)型多式聯(lián)運(yùn)路線優(yōu)化問題可以描述如下：

假設(shè)一個(gè)物流企業(yè)將一批貨物從貨物的起始地點(diǎn)O運(yùn)送到目的地Q，中途經(jīng)過n個(gè)城市，任意相鄰的兩個(gè)城市之間都有g(shù)條運(yùn)輸路線可供選擇，在一城市對之間只能選擇一條路線。該批貨物從城市i到城市i+1選擇第k條路線的運(yùn)輸成本為區(qū)間數(shù)ki，i+1，運(yùn)輸時(shí)間為區(qū)間數(shù)ki，i+1，該批貨物在城市i由第k條路線轉(zhuǎn)換到第l條路線的中轉(zhuǎn)費(fèi)用為區(qū)間數(shù)kli，中轉(zhuǎn)時(shí)間為區(qū)間數(shù)kli。試確定最佳的路線組合方式，使得：

a）在運(yùn)輸總時(shí)間不超過運(yùn)輸期限T0的情況下，盡量降低運(yùn)輸總成本。

b）在運(yùn)輸總成本不超過預(yù)算費(fèi)用C0的情況下，盡量縮短運(yùn)輸總時(shí)間。

上述兩種情況的求解思路是一樣的，下面以第一種情況為例，來研究問題的求解方法。

為了更直觀地描述問題，這里用一個(gè)虛擬運(yùn)輸網(wǎng)絡(luò)圖^[6，8]對問題進(jìn)行描述：

a）除始發(fā)點(diǎn)O和終點(diǎn)Q外，其他各城市分別擴(kuò)展為2g個(gè)城市節(jié)點(diǎn)，如圖1所示。對于城市A，其中左側(cè)g個(gè)節(jié)點(diǎn)A11，A12，…，A1g分別表示g條路線輸入節(jié)點(diǎn)，右側(cè)g個(gè)節(jié)點(diǎn)A21，A22，…，A2g分別表示g條路線輸出節(jié)點(diǎn)。



b）各條弧上的權(quán)重分為費(fèi)用權(quán)重(兩城市之間的運(yùn)費(fèi)＋中轉(zhuǎn)費(fèi)用)和時(shí)間權(quán)重（兩城市之間的運(yùn)輸時(shí)間＋中轉(zhuǎn)時(shí)間）。

c）終點(diǎn)Q再擴(kuò)展g個(gè)輸入節(jié)點(diǎn)，Qi到Q之間的時(shí)間和費(fèi)用均為零。

如圖1所示，設(shè)I表示所有要經(jīng)過的城市的集合，J表示可供選擇的運(yùn)輸路線的集合，那么在運(yùn)輸總時(shí)間不超過運(yùn)輸期限T0的情況下，以盡量降低運(yùn)輸總成本為目標(biāo)的數(shù)學(xué)模型可描述如下：

目標(biāo)函數(shù)

Z=min{i∈Ik∈Jxki，i+1ki，i+1+i∈Ik∈Jl∈Jγklikli}（4）

約束條件

k∈Jxki，i+1=1 i∈I（5）

k∈Jl∈Jγkli=1 i∈I（6）

xki-1，i+xli，i+1≥2γkli i∈I，k∈J，l∈J

（7）

i∈Ik∈Jki，i+1xki，i+1+i∈Ik∈Jl∈Jkliγkli≤T0（8）

xki，i+1=1 在城市i與城市i+1之間選擇第k條路線

0在城市i與城市i+1之間選擇其他路線（9）

γkli=1 在城市i從第k條路線轉(zhuǎn)換到第l條路線

0不發(fā)生轉(zhuǎn)換（10）

其中:ki，i+1表示貨物從城市i到城市i+1選擇第k條路線的運(yùn)輸成本；ki，i+1表示從城市i到城市i+1選擇第k條路線的運(yùn)輸時(shí)間；kli表示貨物在城市i由第k條路線轉(zhuǎn)換到第l條路線的中轉(zhuǎn)費(fèi)用；kli表示在城市i由第k條路線轉(zhuǎn)換到第l條路線的中轉(zhuǎn)時(shí)間；T0表示從貨物中心點(diǎn)O到目的地Q允許的時(shí)間期限。式（4）中目標(biāo)函數(shù)以整個(gè)運(yùn)輸過程中的運(yùn)輸成本最少為目標(biāo)，而運(yùn)輸成本由運(yùn)費(fèi)和中轉(zhuǎn)費(fèi)用組成；式（5）表明在某一特定的城市對之間只能選擇一條運(yùn)輸路線，即運(yùn)量不能分割；式（6）表明在城市i只有一次運(yùn)輸中轉(zhuǎn)；式（7）確保了運(yùn)輸?shù)倪B續(xù)性；式（8）表明貨物必須在規(guī)定期限內(nèi)運(yùn)到；式（9）和（10）表明決策變量是取整數(shù)0或1。

3 求解問題的混合型遺傳算法

3.1 算法的基本思路

通過對前面問題描述和虛擬運(yùn)輸網(wǎng)絡(luò)圖的分析可以看出，該路線優(yōu)化問題可視為帶約束條件的最短路問題，也就是在一定約束條件下尋求各城市對之間路線的最佳組合問題。對于帶約束的最短路問題的求解，Dijkstra算法等傳統(tǒng)方法顯得不夠靈活。因此，本文考慮用遺傳算法的隨機(jī)化搜索來確定各城市對之間路線的最佳組合。首先通過編碼和初始化群體（群體規(guī)模為M）生成一組方案集，求出各方案運(yùn)輸總成本F~(k)(k=1，2，…，M)；然后用區(qū)間數(shù)排序方法對F~(k)進(jìn)行排序，從而確定個(gè)體的優(yōu)劣，作為遺傳算法選擇操作的依據(jù)，以此構(gòu)造混合型遺傳算法來求得最佳路線組合方案。算法的基本流程如圖2所示。

3.2 染色體編碼方法

在本模型中使用字符代碼編碼方法，用城市對之間的運(yùn)輸路線編號來表示該問題的染色體編碼。若從運(yùn)輸起點(diǎn)O到運(yùn)輸目的地Q之間經(jīng)過n個(gè)城市，則在虛擬運(yùn)輸網(wǎng)絡(luò)圖中，從起點(diǎn)O到最終點(diǎn)Q之間要經(jīng)過2n+1個(gè)虛擬城市。這里用長度為2n+1的一組數(shù)字來表示一運(yùn)輸路線組合的染色體編碼。例如：

ch(k)=(3 1 1 2 2 3 … 22n+1)（11）

為一運(yùn)輸路線的染色體編碼，它表示在起點(diǎn)和第1個(gè)城市之間選擇第3條路線，在第1個(gè)城市和第2個(gè)城市之間選擇第1條路線，在第2個(gè)與第3個(gè)城市之間選擇第3條路線……在第n個(gè)城市到終點(diǎn)之間選擇第2條路線。初始化群體時(shí)，每個(gè)染色體的第1，3，5，7，…，2n-1，2n+1個(gè)基因從城市對之間的路線編號1，2，…，g中間隨機(jī)產(chǎn)生排列組成，第2，4，6，…，2n個(gè)基因分別與第3，5，7，…，2n+1個(gè)基因相同，可分別從第3，5，7，…，2n+1個(gè)基因直接復(fù)制。由個(gè)體的染色體編碼串，可以統(tǒng)計(jì)出某運(yùn)輸任務(wù)在各個(gè)城市之間所選擇的路線。3.3 適應(yīng)度函數(shù)定義

在本模型中運(yùn)輸路線優(yōu)化的目標(biāo)就是考慮在時(shí)間約束下，使所用運(yùn)輸費(fèi)用最省。設(shè)某一染色體ch(k)=(y1，y2，…，y2j-1，y2j，y2j+1，…，y2n，y2n+1)，它表示在第j-1與第j個(gè)城市之間選擇第y2j-1條路線，在第j與第j+1個(gè)城市之間選擇第y2j條路線，在第j個(gè)城市要從第y2j-1條路線轉(zhuǎn)換到第y2j條路線，取染色體ch(k)所示路線組合方案的運(yùn)輸總成本F~(k)為目標(biāo)函數(shù)： min F~(k)=C~y11，2+nj=1y2jj， j+1+nj=1y2j-1y2jj（12）

運(yùn)輸總時(shí)間為

(k)=y11，2+

nj=1c2jj，j+1+nj=1y2j-1y2jj（13）

式（12）中F~(k)屬于求費(fèi)用最小型函數(shù)，設(shè)計(jì)適應(yīng)度函數(shù)E~(k)為

E~(k)=Cmax-(k) F~(k)＜Cmax

0其他（14）

其中:Cmax為一適當(dāng)?shù)妮斎胫担m應(yīng)度函數(shù)值越大，表示個(gè)體的適應(yīng)度越好，則該個(gè)體遺傳到下一代的概率越大；反之，個(gè)體遺傳到下一代的概率越小。

對區(qū)間數(shù)型適應(yīng)度進(jìn)行比較時(shí)，按照區(qū)間數(shù)的排序方法進(jìn)行操作，其步驟如下：

a)用式（2）計(jì)算各個(gè)個(gè)體適應(yīng)度E~(k)兩兩比較的可能度pij=p(E~(i)≥E~(j))(i， j=1，2，…，M)，M為群體規(guī)模，得到可能度矩陣P=(pij)M×M。

b)用式（3）求出可能度矩陣的排序向量v，依據(jù)v來確定適應(yīng)度的大小。

3.4 約束判斷與調(diào)整

本模型中，在尋求運(yùn)輸總成本最低的過程中存在運(yùn)輸總時(shí)間不超過運(yùn)輸期限T0（實(shí)數(shù)T0可以寫為區(qū)間數(shù)T~0=[T0，T0]）的約束條件，但在算法的進(jìn)化過程中，可能會(huì)出現(xiàn)某些個(gè)體所表示方案的運(yùn)輸時(shí)間超過運(yùn)輸期限，從而降低算法的進(jìn)化效率。為此，需要對群體進(jìn)行控制與調(diào)整，其方法如下：

a)計(jì)算個(gè)體所表示方案的運(yùn)輸總時(shí)間T~(k)。

b)利用區(qū)間數(shù)比較的可能度公式判斷每個(gè)個(gè)體所示方案的運(yùn)輸總時(shí)間T~(k)是否超過運(yùn)輸期限T~0。若T~(k)＞T~0，則以一定的概率將該個(gè)體從群體中刪除。

c)若在步驟b)中刪除了q個(gè)個(gè)體，需要從剩余的群體中復(fù)制q個(gè)個(gè)體，以保持群體的規(guī)模不變。

3.5 遺傳算子的設(shè)計(jì)

1）選擇算子 采取排序選擇策略，具體設(shè)計(jì)如下：首先將群體中的個(gè)體按照適應(yīng)度值從大到小的順序進(jìn)行排列并依次均分為10組，然后將第1組個(gè)體復(fù)制兩份，將第2~9組個(gè)體復(fù)制一份，最后一組不復(fù)制。這種方法保證了在每一代進(jìn)化過程中都能使適應(yīng)度好的個(gè)體被選擇復(fù)制到新的種群中去，并保證群體規(guī)模不變。

2）交叉算子 采用單點(diǎn)交叉的方法，首先對群體進(jìn)行隨機(jī)配對，其次按照均勻分布隨機(jī)產(chǎn)生交叉點(diǎn)位置，最后以交叉概率Pc交換配對染色體之間交叉點(diǎn)之后的基因，產(chǎn)生新的個(gè)體。為保證進(jìn)行交叉操作之后所產(chǎn)生的兩個(gè)新個(gè)體仍然為有效染色體，對交叉點(diǎn)位置進(jìn)行如下設(shè)計(jì)。設(shè)ch(x)、ch(y)為一對相互交叉的染色體，交叉點(diǎn)為第k個(gè)基因座之后，則k的取值為

k=2×round(ra×(n-1))+1（15)

其中:ra為[0，1]內(nèi)符合均勻概率分布的一個(gè)隨機(jī)數(shù)；n為所經(jīng)過城市的數(shù)量；round()表示四舍五入至最近的整數(shù)。

3）變異算子 采用單點(diǎn)動(dòng)態(tài)變異法，個(gè)體ch(x)=(c1，c2，…，ck，…，c2n+1)向

ch(x)=(c1，c2，…，ck，…，c2n+1)變異時(shí)，對ck進(jìn)行變異，則k及變異值ck的取值為

k=2×round(ra×n)+1（16)

ck=round(ra×(g-1))+1（17)

其中:ra為[0，1]內(nèi)符合均勻概率分布的一個(gè)隨機(jī)數(shù)；n為所經(jīng)過城市的數(shù)量；g為城市對之間路線的數(shù)量；round()表示四舍五入至最近的整數(shù)。根據(jù)染色體編碼的特點(diǎn)，為保證交叉操作之后新個(gè)體仍然為有效染色體，對個(gè)體ch(x)=(c1，c2，…，ck，…，c2n+1)進(jìn)行單點(diǎn)動(dòng)態(tài)變異的具體方法設(shè)計(jì)如下：

a)根據(jù)式（16）（17）產(chǎn)生變異點(diǎn)k及變異值ck。

b)如果k=1，則令ck=ck；如果k≠1，令ck=ck且ck-1=ck，從而產(chǎn)生新的個(gè)體。

3.6 群體多樣性控制

在群體的進(jìn)化過程中，為了防止陷入局部最優(yōu)，需要對群體的多樣性進(jìn)行控制。本文運(yùn)用信息熵理論來定義群體的多樣性和多樣性閾值^[12]。設(shè)群體規(guī)模為M，染色體長度為Rn，編碼符號集大小為g(g為城市對之間路線的數(shù)量)，則第j個(gè)基因座的信息熵為

Φj(M)=-gτ=1pτj log2 pτj（18）

其中:pτj=nτj/M，表示基因座j上出現(xiàn)第τ個(gè)符號的概率；nτj為在基因座j上出現(xiàn)第τ個(gè)符號的總個(gè)數(shù)。對于一個(gè)種群來說，Φj(M)越大，說明基因座的多樣性越好。

定義每代的多樣性閾值

(s)=ξe-μs/Slog2 g（19）

其中:ξ∈(0，1)為調(diào)節(jié)系數(shù)；μ＞0為加速因子；s為當(dāng)前進(jìn)化代數(shù)；S為總的進(jìn)化代數(shù)。在進(jìn)化過程中，若群體多樣性低于閾值，則對其多樣性進(jìn)行調(diào)整，調(diào)整方法如下：

首先，從群體中以概率ρ(0＜ρ＜1)隨機(jī)選擇m個(gè)染色體；然后對所選的個(gè)體進(jìn)行低多樣性基因位的隨機(jī)互換，直到低多樣性基因座的個(gè)數(shù)不低于Rn/，為整數(shù)且2≤≤5。

3.7 算法的主要步驟

根據(jù)前面的分析，用混合型遺傳算法求解區(qū)間數(shù)型聯(lián)運(yùn)路線優(yōu)化問題的主要步驟如下：

a)初始化群體G(s)，s=0（s表示進(jìn)化代數(shù)，G(s)表示第s代群體），設(shè)群體規(guī)模為M，初始化群體編碼。

b)計(jì)算個(gè)體的適應(yīng)度E~(k)和個(gè)體所表示方案的運(yùn)輸總時(shí)間T~(k)。

c)判斷每個(gè)個(gè)體所示方案的運(yùn)輸總時(shí)間T~(k)是否超過運(yùn)輸期限T~0，若T~(k)＞T~0，則將該個(gè)體刪除。

d)若在步驟d)中刪除了q個(gè)個(gè)體，需要從剩余的群體中復(fù)制q個(gè)個(gè)體，以保持群體的規(guī)模不變。

e)按照區(qū)間數(shù)排序的方法對群體中的個(gè)體按適應(yīng)度從大到小進(jìn)行排序。

f)如果s≤S（S表示遺傳運(yùn)算終止條件），轉(zhuǎn)步驟g)，否則轉(zhuǎn)步驟l)。

g)對群體G(s)進(jìn)行選擇操作。

h)以交叉概率Pc對群體G(s)進(jìn)行交叉操作。

i)以變異概率Pm對群體G(s)進(jìn)行變異操作。

j)對群體的多樣性進(jìn)行判斷和調(diào)整。

k)得到新一代群體G(s+1)，G(s)←G(s+1)，s←s+1，轉(zhuǎn)步驟b)。

l)對適應(yīng)度最大的染色體進(jìn)行解碼操作，結(jié)束遺傳運(yùn)算。

4 應(yīng)用示例結(jié)果與分析

示例 將貨物從城市O運(yùn)到城市Q，途經(jīng)A、B、C三個(gè)城市，而且相鄰兩個(gè)城市之間都有三條路線可供選擇，假設(shè)最遲運(yùn)輸期限為40，其他參數(shù)如表1、2所示。問如何選擇運(yùn)輸路線可使運(yùn)輸費(fèi)用最省？

取群體規(guī)模M＝50，交叉概率為0.8，變異概率為0.01，進(jìn)化代數(shù)為50，用開發(fā)的改進(jìn)型遺傳算法程序?qū)ι鲜鰡栴}進(jìn)行求解。當(dāng)進(jìn)化到第5代時(shí)，停止進(jìn)化，此時(shí)運(yùn)輸總費(fèi)用為區(qū)間數(shù)[351.5，371.5]，運(yùn)輸總時(shí)間為[35，38.5]，運(yùn)輸總費(fèi)用和運(yùn)輸總時(shí)間隨進(jìn)化代數(shù)的變化曲線如圖3所示。其運(yùn)輸路線組合為②→②→②→③，其虛擬運(yùn)輸網(wǎng)絡(luò)如圖4所示。

5 結(jié)束語

前文對運(yùn)輸路線優(yōu)化問題的描述中，假設(shè)相鄰兩個(gè)城市之間有g(shù)條運(yùn)輸路線，在實(shí)際情況中可能會(huì)遇到某相鄰城市A和B之間僅有g(shù)(g＜g)條運(yùn)輸路線的情況。此時(shí)只需將A和B之間運(yùn)輸路線數(shù)量擴(kuò)充為g條，其中擴(kuò)充的g-g條運(yùn)輸路線的運(yùn)輸費(fèi)用和運(yùn)輸時(shí)間，以及這g-g條路線與其他路線之間的中轉(zhuǎn)費(fèi)用和中轉(zhuǎn)時(shí)間設(shè)為相對比較大的一個(gè)值，即可運(yùn)用本文算法進(jìn)行求解。從目前公開發(fā)表的文獻(xiàn)來看，對區(qū)間數(shù)型聯(lián)運(yùn)路線優(yōu)化問題進(jìn)行專門研究的文獻(xiàn)尚不多見，本算法的提出可為多式聯(lián)運(yùn)經(jīng)營者的決策提供數(shù)據(jù)參考，具有較強(qiáng)的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)：

［1］COPPERMAN R B，DEVLIN M P，EWALT R M，et al.Coordinating and prioritizing multimodal transportation projects[C]//Proc of Systems and Information Engineering Design Symposium.2004:113-119.

［2］蘇印，李鐵柱．國際多式聯(lián)運(yùn)線路選擇的方法研究[J]．交通運(yùn)輸系統(tǒng)工程與信息，2006，6(2)：91-94.

［3］陳德良.集成GIS的集裝箱多式聯(lián)運(yùn)路徑優(yōu)化方法[J].物流技術(shù)，2005，25(6)：80-82.

［4］張運(yùn)河，林柏梁，梁棟，等.優(yōu)化多式聯(lián)運(yùn)問題的一種廣義最短路方法研究[J].鐵道學(xué)報(bào)，2006，28(4)：22-26.

［5］張得志，凌春雨.多種運(yùn)輸方式的組合優(yōu)化模型及求解算法[J].長沙鐵道學(xué)院學(xué)報(bào)，2002，20(4)：71-75.

［6］張建勇，郭耀煌.一種多式聯(lián)運(yùn)網(wǎng)絡(luò)的最優(yōu)分配模式研究[J].鐵道學(xué)報(bào)，2002，24(4)：114-116.

［7］王濤，王剛．一種多式聯(lián)運(yùn)網(wǎng)絡(luò)運(yùn)輸方式的組合優(yōu)化模式[J]．中國工程科學(xué)，2005，7(10)：46-50.

［8］范志強(qiáng)，莊佳芳．基于多維有向圖的多式聯(lián)運(yùn)中運(yùn)輸方式的選擇研究[J]．物流技術(shù)，2006，26(5):47-48，60.

［9］井祥鶴，魏冬峰，周獻(xiàn)中．運(yùn)輸方式選擇多目標(biāo)優(yōu)化問題的混合遺傳算法[J]．計(jì)算機(jī)工程與應(yīng)用，2008，44(6):210-212，224.

［10］AHN C W，RAMAKRISHNA R S.A genetic algorithm for shortest path routing problem and the sizing of populations[J].IEEE Trans on Evolutionary Computation，2002，6(6):566-579.

［11］徐澤水．不確定多屬性決策方法及應(yīng)用[M].北京：清華大學(xué)出版社，2004.

［12］張毅，楊秀霞．一種新的免疫遺傳算法及其在TSP問題中的應(yīng)用[J]．系統(tǒng)工程與電子技術(shù)，2005，27(1):117-120.