基于時空網(wǎng)絡(luò)的高速鐵路全圖運行線規(guī)劃方法

基于時空網(wǎng)絡(luò)的高速鐵路全圖運行線規(guī)劃方法

0列車行車方案局部調(diào)整列車圖的調(diào)整是根據(jù)運輸需求改進(jìn)運行圖的過程，包括局部調(diào)整和全球調(diào)整。當(dāng)?shù)卣{(diào)整是根據(jù)現(xiàn)有框架下的增加車站需求增加車站線路，包括添加新車站線路的調(diào)整和現(xiàn)有車站線路的調(diào)整。全球調(diào)整就是對整個圖的整體圖進(jìn)行重新設(shè)計的?，F(xiàn)有的高速列車運行圖結(jié)構(gòu)是長期以來鐵路運行圖的結(jié)果，通常不進(jìn)行全面調(diào)整。隨著網(wǎng)絡(luò)連接的改善和交通需求的變化，當(dāng)前的手動提升線解算方法難以得到保證，而且有很大的局限性。因此，有必要研究線路圖的局部調(diào)整模型和算法。列車運行圖調(diào)整屬列車運行圖編制(TrainTimetablingProblem,TTP)范疇,是NP-hard問題上述研究為本文奠定了理論基礎(chǔ).我國高速鐵路運行圖呈非周期性,局部調(diào)整以新增列車開行方案為基本輸入,需調(diào)整的既有運行線可視為一類特殊的新增列車,從而將局部調(diào)整轉(zhuǎn)化為給定框架下的新增運行線求解問題.現(xiàn)有基于拉格朗日松弛的運行圖調(diào)整模型簡化了列車在區(qū)間運行狀態(tài),未考慮停站引起的起停車附加時分1問題描述運行圖可由有向時空網(wǎng)絡(luò)描述設(shè)S為全體車站集合,給定列車集T=(1,…,t),以S上述問題為一定約束下G中自f2運行圖的局部調(diào)整模型2.1變量描述δδθ(v)——節(jié)點v對應(yīng)的時刻;2.2模型限制新增運行線j需滿足一定約束.對兩相鄰列車j、k而言,在任意站i∈(S2.2.1車站間隔約束(1)列車在車站i的出發(fā)時刻應(yīng)不小于該站發(fā)車間隔d約束可表示為對任意i∈S/{s},v∈W(2)列車在車站i+1的到達(dá)時刻應(yīng)不小于該站到達(dá)間隔a約束可表示為對任意i∈S/{1},u∈U(3)兩運行線在區(qū)間內(nèi)不相交,設(shè)v設(shè)區(qū)間內(nèi)列車k的速度高于列車j,約束可表示為對任意相鄰車站i和i+1,運行線j、k,圖4所示的4個節(jié)點(v2.2.2運行線的唯一限制(4)始發(fā)弧數(shù)量約束.(5)節(jié)點v進(jìn)入、離開弧數(shù)量約束.(6)節(jié)點v選擇次數(shù)約束.2.2.3非經(jīng)停站出發(fā)時間限制列車停站約束為列車j在經(jīng)停站停時不少于該站計劃停時;在非經(jīng)停站出發(fā)時刻與到達(dá)時刻相等.設(shè)θ(v)=θ(u)+t(7)經(jīng)停站出發(fā)時刻選擇限制.(8)非經(jīng)停站出發(fā)時刻選擇限制.2.2.4連接變量的限制連接變量約束為各0-1變量間相互約束.(9)弧構(gòu)成約束.(10)節(jié)點選擇約束.2.3目標(biāo)函數(shù)各運行線始發(fā)時間域及總停時限制決定了其所有可選節(jié)點及弧的子圖G設(shè)αs.t.式(1)~式(10)3拉格朗日放松啟動算法3.1拉格朗日松弛上述模型中行車組織約束屬于簇約束,數(shù)量隨問題規(guī)?？焖僭鲩L,會引起模型規(guī)模的急劇擴(kuò)大,對其進(jìn)行拉格朗日松弛可加快求解速度式中:C——由行車組織約束決定的與該節(jié)點不相容弧集λ對式(11)進(jìn)行恒等變換,即s.t.式(4)~式(10)式中:qˉλ原模型松弛后,各運行線間約束關(guān)系被弱化,可由線性規(guī)劃方法快速求解3.2新增運行線萌發(fā)時間域的fd求解算法由于松弛了原模型中部分約束,LD中各運行線拉格朗日松弛解可能是實際非可行解.為求得實際可行解FD,設(shè)計下述啟發(fā)式算法:(1)求解LD,記錄全圖各節(jié)點拉格朗日罰數(shù)λ(2)新增運行線按拉格朗日松弛解利潤大小排序確定鋪畫順序.(3)在新增運行線始發(fā)時間域內(nèi)基于所有可行出發(fā)節(jié)點并考慮p(σ,v)、p(u,v),選擇λ(4)求解全圖實際利潤大于零的運行線實際利潤之和,結(jié)果記錄為FD的解.所求得的FD為D的1個實際可行解3.3目標(biāo)函數(shù)的確定由于FD≤D≤LD,故D最優(yōu)解處于區(qū)間(FD,LD)內(nèi),通過更新拉格朗日乘子,可優(yōu)化FD的目標(biāo)函數(shù)值,使其趨近于D最優(yōu)解(1)初始化各約束次梯度要素viol(λ(2)對各運行線構(gòu)成弧檢查是否滿足第h個約束條件,若違反該約束則對第h個約束的次梯度要素更新為viol(λ(4)根據(jù)Fisher提出的式(15)更新第h個約束對應(yīng)的拉格朗日乘子λ式中:ρ——給定的非負(fù)步長通過上述過程可優(yōu)化LD及FD的目標(biāo)函數(shù)值,從而對FD進(jìn)行迭代優(yōu)化,當(dāng)LD與FD滿足一定條件時可認(rèn)為已求得最優(yōu)可行解3.4拉格朗日乘子更新Step0初始化,記錄起始時間,設(shè)迭代次數(shù)為0,當(dāng)前最優(yōu)可行解為0,當(dāng)前最優(yōu)上界為全圖各運行線初始利潤之和.Step1求解LD,記錄當(dāng)前最優(yōu)上界為min(LD).Step2根據(jù)LD所得各節(jié)點罰數(shù)λStep4以3.3節(jié)所述方法更新拉格朗日乘子λStep5檢查算法運行時間、迭代次數(shù)是否達(dá)到設(shè)定最大值,若是,算法終止,最優(yōu)下界對應(yīng)解即為最優(yōu)可行解;若否,轉(zhuǎn)Step1.4算法有效性驗證以2015年5月京滬高鐵運行圖為例,在原圖302條運行線框架下增鋪24條G類高速運行線,新增列車信息如表1所示.本文主要驗證模型算法的有效性,求解過程中暫不要求列車上下行數(shù)量相等.首先以現(xiàn)有調(diào)整方法進(jìn)行實驗:以初始始發(fā)時刻推線求解,結(jié)果表明僅能增加AD1015/AD1016、AD1019、AD1023/AD1024次等5條運行線;擴(kuò)大始發(fā)時刻可調(diào)整度至60min,可增加AD1009、AD1015/AD1016、AD1018/AD1019、AD1021/AD1022、AD1023/AD1024次等9條運行線.然后驗證本文所提出模型:給定各運行線初始利潤10000,設(shè)α算例對應(yīng)規(guī)模下,可逐一列出所有簇約束所包含的約束條件.為驗證拉格朗日松弛算法效率,調(diào)用ILOGCPLEX12.5求解原模型D進(jìn)行對比驗證.相關(guān)算法以C語言實現(xiàn),實驗在1臺Ubuntu14.04Xeon2.66GHz4G內(nèi)存工作站上進(jìn)行,結(jié)果如表2所示,其中C代表CPLEX求解結(jié)果,L代表拉格朗日算法求解結(jié)果.可見可增鋪運行線數(shù)量隨列車始發(fā)時刻可調(diào)整度增加而增加,說明列車始發(fā)時間域是影響列車運行圖局部調(diào)整的重要因素.簇約束式(1)~式(3)使得模型規(guī)模急劇增加,CPLEX雖然求解精度較高,但求解速度下降明顯;而拉格朗日算法求解時間增加較為平緩,目標(biāo)函數(shù)值、新增列車運行線平均旅速與CPLEX求解所得結(jié)果十分接近(表2),在保證求解質(zhì)量的同時維持了較高的計算效率.統(tǒng)計不同始發(fā)時刻可調(diào)整度下拉格朗日算法所得結(jié)果如表3所示,其中始發(fā)時刻調(diào)整總時長、平均時長、最大調(diào)整時長分別為相應(yīng)始發(fā)時刻可調(diào)整度下各新增運行線較給定理想始發(fā)時刻調(diào)整值之和、各新增運行線始發(fā)時刻調(diào)整值均值、各新增運行線最大始發(fā)時刻調(diào)整度;總停時延長值為相應(yīng)始發(fā)時刻可調(diào)整度下各新增運行線較給定最短停時延長值之和.實驗中隨著始發(fā)時刻可調(diào)整域的增加,相較于根據(jù)給定的理想始發(fā)時刻推線,由于考慮了列車在站停時可在一定程度上延長,使得運行線求解空間增大,例如在始發(fā)時刻可調(diào)整度為60min時,新增運行線在站停時可以在給定最短停時的基礎(chǔ)上適當(dāng)延長(總停時延長不超過10min),某站停時的適當(dāng)延長可能會避免后續(xù)鋪畫時與其他運行線的潛在沖突,在此基礎(chǔ)上遍歷所有的運行線可行解,增加了新增運行線的鋪畫概率,因此,相較按理想始發(fā)時刻及最短停時推線,額外增鋪了6條運行線;但同時由于全程停時的增加,引起了旅速在一定程度上的下降.進(jìn)一步驗證京滬高鐵現(xiàn)有運行圖框架下的最大能力,將各運行線始發(fā)時刻可調(diào)整度放寬至4h,計算滿足天窗限制(0:00-6:00)的可新增運行線數(shù).由于簇約束影響,CPLEX無法在給定時間內(nèi)得到最優(yōu)解;拉格朗日算法經(jīng)過200次迭代、509s后由于迭代次數(shù)達(dá)到設(shè)定上限終止,共鋪畫了有效運行線18條,說明在算例框架下京滬高鐵通過能力已接近飽和,進(jìn)一步增開列車需對原有框架做出一定調(diào)整.5求解效率分析針對給定框架下增鋪運行線問題,基于時空網(wǎng)絡(luò)構(gòu)建整數(shù)規(guī)劃模型,采用基于拉格朗日松弛的啟發(fā)式算法求解,實例驗證得到結(jié)論如下:(1)采用始發(fā)時刻推線方法,算例所述情況下能額外鋪畫9條運行線,而拉格朗日算法能夠鋪畫15條運行線.(2)除始發(fā)時刻可調(diào)整度±10min情景外,拉格朗日算法的求解速度均優(yōu)于CPLEX.(3)隨著始發(fā)時刻可調(diào)整度的增加,模型規(guī)模急劇增長,CPLEX所需的求解時間快速增加,而拉格朗日算法計算時間增加較平緩,計算效率優(yōu)勢明顯.(4)始發(fā)時刻可調(diào)整度由10min增加至60min時,由于各運行線可行解范圍增加,可增鋪的運行線由6條增加至15條.(5)始發(fā)時刻可調(diào)整度4h條件下,CPLEX無法在給定時間內(nèi)求得最優(yōu)解,拉格朗日算法在現(xiàn)有框架下最多增鋪了18條運行線.在原列車運行圖框架不變條件下,新