有時(shí)間限制的多式聯(lián)運(yùn)路徑優(yōu)化模型研究

盧 欣，雷 強(qiáng)，王其才

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

1 研究背景

隨著生產(chǎn)專業(yè)化程度日益提高，生產(chǎn)地點(diǎn)不斷分散，高附加值產(chǎn)品比重也不斷增加，社會(huì)經(jīng)濟(jì)活動(dòng)日趨高效化，使得時(shí)間價(jià)值變得越來越重要。對(duì)輕工、電子產(chǎn)品、紡織品及服裝、醫(yī)藥制品、食品、儀器儀表、鮮活易腐品等高附加值、時(shí)效性強(qiáng)的貨物而言，貨主希望以盡可能少的時(shí)間耗費(fèi)和適宜的價(jià)格交付完好。限時(shí)性的快捷貨物運(yùn)輸已成為貨運(yùn)發(fā)展的趨勢(shì)之一。多式聯(lián)運(yùn)是該類貨物較佳的運(yùn)輸組織形式，靈活的運(yùn)輸方案是從事快捷貨物運(yùn)輸企業(yè)取得競(jìng)爭(zhēng)優(yōu)勢(shì)的關(guān)鍵。在有時(shí)間限制條件下，對(duì)多式聯(lián)運(yùn)路徑進(jìn)行優(yōu)化對(duì)滿足客戶需求和節(jié)約運(yùn)輸成本具有重要意義。

隨著多式聯(lián)運(yùn)需求量的增加，關(guān)于多式聯(lián)運(yùn)路徑優(yōu)化的研究也逐步深入。有學(xué)者研究了多式聯(lián)運(yùn)下的最短可行路徑問題[1]；付曉鳳等從運(yùn)輸時(shí)間與成本的相關(guān)性出發(fā)，建立了基于時(shí)間/成本一體化的多式聯(lián)運(yùn)路徑優(yōu)化模型[2]；佟璐等以成本和時(shí)間為優(yōu)化目標(biāo)，建立了適應(yīng)運(yùn)量變化情況下的多式聯(lián)運(yùn)路徑優(yōu)化模型，將問題轉(zhuǎn)化為廣義的最短路徑，并選擇蟻群算法對(duì)實(shí)際問題進(jìn)行了求解驗(yàn)證[3]；楊文東等提出了有時(shí)間窗的多式聯(lián)運(yùn)問題的雙層優(yōu)化模型，并設(shè)計(jì)了求解路徑優(yōu)化模型的蟻環(huán)算法[4]。以上研究主要是將時(shí)間轉(zhuǎn)化為費(fèi)用，或者將時(shí)間設(shè)為多目標(biāo)規(guī)劃的一個(gè)子目標(biāo)函數(shù)。而對(duì)于有嚴(yán)格送達(dá)時(shí)間限制的快捷貨物運(yùn)輸，求得的最優(yōu)解不一定能完全滿足時(shí)間要求。在此，主要研究用 K 最短路的方法來求解帶時(shí)限的多式聯(lián)運(yùn)路線優(yōu)化問題[5]。

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

假設(shè)有一批貨物要從點(diǎn) O 途經(jīng)n個(gè)城市運(yùn)送到點(diǎn) D，將每個(gè)城市視為一個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)有 4 個(gè)貨運(yùn)站，分別對(duì)應(yīng)公路、水路、鐵路和航空 4 種運(yùn)輸方式，從上一節(jié)點(diǎn)的某個(gè)站出發(fā)只能采取對(duì)應(yīng)的運(yùn)輸方式，并且必須首先到達(dá)下個(gè)節(jié)點(diǎn)的對(duì)應(yīng)貨運(yùn)站，各運(yùn)輸方式的轉(zhuǎn)換只能在各節(jié)點(diǎn)內(nèi)進(jìn)行，并且最多進(jìn)行一次轉(zhuǎn)換。因此，將節(jié)點(diǎn)n拆開成點(diǎn)2n－1和點(diǎn)2n。點(diǎn)2n－1可以表示為節(jié)點(diǎn)n的入口，點(diǎn) 2n表示為節(jié)點(diǎn)n的出口。例如，將節(jié)點(diǎn)1拆成點(diǎn)1和點(diǎn)2，節(jié)點(diǎn)2拆成點(diǎn)3和點(diǎn)4，依次類推，這樣點(diǎn)D就變成點(diǎn)2n＋1，構(gòu)建的多式聯(lián)運(yùn)網(wǎng)絡(luò)如圖1所示。

圖1中的符號(hào)定義為：Noden為節(jié)點(diǎn)城市n；Point 2n－1為節(jié)點(diǎn)n拆分而成的入口；Point 2n為節(jié)點(diǎn)n拆分而成的出口；①、②、③和④分別代表每個(gè)點(diǎn)的4個(gè)貨運(yùn)站；表示以k運(yùn)輸方式從點(diǎn)2n到點(diǎn)2n＋1；表示以k運(yùn)輸方式從點(diǎn)2n到點(diǎn)2n＋1的費(fèi)用；表示以k運(yùn)輸方式從點(diǎn)2n到點(diǎn)2n＋1的時(shí)間；表示在節(jié)點(diǎn)n內(nèi)，運(yùn)輸方式由i轉(zhuǎn)換為j；表示在節(jié)點(diǎn)n內(nèi)，運(yùn)輸方式由i轉(zhuǎn)換為j的費(fèi)用；表示在節(jié)點(diǎn)n內(nèi)，運(yùn)輸方式由i轉(zhuǎn)換為j的時(shí)間。

3 建立模型

建立多式聯(lián)運(yùn)網(wǎng)絡(luò)的數(shù)學(xué)模型為：

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

式中：當(dāng)節(jié)點(diǎn)n到節(jié)點(diǎn)n+1 選擇運(yùn)輸方式k時(shí)，，否則；當(dāng)在節(jié)點(diǎn)n運(yùn)輸方式由i轉(zhuǎn) 換為j時(shí)，否則；當(dāng)在節(jié)點(diǎn)n運(yùn)輸方式由i轉(zhuǎn)換為j時(shí)，否則當(dāng)在節(jié)點(diǎn)n運(yùn)輸方式由i轉(zhuǎn)換為j時(shí)，否則T0為貨物運(yùn)輸?shù)臅r(shí)間限制。

4 求解步驟

通過對(duì)上述問題的描述和多式聯(lián)運(yùn)網(wǎng)絡(luò)圖的分析可以看出，該問題可以看做帶約束條件的最短路徑問題。這也是一個(gè) NP(Non-Deterministic Polynomial) 問題，很難直接得到一個(gè)滿足時(shí)間限制條件的解，但是能迅速對(duì)一個(gè)解是否滿足要求進(jìn)行驗(yàn)證。

對(duì)于最短路問題的求解，Dijkstra 已經(jīng)給出比較好的算法[6]，對(duì)于有約束條件的最短路求解，可以用 K 最短路法來逐次試探。先求得k最短路，然后檢驗(yàn)此路徑是否滿足時(shí)間限制要求。模型的具體算法步驟如下。

步驟 1：用最短路法求運(yùn)輸費(fèi)用的最短路，然后計(jì)算出此路徑所消耗的時(shí)間，如滿足約束條件，則該解為問題最優(yōu)解，如不滿足則轉(zhuǎn)步驟 2。

步驟 2：用最短路法求運(yùn)輸時(shí)間的最短路，如不滿足時(shí)間約束，則此問題無解；如滿足，令k＝1，轉(zhuǎn)步驟 3。

步驟 3：用 K 最短路法計(jì)算運(yùn)輸費(fèi)用最小的第k＋1 條最短路，并計(jì)算出此路徑所消耗的時(shí)間，如滿足約束條件，則該解為問題最優(yōu)解；如不滿足則重復(fù)步驟 3，直至滿足約束要求為止。

5 實(shí)例計(jì)算

現(xiàn)有一批貨物從城市 0 經(jīng)過 2 個(gè)城市運(yùn)送到城市 3，要求貨物運(yùn)輸時(shí)間不超過 12 d，并通過合理選擇運(yùn)輸方式的組合，使運(yùn)輸成本最低。城市間各種運(yùn)輸方式的運(yùn)輸費(fèi)用和時(shí)間如表 1 所示，各城市內(nèi)部各種運(yùn)輸方式的中轉(zhuǎn)費(fèi)用和時(shí)間如表 2 所示。

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

表2 各城市內(nèi)不同運(yùn)輸方式轉(zhuǎn)換的費(fèi)用和時(shí)間

用最短路法求出運(yùn)輸費(fèi)用最小的方案為：0→1選擇水路，在 1 不轉(zhuǎn)運(yùn)；1→2 選擇水路，在 2 不轉(zhuǎn)運(yùn)；2→3 選擇水路。該路徑的運(yùn)輸費(fèi)用為 1 萬元，時(shí)間消耗為 17 d，不滿足時(shí)間約束條件。

用最短路法求出運(yùn)輸時(shí)間最少的方案為：0→1選擇航空，在 1 不轉(zhuǎn)運(yùn)；1→2 選擇航空，在 2 不轉(zhuǎn)運(yùn)；2→3 選擇航空。該路徑的時(shí)間消耗為 5 d，說明此問題有解。

用K最短路法求出運(yùn)輸費(fèi)用最小的第二短路，運(yùn)輸方案為：0→1 選擇水路，在 1 由水路換為鐵路；1→2 選擇鐵路，在 2 由鐵路換為水路；2→3 選擇水路。該路徑的運(yùn)輸費(fèi)用為 1.4 萬元，時(shí)間消耗為 18 d，不滿足時(shí)間約束條件。

用 K 最短路法求出運(yùn)輸費(fèi)用最小的第三短路，結(jié)果有 2 條。①運(yùn)輸方案一。0→1 選擇水路，在 1不轉(zhuǎn)運(yùn)；1→2 選擇水路，在 2 由水路換為鐵路；2→3 選擇鐵路。該路徑的運(yùn)輸費(fèi)用為 1.5 萬元，時(shí)間消耗為 15 d，不滿足時(shí)間約束條件。②運(yùn)輸方案二。0→1 選擇水路，在 1 不轉(zhuǎn)運(yùn)；1→2 選擇水路，在 2 由水路換為航空；2→3 選擇航空。該路徑的運(yùn)輸費(fèi)用為 1.5 萬元，時(shí)間消耗為 12 d，滿足時(shí)間約束條件。因此，運(yùn)輸方案二為滿足 12 d 內(nèi)將貨物送到的運(yùn)輸費(fèi)用最小的方案。

6 結(jié)束語

多式聯(lián)運(yùn)路徑優(yōu)化問題是多因素的綜合規(guī)劃問題，文中僅對(duì)有時(shí)限的多式聯(lián)運(yùn)貨物運(yùn)輸?shù)穆窂絻?yōu)化問題進(jìn)行了研究，模型的算法思路簡(jiǎn)單，但實(shí)際計(jì)算量較大。當(dāng)節(jié)點(diǎn)較少或可供選擇的運(yùn)輸方式較單一時(shí)，可用此模型及算法求解。但是，隨著運(yùn)輸節(jié)點(diǎn)的增多和運(yùn)輸方式的多樣化，會(huì)使問題解的數(shù)目成幾何倍數(shù)增長(zhǎng)，使求解變得異常困難，因此需要考慮引入遺傳算法來改進(jìn)算法，提高求解效率。

[1] Lozano A，Storchi G.?Shortest Viable Path Algorithm in Multimodal Networks[J].?Transportation Research Part A，2001(35)：225-241.

[2] 付曉鳳，馬 彬，張 娟，等.?多目標(biāo)一體化的聯(lián)運(yùn)路徑優(yōu)化方法研究[J].?鐵道運(yùn)輸與經(jīng)濟(jì)，2009，31(9)：83-85.

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

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

[5] Eppstein D.?Finding the K Shortest Paths[J].?SIAM Journal on Computing，1999，28(2)：652-673.

[6] Dijkstra EW.?A Note on Two Problems in Connection with Graphs[J].?Numer. Math，1959(2)：269-271.