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

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

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

中圖分類號(hào)：U116.2 文獻(xiàn)標(biāo)識(shí)碼：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ùn)輸業(yè)的飛速發(fā)展，多式聯(lián)運(yùn)打破運(yùn)輸方式間的界限，在現(xiàn)代經(jīng)濟(jì)的發(fā)展中起到尤為重要的作用，已經(jīng)成為降低物流成本的有效措施，成為提高市場競爭力的有效手段。國民經(jīng)濟(jì)和社會(huì)發(fā)展“十三五”規(guī)劃的發(fā)布，表明國家對(duì)物流、對(duì)多式聯(lián)運(yùn)的重視程度也已經(jīng)有了顯著提高。

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

1 問題描述

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

2 模型假設(shè)和符號(hào)說明

2.1 模型假設(shè)

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

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

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

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

2.2 符號(hào)說明

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

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

4 模型求解

4.1 模型簡化

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

4.2 網(wǎng)絡(luò)變形

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

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

4.3 變化后的模型符號(hào)說明

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

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

4.4 變化后的模型

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

5 算例分析

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

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

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

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

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

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

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

6 結(jié) 論

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

參考文獻(xiàn)：

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

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

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