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

楊海波

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

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

楊海波

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

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

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

1 引言

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

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

2 問題的描述及符號(hào)定義

2.1 問題的描述

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

2.2 時(shí)間效益的定義

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

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

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

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

3.1 約束條件的確定

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

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

3.2 求解算法

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

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

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

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

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

（5）若T>T0，則時(shí)間效益為負(fù)，即總運(yùn)輸成本增加，若T

4 算例分析

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

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

表1 城市間各種運(yùn)輸方式的運(yùn)輸費(fèi)用和運(yùn)輸時(shí)間

表2 城市A各運(yùn)輸方式的換裝費(fèi)用及換裝時(shí)間

表3 城市B各運(yùn)輸方式的換裝費(fèi)用及換裝時(shí)間

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

F244.0

A

1004-7344（2016）09-0131-02

2016-3-15