楊楠

（中國鐵路蘭州局集團有限公司科技和信息化部，甘肅蘭州730000）

1 引言

多式聯(lián)運作為一種高效的貨物運輸組織形式，具有整合不同運輸方式的優(yōu)勢，通過有效轉(zhuǎn)換和無縫銜接來提高貨運效率和質(zhì)量。在集裝箱多式聯(lián)運網(wǎng)絡(luò)中存在若干個運輸節(jié)點和多種運輸方式，如何合理地做出各種運輸組織與調(diào)度的決策是提高聯(lián)運效率的關(guān)鍵，這些決策尤其體現(xiàn)在運輸方式選擇與運輸路徑組合優(yōu)化方面。

張運河等[1]對運輸費用和中轉(zhuǎn)費用進行分析估計，得出廣義費用最小的運輸方案，并利用Dijkstra進行求解。Chang等[2]考慮了固定運輸成本、運輸中轉(zhuǎn)成本，以此構(gòu)建了以最小成本為目標(biāo)并帶有時間窗的規(guī)劃模型。劉艦等[3]考慮了運輸成本、運輸?shù)臅r效性，以此建立了基于運輸成本最小的綜合優(yōu)化模型。張建勇[4]具體描述了多式聯(lián)運網(wǎng)絡(luò)，并以總成本最小為目標(biāo)，建立了一種多式聯(lián)運網(wǎng)絡(luò)的最優(yōu)分配模型。孫華燦等人[5]提出了多種運輸方式聯(lián)合的合理運輸路徑，考慮運輸過程中運輸方式序列的合理性以及轉(zhuǎn)運次數(shù)的合理性，建立了以運輸費用最低為目標(biāo)的聯(lián)合運輸合理路徑選擇模型。張家應(yīng)等人[6]考慮軍事運輸?shù)奶厥庑裕瑧?zhàn)時要求時最短，平時要求總成本最低，分別以運輸時間最短和總成本最小為目標(biāo)建立模型，在計算時間、費用時，考慮了超出運輸期限造成的時間和成本的損耗。雷英杰等人[7-8]提出采用Matlab的遺傳算法工具箱來求解該復(fù)雜問題，并通過案例予說明，將鐵、水、公、空等運輸方式的道路網(wǎng)絡(luò)直接用于求解，但傳統(tǒng)遺傳算法的運行效率十分低。楊秋秋[9]將多式聯(lián)運的運輸優(yōu)化問題轉(zhuǎn)化為最短路徑問題，使用遺傳算法來求解該問題。此種方法適用于網(wǎng)絡(luò)較小的情況，而且在實際中時間最短未必總成本最少，該遺傳算法有待改進。

在已有求解過程中，多是采用傳統(tǒng)的遺傳算法或者確定性的最短路求解問題，沒有考慮時間與總成本的聯(lián)系分開求解。結(jié)合各種運輸方式的客觀需要，本文以總成本最小為目標(biāo)建立模型，考慮了運到時限因素，在總成本中加入超過約束時間的懲罰成本，同時采用一種基于floyd的K短路算法并結(jié)合遺傳算法為各路段分配合理的運輸方式，從而指導(dǎo)運輸方案的制定。

2 多式聯(lián)運模型構(gòu)建

2.1 問題描述

現(xiàn)有一批貨物，欲從O點送至D點，運輸途中有n個節(jié)點（城市），任意相鄰節(jié)點之間均有k（k=1,2）種運輸方式，每個節(jié)點都可以轉(zhuǎn)換貨物的運輸方式，轉(zhuǎn)運需一定的中轉(zhuǎn)費用和中轉(zhuǎn)時間，構(gòu)建從出發(fā)點到目的點的完整路徑，選擇OD間最佳的運輸方式和運輸路徑組合，以使總成本（包括運輸費用和時間成本）最低，且盡可能滿足托運人的運到時限。

2.2 模型假設(shè)

①貨物在運輸節(jié)點中不可分開運輸；②貨物的轉(zhuǎn)運只能發(fā)生在節(jié)點，且在各節(jié)點最多進行一次轉(zhuǎn)載；③貨物在兩個節(jié)點中只能選擇一條運輸路徑和一種運輸方式；④貨物在節(jié)點即時轉(zhuǎn)運，沒有庫存[10]。

2.3 符號說明

構(gòu)造網(wǎng)絡(luò)G（V,E），其中V為節(jié)點集合，E為節(jié)點間的弧集；L為運輸方式集合；為從節(jié)點i到節(jié)點j選擇第k種運輸方式；表示在i點運輸方式由k轉(zhuǎn)換為l；為從節(jié)點i到節(jié)點j選擇第k種運輸方式時所需的費用；為在節(jié)點i處，運輸方式由k轉(zhuǎn)換為運輸方式l時所需要的費用；Tmax、Tmin分別為運到時限的上、下界；p表示實際運輸時間低于下限的懲罰因子；q表示實際運輸時間高于上限的懲罰因子；為在節(jié)點i、j之間以第k種運輸方式通過時所需的時間，其由和分別為通過節(jié)點i到j(luò)的距離與所選運輸方式的速度[11-12]。

2.4 模型建立

根據(jù)以上描述，模型可被定義為具有時間約束的路徑及運輸方式選擇問題，其目標(biāo)為在使總成本最少的前提下，盡可能滿足托運人的時間需求，可建立如下模型[13]：

上述模型中，目標(biāo)函數(shù)（1）表示總費用最小，其主要包括三部分：運輸成本運輸方式轉(zhuǎn)換成本，超出限制時間的懲罰成本；約束（2）表示整體運輸時間為各節(jié)點間運輸時間與轉(zhuǎn)運時間之和；（3）和（4）分別表示運到時間超出時間約束的下限懲罰函數(shù)和上限懲罰函數(shù)；（5）和（6）表示任意兩節(jié)點間只采用一種交通方式，任意節(jié)點處最多進行一次運輸方式轉(zhuǎn)換；（7）確保運輸?shù)倪B續(xù)性；（8）決策變量為整數(shù)。

3 算法設(shè)計

本文研究的問題屬于網(wǎng)絡(luò)優(yōu)化問題，而網(wǎng)絡(luò)和路徑優(yōu)化本身就屬于組合優(yōu)化的問題，該問題已經(jīng)被呂凱等[14]證明是NP-hard問題。目前已有相當(dāng)多的文獻提出了求解該類問題的方法，并且隨著計算機技術(shù)的不斷應(yīng)用，用于解決此類問題的新方法也不斷涌現(xiàn)，具體可以歸納為兩大類：確定性算法和啟發(fā)式算法。結(jié)合確定性算法和啟發(fā)式算法的特點及其適用范圍，對本文所要求解的問題分兩個階段進行求解，第一階段利用基于floyd的K短路算法求出K條運輸路徑；第二階段利用遺傳算法，為求出的K條運輸路徑分配運輸方式。

3.1 基于Floyd的K短路算法

本文研究的路徑優(yōu)化問題中，兩點間的弧無方向約束，即運輸網(wǎng)絡(luò)為無向圖。在多式聯(lián)運中，所求的最短路并不一定是運輸網(wǎng)絡(luò)中的最優(yōu)方案路徑，基于此，將求出的K條最短路作為初始方案中的路徑。具體步驟如下：

對于每一對頂點i和j，看是否存在一個頂點w使得從i到w再到j(luò)比已知的路徑更短，如果是更新它；把網(wǎng)絡(luò)圖G用鄰接矩陣表示，如果從i到j(luò)可達的路徑，則G[i,j]=d，d表示該條路徑的長度，否則G[i,j]=無窮大；定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從i到j(luò)需要經(jīng)過的點，初始化D[i,j]=j；把各個頂點插入圖中，比較插點后的距離與原來的距離，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值變小，則D[i,j]=k；G中包含兩點之間最短道路的信息，D中則包含了最短可通過路徑的信息。

3.2 遺傳算法

遺傳算法采用概率的變遷規(guī)則來指導(dǎo)搜索方向。因此第二階段將上述所求得的K條短路作為問題的初始可行路徑，利用遺傳算法為其匹配運輸方式。

3.2.1 染色體編碼和種群初始化

在運輸網(wǎng)絡(luò)中，用V={1,2,3L n}表示城市節(jié)點集合，用L={1,2}表示兩種運輸方式[11]（公路、鐵路）。以第一階段所求出的K條最短路進行循環(huán)，隨機取L中元素，插入到方案路徑中，即為各個路段分配了對應(yīng)的運輸方式，從而形成了有K條染色體的初始種群，染色體編碼如圖1所示。在編碼過程中，城市節(jié)點和運輸方式分別進行編碼，圖中城市編號中的0表示不通過該節(jié)點。

圖1 染色體編碼圖

3.2.2 適應(yīng)度函數(shù)

本多式聯(lián)運問題將目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)[15]，適應(yīng)度函數(shù)為

3.2.3 選擇算子

選擇操作主要分為兩個階段：第一是計算出單個個體的適應(yīng)度值；第二是以輪盤賭選擇法來進行個體的選擇，具體的操作過程如下：

3.2.4 交叉算子

交叉算子可以產(chǎn)生新的個體，采用雙點交叉，在城市節(jié)點和運輸方式中分別隨機產(chǎn)生兩個交叉點，把兩個交叉點之間的基因進行交換，得到新的個體，具體的交叉過程如圖2所示，虛線位置表示隨機選擇的交叉點。

圖2 雙點交叉算子

3.2.5 變異算子

變異算子是指將個體編碼串中的某些基因值改變或者替換成其他的基因值，從而形成一個新的個體。遺傳算法中使用變異算子的目的主要有兩個：一是改善遺傳算法的局部搜索能力；二是維持種群的基因多樣性，抑制早熟。本文變異采用雙點變異，具體的變異方式如圖3所示。

圖3 雙點變異算子

3.3 算法流程

Step 1.設(shè)置算法初始值；

Step 2.利用floyd算法，找出初始最短路；

Step 3.刪去原值中最短路的邊的權(quán)值，從新的權(quán)值矩陣中求出新的最短路，即次短路，順次求出N最短路，即最初方案；

Step 4.編碼，對上述N最短路進行循環(huán)，隨機產(chǎn)生小于等于k的正整數(shù)，插入最短路方案中，即為各個路段分配了對應(yīng)的運輸方式，從而形成一個完整的染色體；

Step 5.初始化，根據(jù)step4產(chǎn)生初始種群并計算適應(yīng)度值；

Step 6.對Step5的結(jié)果進行輪盤賭選擇；

Step 7.將選擇出來的染色體兩兩進行交叉；

Step 8.檢查生成路徑是否可行，如果可行，保留個體；如果不可行，將父代的兩條染色體執(zhí)行Step 9；

Step 9.變異操作，返回Step8；

Step 10.終止條件，若連續(xù)若干代的最優(yōu)解相同，則終止迭代，解碼并輸出最優(yōu)個體與目標(biāo)函數(shù)值。

4 案例設(shè)計

現(xiàn)在有一批50 t貨物從節(jié)點1運送到節(jié)點18，如圖4，整個運輸過程中共有公路，鐵路，兩種運輸方式可供選擇，各節(jié)點間運輸距離如表1，各運輸方式特征如表2，算法初始值見表3。現(xiàn)要求在托運人指定的時間窗[18 h,24 h]內(nèi)，用最小的經(jīng)濟成本，選擇合理的路徑和運輸方式搭配，將貨物從起點運至終點。其中公鐵單位換裝費用為10￥/t，單位換裝時間為0.01 h/t。

圖4 城市節(jié)點連接圖

表1 節(jié)點間運輸距離

表2 運輸方式特征

表3 算法初始值

本算法屬于啟發(fā)式算法，收斂結(jié)果具有一定隨機性，為驗證混合算法的普適性，在此取各算法運行10次中的最好解和性能評價指標(biāo)進行對比。

圖5 各算法收斂圖

圖6 算法結(jié)果

以此算例作為測試集，運行結(jié)果如圖5～6所示，表4給出了兩種算法的求解結(jié)果，由結(jié)果可知，各算法求得最佳路徑均為1→2→7→10→14→16→18，其中轉(zhuǎn)運方式為：公→鐵→鐵→鐵→鐵→鐵，總花費為23 755元，該方案總耗時19.604 2 h。

表4 各算法求解結(jié)果

從結(jié)果可知混合算法能夠有效收斂到最好解，且收斂代數(shù)較傳統(tǒng)遺傳算法減少22.9%；從仿真過程可以看出混合算法具有更快的收斂能力和更好的優(yōu)化性能。

5 結(jié)語

通過對多式聯(lián)運和遺傳算法相關(guān)的大量文獻進行研究，在對運輸方式和運輸路徑合理選擇的基礎(chǔ)上，考慮運輸成本、轉(zhuǎn)運成本、時間懲罰成本建立了多式聯(lián)運網(wǎng)絡(luò)優(yōu)化模型。

設(shè)計了基于floyd的K短路-GA混合算法，該混合算法增強了算法的搜索能力，避免出現(xiàn)局部最優(yōu)解，并利用MATLAB對模型進行仿真計算，能夠求解得到總成本最少的聯(lián)運方案。

將該混合算法和傳統(tǒng)遺傳算法同時應(yīng)用于多式聯(lián)運算例求解，從混合算法的傳統(tǒng)遺傳算法的求解結(jié)果對比可知混合算法在約36次迭代時達到最優(yōu)，傳統(tǒng)遺傳算法到約50次迭代才達到最優(yōu)，表明混合遺傳算法較傳統(tǒng)算法收斂更快，并驗證了混合算法的有效性。