基于魯棒軟時間窗的鐵路集裝箱空箱調(diào)運優(yōu)化研究

段 剛， 陳 莉， 李引珍， 何瑞春， 朱昌鋒

(1. 蘭州交通大學 交通運輸學院， 甘肅 蘭州 730070; 2. 西北交通經(jīng)濟研究中心， 甘肅 蘭州 730070; 3. 蘭州城市學院 數(shù)學學院， 甘肅 蘭州 730070)

由于我國自然資源分布不均，生產(chǎn)力水平、區(qū)域經(jīng)濟發(fā)展和貿(mào)易不平衡，集裝箱辦理站集裝箱到發(fā)量不均衡以及點線能力不匹配等原因，導致鐵路適箱貨源和箱源分布不平均，進而導致集裝箱運輸?shù)牟黄胶?，由此產(chǎn)生大量空箱，不得不進行空箱調(diào)運。

頻繁進行空箱調(diào)運不但浪費鐵路運能，而且在運輸途中支出的各種費用也給鐵路運輸企業(yè)增加了負擔。中鐵集裝箱運輸有限責任公司向國家鐵路支付的費用共有9項，其中有5項付費涉及空箱運輸，分別是車輛租用費、車輛編解服務費、機車牽引費、車輛掛運費和線路使用費。因此，優(yōu)化空箱調(diào)運方案，對于減少成本，提高運能和運量具有重要意義。

目前全路共有上百個集裝箱辦理站，由于適箱貨源不足且去向不穩(wěn)定，重箱和空箱運輸主要采取混編形式。為加快鐵路集裝箱運輸業(yè)務的發(fā)展，鐵路總公司相繼規(guī)劃建設(shè)上海、昆明、西安、武漢、青島、鄭州、重慶、深圳、哈爾濱、大連、蘭州、沈陽、廣州、成都、烏魯木齊、天津、北京、寧波等鐵路集裝箱物流中心(以下簡稱中心)。由于中心間集裝箱運量大且貨源穩(wěn)定，故采用集裝箱班列形式組織運輸，空箱回送也以整列形式進行，極大地加快集裝箱周轉(zhuǎn)速度，提高集裝箱利用率。

鐵路空箱調(diào)運優(yōu)化問題主要解決的是空箱調(diào)運的數(shù)量、時間以及路徑問題。在現(xiàn)有運輸組織方式下，全路空箱調(diào)配分為2個層次：一是全路范圍(局間)的集裝箱排空計劃，這是硬性規(guī)定，各鐵路局必須完成；二是鐵路局內(nèi)部的空箱調(diào)配計劃。兩者根據(jù)重箱的流向和流量制定。各路局在“一卸二排三裝”的原則下，首先保證完成局間排空任務，然后再對鐵路局內(nèi)部的空箱進行調(diào)整。本文主要研究局內(nèi)空箱調(diào)配優(yōu)化方案，且假定集裝箱運輸?shù)腛D路徑已經(jīng)確定，根據(jù)重箱的流量和流向，在現(xiàn)有運輸能力的基礎(chǔ)上，制定科學合理的空箱調(diào)運方案，優(yōu)化空箱調(diào)運的數(shù)量和時間。

國外學者對海運空箱調(diào)配問題研究較多，對鐵路空箱調(diào)運具有一定的借鑒意義。Le-Griffin[1]研究美國西海岸近海航運空箱調(diào)運問題，為建立區(qū)域港口系統(tǒng)提供適當?shù)闹贫瓤蚣?，以協(xié)調(diào)國家和私人投資近海航運。研究結(jié)果顯示近海航運是可行的策略，在美國西海岸實施區(qū)域港口體系發(fā)展戰(zhàn)略可有效減輕由大城市主要通道頻繁的商業(yè)活動引起的交通擁擠；Song[2]考慮動態(tài)與隨機環(huán)境下空箱配送問題，將其劃分為空箱裝載與卸載2部分，制定靈活的配送策略，即空箱配送的目的地和數(shù)量事先不確定，而在途中根據(jù)港口最新的即時信息確定。當貿(mào)易不均衡時明顯優(yōu)于傳統(tǒng)優(yōu)化方法，可以降低22%成本。靈敏度分析表明其優(yōu)勢受貿(mào)易不平衡方式、船隊規(guī)模和邊界值因素影響很大，但對需求分布類型和船舶容量并不敏感；Lam[3]同樣采用動態(tài)隨機規(guī)劃模型研究擁有2個港口和2條航線的海運系統(tǒng)空箱調(diào)運問題，通過時間差模擬方法獲得近似最優(yōu)解，與精確解進行比較，最后將結(jié)論推廣至多港口多航線；Moon[4]研究空箱最優(yōu)分配以減少港口間集裝箱的不平衡性，將運輸費用、處理費用和存貯費用之和極小化作為目標。同時構(gòu)造混合整數(shù)規(guī)劃模型，對采購及租賃集裝箱的數(shù)量進行研究，采用混合遺傳算法求解；Moon[5]對可折疊集裝箱與一般集裝箱空箱在調(diào)運過程中產(chǎn)生的費用進行比較，該費用包括折疊費用、存貯費用、集裝箱進貨成本與調(diào)運費用，通過靈敏度分析揭示集裝箱進貨成本與調(diào)運費用對可折疊集裝箱調(diào)運的影響；Chou[6]建立混合模糊決策模型，將空箱配送問題分為2個階段：第1階段應用模糊缺貨存貯模型，將最優(yōu)缺貨量作為港口的最優(yōu)租箱量，將最優(yōu)定貨量作為港口的最優(yōu)空箱需求量。第2階段采用網(wǎng)絡模型，基于以上2個最優(yōu)結(jié)果，優(yōu)化多個港口之間的空箱調(diào)運問題。通過橫跨太平洋航線，包括高雄港、香港港、基隆港、神戶港、橫濱港和洛杉磯港的真實案例，證明該模型的有效性。最后指出香港港的最優(yōu)租箱率為10.08%，低于實際20%～25%的租箱率；Li[7]將港口的空箱調(diào)運問題看成非標準的存貯問題，當進口空箱時需求量為正，出口空箱時需求量為負，以期望空箱調(diào)運成本、期望租箱成本和期望搬運成本之和最小為目標，分別對短期和長期規(guī)劃求出最佳策略。

國內(nèi)學者對鐵路空箱調(diào)運問題進行有益的研究。朱德輝[8]對罐式集裝箱重箱流和空箱流調(diào)配進行綜合優(yōu)化，以罐箱運輸費用最小為目標，建立鐵路罐式集裝箱空箱調(diào)配優(yōu)化多商品網(wǎng)絡流模型，并構(gòu)造嵌入模擬退火操作的遺傳算法進行求解；閆海峰[9]根據(jù)集裝箱班列開行特點，以混合箱流的輸送時間、距離和費用3者的綜合最優(yōu)為目標，建立結(jié)點站間基于徑路選擇的空箱調(diào)配混合0-1規(guī)劃模型，將模型模擬為二級耦合反饋系統(tǒng)設(shè)計算法；張得志[10]通過對鐵路集裝箱運輸市場的調(diào)研，建立基于顧客偏好和時間窗的模糊機會約束規(guī)劃模型，采用遺傳算法求解；文獻[11,12]根據(jù)空箱需求的時間要求，建立基于軟時間窗的鐵路集裝箱空箱調(diào)運模型，但沒有考慮走行時間的不確定性。

若知道該參數(shù)的確切概率分布，則可使用隨機優(yōu)化方法進行建模[13]，但求解比較困難。當缺乏統(tǒng)計數(shù)據(jù)或統(tǒng)計數(shù)據(jù)不準確時，難以確定他的概率分布，這時可應用魯棒優(yōu)化的方法[14]。當走行時間變化范圍和均值已知時，魯棒優(yōu)化方法假設(shè)這些不確定的走行時間均按照最壞的情況發(fā)生，即要么是最長走行時間、要么是最短走行時間，主要取決于需求站時間窗要求。比如，某需求站的時間窗為[10:00,14:00]，某供應站到該需求站的走行時間在3～8 h，若出發(fā)時間為10:00，則按最短走行時間計算，到達需求站的時間為13:00，剛好位于時間窗內(nèi)，而若按最長走行時間計算則將晚到4 h。因此考慮最壞情況，我們?nèi)?站的走行時間為最長走行時間。

這些假設(shè)雖然使求出的魯棒解適用于所有可能發(fā)生的情況，但過于保守，因為現(xiàn)實中很少出現(xiàn)所有走行時間都是不確定的情況，即便如此，也不一定都是最壞情況。Bertsimas[15]將該條件放松，認為出現(xiàn)在約束條件中的不確定參數(shù)最多有P個(不一定為整數(shù))將發(fā)生變化，其余參數(shù)為確定的，取其變化的均值。而且從理論上給出證明，即使取均值的參數(shù)也發(fā)生變化時，魯棒解仍以很大的概率保證其可行性。該方法不但具有很強的靈活性，而且最吸引人的是魯棒優(yōu)化問題與對應的確定型問題保持相同的計算復雜性。

采用該思想，將全部走行時間分為確定和不確定2類，并只對不確定的時間采用魯棒優(yōu)化方法，這樣可以改善傳統(tǒng)魯棒優(yōu)化過于保守的缺陷。在Bertsimas[15]建立的模型中，魯棒部分在約束條件中，而考慮的不確定走行時間則位于目標函數(shù)的時間窗里。因此，將其稱為魯棒軟時間窗(Robust Soft Time Window，RSTW)模型。在此基礎(chǔ)上，建立基于魯棒軟時間窗的空箱調(diào)運(Empty Container Allocation with Robust Soft Time Window，ECARSTW)優(yōu)化模型，為解決不確定走行時間問題提供通用模型和一般框架。

1 時間窗的魯棒優(yōu)化

1.1 基于軟時間窗的集裝箱空箱調(diào)運

首先構(gòu)造基于軟時間窗的集裝箱空箱調(diào)運(Empty Container Allocation with Soft Time Window, ECASTW)模型。以空箱調(diào)運成本、提前到達產(chǎn)生的集裝箱庫存成本和延誤到達產(chǎn)生的機會損失成本之和最小為目標函數(shù)

vjmax{ti+tij-lj,0})}

( 1 )

式中：[ej,lj]為j站空箱需求的時間窗，j∈V，V為空箱需求站集合；ti為i站空箱的出發(fā)時間，i∈W，W為空箱供應站集合；tij為i站到j站的走行時間，(i,j)∈E，E=W×V有向邊集合；cij為i站到j站的單位空箱運輸成本；uj為空箱提前到達j站產(chǎn)生的積壓庫存費用；vj為空箱延誤到達j站產(chǎn)生的損失費用；xij為i站到j站調(diào)運的空箱數(shù)。

約束條件

空箱供應約束

( 2 )

式中：ai為i站的空箱供應量。

空箱需求約束

( 3 )

式中：bj為j站的空箱需求量。

OD路徑上的集裝箱通過能力約束

xij≤dij(i,j)∈E

( 4 )

式中：dij為運輸路徑(i,j)上換算為集裝箱的通過能力。

變量聲明

xij≥0 且為整數(shù) (i,j)∈E

( 5 )

1.2 RSTW模型及性質(zhì)

1.2.1RSTW模型

令|E|=r，則在全部r個走行時間中，最多有p(0≤p≤r)個是不確定的。令

由于ECASTW模型不僅考慮提前到達和延誤到達，還需考慮他們的成本，所以也需考慮庫存成本和機會損失成本。令

RSTW模型為

( 6 )

式中：yij為空箱調(diào)運數(shù)量。

1.2.2 模型性質(zhì)

( 7 )

且Δyi0,j0>0。

令S*為滿足下式的集合

( 8 )

即S*是式( 6 )達到最大的集合。

(i0,j0)與S*的關(guān)系存在2種可能：(i0,j0)∈S*或者(i0,j0)∈E/S*。

第1種可能(i0,j0)∈S*

且S*也必定滿足

( 9 )

否則，假設(shè)存在集合S**，滿足

如果(i0,j0)∈S**，那么一定有

模型的準確程度與擬顆粒的大小密切相關(guān)，擬顆粒越小，顆粒越多，計算結(jié)果越準確，但工作量也就越大，計算能力是該模型發(fā)展的一個重要限制。氣體擬顆粒在流動過程中不斷破裂、混合，是瞬時性的，擬合時人為確定，局限于理想狀況，目前發(fā)展還不成熟。

第2種可能為 (i0,j0)∈E/S*，結(jié)論同樣成立。

綜上，有式( 7 )成立。

證畢。

定理1表明在式( 6 )中，yij越大，則

越大，反之則越小。

2 ECARSTW模型及等價變換

2.1 ECARSTW模型及性質(zhì)

2.1.1 模型

我們將RSTW加到式( 1 )中，替換目標中庫存成本或機會損失成本，得到ECARSTW模型

(10)

yij≥xij(i,j)∈E

(11)

2.1.2 性質(zhì)

下面我們給出ECARSTW模型最優(yōu)解的性質(zhì)。

所以

2.2 RSTW的等價變換

令

(12)

下面給出魯棒軟時間窗R(yij,p)的等價線性規(guī)劃形式。

(13)

(14)

0≤zij≤1 (i,j)∈E

(15)

定理4定理3中的線性規(guī)劃即式(13)～式(15)的對偶問題為

(16)

(17)

q≥0

(18)

wij≥0 (i,j)∈E

(19)

式中：q、wij為式(14)、式(15)對應的對偶變量。

證明：由于

(20)

所以，下述線性規(guī)劃問題

(21)

s.t. 式(14)和式(15)

的對偶為

(22)

s.t. 式(17)～式(19)

2.3 ECARSTW模型的等價整數(shù)線性規(guī)劃形式

根據(jù)上述定理，可將ECARSTW模型轉(zhuǎn)換為等價的整數(shù)線性規(guī)劃形式。

定理5ECARSTW模型等價于

(23)

s.t. 式(2) ～式(5)，式(17)～式(19)

證明：由定理4知，ECARSTW模型等價于

(24)

s.t. 式( 2 )～式( 5 )，式(17)～式(19)

≤min

另一方面，由于

所以

由此

由此，我們將ECARSTW模型轉(zhuǎn)換為一般的整數(shù)線性規(guī)劃模型，轉(zhuǎn)換后的模型與ECARSTW模型相比，僅多了1個變量q，且沒有增加新的約束條件(非負限制除外)，但將ECARSTW模型目標中的非線性RSTW部分轉(zhuǎn)換為線性函數(shù)，因此更易于求解。

3 算例

我們通過實例驗證所提模型的正確性。某鐵路局有20個空箱供應站，12個空箱需求站。供應站的空箱供應量和出發(fā)時間見表1，需求站的空箱需求量、時間窗、庫存成本和機會損失見表2，供應站與需求站間走行時間范圍見表3，空箱調(diào)運成本見表4，空箱運輸OD路徑間通過能力見表5。取p= 10，利用LINGO 15.0軟件求解，得到最優(yōu)解為x13=27,x19=2,x24=25,x27=20,x35=26,x42=10,x4,10=1,x53=4,x58=11,x6,11=32,x71=14,x77=66,x86=15,x8,10=50,x91=6,x10,10=23,x10,11=5,x11,9=16,x12,12=30,x13,1=12,x14,3=25,x15,7=17,x15,8=25,x16,11=8,x17,5=22,x17,12=5,x18,10=18,x19,12=35,x20,7=22,w42=21,w4,10=5,w6,11=44,w86=56,w8,10=446,w13,1=32,w14,3=146,w15,7=30,w17,5=51,w20,7=84,q=4。

表1 空箱供應站信息

表2 空箱需求站信息

在最優(yōu)調(diào)運方案中，共有3條OD路徑的空箱調(diào)運量達到通過能力上限，分別為供應站4至需求站2(10個空箱)，供應站8至需求站10(50個空箱)，供應站12至需求站12(30個空箱)。如果提高這些路徑的集裝箱通過能力，將進一步降低空箱調(diào)運成本。

最優(yōu)解中共有29個xij大于0，即發(fā)生29次空箱調(diào)運。由于p= 10，所以只有10個wij取值為正，說明與這10個wij對應的走行時間是不確定的，他們與剩下的19個確定的走行時間使得RSTW達到最大。在不確定的走行時間中，有8個空箱調(diào)運到達時間早于時間窗，分別對應w42、w4,10、w6,11、w8,10、w13,1、w14,3、w15,7、w20,7；2個到達時間晚于時間窗，分別對應w86和w17,5。在確定的走行時間中，共有3個到達時間早于時間窗，分別對應w19、w58、w15,8只有1個到達時間晚于時間窗，對應w10,11。

在全部240個走行時間中，若均按不確定走行時間計算，共有57個到達時間早于時間窗，82個到達時間晚于時間窗；若都按確定的走行時間計算，有48個到達時間早于時間窗，61個到達時間晚于時間窗。顯然，增加不確定走行時間的數(shù)量p，將增加成本。下面對p值進行靈敏度分析。

圖1給出總成本與p的關(guān)系，顯然，總成本是p的增函數(shù)。但當p≥ 12時，總成本不再增加，達到最大值145 301元，所以p的上界是12。該取值與問題的規(guī)模以及不確定走行時間的數(shù)量相比非常小。圖2～圖5分別給出目標中4個成本與p的關(guān)系，可以看出，f1和f3是p的增函數(shù)，f2是p的減函數(shù)。但f4與p沒有這樣的單調(diào)關(guān)系，所以我們對q與p的關(guān)系進行分析，見圖6，顯然，q是p的減函數(shù)。而且當成本達到最大或最小時，p的取值不完全相同。當p= 10時，f1和f2分別達到最大和最??；當p= 13時，f3達到最大，q達到最小值0，f4重新為0。

表3 供應站與需求站間走行時間范圍

表4 空箱調(diào)運成本 元·箱-1

表5 OD路徑的集裝箱通過能力 箱

當p分別取值12和13時，雖然總成本相等，且二者的xij值都相同，但wij的取值卻不同，主要原因為q值不同。當p= 12時，q= 3，而p= 13時，q= 0，為使目標達到極小，式(17)必然等式成立，因此導致wij的不同。且當p= 12或p=13時，二者的不確定走行時間的個數(shù)都小于p，分別為11個和12個。因此，在最優(yōu)解中，不確定走行時間的個數(shù)可以小于p值，而且當p越接近上界，才越有可能發(fā)生這種情況。盡管不確定走行時間的數(shù)量可能很多，但對成本產(chǎn)生影響的卻是有限的幾個，或者說只有很少的不確定走行時間將影響目標。所以，在確定p的數(shù)值時，應從較小的開始，一旦找到其上界，就可確定出那些起作用的不確定走行時間，并盡可能保證這些空箱調(diào)運按時完成，以減少成本。

當p= 0時，所有走行時間均為確定的，此時成本最小，為144 323元。其中，f1= 139 593，f2=4 730，f3= 0，f4= 0，q= 450。從圖2和圖3可以看出，當0≤p≤3時，f1和f2的值均不變。說明變量xij的值相同，而wij的值不同。其原因還是由于q的取值不同。

4 結(jié)論

集裝箱運輸是現(xiàn)代化貨物運輸發(fā)展方向。在北美洲，鐵路集裝箱運輸收入早已超過煤炭運輸收入而高居第1位。我國鐵路集裝箱運輸發(fā)展卻相對緩慢，目前運輸量僅占鐵路貨物發(fā)送量的3%左右，這既受到鐵路運能緊張等客觀因素的制約，也受到運輸作業(yè)組織等管理因素的影響。空箱的科學合理調(diào)運是提高集裝箱周轉(zhuǎn)率、增加運量和順利完成運輸作業(yè)組織的重要保證。因此空箱調(diào)運優(yōu)化具有重要的理論和實際意義。在傳統(tǒng)基于軟時間窗的集裝箱空箱調(diào)運模型基礎(chǔ)上，考慮鐵路運輸過程中走行時間不確定對空箱調(diào)運的影響，首先構(gòu)造基于魯棒軟時間窗的空箱調(diào)運通用模型，得到解的一些性質(zhì)，然后建立解決這類問題的一般框架。模型具有建立簡單，方便計算的特點，既避免隨機約束規(guī)劃的復雜性，又克服傳統(tǒng)魯棒優(yōu)化過于保守的不足性。算例表明不確定走行時間的個數(shù)存在1個較小的上界。該優(yōu)化方法對中鐵集裝箱運輸有限公司制定日?？障湔{(diào)運計劃，具有一定的借鑒意義。

參考文獻：

[1] LE GRIFFIN H D, GRIFFIN M T. Managing Empty Container Flows through Short Sea Shipping and Regional Port Systems[J]. International Journal of Shipping and Transport Logistics, 2010, 2(1): 59-75.

[2] SONG D P, DONG J X. Effectiveness of An Empty Container Repositioning Policy with Flexible Destination Ports[J]. Transport Policy, 2011, 18(1): 92-101.

[3] LAM S W, LEE L H, TANG L C. An Approximate Dynamic Programming Approach for the Empty Container Allocation Problem[J]. Transportation Research Part C, 2007, 15(4): 265-277.

[4] MOON I K, NGOC A D, HUR Y S. Positioning Empty Containers among Multiple Ports with Leasing and Purchasing Considerations[J]. OR Spectrum, 2010, 32(3): 765-786.

[5] MOON I K, NGOC A D, KONINGSC R. Foldable and Standard Containers in Empty Container Repositioning[J]. Transportation Research Part E, 2013, 49(1): 107-124.

[6] CHOU C C, GOU R H, TSAI C L, et al. Application of A Mixed Fuzzy Decision Making and Optimization Programming Model to the Empty Container Allocation[J]. Applied Soft Computing, 2010, 10(4): 1071-1079.

[7] LI J A, LIU K, LEUNG S, et al. Empty Container Management in A Port with Long-run Average Criterion[J]. Mathematical and Computer Modelling, 2004, 40(1-2): 85-100.

[8] 朱德輝, 何世偉. 鐵路罐式集裝箱空箱調(diào)配優(yōu)化模型及遺傳模擬退火算法[J]. 中國鐵道科學, 2008, 29(6): 104-110.

ZHU De-hui, HE Shi-wei. Optimization Model of Railway Empty Tank Container Allocation and Genetic Simulated Annealing Algorithm[J]. China Railway Science, 2008, 29(6): 104-110.

[9] 閆海峰, 董守清. 鐵路集裝箱結(jié)點站間空箱調(diào)配的優(yōu)化[J]. 中國鐵道科學, 2009, 30(1): 131-135.

YAN Hai-feng, DONG Shou-qing.Optimization of the Empty Containers Distribution Among Railway Network Container Freight Stations[J]. China Railway Science, 2009, 30(1): 131-135.

[10] 張得志, 謝如鶴, 黃孝章. 鐵路集裝箱空箱調(diào)度模型及求解算法[J]. 中國鐵道科學, 2003, 24(3): 125-129.

ZHANG De-zhi, XIE Ru-he, HUANG Xiao-zhang. Dispatch Model and Solution Algorithm of Railway Empty Container[J]. China Railway Science, 2003, 24(3): 125-129.

[11] 段剛, 陳志忠, 陳莉, 等. 基于技術(shù)站改編作業(yè)的集裝箱空箱調(diào)運優(yōu)化模型[J]. 鐵道運輸與經(jīng)濟, 2011, 33(10): 70-73.

DUAN Gang, CHEN Zhi-zhong, CHEN Li, et al. Empty Container Allocation Optimization Model Based on Technique Station Reclassifying Operation[J]. Railway Transport and Economy, 2011, 33(10): 70-73.

[12] 段剛, 陳莉, 陳志忠, 等. 基于技術(shù)站改編作業(yè)的集裝箱空箱動態(tài)調(diào)運優(yōu)化模型與算法[J]. 交通運輸系統(tǒng)工程與信息, 2012, 12(2): 111-118.

DUAN Gang, CHEN Li, CHEN Zhi-zhong, et al. Dynamic Empty Container Allocation Model and Algorithm Based on Technique Station Transfer Operation[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2): 111-118.

[13] 段剛, 盧躍榮, 陳莉, 等. 不確定環(huán)境下鐵路集裝箱空箱調(diào)運優(yōu)化研究[J]. 蘭州交通大學學報, 2012, 31(6): 97-102.

DUAN Gang, LU Yue-rong, CHEN Li, et al. Optimization on Railway Empty Container Allocation under Uncertain Environment[J]. Journal of Lanzhou Jiaotong University, 2012, 31(6): 97-102.

[14] BEN-TAI A, BERTSIMAS D, BROWN D. A Soft Robust Model for Optimization under Ambiguity[J]. Operations Research, 2010, 58 4(1): 1220-1234.

[15] BERTSIMAS D, SIM M. The Price of Robustness[J].Operations Research, 2004, 52 (1):35-53.