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

周宇

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

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

周宇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

裝車開始時(shí)刻：，

2 模型建立

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

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

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

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

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

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

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

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

約束條件：

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

其中

3 求解算法

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

U292.4+5

A

1006-8686（2012）03-0036-03