動(dòng)車組運(yùn)用計(jì)劃的優(yōu)化模型

動(dòng)車組運(yùn)用計(jì)劃的優(yōu)化模型

重組車輛使用計(jì)劃對(duì)于提高鐵路運(yùn)輸生產(chǎn)效率具有重要意義。國外的動(dòng)態(tài)車輛使用計(jì)劃通常使用信息技術(shù)和計(jì)算機(jī)技術(shù)來建立綜合的運(yùn)輸信息管理。該算法的高效計(jì)算可以自動(dòng)編制動(dòng)態(tài)車輛使用計(jì)劃，并以動(dòng)態(tài)交通圖的形式發(fā)布。目前，中國的動(dòng)態(tài)車輛使用計(jì)劃仍然是手動(dòng)編制的，這需要很多經(jīng)驗(yàn)。特別是如果列車票的具體修改頻率較大，則有效車輛的使用計(jì)劃和編制人數(shù)將增加，這將使以后的研究更加困難。因此，有必要研究適合我國高速發(fā)展的動(dòng)態(tài)車輛使用模式和算法。許多中國專家和科學(xué)家在科學(xué)研究中使用了優(yōu)化車輛使用的算法。例如，文獻(xiàn)介紹了自動(dòng)準(zhǔn)備算法的含義、類型、條件、評(píng)估標(biāo)準(zhǔn)和節(jié)假日應(yīng)用計(jì)劃。這些現(xiàn)有的研究成果對(duì)后續(xù)研究非常重要。在對(duì)車輛使用計(jì)劃進(jìn)行分析的基礎(chǔ)上，作者提出了一種適應(yīng)我國客運(yùn)線路的動(dòng)態(tài)車輛使用計(jì)劃。1動(dòng)車組運(yùn)用計(jì)劃編制圖1是某列車運(yùn)行圖及其動(dòng)車組運(yùn)用計(jì)劃的例子.圖1中,將某些運(yùn)行線按照接續(xù)標(biāo)準(zhǔn)形成1列動(dòng)車組1天運(yùn)用內(nèi)容(包括檢修)稱為動(dòng)車組交路段.將幾個(gè)可用交路段按照接續(xù)規(guī)則滿足定檢和定修要求連接形成1個(gè)動(dòng)車組1個(gè)一級(jí)修周期內(nèi)運(yùn)用內(nèi)容稱為動(dòng)車組運(yùn)用交路.動(dòng)車組運(yùn)用計(jì)劃按照使用模式可以分為固定區(qū)段和不固定區(qū)段使用兩種運(yùn)用模式.研究表明,不固定區(qū)段使用方式是動(dòng)車組利用率較高的運(yùn)用模式,本文中的研究均基于這一方式.動(dòng)車組的檢修體制主要分為日常檢修和定期檢修兩大類.按照修程規(guī)定每級(jí)維修均需在對(duì)應(yīng)作業(yè)場所完成.各級(jí)修程分別對(duì)應(yīng)檢修周期運(yùn)行距離.當(dāng)動(dòng)車組運(yùn)行距離達(dá)到修程范圍,該車組就必須進(jìn)行與之相對(duì)應(yīng)等級(jí)的檢修.因此,在編制動(dòng)車組運(yùn)用計(jì)劃時(shí)需要將動(dòng)車組檢修作業(yè)考慮在內(nèi).在編制動(dòng)車組運(yùn)用計(jì)劃時(shí),考慮到列車運(yùn)行圖結(jié)構(gòu)以及動(dòng)車組的檢修體制,動(dòng)車組運(yùn)用計(jì)劃必須符合以下運(yùn)用規(guī)則:(1)任意一列車車次必須有且僅有一列動(dòng)車組擔(dān)當(dāng)運(yùn)輸任務(wù).(2)動(dòng)車組的日常運(yùn)轉(zhuǎn)必須與列車運(yùn)行圖一致.(3)動(dòng)車組達(dá)到修程規(guī)定,必須到相應(yīng)的檢修場所檢修,并且必須保證一定的檢修時(shí)間.(4)動(dòng)車組在進(jìn)行列車接續(xù)的時(shí)候需要進(jìn)行一定的整備作業(yè),動(dòng)車組所擔(dān)當(dāng)列車運(yùn)行線之間的接續(xù)必須滿足整備時(shí)間標(biāo)準(zhǔn).動(dòng)車組本身比較昂貴,檢修費(fèi)用較高.因此,一般采用下面幾個(gè)指標(biāo)評(píng)價(jià)動(dòng)車組運(yùn)用計(jì)劃:使用的動(dòng)車組數(shù)少,定期檢修次數(shù)和日常檢修次數(shù)少,各動(dòng)車組交路利用率比較均衡.2動(dòng)車組運(yùn)用計(jì)劃的簡化由于旅客列車運(yùn)行圖通常情況下都是成對(duì)運(yùn)行圖,為簡化,本文中不討論不成對(duì)運(yùn)行圖.由于多車種動(dòng)車組運(yùn)用計(jì)劃的編制可以簡化為多個(gè)單車種動(dòng)車組運(yùn)用計(jì)劃,故本文中只討論單車種的情況.2.1列車連通的計(jì)算公式假設(shè)客運(yùn)專線設(shè)有動(dòng)車段D和若干運(yùn)用所,將動(dòng)車組設(shè)為dm(m=1,2,…,M),待擔(dān)當(dāng)?shù)牧熊囘\(yùn)行線表示為ln(n=1,2,…,N),第j條運(yùn)行線始發(fā)時(shí)刻為tdj,終到時(shí)刻為taj,運(yùn)行距離為sj,運(yùn)行時(shí)間為Tj.運(yùn)行線li與lj在車站接續(xù)時(shí)間為Tij,日檢需留時(shí)間Tc,一級(jí)修需留時(shí)間Tr.日檢定檢里程標(biāo)準(zhǔn)sc,一級(jí)修定檢里程標(biāo)準(zhǔn)sr.在列車運(yùn)行圖中,由于列車運(yùn)行線是有向線段,如果將圖中的車站線看作沿著時(shí)間坐標(biāo)軸方向的有向線,那么整個(gè)運(yùn)行圖就是有向連通圖.在該連通圖中,將兩列車車次之間的接續(xù)表示為E={(l1,l2),(l1,l3),…},E的權(quán)值以列車之間接續(xù)時(shí)間度量,f是E的映射函數(shù),f(eij)=t<li,lj>(i≠j?eij∈E).f(eij)=t<li,lj>(i≠j?eij∈E).2.2動(dòng)車組主要運(yùn)行任務(wù)的確定在編制動(dòng)車組運(yùn)用計(jì)劃時(shí),主要是考慮列車車次如何接續(xù)的問題,即如何使動(dòng)車組列車接續(xù)時(shí)間減少,在維修周期內(nèi)提高運(yùn)用效率,從而降低設(shè)備成本;同時(shí),還要使動(dòng)車組運(yùn)用比較均衡,從而有利于日常的動(dòng)車組調(diào)度調(diào)整.設(shè)動(dòng)車組交路k運(yùn)用率ηk=∑Τj∑Τj+∑f(eij)?ηk=∑Tj∑Tj+∑f(eij)?各動(dòng)車平均利用率ˉη=Κ∑k=1ηkΚ?ηˉ=∑k=1KηkK?上式中,K為動(dòng)車交路總數(shù).要滿足各交路均衡,要求各交路利用率即各隨機(jī)動(dòng)車?yán)寐示讲瞀易钚?設(shè)完成目標(biāo)列車運(yùn)行圖擔(dān)當(dāng)列車任務(wù)需要的動(dòng)車組數(shù)量為M,結(jié)合前面動(dòng)車組運(yùn)用規(guī)則中對(duì)動(dòng)車組運(yùn)用評(píng)價(jià)指標(biāo)的分析,目標(biāo)函數(shù)和約束條件可以歸結(jié)如下:目標(biāo)函數(shù):minM,(1)min√1ΚΚ∑k=1(ηk-ˉη)2,(2)s.t.設(shè)變量xij={1,動(dòng)車組擔(dān)當(dāng)列車(li,lj)任務(wù)；0,動(dòng)車組不擔(dān)當(dāng)列車(li,lj)任務(wù)；n∑i=1xij=1?n∑j=1xij=1;f(eij)≥Tback,Tback為折返作業(yè)時(shí)間標(biāo)準(zhǔn);f(eij)≥Tr,當(dāng)|∑sj-sr|≥αsr時(shí)(α為檢修周期浮動(dòng)系數(shù)).前兩個(gè)約束條件意味著每條運(yùn)行線都有1組動(dòng)車組擔(dān)當(dāng),并且每組動(dòng)車組僅擔(dān)當(dāng)1次;后兩個(gè)約束條件保證滿足檢修的時(shí)間標(biāo)準(zhǔn)和地點(diǎn)標(biāo)準(zhǔn).3該算法3.1交路段求解算法由于動(dòng)車組交路的復(fù)雜性,直接求解交路比較困難.構(gòu)造有向連通圖模型過程可以發(fā)現(xiàn),在動(dòng)車組交路圖中存在很多組始發(fā)站和終到站都相同的交路段,而且每個(gè)交路由幾個(gè)相互接續(xù)的交路段組成.這樣,就可以將動(dòng)車組交路求解的問題簡化為交路段求解和如何用交路段生成交路的問題,對(duì)基于運(yùn)行線組合的交路求解的目標(biāo)函數(shù)分步處理.因此,求解動(dòng)車組交路可以分兩步進(jìn)行:首先按照接續(xù)要求生成所有交路段,主要是通過搜索使產(chǎn)生的交路段數(shù)量最少,即目標(biāo)函數(shù)(1),本文中采用多起點(diǎn)搜索的局部優(yōu)化算法實(shí)現(xiàn);第2步再將交路段組合形成完整的動(dòng)車組交路,在組合時(shí),主要考慮動(dòng)車組的檢修條件和各交路動(dòng)車組運(yùn)用效率均衡的目標(biāo),即目標(biāo)函數(shù)(2).3.2交路段串聯(lián)比選在求解交路段時(shí),需要每個(gè)交路段內(nèi)列車接續(xù)時(shí)間盡量短,從而提高動(dòng)車組運(yùn)用率,減少動(dòng)車組需用數(shù)量.本文中采用緊湊指派策略.具體操作中引入運(yùn)行線連接優(yōu)先度,優(yōu)先度越大則越優(yōu)先連接,優(yōu)先度為零就無法連接.在生成交路段的過程中,一般是逐個(gè)生成交路段或者基于各個(gè)車站線上接續(xù)后聯(lián)結(jié)成交路段,這里用多個(gè)交路段逐步生成的方法求解,動(dòng)車組的數(shù)量在交路段生成過程中依據(jù)接續(xù)要求逐步增加,并通過迭代算法將列車接續(xù)逐步優(yōu)化.在旅客列車運(yùn)行圖中,通常存在密集到發(fā)的“高峰時(shí)段”,而“高峰時(shí)段”的動(dòng)車組需用數(shù)量通常是最高的,所以,算法的搜索范圍從列車運(yùn)行圖“高峰時(shí)段”開始,計(jì)為[tb,tnd),tb是高峰開始時(shí)間,tnd為次日的該時(shí)刻.本算法采用基于多起點(diǎn)搜索的緊湊指派迭代算法,既保證了運(yùn)行線之間的最短接續(xù),也解決了求解時(shí)由于動(dòng)車組數(shù)量不確定而帶來的某些運(yùn)行線沒有動(dòng)車組擔(dān)當(dāng)?shù)膯栴},同時(shí)也給出了該方案下動(dòng)車組使用數(shù)量和接續(xù)方案.在指派中,通過對(duì)大量的動(dòng)車運(yùn)用計(jì)劃發(fā)現(xiàn),緊湊指派能較好地滿足各動(dòng)車組交路段運(yùn)用均衡的問題.采用此算法缺陷在于實(shí)際運(yùn)用時(shí),由于均是緊湊接續(xù),若有列車晚點(diǎn),后續(xù)列車恢復(fù)圖定運(yùn)行困難,不利于列車運(yùn)行調(diào)整.算法步驟:設(shè)動(dòng)車組交路段集合為C={Cm},m=1,2,…,M.(1)M←1,動(dòng)車組交路段(2)找到運(yùn)行圖的tb時(shí)刻起任一站的終到列車運(yùn)行線,記為lb,該列車的到達(dá)時(shí)刻為Tab←tab;(3)搜索所有Ν∑i=1Ν∑j=1xij=0運(yùn)行線,對(duì)于第j條運(yùn)行線,如果tdj∈(tb,tab)將該運(yùn)行線加入集合W;將集合Cm中的元素也加入集合W中;(4)對(duì)集合W={w1,w2,…,wY}(Y為W中運(yùn)行線數(shù)量)中的元素依據(jù)聯(lián)結(jié)優(yōu)先度原則進(jìn)行匹配處理,產(chǎn)生W中的接續(xù)方案;(7)搜索所有l(wèi)y1y2?Cm,記為集合U,連接運(yùn)行線lb與集合U中的運(yùn)行線,其優(yōu)先度pby2的計(jì)算:如果Y∑y2=1pby2=0,轉(zhuǎn)(8);否則取優(yōu)先度最大的運(yùn)行線lmax,lb←lmax,Tab←tab轉(zhuǎn)(3);(8)如果Tab<Tnd或((Tab>Tnd且Tab<Tnd+1440),Tab←Tnd,轉(zhuǎn)(3);(9)結(jié)束.聯(lián)結(jié)優(yōu)先度原則——在動(dòng)車組運(yùn)行線進(jìn)行接續(xù)時(shí),既需要滿足一定的聯(lián)結(jié)約束條件,同時(shí)又要盡可能使運(yùn)行線的接續(xù)時(shí)間最小,故引入聯(lián)結(jié)優(yōu)先度的規(guī)則定義如下:(1)如果某一運(yùn)行線li不能和運(yùn)行線lj接續(xù),記pij=0;(2)一般情況下,有pij={1tdj-tai,若tdj＞tai且(tdj-tai)≥Τback,0,若|tdj-tai|＜Τback,11440+tdj-tai?若tdj＜tai且(1440+tdj-tai)≥Τback.3.3交路段互換算法在求出Cm后,還需要依據(jù)動(dòng)車組的檢修條件在交路段的基礎(chǔ)上求出所有的動(dòng)車組交路集合V,同時(shí)需要考慮各交路動(dòng)車組運(yùn)用效率比較均衡.采用基于交路段互換的隨機(jī)搜索算法求解.在動(dòng)車組交路段集合中,選擇某一含有滿足檢修停時(shí)的交路段作為起始交路段,從該交路段開始,搜索可以與其接續(xù)的任意一個(gè)交路段作為交路的下一動(dòng)車段,然后依次搜索交路的下一個(gè)交路段,直到該交路的運(yùn)行距離(或者運(yùn)行周期)進(jìn)入動(dòng)車組修程波動(dòng)范圍(盡可能取波動(dòng)范圍最大值)并且交路的最后一個(gè)交路段的終到站與起始交路的始發(fā)站相同時(shí)結(jié)束,得到一個(gè)交路的初始解.按照上述原則繼續(xù)搜索,從而得到所有交路的初始解集合V.對(duì)于V中的交路,分別計(jì)算交路的運(yùn)用率并按運(yùn)用率排列V={v1,v2,…,vK},對(duì)于V中的交路段按運(yùn)用率差值成對(duì)匹配成組<v1,vK>,<v2,vK-1>,…,然后將每組中的在兩個(gè)交路中的具有相同始發(fā)終到站的交路段按一定原則進(jìn)行互換,以減少同組中兩交路的運(yùn)用率的差值,使各交路動(dòng)車組的運(yùn)用率均衡;交路段互換完畢后又重新計(jì)算各交路的運(yùn)用率,并分組互換,如此迭代,直到滿足一定的均衡條件或終止條件為止.具體算法如下:建立集合Cs,記錄所有含有滿足檢修作業(yè)停時(shí)的交路段集合.搜索所有的動(dòng)車組交路段,判斷交路段中的最大列車接續(xù)時(shí)間Tcon,如果該車站包含(或緊靠)動(dòng)車段,并且Tcon≥Tr+2Tio(Tio為出入動(dòng)車段時(shí)間),將該交路段加入到Cs中.將所有的動(dòng)車組交路段按照始發(fā)站和終到站進(jìn)行分類,分別建立集合如C01,C02,…,C11,C12,…,CSS(下標(biāo)的第1位表示始發(fā)站編號(hào),第2位表示終到站編號(hào),S表示始發(fā)終到站數(shù)量).(1)K←1,交路(2)從集合Cs中任選一個(gè)元素不屬于Vk(k=1,2,…,K)作為新交路Vk的起始交路段,表示為Csq(q為Csq在Cs中的序號(hào),q=1,2,…,Q),并記sq為交路段Csq列車運(yùn)行里程;(3)在集合CSS中按照聯(lián)結(jié)優(yōu)先度原則查找與Csq接續(xù)的并且不屬于Vk的交路段Ctmp,如果不存在,轉(zhuǎn)(6);(4)檢查Q∑q=1sq,如果Q∑q=1sq∈sr,將Ctmp寫入Vk;否則,轉(zhuǎn)(5);(5)檢查Vk中的最后進(jìn)入的交路段,如果該交路段的終到站與Csq的起點(diǎn)站相同,K=K+1,轉(zhuǎn)(2);否則,Vk←ue07e,轉(zhuǎn)(2)重做;(6)計(jì)算V中各交路利用率η,并且按照η排列;V={V1,V2,…,VK}(η1≤η2≤…≤ηK);將V中交路分組<V1,VK>,<V2,VK-1>,…;(7)對(duì)于每一交路分組<Vj,VK-j>,計(jì)算Vj和VK-j中各交路段的利用率,對(duì)于Vj中的每一元素Cj,搜索VK-j中具有相同始發(fā)終到站的交路段CK-j,如果ηj<ηK-j,并且Cj與CK-j互換后分別滿足所在交路與前后交路段的接續(xù)條件,則將Vj中的元素Cj與VK-j中的元素CK-j互換.計(jì)算所有交路組后,檢查各交路的運(yùn)用率,如果各交路段運(yùn)用率的均方差δ>δ0(δ0為根據(jù)問題規(guī)模事先人工給定的均方差限界),且迭代次數(shù)<人工給定值,轉(zhuǎn)(6);否則轉(zhuǎn)(8);(8)結(jié)束.3.4動(dòng)車組運(yùn)用率對(duì)比用本文中的模型及算法,用VC++語言編程,采用武廣客運(yùn)專線方案的運(yùn)行圖數(shù)據(jù),編制出的動(dòng)車組運(yùn)用計(jì)劃方案圖中的某一動(dòng)車組交路如圖2.該交路共包含8個(gè)交路段,列車?yán)锍虨?7020km,日車?yán)锍虨?377.5km,動(dòng)車組運(yùn)用率達(dá)到55%.考慮到運(yùn)行圖天窗因素,結(jié)果比較合理.原