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

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

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

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

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

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

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

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

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

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

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

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

1.1 基于軟時間窗的集裝箱空箱調運

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

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站產生的積壓庫存費用；vj為空箱延誤到達j站產生的損失費用；xij為i站到j站調運的空箱數。

約束條件

空箱供應約束

( 2 )

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

空箱需求約束

( 3 )

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

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

xij≤dij(i,j)∈E

( 4 )

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

變量聲明

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

( 5 )

1.2 RSTW模型及性質

1.2.1RSTW模型

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

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

RSTW模型為

( 6 )

式中：yij為空箱調運數量。

1.2.2 模型性質

( 7 )

且Δyi0,j0>0。

令S*為滿足下式的集合

( 8 )

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

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

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

且S*也必定滿足

( 9 )

否則，假設存在集合S**，滿足

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

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

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

綜上，有式( 7 )成立。

證畢。

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

越大，反之則越小。

2 ECARSTW模型及等價變換

2.1 ECARSTW模型及性質

2.1.1 模型

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

(10)

yij≥xij(i,j)∈E

(11)

2.1.2 性質

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

所以

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模型的等價整數線性規(guī)劃形式

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

定理5ECARSTW模型等價于

(23)

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

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

(24)

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

≤min

另一方面，由于

所以

由此

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

3 算例

我們通過實例驗證所提模型的正確性。某鐵路局有20個空箱供應站，12個空箱需求站。供應站的空箱供應量和出發(fā)時間見表1，需求站的空箱需求量、時間窗、庫存成本和機會損失見表2，供應站與需求站間走行時間范圍見表3，空箱調運成本見表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)調運方案中，共有3條OD路徑的空箱調運量達到通過能力上限，分別為供應站4至需求站2(10個空箱)，供應站8至需求站10(50個空箱)，供應站12至需求站12(30個空箱)。如果提高這些路徑的集裝箱通過能力，將進一步降低空箱調運成本。

最優(yōu)解中共有29個xij大于0，即發(fā)生29次空箱調運。由于p= 10，所以只有10個wij取值為正，說明與這10個wij對應的走行時間是不確定的，他們與剩下的19個確定的走行時間使得RSTW達到最大。在不確定的走行時間中，有8個空箱調運到達時間早于時間窗，分別對應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個到達時間晚于時間窗。顯然，增加不確定走行時間的數量p，將增加成本。下面對p值進行靈敏度分析。

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

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

表4 空箱調運成本 元·箱-1

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

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

當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 結論

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

參考文獻：

[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] 朱德輝, 何世偉. 鐵路罐式集裝箱空箱調配優(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] 閆海峰, 董守清. 鐵路集裝箱結點站間空箱調配的優(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] 張得志, 謝如鶴, 黃孝章. 鐵路集裝箱空箱調度模型及求解算法[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] 段剛, 陳志忠, 陳莉, 等. 基于技術站改編作業(yè)的集裝箱空箱調運優(yōu)化模型[J]. 鐵道運輸與經濟, 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] 段剛, 陳莉, 陳志忠, 等. 基于技術站改編作業(yè)的集裝箱空箱動態(tài)調運優(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)境下鐵路集裝箱空箱調運優(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.