基于時(shí)間窗的鐵路空箱調(diào)運(yùn)問題分析

鄭 燕

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

1 機(jī)會(huì)成本與重箱的經(jīng)濟(jì)效益

機(jī)會(huì)成本是一個(gè)多階段的優(yōu)化問題，本文中為研究方便，當(dāng)考慮機(jī)會(huì)成本最小時(shí)，只考慮若早于時(shí)間窗情況下給予的線性處罰；若晚于時(shí)間窗到達(dá)的話，將資源用于下一周期使用，此過程中空箱將產(chǎn)生堆存費(fèi)，另外，沒有按要求時(shí)間到達(dá)的空箱，因沒有投入生產(chǎn)，也會(huì)損失部分運(yùn)輸收入，這部分收入也將作為機(jī)會(huì)成本的處罰。因此，要使本規(guī)定的機(jī)會(huì)成本最小。

當(dāng)空箱轉(zhuǎn)載貨物以后變成重箱，重箱不斷累加，形成重箱流（重箱流指某條徑路上由重箱形成的流）。在考慮集裝箱空箱調(diào)運(yùn)優(yōu)化時(shí)，應(yīng)盡量考慮如何使空箱變成重箱后產(chǎn)生的總價(jià)值最大。例如：A 地調(diào)運(yùn)到B地的調(diào)運(yùn)成本為2 000，產(chǎn)生的經(jīng)濟(jì)效益是4 000，而A 地調(diào)運(yùn)到C 地的調(diào)運(yùn)成本為3 000，產(chǎn)生的經(jīng)濟(jì)效益為6 000，那么在決策時(shí)當(dāng)然要選擇從A 地調(diào)運(yùn)到C地。因?yàn)?，其空箱變成重箱后產(chǎn)生的總價(jià)值，后者顯然要比前者大。

在眾多的研究中，絕大多數(shù)研究均注重調(diào)運(yùn)成本，甚至把調(diào)運(yùn)成本最小化作為唯一的優(yōu)化目標(biāo)，當(dāng)然，這也是有一定道理的，但是從空箱的產(chǎn)生到空箱的調(diào)運(yùn)，再到空箱的使用，這個(gè)宏觀體系來考慮，其實(shí)這幾個(gè)環(huán)節(jié)是相互影響，而不是獨(dú)立的，因此，在研究過程中也應(yīng)當(dāng)考慮空箱的使用。

2 基于時(shí)間窗的鐵路空箱調(diào)運(yùn)問題分析

空箱調(diào)運(yùn)問題是一類重要的運(yùn)籌學(xué)和組合優(yōu)化問題，合理科學(xué)的調(diào)運(yùn)空箱方案，不但可以提高集裝箱的配送效率，同時(shí)又能夠產(chǎn)生巨大的經(jīng)濟(jì)和社會(huì)效益，帶來眾多正面效應(yīng)。用戶使用集裝箱來運(yùn)輸自己的貨物時(shí)，必然會(huì)對(duì)何時(shí)能夠得到空箱有一定的要求，所以，在服務(wù)時(shí)間上空箱到達(dá)一般分為3種情況：沒有時(shí)間窗要求（A）、有硬時(shí)間窗要求（B），有軟時(shí)間窗要求（C）。

硬時(shí)間窗要求是指客戶接受服務(wù)的條件是對(duì)客戶的服務(wù)必須在給定的時(shí)間段內(nèi)進(jìn)行，沒有商量的余地，否則，該客戶拒絕接受服務(wù)。

上述機(jī)會(huì)損失可以表示為：

1）在規(guī)定時(shí)間內(nèi)到達(dá)，而此時(shí)正好需要空箱，于是空箱正好被及時(shí)的投入生產(chǎn)，這是恰到好處的情況。

2）在規(guī)定的時(shí)間段內(nèi)提前到達(dá)，空箱將會(huì)被暫時(shí)的存放，由于這個(gè)原因而產(chǎn)生一些空箱堆存費(fèi)，這是等待的情況。

3）在規(guī)定時(shí)間段延后達(dá)到，即前一個(gè)時(shí)段已經(jīng)結(jié)束，于是即使空箱到達(dá)了也不能夠在此周期將空箱投入生產(chǎn)，此時(shí)的選擇便是：可以選擇不調(diào)運(yùn)或者把調(diào)運(yùn)的空箱投入下一周期。

在研究過程中所做的目標(biāo)就是如何使這種機(jī)會(huì)損失達(dá)到最小，本論文對(duì)于那些晚于時(shí)間窗到達(dá)的空箱放到下一周期使用，但把這部分空箱的堆存費(fèi)和假設(shè)按時(shí)到達(dá)產(chǎn)生的收益作為懲罰成本。

2.1 模型假設(shè)

假設(shè)系統(tǒng)中，有m個(gè)貨運(yùn)車站，由于運(yùn)空箱需求和供應(yīng)的不平衡性，必然導(dǎo)致部分車站空箱多余、部分車站空箱不足，為了更好的利用空箱，需要對(duì)這m個(gè)車站的空箱進(jìn)行調(diào)運(yùn)。由于各車站對(duì)集裝箱空箱的到、發(fā)時(shí)間有一定的要求，需在帶有時(shí)間約束情況下合理調(diào)運(yùn)空箱。空箱調(diào)運(yùn)周期設(shè)為T天，為簡化計(jì)算，各車站之間視為只有一種類型的集裝箱，而且車站之間延誤的單位集裝箱損失的經(jīng)濟(jì)效益相同。

參數(shù)設(shè)定如下：

1）第i個(gè)車站中，可供應(yīng)的集裝箱空箱數(shù)為Gi（i＝1，2，3，…，m）；

2）第j個(gè)車站中，需求的集裝箱空箱數(shù)Xj（j＝1，2，3，…，m）；

3）i車站到j(luò)車站：集裝箱空箱的單位的運(yùn)輸成本Cij；

4）i車站可以從j車站調(diào)配到的集裝箱空箱的數(shù)量xij；

5）i車站到j(luò)車站的實(shí)際運(yùn)輸時(shí)間（與箱型無關(guān)）tij；

6）i車站出發(fā)到j(luò)車站的空箱的到達(dá)、發(fā)送時(shí)間分別為

7）沒按規(guī)定時(shí)間到達(dá)，造成的單位空箱單位時(shí)間集裝箱場地占有費(fèi)為F；

8）遲于最晚時(shí)間到達(dá)的單位空箱，在準(zhǔn)時(shí)到達(dá)時(shí)投入生產(chǎn)所產(chǎn)生的經(jīng)濟(jì)效益W；

9）i車站到j(luò)車站的之間，存在的集裝箱空箱運(yùn)輸能力限制為Lij；

10）在i車站所能接受的集裝箱空箱最早時(shí)間、最晚時(shí)間分別為ei，li；

在存在時(shí)間窗的狀況下，可以假設(shè)調(diào)運(yùn)任務(wù)i需在時(shí)間段［ai，bi］內(nèi)完成，其一般關(guān)系如下

式中：τi為到達(dá)i節(jié)點(diǎn)的時(shí)刻，ti為在i節(jié)點(diǎn)等待的時(shí)間，si為到達(dá)j節(jié)點(diǎn)的時(shí)間。

式（3）表示在硬時(shí)間窗內(nèi)必須滿足在要求時(shí)間內(nèi)完成空箱調(diào)運(yùn)，否則為不可行解；那么在軟時(shí)間窗時(shí)不能按照要求時(shí)間完成的任務(wù)將給予一定懲罰。

客戶基本上都會(huì)有一個(gè)允許的提供的空箱最早和最晚到達(dá)時(shí)間的容忍區(qū)間，空箱提前到達(dá)，對(duì)于之后的貨物運(yùn)輸工作實(shí)現(xiàn)了條件，但同時(shí)也會(huì)產(chǎn)生一些問題：比如說會(huì)產(chǎn)生一定的場地積壓費(fèi)用，而且也會(huì)占用集裝箱堆場的空間。而如果空箱到達(dá)太晚，必定會(huì)損失一定的客源，由于一些客戶對(duì)時(shí)間的要求非常嚴(yán)格，這便產(chǎn)生了一些無形的但是又有實(shí)際負(fù)面效果的機(jī)會(huì)成本。

2.2 基于時(shí)間窗的鐵路集裝箱空箱調(diào)運(yùn)問題分析

2.2.1 不考慮時(shí)間窗的約束

模型此時(shí)即轉(zhuǎn)化為經(jīng)典的“貨郎擔(dān)”問題，只需使用動(dòng)態(tài)規(guī)劃的方法，便可求出全局的最優(yōu)解。如果把目標(biāo)定為成本最小，模型為

約束條件為

式（6）表示多余空箱節(jié)點(diǎn)發(fā)送到缺箱節(jié)點(diǎn)的空箱總和，小于或者等于多余空箱節(jié)點(diǎn)可提供的空箱數(shù)目；式（7）表示要盡量滿足缺箱節(jié)點(diǎn)上反映出的缺箱需求；式（8）表示要滿足運(yùn)輸能力的約束，不能忽略實(shí)際情況；式（9）表示發(fā)送節(jié)點(diǎn)的發(fā)送時(shí)間加上發(fā)到節(jié)點(diǎn)之間的運(yùn)行時(shí)間等于到節(jié)點(diǎn)的到達(dá)時(shí)間。

此種情況下約束條件中的都應(yīng)滿足非負(fù)數(shù)約束。

2.2.2 軟時(shí)間窗

假如某些任務(wù)不能在規(guī)定的時(shí)間窗內(nèi)完成，這種狀況下，必定會(huì)增加部分費(fèi)用，第一種假設(shè)條件，假定沒有時(shí)間窗，這便回到了（1）狀況，用（1）的方法求的無時(shí)間窗下的最優(yōu)成本，若此時(shí)有時(shí)間要求的話，則可能會(huì)違反時(shí)間窗的范圍，這便會(huì)出現(xiàn)相應(yīng)的堆存費(fèi)與延誤費(fèi)，在一定意義上便增加成本值及其余相關(guān)費(fèi)用。因此，問題轉(zhuǎn)化為堆存費(fèi)和假設(shè)沒有遲于最晚時(shí)間的空箱產(chǎn)生的經(jīng)濟(jì)效益的減少與運(yùn)輸成本增加之間尋求最優(yōu)值。

在軟時(shí)間窗下除了一部分滿足時(shí)間要求，即在規(guī)定時(shí)間內(nèi)提供服務(wù)，還有一部分不能夠在要求時(shí)間內(nèi)到達(dá)，在本文中將其產(chǎn)生的堆存費(fèi)和假設(shè)沒有遲于最晚時(shí)間的空箱產(chǎn)生的經(jīng)濟(jì)效益定義為機(jī)會(huì)成本，表示這些空箱未能夠得到充分利用，則問題可轉(zhuǎn)化為在優(yōu)化時(shí)使機(jī)會(huì)成本最小。對(duì)于那些遲于最晚時(shí)間到達(dá)的空箱可為不確定條件下的空箱需求或者直接轉(zhuǎn)為下一周期使用，本論文不考慮不確定性條件下的空箱需求。

首先設(shè)定選擇軟時(shí)間窗情況下空箱調(diào)運(yùn)的處罰函數(shù)

f（xij）為從i車站到j(luò)車站調(diào)運(yùn)的空箱xij獲得的懲罰成本。

模型為

機(jī)會(huì)成本最小模型約束條件與無時(shí)間窗約束條件一樣。

在空箱配流時(shí)一般情況下都要考慮調(diào)運(yùn)成本最小，式（11）如果加上這些集裝箱空箱走行費(fèi)用則為在軟時(shí)間窗下空箱調(diào)運(yùn)費(fèi)用最小化模型

2.2.3 只有硬時(shí)間窗

在規(guī)定內(nèi)的時(shí)間內(nèi)完成每項(xiàng)調(diào)運(yùn)任務(wù)，而且是硬性要求的。即必須滿足式（3），若超出這個(gè)范圍，便會(huì)得到不可行解。

這種情況下有一種辦法，便是可以將單位時(shí)間堆存費(fèi)，以及假設(shè)沒有遲于最晚時(shí)間的空箱產(chǎn)生的經(jīng)濟(jì)效益設(shè)置為無窮大（F＝W＝P（P→∞）），即必須滿足時(shí)間窗，毫無例外，在這樣約束的情況下，進(jìn)行求解，否則不可行。

此時(shí)模型目標(biāo)應(yīng)為調(diào)運(yùn)費(fèi)用最小化，模型為

約束條件與無時(shí)間窗約束條件一樣。

2.2.4 如果同時(shí)含有軟時(shí)間窗和硬時(shí)間窗

假定先不考慮硬時(shí)間窗，求最優(yōu)路徑的方法是按（11）求得，之后，在考慮硬時(shí)間窗的點(diǎn)，逐步檢查看是否滿足，滿足則可行，即為最優(yōu)解，否則只能硬時(shí)間窗單獨(dú)提出來，對(duì)剩余的點(diǎn)按照（13）進(jìn)行判定，逐步優(yōu)化，哪些點(diǎn)是機(jī)會(huì)成本最小的，這便得到了，在這種狀況下的最優(yōu)成本及路徑。

3 結(jié)束語

鐵路集裝箱空箱調(diào)運(yùn)一直困擾著我國鐵路集裝箱事業(yè)的發(fā)展，做好空箱調(diào)運(yùn)工作，能夠最大的挖掘其存在的產(chǎn)業(yè)效益潛力，對(duì)我國鐵路集裝箱事業(yè)產(chǎn)生巨大的推動(dòng)作用。本文結(jié)合自身專業(yè)知識(shí)，并參考大量文獻(xiàn)，對(duì)基于時(shí)間窗的鐵路集裝箱空箱調(diào)運(yùn)問題提出了一些解決方法。但是本文在一些方面仍需努力，如對(duì)客戶價(jià)值進(jìn)行劃分，由于空箱調(diào)運(yùn)是一個(gè)系統(tǒng)的工作，實(shí)際有不同主體及其利益，從客戶來講，不同客戶具有不同的價(jià)值，將客戶進(jìn)行系統(tǒng)的劃分，區(qū)分其價(jià)值大小，然后將客戶價(jià)值與調(diào)運(yùn)成本結(jié)合起來，有助于提高整個(gè)鐵路企業(yè)的經(jīng)濟(jì)效益。

［1］趙丹.隨機(jī)環(huán)境下海運(yùn)集裝箱空箱調(diào)配問題研究［D］.上海：上海海事大學(xué)，2005.

［2］閆海峰，彭其淵，譚云江.結(jié)點(diǎn)站間集裝箱班列開行方案的優(yōu)化模型及算法［J］.中國鐵道科學(xué)，2008，29（1）：101－189.

［3］周紅梅，方芳.航運(yùn)集裝箱空箱調(diào)運(yùn)優(yōu)化模型的研究［J］.武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2003（6）：354－357.

［4］汪傳旭，劉大熔，賀斌.隨機(jī)條件下空箱調(diào)配模型研究［J］.交通運(yùn)輸工程學(xué)報(bào)，2001（9）：119－122.

［5］羅孝彬.楊容浩.鄧虎成.帶時(shí)間窗的貨物配送方案模型及軟件實(shí)現(xiàn)［J］.成都信息工程學(xué)院學(xué)報(bào)，2005（3）：175－179.

［6］楊銀奇.集裝箱空箱調(diào)運(yùn)問題研究［D］.大連：大連海事大學(xué)，2007.

［7］彭其淵，閆海峰，周勇.集裝箱班列編組計(jì)劃相關(guān)因素分析［J］.中國鐵道科學(xué)，2003，24（5）：120－123.