胡劍鵬，羅 霞，甘易玄

（西南交通大學 交通運輸與物流學院，四川 成都 611756)

0 引言

集裝箱運輸是實現(xiàn)“門到門”運輸?shù)囊环N高效率和高效益的運輸方式，但鐵路車站普遍存在集裝箱發(fā)到不均的情況，為了避免空箱對流與閑置，需要采取科學合理的方法確定集裝箱空箱調(diào)運方案。

目前，國內(nèi)外學者對集裝箱空箱調(diào)運的研究多集中于模型構(gòu)建和算法的實現(xiàn)。在模型構(gòu)建方面，主要研究主要體現(xiàn)在目標函數(shù)上，目標函數(shù)大致分為單目標和多目標2 種類型，單目標類主要包括單位時間內(nèi)調(diào)運費用最小[1]、鐵路運輸利潤最大[2]、乘客滿意度最高[3]、空箱利用率最大[4]、供應鏈總服務成本最小[5]；多目標類則由上述各項組合而成。在模型求解算法方面，主要分為針對線性規(guī)劃模型的單純形法和運輸算法[1-2]，以及針對非線性規(guī)劃模型的遺傳算法等啟發(fā)式算法[3-4]。此外，為了深入探究空箱調(diào)運的特征，部分研究將運輸網(wǎng)絡分為確定性運輸網(wǎng)絡[2]和不確定性運輸網(wǎng)絡[6-7]2種，在空箱調(diào)運費用方面將其分為不考慮時間窗因素[1-2]和考慮時間窗的因素[7-8]2 類。蔡德倫等[9]還就空箱調(diào)運時的信息收集方法進行研究。

既有研究缺乏對空箱調(diào)運時優(yōu)先滿足站間最低排空要求目標的考慮，國內(nèi)外集裝箱空箱調(diào)運研究在計算效益時多關注于空箱調(diào)運的路徑消耗費用，較少考慮空箱需求站時間窗造成的庫存費用和機會損失費用。因此，應以最大化滿足站間最低排空要求和最大化空箱調(diào)運收益為目標構(gòu)建了雙層規(guī)劃模型，同時考慮供需關系約束和不同站點空箱輸送能力約束。

1 基于時間窗和最低排空要求的集裝箱空箱調(diào)運優(yōu)化模型構(gòu)建

站間最低排空要求是指為了規(guī)范鐵路運輸秩序，從而要求某些空箱供應站按照規(guī)定的排空數(shù)量與排空周期向某些需求站供應空箱的一種計劃。在站間最低排空要求的基礎上，考慮軟時間窗導致的庫存費用和機會損失費用，結(jié)合路網(wǎng)中的空箱供需關系進行空箱調(diào)運計劃的制定，其中各站間各型箱的空箱調(diào)運數(shù)量為自變量，站間最低排空箱的滿足數(shù)目與空箱輸送效益為因變量，構(gòu)建基于時間窗和最低排空要求的集裝箱空箱調(diào)運優(yōu)化模型。

1.1 模型假設

（1）可輸送空箱的列車出發(fā)時間已由運行圖固定且各站間的空箱發(fā)送費用已知。

（2）供應站與需求站間的最低排空要求已知。

（3）需求站存在1 個或多個對于集裝箱需求旺盛即密集裝車和發(fā)車的時間窗，在該有效時間窗內(nèi)到達的貨物不會因無法發(fā)出而產(chǎn)生庫存費用和機會損失費用。

（4）需求站存在1 個或多個無效時間窗，在無效時間窗內(nèi)到達的貨物相對于鄰近的后一有效時間窗會產(chǎn)生庫存費用，相對于鄰近的前一個有效時間窗會產(chǎn)生機會損失費用。j站1 天中的時間窗示意圖如圖1 所示，其中s表示第幾個無效時間窗，s∈ 1，2，…，n；為j站第s個無效時間窗的起始時刻；為j站第s個無效時間窗的終止時刻。

1.2 模型構(gòu)建

1.2.1 上層規(guī)劃

（1）上層規(guī)劃以站間最低排空箱的數(shù)目作為目標，計算公式為

圖 1 時間窗示意圖Fig.1 Diagram of time window

式中：i為空箱供應站點；j為空箱需求站點；w為集裝箱類型；為i站發(fā)往j站的w型集裝箱中用于滿足i站至j站間w型集裝箱最低排空要求的部分；為i站發(fā)往j站的w型集裝箱總數(shù)；為i站發(fā)往j站的w型集裝箱的最低排空數(shù)量。

公式 ⑴ 表示站間最低排空箱發(fā)送總數(shù)；公式⑵ 表示由i站發(fā)往j站的w型空箱優(yōu)先用于滿足站間最低排空要求，即在>時供給j站的空箱中用于滿足最低排空要求的w型集裝箱數(shù)量為，在≤時供給j站的空箱中用于滿足最低排空要求的w型集裝箱數(shù)量為。

1.2.2 下層規(guī)劃

（1）目標函數(shù)。下層規(guī)劃以最大化空箱調(diào)運方案的總收益為目標，計算公式為

公式 ⑶ 表示空箱調(diào)運的效益，其中第1 項表示空箱到達需求站后由需求站裝車發(fā)出所產(chǎn)生收益；第2 項表示空箱調(diào)運時產(chǎn)生的路徑消耗費用；第3 項表示空箱在無效時間窗內(nèi)到達時產(chǎn)生的庫存費用與機會損失費用。公式 ⑷ 表示i站w型空箱的合計發(fā)送量不得超過i站既有的可供發(fā)送的w型空箱數(shù)目。公式 ⑸ 表示各供應站發(fā)往需求站j站的w型空箱數(shù)目總和應當?shù)扔趈站對w型空箱的需求量。公式 ⑹ 表示由i站發(fā)往j站的集裝箱換算數(shù)目不得超過i站與j站間線路空箱輸送能力。公式 ⑺表示站間空箱輸送數(shù)量應大于等于0。公式 ⑻ 表示當位于無效時間窗和之間時= 1，此時要考慮庫存費用和時間費用，當不位于無效時間窗和之間時= 0，即不考慮庫存費用和時間費用。需要注意的是，當無效時間窗跨天時，雖然位于無效時間窗內(nèi)，但此時= 0，為了避免此種情況，在實際處理時若無效時間窗跨天如[23 : 00—2 : 00]，則因?qū)⑵淇醋? 個時間窗即[23 : 00—0 : 00]和[0 : 00—2 : 00]，對應分鐘制的[1 380—1 440]和[0—120]。公式 ⑼ 中取余數(shù)原因在于，如果Tij+tij> 1 440，則應當位于后一天的有效或無效時間窗，但研究中統(tǒng)一時間為1d，因而通過取余數(shù)將1 440 后到達的時刻轉(zhuǎn)換為同一天內(nèi)的時刻，使其與時間窗單位統(tǒng)一。

2 算法求解

該雙層規(guī)劃模型為非線性規(guī)劃模型，無法利用Cplex 等求解器直接求解。因此，研究中將空箱調(diào)運過程分為以滿足最大排空要求為目的進行的調(diào)運和以效益最大為目的進行的調(diào)運，并將后者轉(zhuǎn)化為了容量限制下的最小費用最大流問題。記S，E為虛擬節(jié)點表起始點和終點，構(gòu)建多品種網(wǎng)絡圖如圖2 所示，括號內(nèi)表示路段阻抗和路段最大容量，網(wǎng)絡中虛擬起點至供應點，需求點至虛擬終點間阻抗均為0，為w型空箱在站點i→j的路段阻抗取值見公式 ⑽。虛擬起點與供應點間路段最大容量值為供應點的空箱供應數(shù)量，供應點與需求點間路段的最大容量值為i站和j站間空箱換算通過能力Fij，需求站與虛擬終點間路段的最大容量值為需求站j需要的w型空箱的總數(shù)。

為了令其與雙層規(guī)劃模型的目標一致，供應站與需求站間網(wǎng)絡阻抗可表示為

圖2 多品種網(wǎng)絡圖Fig.2 Multi-commodity traffic network

式中：C是一個常數(shù)；為i→j站間w型空箱的輸送利潤。

不同站點間空箱輸送效益越大路段阻抗就越小，結(jié)合最低排空要求扣除相應的供應量、需求量和站間容量后，可以將模型的求解轉(zhuǎn)化為下式。

式中：為虛擬起點S與供應點i間w型空箱的輸送數(shù)量；為需求點j與虛擬終點E間的w型空箱輸送數(shù)量。

結(jié)合上層規(guī)劃最優(yōu)對網(wǎng)絡進行調(diào)整后的模型為線性規(guī)劃模型，可以用Cplex 進行求解，但該方法求解過程不直觀，基于圖論的配流方法更能準確的反映配流過程，因而針對下層規(guī)劃模型，采用網(wǎng)絡配流方法進行求解。

（1）以上層規(guī)劃最優(yōu)為目標的網(wǎng)絡的調(diào)整方法。為了實現(xiàn)上層規(guī)劃最優(yōu)，對配流前的網(wǎng)絡按下述步驟進行調(diào)整。

步驟1：空箱供應數(shù)量調(diào)整。從各供應站i的供應量中扣除用于滿足站間最低排空要求的各型集裝箱數(shù)量，計算公式為

步驟2：空箱需求數(shù)量調(diào)整。從需求站j中扣除由最低排空計劃所滿足的空箱需求數(shù)量，計算公式為

步驟3：站間最大空箱輸送數(shù)量調(diào)整。從各站間線路通過能力Fij中扣除站間最低排空計劃所占用的部分，計算公式為

上述步驟保證了站間最低排空計劃的落實，實現(xiàn)了上層規(guī)劃目標的最優(yōu)。

（2）結(jié)合網(wǎng)絡配流的下層規(guī)劃求解方法。對調(diào)整后的新網(wǎng)絡N按照下述步驟進行配流(以2 個箱型的空箱調(diào)運網(wǎng)絡為例)。

步驟1：令初始k=1，利用Dijkstra 算法找出網(wǎng)絡N中不同箱型在S，E間的最短路(Lw1，Lw2)，選取min (Lw1，Lw2)對應箱型的最短路上進行流量分配，假設被選擇路徑為Lw1，每條路徑上第2 個節(jié)點為供應站i第3 個節(jié)點為需求點j，則分配流量計算公式為

步驟2：更新被選中路徑上的供應站空箱供應數(shù)量，需求站空箱需求數(shù)量和剩余可利用通過能力，更新方法如公式 ⒆ 所示，該更新方法可以保證站間分配流量滿足供需約束和通過能力約束。

步驟3：更新被選擇路徑阻抗值，包括公式 ⒇ 中的3 種情形，通過此法可以避免在供應量耗盡、需求量全部滿足或已達站間最大通過能力的路徑上繼續(xù)配流，從而避免了不可行空箱調(diào)運方案的產(chǎn)生。

步驟4：由步驟3 得到阻抗更新后的網(wǎng)絡N1，在新網(wǎng)絡的基礎上重復步驟1-3，直至或即供應量耗盡或需求量全部滿足，求得一組可行方案plan和plan，可行方案形式如公式(21)，表示第k次配流時w型空箱的配流方案。轉(zhuǎn)至步驟5。

步驟5：利用BPR 阻抗函數(shù)公式將得到的可行方案plan和plan代入公式(22)更新阻抗，由網(wǎng)絡N得到新的網(wǎng)絡N2，需要說明的是生成網(wǎng)絡N1的目的是求出一個可行方案，生成網(wǎng)絡N2的目的是進行迭代尋優(yōu)。

步驟6：按照公式(23)更新方案，，分別為第k- 1 次和第k次配流完成后迭代求和得到的w型空箱的配流方案，初始時?。由的數(shù)值，判斷是否滿足收斂條件，滿足則輸出最優(yōu)方案，否則k=k+ 1，并將N2作為步驟1的初始網(wǎng)絡轉(zhuǎn)至步驟1。

3 實例分析

研究選取了12 個空箱供應站，10 個空箱需求站以及20 TEU 和40 TEU2 種箱型進行模型及算法的驗證。供應站點空箱供應數(shù)量如表1 所示，需求站空箱需求數(shù)量及發(fā)送效益如表2 所示，站間最低排空數(shù)量要求箱如表3 所示，空箱調(diào)運費用如表4 所示。

集裝箱單位時間庫存費用20 TEU 型箱取a，40 TEU 型箱取2a；機會損失費用20 TEU 型箱取2a，40 TEU 型箱取4a，取a 值為10 元/h-1[4]。20 TEU 型集裝箱換算系數(shù)取f1= 1，40 TEU 型集裝箱換算系數(shù)取f2= 2。配流方法求得的空箱調(diào)運方案如表5 所示。

表1 供應站點空箱供應數(shù)量 箱Tab.1 Empty container supply quantity in supply stations

表2 需求站空箱需求數(shù)量及發(fā)送效益Tab.2 Empty container demand quantity in demand stations

表3 站間最低排空數(shù)量要求 箱Tab.3 Minimum emptying container among stations

該最小費用最大流模型為線性規(guī)劃模型，因而可以利用Cplex 加以求解，由Cplex 求得方案的效益值為425 412 元，由配流方法求得的空箱運輸效益為415 832 元，配流方法求得效益為Cplex求得效益的97.75%，并且此時226 個站間最低排空箱數(shù)目均得到滿足，說明該方法具備較強的可行性。

求得方案中存在站間最低排空要求的站點間的空箱輸送存在2 種情況，一種是恰好滿足(如站點1 →3，7 →5)，此種情況產(chǎn)生是由于與其他路徑相比該輸送路徑的運輸費用較高，是以效益損失為代價來滿足最低排空要求；一種為超量滿足(如站點1 →7)，此時該路徑的運輸費用低，選擇該路徑不僅可以滿足站間最低排空要求也能提高空箱調(diào)運收益。因此，可以認為該模型較好地兼顧了空箱調(diào)運的運輸秩序與運輸效益。

不同a值下的空箱輸送效益如圖3 表示，可以看出隨著a值的增大，空箱輸送效益不斷減小，并且排空優(yōu)先條件下求得的效益與僅考慮效益條件下求得的效益之間的差值不斷縮小，即為滿足最低排空要求所付出的效益損失代價隨時間窗對應庫存費用和機會損失費用的增大而減少。

表4 空箱調(diào)運費用 元/箱Tab.4 Empty container transfer cost

表5 配流方法求得的空箱調(diào)運方案 箱Tab.5 Container transfer plan by flow distribution method

圖3 不同a 值下的空箱輸送效益Fig.3 Benefits of empty container transfer at different values of a

4 研究結(jié)論

為了兼顧空箱調(diào)運效益和鐵路運輸秩序，研究中考慮了時間窗費用和站間最低排空需求并構(gòu)建了雙層規(guī)劃模型以解決空箱調(diào)運優(yōu)化問題。針對建立模型非線性的性質(zhì)，將調(diào)運過程劃分為了以滿足最大排空要求為目的進行的調(diào)運和以效益最大為目的進行的調(diào)運，將后者轉(zhuǎn)化為了容量限制條件下的最小費用最大流問題并設計了相應算法，主要研究結(jié)論如下。

（1）利用設計算法對該空箱調(diào)運問題進行求解時，算法求得效益值為由Cplex 求得最佳效益值的97.75%，說明配流方法在尋找空箱調(diào)運問題的全局最優(yōu)解時具備較佳的應用效果。

（2）求得方案中站間最低排空要求存在恰好滿足和超量滿足2 種情形，恰好滿足時是以效益損失為代價來滿足最低排空需求，超量滿足時則說明該供應方式不僅有利于滿足站間最低排空要求還有助于提高輸送效益。說明所得方案是在保證空箱調(diào)運秩序的基礎上實現(xiàn)的效益最大化。

（3）需求站無效時間窗內(nèi)單位時間庫存費用和機會損失費用的變化對空箱調(diào)運的效益有顯著影響，為滿足最低排空要求所付出的效益損失代價隨時間窗內(nèi)庫存費用和機會損失費用的增大而減小。