基于節點拆分指派問題的多式聯運路徑優化問題研究

王丹++張磊++許艷麗++于新升

摘 要：在多式聯運路徑優化問題中，城市節點、運輸方式、轉運方式的選擇尤為重要。把不同運輸方式、轉運方式通過節點的拆分融入到網絡圖中，以運輸總成本最低、運輸總時間最短作為路徑優化的整體目標，建立了多式聯運路徑優化問題模型。通過權重系數的引入，將多目標規劃問題轉換為單目標規劃問題，并將優化模型轉化為指派問題模型。最后，以算例證明了路徑優化模型的可行性和有效性。

關鍵詞：多式聯運；節點拆分；指派問題

中圖分類號：U116.2 文獻標識碼：A

Abstract： In the problem of path optimization about the multimodal transportation， the choice of city node， mode of transportation and mode of transit is very important. To put the different modes of transport， transit mode integrate into the network map through the node split， the final objective is the total transportation cost and the total time to the minimum. Transform the multi-objective planning problem into a single-objective planning problem by introducing the weighting factor， and transform the optimization model into an assignment problem model. Finally， the feasibility and effectiveness of the model is proved by examples.

Key words： multimodal transportation； node splitting； assignment problem

0 引 言

隨著現代物流業與交通運輸業的飛速發展，多式聯運打破運輸方式間的界限，在現代經濟的發展中起到尤為重要的作用，已經成為降低物流成本的有效措施，成為提高市場競爭力的有效手段。國民經濟和社會發展“十三五”規劃的發布，表明國家對物流、對多式聯運的重視程度也已經有了顯著提高。

國內外眾多學者在多式聯運方面做出了廣泛而深刻的研究。王清斌研究了帶有時間約束的、以總運輸成本最小為目標的混合整數規劃模型[1]；Hu Z H設計了免疫近似算法來解決應急調度的路徑優化[2]；JANSEN研究了模擬基于港口的集裝箱運營規劃[3]；Grabener T研究了基于時間窗的城市交通多目標路徑優化模型，并利用改進的Martins算法求解[4]；佟璐認為多式聯運路徑的選擇受到多方面相關因素的影響，并將問題轉化成為廣義最短路徑優化問題[5]；雷定猷等將長大貨物作為研究目標，將多目標多式聯運問題簡化，并采用遺傳算法求解[6]；周騫等用遺傳算法求解了以配送成本最低和時間成本最小為目標的配送網絡優化模型[7]。

1 問題描述

在多式聯運網絡中，存在一個起始節點和一個終止節點以及若干中間節點，任意兩個節點之間可能存在若干種運輸方式，由一種運輸方式轉變為另一種運輸方式需要一定的轉運時間和轉運成本。總成本包含運輸成本和轉運成本，總時間包含運輸時間和轉運時間。要解決的問題是：從起始節點到終止節點之間尋找一條運輸路徑使得總成本最低，同時總時間最短。

2 模型假設和符號說明

2.1 模型假設

（1）運輸過程中的運量不可分割，在某一節點處發生運輸方式的變化時，該節點和下一可達節點之間只能選擇一種運輸方式。

（2）在節點處發生運輸方式的變化時，只考慮轉運時間和轉運成本；在兩節點之間只考慮運輸時間和運輸成本。

（3）運輸方式的改變只能發生在節點處。

（4）每個運輸節點都具備運輸方式轉變的所有條件，即在任一節點處發生運輸方式的轉變都是可行的。

2.2 符號說明

A表示所有節點集合，i∈A；A表示初始節點；A表示終止節點；B表示節點i可到達的節點集合，j∈B；D表示運輸方式的集合，k，l∈D；c表示節點i，j之間選擇第k種運輸方式的運輸成本；t表示節點i，j之間選擇第k種運輸方式的運輸時間；c表示在節點i，運輸方式由k轉換到l所需費用；t表示在節點i，運輸方式由k轉換到l所需時間；x

式（1）、式（2）為目標函數，其中式（1）使總成本最低，式（2）使總時間最短；式（3）至式（9）為約束條件，其中式（3）至式（5）保證模型的解能獲得一條從起始節點到終止節點的路徑，式（6）使若路徑經過節點i，則i，j兩個節點之間只能選擇一種運輸方式，式（7）保證運輸的連續性，式（8）、式（9）使決策變量只能取0或1。

4 模型求解

4.1 模型簡化

由于多目標模型的多個目標函數之間往往互不相容，因此導致求解復雜，為簡化求解，加入成本和時間的權重系數，將多目標函數轉化為單目標函數，用其反映在路徑選擇中分別對成本和時間的重視程度。

4.2 網絡變形

圖1中，包含3個網絡節點，其中a為初始節點，a為中間節點，a為終止節點。因為每個路徑存在幾種運輸方式，所以將節點進行拆分，若經由a節點進出有兩種運輸方式，經由a節點進出有兩種運輸方式，則將節點拆分后的網絡圖如圖2所示。

圖2中，a為虛擬初始節點，a、a為a節點拆分后的中間節點，a、a為a節點拆分后的中間節點，a為終止節點。每個路徑代表一種運輸方式或轉運方式。

4.3 變化后的模型符號說明

A表示變化后所有節點集合，i∈A；A表示變化后的初始節點；A表示變化后的終止節點；c表示節點i，j之間產生的成本；t表示節點i，j之間產生的時間；x=

；α表示運輸過程中成本的權重系數；β表示運輸過程中時間的權重系數；μ表示貨物的單位時間價值，即集裝箱遲到目的地1h所產生的成本或費用，由貨物的種類及數量決定。

4.4 變化后的模型

式（10）為目標函數，目標是總成本最小；式（11）至式（16）為約束條件，其中式（12）至式（14）保證模型的解能獲得一條從起始節點到終止節點的路徑，式（7）保證路徑方向由起始節點指向終止節點，式（16）使決策變量只能取0或1。

5 算例分析

一個20英尺集裝箱從鄭州運往韓國首爾，途中有濟南、濟寧兩個中轉站以及青島、連云港兩個港口。各城市之間的運輸網絡如圖3所示。其中，鄭州到濟南、鄭州到濟寧、濟寧到濟南間的運輸方式包含公路運輸和鐵路運輸，濟南到青島有公路運輸和鐵路運輸，濟寧到連云港之間有公路運輸和鐵路運輸，濟南到連云港只存在公路運輸，青島、連云港和韓國首爾間只存在水路運輸。各節點之間的運輸網絡如圖4所示。各節點之間的運輸成本如表1所示；其中，不存在運輸路徑的兩節點運輸成本取一個足夠大的數，本例中取1 000 000元。

圖4中，0代表虛擬初始節點，1代表在鄭州選擇公路運輸，2代表在鄭州選擇鐵路運輸，3代表在濟寧選擇公路運輸，4代表在濟寧選擇鐵路運輸，5代表在濟南選擇公路運輸，6代表在濟南選擇鐵路運輸，7代表在青島選擇公路運輸，8代表在青島選擇鐵路運輸，9代表在青島選擇水路運輸，10代表在連云港選擇公路運輸，11代表在連云港選擇鐵路運輸，12代表在連云港選擇水路運輸，13代表終點首爾。

各節點之間的運輸時間如表2所示。其中，不存在運輸路徑的兩節點運輸時間取一個足夠大的數，本例中取1 000 000小時。

利用Excel進行規劃求解。μ表示貨物的單位時間價值，即集裝箱遲到目的地1h所產生的成本或費用，由貨物的種類及數量決定；本例中取200元/小時。現實環境中，不同公司或產品對時間和成本的要求存在差異，于是α值的變化會導致最優解的變化。

當α=0.1時，計算結果如表3所示，即運輸路徑為：鄭州-（公路）-濟南-（公路）-青島-（水路）-首爾。運輸總時間為28.5小時，運輸總成本為9 845.6元。

當α=0.4時，計算結果如表4所示，即運輸路徑為：鄭州-（公路）-濟南-（鐵路）-青島-（水路）-首爾。運輸總時間為30.5小時，運輸總成本為9 043元。

當α=0.6時，計算結果如表5所示，即運輸路徑為：鄭州-（鐵路）-濟南-（鐵路）-青島-（水路）-首爾。運輸總時間為34小時，運輸總成本為8 134.3元。

6 結 論

在各參數確定的情況下，模型存在一個最優解。時間較短的運輸路線，自然成本相對較高，反之亦然，公司往往需要依據實際情況，調整相關參數，得出綜合考慮時間和成本意義上的最優運輸路徑。

參考文獻：

[1] 王清斌，韓增霞，計明軍，等. 基于節點作業隨機特征的集裝箱多式聯運路徑優化[J]. 交通運輸系統工程與信息，2011，11（6）：137-144.

[2] Hu Z H. A container multimodal transportation scheduling approach based on immune affinity model for emergency relief[J]. Expert Systems with Applications， 2011，38（3）：2632-2639.

[3] Jansen B， Swinkels P C J， Teeuwen G J A， et al. Operational planning of a large-scale multi-modal transportation system[J]. European Journal of Operational Research， 2004，156（1）：41-53.

[4] Grabener T， Berro A， Duthen Y. Time dependent multi objective best path for multimodal urban routing[J]. Electronic Notes in Discrete Mathematics， 2010，36：487-494.

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

[6] 雷定猷，游偉，張英貴，等. 長大貨物多式聯運路徑優化模型與算法[J]. 交通運輸工程學報，2014（1）：75-83.

[7] 周騫，白云卯，徐春龍. 基于遺傳算法的多式聯運物流運輸配送路徑優化研究[J]. 物流工程與管理，2015，37（1）：89-91.