基于節(jié)點拆分指派問題的多式聯(lián)運路徑優(yōu)化問題研究

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

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

關鍵詞：多式聯(lián)運；節(jié)點拆分；指派問題

中圖分類號：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 引 言

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

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

1 問題描述

在多式聯(lián)運網(wǎng)絡中，存在一個起始節(jié)點和一個終止節(jié)點以及若干中間節(jié)點，任意兩個節(jié)點之間可能存在若干種運輸方式，由一種運輸方式轉(zhuǎn)變?yōu)榱硪环N運輸方式需要一定的轉(zhuǎn)運時間和轉(zhuǎn)運成本?？偝杀景\輸成本和轉(zhuǎn)運成本，總時間包含運輸時間和轉(zhuǎn)運時間。要解決的問題是：從起始節(jié)點到終止節(jié)點之間尋找一條運輸路徑使得總成本最低，同時總時間最短。

2 模型假設和符號說明

2.1 模型假設

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

（2）在節(jié)點處發(fā)生運輸方式的變化時，只考慮轉(zhuǎn)運時間和轉(zhuǎn)運成本；在兩節(jié)點之間只考慮運輸時間和運輸成本。

（3）運輸方式的改變只能發(fā)生在節(jié)點處。

（4）每個運輸節(jié)點都具備運輸方式轉(zhuǎn)變的所有條件，即在任一節(jié)點處發(fā)生運輸方式的轉(zhuǎn)變都是可行的。

2.2 符號說明

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

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

4 模型求解

4.1 模型簡化

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

4.2 網(wǎng)絡變形

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

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

4.3 變化后的模型符號說明

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

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

4.4 變化后的模型

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

5 算例分析

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

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

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

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

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

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

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

6 結(jié) 論

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

參考文獻：

[1] 王清斌，韓增霞，計明軍，等. 基于節(jié)點作業(yè)隨機特征的集裝箱多式聯(lián)運路徑優(yōu)化[J]. 交通運輸系統(tǒng)工程與信息，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] 佟璐，聶磊，付慧伶. 多式聯(lián)運路徑優(yōu)化模型與方法研究[J]. 物流技術(shù)，2010，29（3）：57-60.

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

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