含多個時間限制因素的空車調(diào)整優(yōu)化模型

周宇

（西南交通大學(xué)交通運輸與物流學(xué)院，碩士研究生，四川成都 610031）

含多個時間限制因素的空車調(diào)整優(yōu)化模型

周宇

（西南交通大學(xué)交通運輸與物流學(xué)院，碩士研究生，四川成都 610031）

針對當(dāng)前空車調(diào)整模型沒有從空車流產(chǎn)生開始便全面地進行綜合調(diào)整優(yōu)化的問題，在傳統(tǒng)空車調(diào)整模型的基礎(chǔ)上，綜合考慮了排空過程中各項時間限制因素，提出了以滿足貨主裝車時間為重點，給定了途經(jīng)中間站、技術(shù)站、裝車站的時間限制條件，以滿足轉(zhuǎn)車時間為導(dǎo)向的空車調(diào)整優(yōu)化模型。并對模型提出了現(xiàn)代啟發(fā)式算法中遺傳算法的求解思想，為解決在不同運輸方式的銜接提供思路。

空車調(diào)整；滿意裝車時間；優(yōu)化模型；遺傳算法

空車調(diào)整問題的產(chǎn)生，是由于裝車地裝車所需空車數(shù)小于本站卸車數(shù)，卸車地卸車產(chǎn)生的空車數(shù)大于裝車數(shù)，需對整個路網(wǎng)上各車站產(chǎn)生的空車流進行整體調(diào)整，擬定排空方向，制定空車編組方案。從一支空車流產(chǎn)生至這支空車流消失的整個空車調(diào)整過程，劃分為“空車流產(chǎn)生—排空—空車流消失”三大部分。針對時間限制的空車調(diào)整問題已有了大量研究成果，如李宗平、夏劍鋒以減少空車走行距離為目標(biāo)，從充分利用排空站運輸資源和滿足時間約束2個方面進行空車調(diào)配優(yōu)化；陳煜、張喜提出“到達時間窗”的概念，建立以減少空車總走行公里和廣義運輸成本最小化為目標(biāo)的空車調(diào)整優(yōu)化模型；孫焰提出礦區(qū)的最優(yōu)空車分配方案，以使全礦的總落地煤最少，建立了數(shù)學(xué)定義和數(shù)學(xué)模型。以上模型的目標(biāo)函數(shù)都是考慮了空車到達裝車站的合理時間范圍，從而降低不合理到達時間所產(chǎn)生的額外費用，并且有助于降低運輸調(diào)配的難度。但是都沒有相應(yīng)反映出空車編組站或發(fā)車站的合理發(fā)車時間，無法全面地對空車調(diào)整作出從空車流產(chǎn)生階段開始的綜合優(yōu)化。因此，本文基于裝車站的貨主滿意裝車時間范圍，聯(lián)系各鐵路局間分界站及局管內(nèi)主要編組站，推算空車合理發(fā)車時間，在分界站或中間站的通過時間限制及在技術(shù)站的合理到達時間。從空車流產(chǎn)生階段全面分析排空過程各時間限制條件，強調(diào)滿足貨主滿意裝車時間限制。求解含多個時間約束尋求總消耗最少的空車調(diào)整優(yōu)化模型，從而得到一個合理的空車調(diào)整計劃。

1 排空過程時間限制因素及表示方法

1.1 排空過程3個階段的時間限制因素空車調(diào)整是整個貨運組織的重要一環(huán)，是貨物裝卸的銜接紐帶，良好的銜接不僅體現(xiàn)在車流量的均衡分配，也體現(xiàn)在時間的精確對接。現(xiàn)在空車無法滿足需求的現(xiàn)狀，也使空車調(diào)整的時間接續(xù)性需要進一步優(yōu)化。

時效性體現(xiàn)在空車調(diào)整的各個環(huán)節(jié)中：

1）在空車流消失端需要滿足貨主裝車的所需時間，避免貨物的堆存損失，甚至貨源的流失。所以應(yīng)盡量滿足空車在無附加費用產(chǎn)生時間段內(nèi)到達。

2）排空過程中排空徑路所經(jīng)過技術(shù)站的技術(shù)作業(yè)時間，例如由A局發(fā)往B局的一組空車在C編組站改編，在t1～t2時間范圍內(nèi)可編掛在a列車上，而t2～t3時間范圍內(nèi)a列車已開出且集結(jié)過程需要1d。則會大大增加排空時間，導(dǎo)致無法在貨主滿意時間范圍內(nèi)到達。對于空車直達列車則不考慮技術(shù)作業(yè)對時間的影響。

3）對于局管內(nèi)空車產(chǎn)生端的時間影響因素，則是指的分界站或排空徑路上，通過的中間站在某時段的通過能力是否影響列車的正常。空車由發(fā)車站至裝車站的排空過程如圖1所示。

圖1 空車由發(fā)車站至裝車站的排空過程

1.2 各階段時間限制描述及時刻表示方法圖1中4個車站分別為空車排空發(fā)站、途經(jīng)中間站、途經(jīng)需要進行編組作業(yè)的技術(shù)站、空車排空到站。

2）列車到達空車改編作業(yè)技術(shù)站的到達時間為t技到，根據(jù)歷史技術(shù)站作業(yè)圖表推算在t技到時刻列車到達技術(shù)站所需的編組作業(yè)時間t編。

3）由技術(shù)站發(fā)車到達空車裝車站的時刻為t裝，根據(jù)貨主要求的貨物滿意裝車時間范圍為［t1，t2］，貨物可行裝車時間范圍為［t裝min，t裝max］，當(dāng)列車在［t1，t2］范圍內(nèi)到達則不產(chǎn)生存放、貨損等附加費，當(dāng)列車［t裝min，t1］∪［t2，t裝max］在范圍內(nèi)到達則產(chǎn)生額外費用c，當(dāng)列車在可行裝車時間范圍外到達則造成車站的空車積壓或貨源流失。假設(shè)列車在區(qū)段內(nèi)運行時間一定，則tij表示i站到j(luò)站的運行時間。所有時間點的值需滿足0≤t≤24，當(dāng)t≥24則用同余轉(zhuǎn)化。

裝車開始時刻：，

2 模型建立

2.1 空車調(diào)整模型假設(shè)條件

1）根據(jù)車流徑路理論，模型假設(shè)滿足空車流徑路是空間對稱的；

2）對于相同OD點的車流滿足車流不拆散原理，即相同OD點車流徑路有且僅有1條；

3）基于貨主的裝車需求，已知空車需求量與滿意裝車時間即無裝車站附加費；

4）假設(shè)管內(nèi)各區(qū)段均滿足車流通過能力要求，且在區(qū)段內(nèi)運行時間確定，其中分界站或中間站在且僅在時間范圍［t中min，t中max］內(nèi)滿足通過能力；

5）某支空車車流滿足開行空車直達列車條件，則安排開行由排空站至裝車站的空車直達列車。

2.2 空車調(diào)整模型建立

目標(biāo)函數(shù)為

約束條件：

2.3 模型說明目標(biāo)函數(shù)包括空車運行中所消耗的費用和因時間空廢造成的附加費用。時間附加費包括在技術(shù)站進行作業(yè)造成的空廢時間附加費，因列車未在貨主滿意裝車時間范圍內(nèi)到達裝車站產(chǎn)生的額外費用。運輸費用中c運為空車單位運輸費，xij為i到j(luò)的空車數(shù)，lij為（i，j）間的運輸距離。時間附加費中cij編為空車在運送j裝車站需裝車的貨物時單位時間的運費，c裝為空車未在貨主滿意時間內(nèi)到達產(chǎn)生的單位額外費用。即：

其中

3 求解算法

目標(biāo)函數(shù)可以拆分為尋求運輸費用最小和尋求時間附加費用最小2部分。其中運輸費用中決策變量為由i站發(fā)往j站的空車數(shù)xij；時間費用中決策變量為由i站發(fā)往就j站途經(jīng)邊界站的技術(shù)作業(yè)時間tij中給2個目標(biāo)函數(shù)分別賦予權(quán)重ω1，ω2將目標(biāo)函數(shù)轉(zhuǎn)化為但目標(biāo)優(yōu)化問題。由于本文突出對貨主滿意裝車時間的要求，使附加時間費用的重要程度相對較高，并采用遺傳算法進行求解。

3.1 編碼方法采用矩陣的編碼結(jié)構(gòu)形式，矩陣中的每一個向量表示一個空車發(fā)車站到各裝車站的決策變量信息：

其中xij取值小于發(fā)車站的最大車流量，tij中取值在中間技術(shù)站技術(shù)作業(yè)要求時間范圍內(nèi)，保證初代遺傳基因的質(zhì)量，提高運算的效率，并采用輪盤選擇法產(chǎn)生初始種群。

3.2 適應(yīng)度函數(shù)為了滿足車流量約束，分界站結(jié)束作業(yè)限制及貨主滿意裝車時間限制，需要構(gòu)造罰函數(shù)P以滿足約束條件的要求。

令適應(yīng)度函數(shù)Fintness=Z+P1+P2，以評價種群的適應(yīng)性。

3.3 交叉變異每個個體編碼由2部分組成，在交叉過程中，為了使下一代在車流量與中間站技術(shù)作業(yè)時間2部分的基因，都有更大的機會可以進行交換，所以采用2點交叉。即在相互配對的2個個體編碼串中隨機設(shè)置2個交叉點，交換2個個體在所設(shè)定的2個交叉點之間的部分染色體。

將個體染色體編碼串中的某些基因座上的基因值，用該基因座的其它等位基因來替換，從而形成一個新的個體，可以改善局部搜索能力及防止早熟現(xiàn)象。本文采用均勻變異，分別用符合限制條件以均勻分布選擇一隨機數(shù)，以某一較小概率，來替換個體編碼串中各個基因座上的原有基因值。

4 結(jié)束語

本文通過分析空車流產(chǎn)生到空車流消失的整個過程，給出了由發(fā)車站到裝車站時間限制的描述。建立了綜合各種時間約束的空車調(diào)整模型，深化了空車調(diào)整的時間限制因素，使排空站可以尋求一個合理的發(fā)車時間，減少途中消耗。同時貨主可以在滿意裝車時間內(nèi)裝車，減少在裝車站的管理費用及貨損帶來的額外耗費，并且從整體考慮時間限制的優(yōu)化，貨主可以進一步了解何時聯(lián)系托運人，可以得到最佳的服務(wù)，何時將貨物運到裝車站，可以使額外消耗最少。不僅使鐵路空車調(diào)整計劃進一步得到優(yōu)化，并且使鐵路公路聯(lián)運方面可以得到進一步的緊密聯(lián)系。

［1］李宗平，夏劍鋒.基于時間約束的鐵路空車調(diào)配模型與算法［J］.西南交通大學(xué)學(xué)報，2005（3）：361-365.

［2］陳煜，張喜.帶時間窗空車調(diào)整問題的遺傳算法研究［J］.鐵路計算機應(yīng)用，2007（2）：4-7.

［3］孫焰.煤礦鐵路最優(yōu)空車分配方案的數(shù)學(xué)模型及算法［J］.上海交通大學(xué)學(xué)報，2000（34）22-26.

U292.4+5

A

1006-8686（2012）03-0036-03