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

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

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