雙向編組站配流問題研究

階段計劃是鐵路技術站日常規(guī)劃和指揮的重要計劃，其主要內(nèi)容是確定出發(fā)列車的組成內(nèi)容。指定一個人員調(diào)整和調(diào)機任務。出發(fā)列車必須組織到發(fā)送線。其中,前2個問題的關系最為緊密,第3個問題需以它們的解作為輸入。因此,學術界常將前2個問題放在一起研究,且有許多稱謂,簡便起見,本文將其定義為配流問題。我國鐵路技術站包括區(qū)段站、單向編組站和雙向編組站,區(qū)段站和單向編組站僅有1套改編系統(tǒng),而雙向編組站在上下行方向各有1套功能完善且相對獨立的改編系統(tǒng),因此不可避免地存在折角車流,即某系統(tǒng)的部分中轉車流只能被轉場到對向系統(tǒng)才能找到接續(xù)的出發(fā)列車,即某系統(tǒng)的折角車流是對向系統(tǒng)出發(fā)列車的候選車流來源,如何轉場折角車流是雙向編組站配流需解決的關鍵問題。另外,大型雙向編組站在某階段內(nèi)可能需要解編50列~60列列車,運用10余臺調(diào)機,工作負荷大,作業(yè)過程非常復雜。因此,雙向編組站配流是具有挑戰(zhàn)性的鐵路技術站配流問題。配流問題是編組站階段計劃優(yōu)化編制的關鍵,幾十年以來,學術界進行大量研究,現(xiàn)狀與發(fā)展趨勢見黎浩東1數(shù)學模型1.1列被占用研究的交互系統(tǒng)本文模型基于如下假設:假設1任意1列車列的解體或編組作業(yè)僅需1臺專用調(diào)機負責,且作業(yè)過程不允許中斷;假設22個系統(tǒng)的駝峰均采用雙推單溜作業(yè)方案,即駝峰溜放線同一時間僅為1列解體車列占用;假設32個系統(tǒng)的峰尾同一時間僅為1列編成轉線車列占用;假設4到達列車的接入系統(tǒng)和出發(fā)列車的發(fā)出系統(tǒng)已確定,即各系統(tǒng)接入的到達列車和發(fā)出的出發(fā)列車的數(shù)量及性質(zhì)已知;假設5折角車流利用交換場進行轉場,即各系統(tǒng)的折角車流在本系統(tǒng)調(diào)車場內(nèi)集結交換車列,滿列的交換車列首先被本系統(tǒng)的編組調(diào)機編組后從本系統(tǒng)出發(fā)場轉到交換場,然后被對向系統(tǒng)的解體調(diào)機從交換場轉到對向系統(tǒng)的到達場,并再進行解體;假設6各系統(tǒng)可利用的交換車列數(shù)量已知。該值在現(xiàn)場是未知的,但可根據(jù)各自系統(tǒng)交換車的總數(shù)及每列交換車列的容量進行粗略地估計。1.2系統(tǒng)編制約下的模型雙向編組站配流問題(O)需同時考慮解體作業(yè)約束、編組作業(yè)約束和車流接續(xù)約束等,并有多個可考慮的優(yōu)化目標。參照既有文獻為區(qū)段站和單向編組站配流問題提出的建模方法(1)解體作業(yè)約束首先,各系統(tǒng)中各到達車列和交換車列僅由1臺解體調(diào)機進行(重復)解體(前者的調(diào)機與其屬于同一系統(tǒng),后者的調(diào)機屬于對向系統(tǒng)),且他們只能在其解體最早可能結束時刻之后完成解體,即式中:w為車站改編系統(tǒng)的索引變量,當w等于0或1時,分別表示下行和上行系統(tǒng);i為到達列車的索引變量;k為解體調(diào)機的索引變量;I其次,每個系統(tǒng)中各解體調(diào)機單位能力為1,同時最多只能解體1列到達車列或交換車列,即式中,h為解體作業(yè)時間間隔的索引變量。到達車列和交換車列的解體結束時刻為式中,c最后,各系統(tǒng)駝峰溜放線同一時間最多僅由1列解體車列占用。例如,對于2列將在同系統(tǒng)解體的車列i和i′,若車列i先于車列i′解體,則后者的解體結束時刻需與前者至少間隔1個駝峰溜放時間標準,否則,反之。即(2)編組作業(yè)約束首先,各系統(tǒng)中各出發(fā)車列或交換車列僅由1臺編組調(diào)機進行編組(2類車列的調(diào)機與其屬于同一系統(tǒng)),且它們的編組作業(yè)需在其最晚必須開始時刻前啟動,即式中:j為出發(fā)列車的索引變量;kk為編組調(diào)機的索引變量;J其次,各系統(tǒng)中各編組調(diào)機單位能力為1,同時最多只能編組1列出發(fā)車列或交換車列。即式中,s為編組作業(yè)時間間隔的索引變量。出發(fā)車列和交換車列的編組開始時刻為式中,a最后,各系統(tǒng)中峰尾在同一時間最多只能供1列轉線車列占用。例如,對于2列需在同系統(tǒng)編組的車列j和j′,若車列j被安排早于車列j′編組,則后者的編組結束時刻需與前者至少間隔1個峰尾轉線時間標準,否則,反之。即(3)車流接續(xù)約束首先,到達列車需滿足車流守恒約束,某系統(tǒng)到達列車中的車流既可被分配本系統(tǒng)的出發(fā)列車和殘存列車當中,也可經(jīng)交換列車被分配到對向系統(tǒng)的出發(fā)列車及其殘存列車當中,即式中:b為編組去向的索引變量;B為車站編組去向的集合;V其次,各系統(tǒng)中出發(fā)列車只有當滿軸(滿重或滿長)后才能開行。在雙向編組站,某系統(tǒng)出發(fā)列車的車流來源既包括本系統(tǒng)的普通車流,也包括對向系統(tǒng)的經(jīng)交換列車轉場來的折角車流。即第三,各系統(tǒng)中交換列車只有當折角車流集結滿列后才能開始編組,即第四,各系統(tǒng)中出發(fā)列車和交換列車均不能吸收在其編組開始時還未結束解體的到達列車和交換列車中的車流,即式中:φ第五,根據(jù)列車編組計劃,需限制出發(fā)列車車流來源的范圍,各系統(tǒng)中出發(fā)列車不能吸收其可編去向以外的車流,無論是普通車流還是折角車流。即式中:f最后,從實際情況出發(fā),限制在各系統(tǒng)中交換列車只能吸收折角車流,而非普通車流。即式中:(4)連接約束以下2組約束確保模型的正確性和有效性式中,M式(24)為連接部分決策變量,保證車流時間接續(xù)約束(18)~約束(20)的正確性。式(25)為各系統(tǒng)中各交換列車需在對向系統(tǒng)進行重復解體前完成編組作業(yè)。值得指出的是,當車流來源不足時,基于連接約束,整個模型可巧妙地確定哪些出發(fā)列車和交換列車需被停運,并在最終輸出的調(diào)機運用方案中將那些列車安排在最不利的位置完成需要的技術作業(yè)。在轉換為實際的作業(yè)計劃時,調(diào)機不需解編被停運的列車。(5)目標函數(shù)技術站配流問題在本質(zhì)上是多目標優(yōu)化問題,優(yōu)化目標包括最小化車輛在站總停留時間、最小化車輛在站平均停留時間、最大化車站中轉車輛數(shù)、最大化正點出發(fā)列車數(shù),等等。本文取最小化車輛在站總停留時間為目標函數(shù),即綜上,以式(26)為目標函數(shù),以式(1)~式(25)為約束,構建雙向編組站配流問題的整數(shù)規(guī)劃模型,該模型為混合整數(shù)線性規(guī)劃模型。顯然,原問題(O)是NP-hard問題,因為若松弛連接約束(24)和約束(25),可被簡化為2個獨立且相似的子問題,每個子問題又類似于均已被證明為NP-hard類的具有最小運輸量約束的最小費用網(wǎng)絡流問題2求解算法拉格朗日松弛算法2.1子問題s1如前文所述,約束(24)和約束(25)共同構成原問題(O)的困難約束,若引入拉格朗日乘子向量分別松弛掉該2項約束,并將他們添加到目標函數(shù)中作為懲罰項,原問題(O)轉變?yōu)樗沙趩栴}(R)為松弛問題(R)的目標函數(shù)又可重新表達為于是,若已知拉格朗日乘子μ和π,松弛問題(R)可被分解為3個獨立的子問題。第2個子問題(S2)只關注編組排序方案與原問題(O)相比,上述3個子問題的數(shù)學結構更為簡單,從實際應用的角度出發(fā),對他們直接采用商業(yè)優(yōu)化軟件求解到最優(yōu)或預定的計算時間達到為止。從計算復雜度看,子問題(S1)和(S2)均為同類復雜的并行機調(diào)度問題,子問題(S3)為另一類具有邊界約束的最小費用網(wǎng)絡流問題,類似于原問題,3個子問題仍然是NP-hard問題。至今仍沒有多項式算法,精確求解也有很大難度。然而,并行機調(diào)度問題和最小費用流問題不屬于本文的研究內(nèi)容。由理論可知,松弛問題(R)的最優(yōu)解不一定是原問題(O)的可行解,但目標函數(shù)值可為原問題(O)的目標函數(shù)提供理論下界,若不能成功獲得松弛問題(R)的最優(yōu)解,只取其線性松弛解估計原問題(O)的下界。2.2量的可行解和理論上界本節(jié)介紹在松弛問題(R)解的基礎上,如何構造原問題(O)高質(zhì)量的可行解,并由此獲得好的理論上界。對問題分解后,松弛問題(R)的最優(yōu)(松弛)解y,c,z,a,x和ue0af有可能因違背約束式(24)和式(25)不能成為原問題(O)的可行解。2.3拉格朗日乘子法拉格朗日乘子μ和π對松弛問題(R)的向下定界效果起著非常重要的作用。理論上,乘子最優(yōu)值可通過最大化如下的對偶問題(D)獲得然而,松弛問題(R)的目標函數(shù)z(μ,π)是拉格朗日乘子μ和π的分段線性凸函數(shù),在由μ和π構成的解空間內(nèi)均不可微。因此傳統(tǒng)的基于導數(shù)的數(shù)值算法對問題(D)均不適用。既有文獻為有效求解問題(D)提出許多近似算法2.4算法步驟拉格朗日松弛算法的計算步驟為3到達列車情況及約束測試案例來源于某大型雙向編組站,見圖1。該站位于2條繁忙干線的交點處,銜接東南西北4個方向。其中,東西方向連接1條干線,南北方向連接另1條干線。下行系統(tǒng)僅接入來自西、北方向的到達列車,且只發(fā)送到達東、南方向的出發(fā)列車,始于東和南方向的到達列車和去往西和北方向的出發(fā)列車只能在上行系統(tǒng)辦理技術作業(yè),2個系統(tǒng)均配備3臺解體調(diào)機、3臺編組調(diào)機,下行系統(tǒng)的解體調(diào)機為1調(diào)、2調(diào)和3調(diào),編組調(diào)機為4調(diào)、5調(diào)和6調(diào),上行系統(tǒng)的解體調(diào)機和編組調(diào)機分別為7調(diào)、8調(diào)和9調(diào)以及10調(diào)、11調(diào)和12調(diào),2個系統(tǒng)駝峰和峰尾的固定占用時間分別為12min和10min。該站有16個編組去向,每個銜接方向對應4個去向,1個去向集結1列出發(fā)列車,去向根據(jù)所屬方向按東南西北依次遞增進行編號。測試站8:00~12:00共接入30列到達列車,2個系統(tǒng)各占一半。其中,到達列車1000次和2000次分別表示下行系統(tǒng)和上行系統(tǒng)上一階段的殘存列車,該類列車無需再進行到達作業(yè)和解體作業(yè)。到達列車信息見表1。設定各到達列車各去向車輛的平均總重為80t、平均換長為1.3,除殘存列車外,其余列車的到達作業(yè)時間和解體作業(yè)時間分別為35min和30min。根據(jù)現(xiàn)場經(jīng)驗,車流接續(xù)時間標準為2h,即出發(fā)列車的計劃時段為10:00~14:00,該時段內(nèi)2個系統(tǒng)各有15列出發(fā)列車可利用,共30列出發(fā)列車。其中,東西方向各有7列,南北方向各有8列,見表2。已知去往東、西方向出發(fā)列車的最大總重和最大換長分別為4000t和78,去往南、北方向分別為4400t和84,允許欠軸80t,欠長1.3。根據(jù)表1所示的折角車流,估算上下行系統(tǒng)可利用的交換列車各有4列,分別記為5002次~5008次和5001次~5007次。設定所有出發(fā)列車的編組作業(yè)時間和出發(fā)作業(yè)時間均為30min,各交換列車的編組作業(yè)時間和(重復)解體時間均為35min,最小車數(shù)和最大車數(shù)分別為45輛和55輛。取最優(yōu)誤差ε為1×10由表5可見,使用本文提出的算法,算例中大部分出發(fā)列車均能滿軸開行,開往東方向的1008次列車及開往西方向的3009次列車和3011次列車除外。另外,大部分出發(fā)列車的編組內(nèi)容包含對向系統(tǒng)的折角車流,該結果說明在雙向編組站,折角車流是出發(fā)列車重要的車流來源,如何及時有效地轉場折角車流,最大程度地促進出發(fā)列車滿軸,是雙向編組站配流的關鍵,從本文建模過程看,也是難點所在。分析算法計算表現(xiàn),對于測試算例,借助構建的整數(shù)規(guī)劃模型,在5min同樣的限制時間內(nèi),CPLEX沒有找到任何可行解。而現(xiàn)場基于先到先服務的經(jīng)驗方法盡管能確定可行的配流計劃,但需停運7列出發(fā)列車,目標函數(shù)值增加為430425車·min,最優(yōu)誤差高達(430425-383325)/383325×100%=12.3%。綜上,與CPLEX和經(jīng)驗方法相比,本文提出的拉格朗日松弛算法更具有競爭力,在5min限制時間內(nèi),返回距離最優(yōu)解誤差不超過3%的滿意解,求解精度和效率能夠滿足現(xiàn)場要求。4下一步研究內(nèi)容不同類型的鐵路技術站中,雙向編組站配流問題最為復雜,需同時協(xié)調(diào)2個改編系統(tǒng)的普通車流和折角車流的技術作業(yè),該問題至今沒有引起學術界太多的關注。本文探討典型雙向編組站配流問題。其中,折角車流采用交換場進行轉場,基于整數(shù)規(guī)劃理論與方法為該問題設計具有實際可行性的求解方法。算例表明,本算法能夠在合理的限制時間內(nèi)找到比現(xiàn)場經(jīng)驗方法更優(yōu)越的解。本文研究可進一步改進:首先,提出的拉格朗日松弛算法仍然面臨收斂慢的問題,需要探討計算效率更高的求解方法,啟發(fā)式算法是下一步重點研究內(nèi)容;另外,本文假定系統(tǒng)分工方案給定且固定。然而以往研究已表明,在條件允許的雙向編組站,靈活的系統(tǒng)分工方案更有利于提高配流效率。所以,如何實時調(diào)整系統(tǒng)分工方案也是未來的研究方向。式中:若給定所有系統(tǒng)中各車列的解體結束時刻cs.t.式(1)~式(3);式(6)~式(8);式(11)~式(17)可以看出,問題(U)具有更簡單的數(shù)學結構,且被構建為已有許多有效算法的混合整數(shù)線性規(guī)劃模型,求解難度比原問題和子問題更小。本文借助商業(yè)優(yōu)化軟件直接求解問題(U),直至找到最優(yōu)解或超過給定的計算時間限制為止。Step4更新拉格朗日乘子為初始化參數(shù)λ式中:式中:式中:g式中:式中:s.t.式(6)~式(10)s.t.式(1)~式(5)s.t.式(1)