有時間限制的多式聯運路徑優化模型研究

盧 欣，雷 強，王其才

（西南交通大學 交通運輸與物流學院，四川 成都 610031）

1 研究背景

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

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

2 問題描述與符號定義

假設有一批貨物要從點 O 途經n個城市運送到點 D，將每個城市視為一個節點。每個節點有 4 個貨運站，分別對應公路、水路、鐵路和航空 4 種運輸方式，從上一節點的某個站出發只能采取對應的運輸方式，并且必須首先到達下個節點的對應貨運站，各運輸方式的轉換只能在各節點內進行，并且最多進行一次轉換。因此，將節點n拆開成點2n－1和點2n。點2n－1可以表示為節點n的入口，點 2n表示為節點n的出口。例如，將節點1拆成點1和點2，節點2拆成點3和點4，依次類推，這樣點D就變成點2n＋1，構建的多式聯運網絡如圖1所示。

圖1中的符號定義為：Noden為節點城市n；Point 2n－1為節點n拆分而成的入口；Point 2n為節點n拆分而成的出口；①、②、③和④分別代表每個點的4個貨運站；表示以k運輸方式從點2n到點2n＋1；表示以k運輸方式從點2n到點2n＋1的費用；表示以k運輸方式從點2n到點2n＋1的時間；表示在節點n內，運輸方式由i轉換為j；表示在節點n內，運輸方式由i轉換為j的費用；表示在節點n內，運輸方式由i轉換為j的時間。

3 建立模型

建立多式聯運網絡的數學模型為：

圖1 多式聯運網絡示意圖

式中：當節點n到節點n+1 選擇運輸方式k時，，否則；當在節點n運輸方式由i轉 換為j時，否則；當在節點n運輸方式由i轉換為j時，否則當在節點n運輸方式由i轉換為j時，否則T0為貨物運輸的時間限制。

4 求解步驟

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

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

步驟 1：用最短路法求運輸費用的最短路，然后計算出此路徑所消耗的時間，如滿足約束條件，則該解為問題最優解，如不滿足則轉步驟 2。

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

步驟 3：用 K 最短路法計算運輸費用最小的第k＋1 條最短路，并計算出此路徑所消耗的時間，如滿足約束條件，則該解為問題最優解；如不滿足則重復步驟 3，直至滿足約束要求為止。

5 實例計算

現有一批貨物從城市 0 經過 2 個城市運送到城市 3，要求貨物運輸時間不超過 12 d，并通過合理選擇運輸方式的組合，使運輸成本最低。城市間各種運輸方式的運輸費用和時間如表 1 所示，各城市內部各種運輸方式的中轉費用和時間如表 2 所示。

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

表2 各城市內不同運輸方式轉換的費用和時間

用最短路法求出運輸費用最小的方案為：0→1選擇水路，在 1 不轉運；1→2 選擇水路，在 2 不轉運；2→3 選擇水路。該路徑的運輸費用為 1 萬元，時間消耗為 17 d，不滿足時間約束條件。

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

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

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

6 結束語

多式聯運路徑優化問題是多因素的綜合規劃問題，文中僅對有時限的多式聯運貨物運輸的路徑優化問題進行了研究，模型的算法思路簡單，但實際計算量較大。當節點較少或可供選擇的運輸方式較單一時，可用此模型及算法求解。但是，隨著運輸節點的增多和運輸方式的多樣化，會使問題解的數目成幾何倍數增長，使求解變得異常困難，因此需要考慮引入遺傳算法來改進算法，提高求解效率。

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

[2] 付曉鳳，馬 彬，張 娟，等.?多目標一體化的聯運路徑優化方法研究[J].?鐵道運輸與經濟，2009，31(9)：83-85.

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

[4] 楊文東，王文芳.?有時間窗的多式聯運問題分析與建模[J].?南京航空航天大學學報，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.