基于時(shí)間窗和最低排空要求的集裝箱空箱調(diào)運(yùn)優(yōu)化研究

胡劍鵬，羅 霞，甘易玄

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756)

0 引言

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

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

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

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

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

1.1 模型假設(shè)

（1）可輸送空箱的列車(chē)出發(fā)時(shí)間已由運(yùn)行圖固定且各站間的空箱發(fā)送費(fèi)用已知。

（2）供應(yīng)站與需求站間的最低排空要求已知。

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

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

1.2 模型構(gòu)建

1.2.1 上層規(guī)劃

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

圖 1 時(shí)間窗示意圖Fig.1 Diagram of time window

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

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

1.2.2 下層規(guī)劃

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

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

2 算法求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

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

表1 供應(yīng)站點(diǎn)空箱供應(yīng)數(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

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

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

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

表4 空箱調(diào)運(yùn)費(fèi)用 元/箱Tab.4 Empty container transfer cost

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

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

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

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