基于樹狀徑路的鐵路行車路徑優(yōu)化模型

基于樹狀徑路的鐵路行車路徑優(yōu)化模型

流量路徑是鐵路根據(jù)道路設(shè)計(jì)的交通規(guī)則、技術(shù)計(jì)劃、列車組計(jì)劃和運(yùn)營(yíng)方案的基礎(chǔ)。它也是調(diào)整日常交通的主要措施之一。專家對(duì)路網(wǎng)中車流分配、徑路優(yōu)化及求解算法進(jìn)行廣泛深入的研究車流徑路方案作為制定編組計(jì)劃的基礎(chǔ)必須與改編方案相互匹配,車流徑路由沿途編組去向的徑路組合而成1優(yōu)化模型1.1支點(diǎn)站集合識(shí)別定義有向圖G=(V,A)為簡(jiǎn)化后支點(diǎn)鐵路網(wǎng)絡(luò)圖。其中,V為鐵路網(wǎng)中支點(diǎn)站集合,且ue420i,j,s,t∈V;A為鐵路網(wǎng)中有向弧段(i,j)集合且ue420(i,j)∈A。1.2模型求解算法結(jié)合鐵路運(yùn)輸組織要求,基于多商品網(wǎng)絡(luò)流思想,構(gòu)建滿足以路網(wǎng)節(jié)點(diǎn)流量守恒、車流徑路唯一約束、車流徑路樹狀結(jié)構(gòu)特點(diǎn)及弧段能力限制約束,以車流總走行廣義費(fèi)用最小化為目標(biāo)的鐵路車流分配優(yōu)化模型P,即式(1)為目標(biāo)函數(shù),表示支點(diǎn)路網(wǎng)上所有車流總走行廣義費(fèi)用最小;式(2)~式(7)為約束條件,式(2)表示保證路網(wǎng)內(nèi)所有支點(diǎn)入、出車流量守恒約束;式(3)、式(4)共同保證車流走形徑路具有唯一性,滿足鐵路運(yùn)輸組織中每股OD均被視為1個(gè)不可拆散整體;式(5)、式(6)表示車流徑路的樹狀結(jié)構(gòu)約束,保證終點(diǎn)相同的車流在某個(gè)支點(diǎn)站匯合后走行徑路一致,直至運(yùn)輸?shù)浇K點(diǎn)站;式(7)表示路網(wǎng)中路段能力限制約束;式(8)式(10)表示模型變量取值范圍。車流分配問題就是按照運(yùn)輸組織原則將多支車流分配到給定路網(wǎng)中,該問題本質(zhì)上是1個(gè)大規(guī)模組合優(yōu)化問題,是N-P難題。小規(guī)模求解可通過精確算法(如分支定界)進(jìn)行精確求解,通常使用IBMILOGCPLEX、LINGO等商業(yè)優(yōu)化軟件;大規(guī)模求解難以通過精確算法解決,即使得到最優(yōu)解,計(jì)算時(shí)間、占用空間則無法接受或不現(xiàn)實(shí)。因此,需要設(shè)計(jì)有效算法,以得到最優(yōu)解或是近似最優(yōu)解。2拉格朗日松弛算法拉格朗日松弛算法是求解大規(guī)模組合優(yōu)化問題的有效算法,文獻(xiàn)2.1問題轉(zhuǎn)化和模型求解拉格朗日松弛算法應(yīng)用基本原理是將造成問題的難約束吸收到目標(biāo)函數(shù)中,使問題易于求解。分析模型P可知弧段能力約束式(7)是問題的難約束,根據(jù)拉格朗日松弛算法,定義非負(fù)拉格朗日乘子向量U={u當(dāng)拉格朗日乘子向量U={us.t.式(2)式(6)、式(8)式(10)式(13)中拉格朗日松弛乘子向量可看作是路網(wǎng)中占用瓶頸區(qū)段的附加成本,即等同于增加路段里程。本質(zhì)上,更新拉格朗日松弛乘子的作用是通過支付弧段占用成本以調(diào)整鐵路網(wǎng)中各路段的能力資源配置,得到最優(yōu)的車流分配方案。由于模型中不存在能力約束,求解優(yōu)化問題式(13)是所有車流按照最短路徑進(jìn)行車流分配,此時(shí)所有車流走行徑路均為最短路徑,同一終到點(diǎn)的車流徑路也必然呈“樹狀結(jié)構(gòu)”。為便于模型分析與分解,可暫時(shí)忽略對(duì)模型求解結(jié)果無影響的樹狀徑路約束條件式(5)、式(6)。假設(shè)現(xiàn)有M支OD車流,問題式(13)等價(jià)于分別求解M支車流分配子問題。因此,問題式(13)可分解為分別求解如下M子問題的最優(yōu)解每個(gè)子問題式(14)均可以通過優(yōu)化器分別求解,M個(gè)子問題的優(yōu)化解構(gòu)成松弛問題的解,而原問題的下界可由式(12)得到。2.2控制變量與生長(zhǎng)過程間關(guān)系若本節(jié)得到的解滿足模型P中弧段通過能力約束式(7),則該松弛解為原問題P的可行解,帶入原問題的目標(biāo)函數(shù)得到上界值z(mì)Step1車流加載。按照一定的車流排序規(guī)則將松弛解依次加載到路網(wǎng)中。Step2如果第i支車流加載后路網(wǎng)中有弧段(q,v)通過能力超過限制,則屏蔽已加載車流的特定路段,即針對(duì)所有同一到站的OD車流屏蔽起點(diǎn)站到支點(diǎn)u之間路段,并令對(duì)應(yīng)的車流路徑控制變量賦零。為保證第i支車流再分配后的車流路徑滿足樹形結(jié)構(gòu)特點(diǎn),需要根據(jù)式(20)~式(22)中的路徑控制變量與樹形控制變量之間的關(guān)系對(duì)車流路徑控制變量作賦零設(shè)置。Step3求解子問題。根據(jù)式(14)和當(dāng)前變量賦值情況求解第i支車流的分配子問題。判斷當(dāng)前解是否可行,若可行則轉(zhuǎn)到Step1;否則轉(zhuǎn)到Step2。Step4上界計(jì)算。當(dāng)所有車流再分配完成后得到新解為原模型P的1個(gè)可行解,帶入原問題目標(biāo)函數(shù)中到原問題的1個(gè)上界。2.3拉格朗日對(duì)偶優(yōu)化拉格朗日松弛問題R的最優(yōu)解是原問題P的1個(gè)下界。為得到原問題模的最大下界,需要求解如下拉格朗日對(duì)偶問題s.t.式(2)式(6)、式(8)式(10)通常采用次梯度優(yōu)化方法迭代求解拉格朗日對(duì)偶問題式(23)。初始化迭代指數(shù)k=1;迭代步長(zhǎng)為β式中:θ此時(shí),第k+1次迭代的拉格朗日乘子為u2.4終止條件達(dá)到以下任意1個(gè)條件即可終止迭代,否則k=k+1繼續(xù)迭代。(1)達(dá)到最大迭代次數(shù);(2)上下界的差值變化率小于特定值。3步長(zhǎng)調(diào)節(jié)因子對(duì)拉格朗日松弛算法收斂性的影響以我國(guó)某局部地區(qū)鐵路支點(diǎn)網(wǎng)絡(luò)為算例,驗(yàn)證拉格朗日松弛算法求解模型的有效性,見圖1。該支點(diǎn)鐵路網(wǎng)絡(luò)圖由41個(gè)車站、110條有向路段構(gòu)成。假定當(dāng)前路網(wǎng)中共有10條瓶頸區(qū)段需要限制通過能力,具體能力上限見表1。基于以上路網(wǎng)結(jié)構(gòu)和參數(shù),模擬生成1530股OD求解模型。首先在Matlab語言平臺(tái)上編程調(diào)用IBMILOGCPLEX優(yōu)化器求解原模型P,出現(xiàn)內(nèi)存不足狀況。因此,設(shè)計(jì)拉格朗日松弛算法對(duì)模型進(jìn)行求解。次梯度優(yōu)化過程中步長(zhǎng)大小影響拉格朗日松弛算法收斂的速度,可通過控制步長(zhǎng)調(diào)整因子控制步長(zhǎng)大小。通常步長(zhǎng)調(diào)整因子取值限制在0~2之間的非零值,實(shí)際操作時(shí)需要結(jié)合求解的模型和路網(wǎng)規(guī)模選取合適的步長(zhǎng)調(diào)整因子。為測(cè)試不同步長(zhǎng)調(diào)整因子初始值θ由圖2(a)看出步長(zhǎng)調(diào)整因子無論取任何初始值在迭代初期下界值均無明顯變化,當(dāng)?shù)揭欢ù螖?shù)后步長(zhǎng)調(diào)整因子取值為0.4、0.6、0.8時(shí)的下界開始迅速增大,迭代后期下界取值維持恒定狀態(tài);而步長(zhǎng)調(diào)節(jié)因子取值為0.2時(shí),整算法個(gè)迭代過程中下界取值無明顯變化。由圖2(b)看出在迭代10次以內(nèi),步長(zhǎng)調(diào)節(jié)因子取值較大的上界下降速度較快;迭代10~20次之間只有步長(zhǎng)調(diào)節(jié)因子取0.8時(shí)上界值呈現(xiàn)明顯變小趨勢(shì);當(dāng)?shù)^20次之后,上界取值均趨于平穩(wěn),且步長(zhǎng)調(diào)節(jié)因子取值0.4時(shí)上界取值大于其他。綜合圖2可得出:不同步長(zhǎng)調(diào)節(jié)因子對(duì)拉格朗日松弛算法收斂速度影響明顯。步長(zhǎng)調(diào)節(jié)因子取值小將導(dǎo)致拉格朗日松弛因子增減幅度小。因此,拉格朗日松弛因子對(duì)車流分配及路徑方案的調(diào)整效果不明顯,進(jìn)而造成問題下、上界收斂較慢。不同的步長(zhǎng)調(diào)節(jié)因子取值原問題最優(yōu)值的上、下界及對(duì)偶間隙,見表2。由表2可明顯看出,當(dāng)θ當(dāng)θ車流分配優(yōu)化后路網(wǎng)中瓶頸路段的通過能力占用率見表4,可看出各能力限制區(qū)段上的車流通過量均小于限制上限。說明通過拉格朗日松弛算法求解模型得到的車流分配方案可行,滿足模型中能力限制約束及車流徑路的樹狀結(jié)構(gòu)約束。4拉格朗日松弛算法優(yōu)化研究本文基于商品網(wǎng)絡(luò)流思想構(gòu)建具有樹狀徑路結(jié)構(gòu)的鐵路車流分配及徑路優(yōu)化混合整數(shù)規(guī)劃模型,模型以全部車流廣義里程最小為優(yōu)化目標(biāo),以單支車流不可拆分約束、瓶頸路段通過能力限制約束及同一終到站車流徑路的樹狀結(jié)構(gòu)約束等為約束條件。設(shè)計(jì)拉格朗日松弛算法求解模型,通過算例驗(yàn)證商業(yè)優(yōu)化軟件在較大