考慮時間效益的多式聯(lián)運路徑優(yōu)化模型研究

楊海波

（中鐵西安勘察設(shè)計研究院有限責(zé)任公司 西安 610054）

考慮時間效益的多式聯(lián)運路徑優(yōu)化模型研究

楊海波

（中鐵西安勘察設(shè)計研究院有限責(zé)任公司 西安 610054）

多式聯(lián)運路徑優(yōu)化問題是在路網(wǎng)中通過多種運輸方式的合理組合運輸，以達到節(jié)省運輸時間、降低運輸費用、提高運輸服務(wù)質(zhì)量的目的。本文首先引入了時間效益的概念，建立了運輸成本、中轉(zhuǎn)成本以及時間效益組成的總運輸成本最小模型，并找到合適該模型的算法。

多式聯(lián)運；路徑優(yōu)化；時間效益；總運輸成本最小模型

1 引言

隨著社會經(jīng)濟的快速發(fā)展，物流的空間距離被持續(xù)拉大，而時間距離、運輸成本的要求卻越來越高，單一的運輸方式已經(jīng)不能滿足物流時效性、經(jīng)濟性的需要。在這種情況下，多式聯(lián)運為物流的快速運輸提供了相應(yīng)的解決方案。多式聯(lián)運是我國綜合交通運輸系統(tǒng)的核心，多式聯(lián)運的路徑優(yōu)化有助于節(jié)省運輸費用或運輸時間，從而對提高運輸服務(wù)水平、企業(yè)競爭能力以及社會綜合效益有著重要意義。

隨著多式聯(lián)運需求的增加，國內(nèi)外學(xué)者對多式聯(lián)運路徑優(yōu)化的研究逐漸深入。Angelica Lozano等研究了多式聯(lián)運背景下的最短可行路徑問題，并通過順序算法來進行求解[1]；張運河等在分析Reddy構(gòu)建的多式聯(lián)運優(yōu)化模型的基礎(chǔ)上，提出了一種求解最佳運輸路線的廣義最短路法[2]；楊文東、王文芳在考慮不同時間約束的情況下，建立了有時間窗的多式聯(lián)運優(yōu)化的雙層規(guī)劃模型[3]；佟璐等以成本和時間為優(yōu)化目標(biāo)，建立了適應(yīng)運量變化情況下的多式聯(lián)運路徑優(yōu)化模型，將問題轉(zhuǎn)化為廣義的最短路徑，并選擇蟻群算法對實際問題進行了求解驗[4]；上述研究，較少考慮貨物送到時間對運輸總成本的影響。因此，本文從貨物收發(fā)貨人或代理人的角度出發(fā)，在考慮時間效益的基礎(chǔ)上，建立總成本最小模型，通過偏移路徑法求解K最短路，從而得到最優(yōu)方案。

2 問題的描述及符號定義

2.1 問題的描述

假設(shè)有一批貨物需要從源點O經(jīng)由多個節(jié)點運送至終點D，每個節(jié)點代表一個城市，每個城市包含公路、鐵路、航空以及水路4種運輸方式，每種運輸方式分別對應(yīng)一個貨運站。相鄰兩個城市之間存在著4種運輸方式及相應(yīng)的運輸路線可供選擇。這些運輸路線，就構(gòu)成了多式聯(lián)運網(wǎng)絡(luò)圖。在這個網(wǎng)絡(luò)圖中，相鄰兩節(jié)點間只能采用一種運輸方式進行運輸，貨物的換裝只能在節(jié)點內(nèi)部進行，并且只能進行一次換裝，構(gòu)建的多式聯(lián)運網(wǎng)絡(luò)圖如圖1所示。

2.2 時間效益的定義

時間效益是針對多式聯(lián)運收發(fā)貨人或代理人提出的，分為時間正效益和時間負效益兩類。對多式聯(lián)運收發(fā)貨人或代理人他們而言，貨物在規(guī)定的時間內(nèi)運到是最好的。若貨物早于最遲時間送到規(guī)定的地點，則該批貨物具有一定的時間正效益，那么運輸總成本相應(yīng)減少；若貨物晚于最遲時間送到規(guī)定地點，則該批貨物具有時間負效益，那么運輸總成本相應(yīng)增加。

圖1 多式聯(lián)運網(wǎng)絡(luò)示意圖

2.3 多式聯(lián)運網(wǎng)絡(luò)模型參數(shù)說明

3 多式聯(lián)運路徑優(yōu)化模型的建立

3.1 約束條件的確定

建立多式聯(lián)運網(wǎng)絡(luò)模型如下：

其中，目標(biāo)函數(shù)以整個運輸過程中的運輸總成本最少為目標(biāo)，而運輸總成本由運輸成本、中轉(zhuǎn)成本以及時間效益三部分組成。第1個約束條件表示這批貨物從源點O運到終點D的實際總運輸時間，由運輸時間、中轉(zhuǎn)時間兩部分組成。第2個約束條件表示在節(jié)點i-1，i之間采用第k種運輸方式，那么在節(jié)點i，i+1之間采用第j種運輸方式，以確保運輸?shù)倪B續(xù)性；第3個約束條件表示在某一特定的城市對之間只能選擇一種運輸方式；第4個約束條件表明，在城市i，只有一次運輸換裝，即從第k種運輸方式換裝為第j種運輸方式；第5個約束條件表明決策變量是取整數(shù)O或1；第6個約束條件表明時間效益因子為非負。

3.2 求解算法

上述模型是基于總成本最小的多式聯(lián)路徑優(yōu)化模型，總成本由運輸成本、中轉(zhuǎn)成本以及時間效益所組成。根據(jù)上述問題描述及多式聯(lián)運網(wǎng)絡(luò)示意圖可知，該問題可以轉(zhuǎn)化為最短路徑問題，Dijkstra算法是一種求解單一最短路問題的較好算法。考慮到時間效益，本文采用k最短路法，求解步驟如下：

（1）在不考慮時間的情況下，找出多式聯(lián)運網(wǎng)絡(luò)中所有節(jié)點到終點D的最短路徑，即以終點D為根的最短路徑生成樹；

（2）最短路徑生成樹中起點O到終點D的路徑P1就是所求的k條路徑中最短的一條，將P1放入路徑集合H；

（3）重復(fù)進行上述步驟，依次找出起點O到終點D的次最短路徑P2，……，k-1最短路徑Pk-1，k最短路徑Pk，放入路徑集合H；

（4）依次計算出路徑集合中k條最短路徑的運輸成本和中轉(zhuǎn)成本，并計算路徑所對應(yīng)的運輸總時間T，將其與最遲運到時間進行比較；

（5）若T>T0，則時間效益為負，即總運輸成本增加，若T

4 算例分析

一批貨物從城市O經(jīng)由A、B兩個城市運到城市D，A、B兩個城市間運輸方式有航空、鐵路、公路以及水路四種運輸方式，貨物運到最遲期限為12d，時間正效益為1萬元/d，時間負效益為1萬元/d。各城市間的多式聯(lián)運網(wǎng)絡(luò)模型如圖2所示，各種運輸方式的運輸費用和運輸時間如表1所示，城市A各運輸方式間的換裝費用和換裝時間如表2所示，城市B各運輸方式的換裝費用和換裝時間如表3所示。

圖2 各城市間多式聯(lián)運網(wǎng)絡(luò)示意圖

表1 城市間各種運輸方式的運輸費用和運輸時間

表2 城市A各運輸方式的換裝費用及換裝時間

表3 城市B各運輸方式的換裝費用及換裝時間

在不考慮時間的情況下，用K最短路算法求出費用最優(yōu)解可得：

最短的運輸路徑（方案一）為：O→A選擇水路，在A不轉(zhuǎn)運；A→B選擇水路，在B不轉(zhuǎn)運；B→D選擇水路，在B不轉(zhuǎn)運。

其次最短運輸路徑（方案二）為：O→A選擇水路，在A由水路轉(zhuǎn)為鐵路，A→B選擇鐵路，在B由鐵路轉(zhuǎn)為水路，B→D選擇水路。

第三最短運輸路徑（方案三）為：O→A選擇鐵路，在A由鐵路轉(zhuǎn)為水路，A→B選擇水路，在B由水路轉(zhuǎn)為鐵路，B→D選擇鐵路。

方案一運到周期T1=5+5+9=19d；方案二運到周期T2為運輸時間與轉(zhuǎn)運時間之和，即 T2=（5+3+9）+（1+1）=19d；方案三運到周期 T3也為運輸時間與轉(zhuǎn)運時間之和，即為 T3=（2+5+3）+（1+1）=12d。

方案一與方案二運到周期均大于最遲運到時間，因此，必須考慮時間負效益，方案一運輸總本為：Z1=3+3+4+（19-12）×1=17（萬元）；方案二運輸總成本Z2應(yīng)為運輸成本、中轉(zhuǎn)成本以及時間負效益之和，則方案二的運輸總成本。

Z2=（3+5+4）+（1+1）+（19-12）×1=19（萬元）。方案三運輸總成本為運輸成本與中轉(zhuǎn)成本之和，則 Z3=（4+3+6）+（1+1）=16（萬元）。

因此，選擇方案三，運輸路徑為O→A選擇鐵路，在A由鐵路轉(zhuǎn)為水路，A→B選擇水路，在B由水路轉(zhuǎn)為鐵路，B→D選擇鐵路。

5 結(jié)束語

多式聯(lián)運路徑優(yōu)化問題是多因素的綜合規(guī)劃問題，多種運輸方式的有效結(jié)合才能使運營企業(yè)進行最優(yōu)成本控制的同時，以最快的速度將貨物運送至目的地。本文考慮到時間對企業(yè)的經(jīng)營具有效益（正效益和負效益），因此，建立了考慮時間效益的總成本最小模型。模型的算法思路簡單，但實際計算量隨著節(jié)點城市的增多而成倍的增長，當(dāng)節(jié)點較多時，建議使用遺傳算法或模擬退火算法進行求解。

[1]LozanoA，StorchiG.Shortest viable path algorithm in multimodal networks[J].Transportation Research PartA，2001，35：225～241.

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

[3]楊文東，王文芳.有時間窗的多式聯(lián)運問題分析與建模[J].南京航空航天大學(xué)學(xué)報，2009，41（1）：111～115.

[4]佟璐，聶磊，付慧伶.多式聯(lián)運路徑優(yōu)化模型與方法研究[J].物流技術(shù)，2010，212（3）：57～60.

[5]魏眾，申金升，等.多式聯(lián)運的最短時間路徑－運輸費用模型研究[J].中國工程科學(xué)，2006，8（8）．

F244.0

A

1004-7344（2016）09-0131-02

2016-3-15