多式聯(lián)運(yùn)運(yùn)輸方案選擇的和聲搜索算法

摘要：考慮多式聯(lián)運(yùn)路徑上運(yùn)輸方案選擇問(wèn)題，建立了降低運(yùn)輸總成本和縮短運(yùn)輸總時(shí)間的多目標(biāo)數(shù)學(xué)模型，通過(guò)加權(quán)兩個(gè)目標(biāo)函數(shù)，設(shè)計(jì)新的和聲生成方式及微調(diào)方式，采用新和聲競(jìng)爭(zhēng)式替換記憶庫(kù)中最差和聲的方式，提出一種基于字符編碼方式的和聲搜索算法，最后用示例驗(yàn)證了算法的有效性。

關(guān)鍵詞：多式聯(lián)運(yùn)； 運(yùn)輸方案； 和聲搜索算法

中圖分類號(hào)：TP301.6； U116 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）02-0042-03

0引言

隨著國(guó)內(nèi)物流基礎(chǔ)設(shè)施的完善及經(jīng)濟(jì)的快速發(fā)展，客戶對(duì)物流服務(wù)水平的要求越來(lái)越高，單一的物流運(yùn)輸方式已無(wú)法滿足客戶多方面的需求，合理的多式聯(lián)運(yùn)可以實(shí)現(xiàn)成本或時(shí)間的節(jié)省，對(duì)于提高物流公司的服務(wù)水平、競(jìng)爭(zhēng)能力及效益或效率均具有重要的現(xiàn)實(shí)意義。國(guó)內(nèi)外學(xué)者對(duì)多式聯(lián)運(yùn)的相關(guān)研究工作也愈發(fā)關(guān)注，并陸續(xù)推出研究效果。如Lozano等利用順序算法研究了多式聯(lián)運(yùn)下的最短可行路徑問(wèn)題[1]，張運(yùn)河等通過(guò)加入虛擬的節(jié)點(diǎn)構(gòu)建多式聯(lián)運(yùn)多重圖并基于最短路算法求解[2]，更多學(xué)者將改進(jìn)或混合遺傳算法[3-7]應(yīng)用于多式聯(lián)運(yùn)運(yùn)輸方式選擇方案問(wèn)題中，也已取得良好效果。

和聲搜索算法（Harmony Search， HS）是Geem等[8]受樂(lè)師反復(fù)調(diào)整樂(lè)隊(duì)中各樂(lè)器音調(diào)而得到優(yōu)美和聲這一現(xiàn)象的啟發(fā)而提出的一種新的啟發(fā)式搜索算法，目前已成功應(yīng)用于多個(gè)優(yōu)化領(lǐng)域中[9-10]。這一現(xiàn)象表示了該算法具有較強(qiáng)的魯棒性和廣泛的應(yīng)用前景，但卻鮮有學(xué)者將和聲搜索算法應(yīng)用于多式聯(lián)運(yùn)中運(yùn)輸方案的優(yōu)化選擇。本文從多式聯(lián)運(yùn)運(yùn)輸方案優(yōu)化角度入手，結(jié)合問(wèn)題的特征，將其轉(zhuǎn)化為降低運(yùn)輸總成本和縮短運(yùn)輸總時(shí)間這一多目標(biāo)問(wèn)題，提出一種高效的求解該問(wèn)題的和聲搜索算法，算例結(jié)果表明本文所給算法表現(xiàn)出了優(yōu)異的搜索性能。

1問(wèn)題的提出與描述

設(shè)有一個(gè)多式聯(lián)運(yùn)運(yùn)輸方式選擇問(wèn)題：將一批貨物從始發(fā)地運(yùn)到目的地，途經(jīng)若干城市，任意相鄰城市間有多種運(yùn)輸方式可供選擇，相鄰城市間的運(yùn)輸時(shí)間和成本不盡相同，當(dāng)從一種運(yùn)輸方式轉(zhuǎn)換到另一種運(yùn)輸方式時(shí)需要一定的時(shí)間和成本，問(wèn)如何選擇運(yùn)輸方式，使得運(yùn)輸總成本或運(yùn)輸總時(shí)間最小。

為便于模型建立和說(shuō)明，作如下假設(shè)：

假設(shè)1 只有一個(gè)作業(yè)，且作業(yè)的運(yùn)輸量不超過(guò)任一種運(yùn)輸方式的運(yùn)量；

假設(shè)2 貨物只在城市處整批裝載，在城市間不允許發(fā)生裝載，且在每個(gè)城市最多裝載一次；

假設(shè)3 貨物在兩個(gè)城市間只能選擇一種運(yùn)輸方式和一條運(yùn)輸路徑；

假設(shè)4 貨物在每個(gè)城市即時(shí)換裝，不存在庫(kù)存或看管問(wèn)題。

在上述假設(shè)下，同時(shí)兼顧降低運(yùn)輸總成本和縮短運(yùn)輸總時(shí)間兩個(gè)目標(biāo)的數(shù)學(xué)模型如下：

其中，Z1，Z2分別表示運(yùn)輸總成本及運(yùn)輸總時(shí)間，Cki，i+1和Tki，i+1分別表示貨物經(jīng)城市i到i+1運(yùn)輸時(shí)選擇第k種運(yùn)輸方式的運(yùn)輸成本及運(yùn)輸時(shí)間，SCkli和STkli分別表示貨物在城市i處轉(zhuǎn)換運(yùn)輸方式時(shí)的中轉(zhuǎn)成本和中轉(zhuǎn)時(shí)間；xki，i+1=1表示運(yùn)輸時(shí)在城市i與i+1之間選擇第k種運(yùn)輸方式，若不選擇該種方式，則為0；ωkl1=1表示運(yùn)輸時(shí)在城市i處從運(yùn)輸方式k轉(zhuǎn)到運(yùn)輸方式l，若非如此，則為0；R表示運(yùn)輸時(shí)需要經(jīng)過(guò)的城市集合，M表示可供選擇的運(yùn)輸方式集合。式（3）表示任意兩個(gè)城市間只能選擇一種運(yùn)輸方式，式（4）表示在任一城市處不轉(zhuǎn)換運(yùn)輸方式（k=l）或只轉(zhuǎn)換一次運(yùn)輸方式（k≠l），式（5）-（7）確保運(yùn)輸?shù)倪B續(xù)性，式（8）表明決策變量為0-1變量。第2期賴志柱：多式聯(lián)運(yùn)運(yùn)輸方案選擇的和聲搜索算法智能計(jì)算機(jī)與應(yīng)用第3卷

2求解運(yùn)輸方案選擇的和聲搜索算法

21問(wèn)題的編碼

問(wèn)題中，模型求解僅需確定運(yùn)輸時(shí)各子路徑（城市與城市間）上的運(yùn)輸方式，而與其它因素?zé)o關(guān)。為此，假設(shè)有m種可能的運(yùn)輸方式，先將各運(yùn)輸方式編號(hào)為1，2，…m，若選定的兩個(gè)城市間沒(méi)有某種運(yùn)輸方式，則將此處的運(yùn)輸成本和時(shí)間均設(shè)置成很大數(shù)值，其后可采用字符編碼方式，每一碼位表示運(yùn)輸過(guò)程中所經(jīng)過(guò)的一條子路徑，碼位上的值表示在該子路徑上運(yùn)輸時(shí)選擇的運(yùn)輸方式。例如，若從運(yùn)輸起點(diǎn)O到運(yùn)輸終點(diǎn)P之間順序經(jīng)過(guò)3個(gè)城市ABC，用長(zhǎng)度為4的一組數(shù)字表示某一運(yùn)輸方式選擇方案，如和聲x=（1，3，2，3）表示從O到A選擇運(yùn)輸方式1，從A到B選擇運(yùn)輸方式3，從B到C選擇運(yùn)輸方式2，從C到P選擇運(yùn)輸方式3，此時(shí)每個(gè)中間城市處都發(fā)生了運(yùn)輸方式轉(zhuǎn)換。

22適應(yīng)度的計(jì)算

將兩個(gè)目標(biāo)函數(shù)進(jìn)行簡(jiǎn)單加權(quán)處理，具體計(jì)算公式為：

23算法步驟

如果多式聯(lián)運(yùn)問(wèn)題包含運(yùn)輸方式的運(yùn)量限制，可以先將作業(yè)運(yùn)量與運(yùn)輸方式運(yùn)量作一比較，無(wú)法作業(yè)的運(yùn)輸方式所在路徑的預(yù)處理結(jié)果為此處不存在路徑，再應(yīng)用本文算法進(jìn)行求解即可。當(dāng)多式聯(lián)運(yùn)路徑取道的城市太多，加入虛擬城市的模型則易出現(xiàn)“組合爆炸”現(xiàn)象，此時(shí)再用最短路算法求解也未必理想，而利用本文算法，因其易于理解、實(shí)現(xiàn)簡(jiǎn)單及效果顯著，就可以用來(lái)實(shí)現(xiàn)運(yùn)輸方式的高效優(yōu)化方案選擇。

參考文獻(xiàn)：

[1] LOZANO A， STORCHI G. Shortest viable path algorithm in multimodal networks[J] . Transportation Research Part A ，2001，35：225-241.

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

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

[4]俞武揚(yáng). 多式聯(lián)運(yùn)運(yùn)輸問(wèn)題的混合遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2009，45（33）： 10-12.

[5]王旭， 遲增彬， 葛顯龍. 帶時(shí)間窗的整車多式聯(lián)運(yùn)模型研究與解析[J]. 計(jì)算機(jī)應(yīng)用研究， 2011，28（2）： 563-565.

[6]李愈， 趙軍， 吳剛， 等. 帶有固定運(yùn)費(fèi)的多式聯(lián)運(yùn)方式選擇[J]. 西南交通大學(xué)學(xué)報(bào)， 2012，47（5）： 881-887.

[7]盛景軍， 王晴， 侯立峰， 等. 基于Pareto適應(yīng)度的混合遺傳算法在多式聯(lián)運(yùn)中的應(yīng)用[J]. 西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012，37（9）： 43-47.

[8]GEEM Z W， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search， Simulation 2001，76（2）： 60–68.

[9]MAHDAVI M， FESANGHARY M， E. DAMANGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation， 2007，188： 1567–1579.

[10]武磊， 潘全科， 桑紅燕， 等. 求解零空閑流水線調(diào)度問(wèn)題的和聲搜索算法[J]. 計(jì)算機(jī)集成制造系統(tǒng)， 2009，15（10）：1960-1967.