牛紅霞，張大勇

（鄭州鐵路職業(yè)技術(shù)學(xué)院 運(yùn)輸管理學(xué)院，河南 鄭州 451460）

0 引言

按圖行車是鐵路運(yùn)輸組織的基本要求，然而突發(fā)設(shè)備故障、惡劣天氣等異常事件會影響運(yùn)行秩序和運(yùn)行安全[1]，會使列車偏離既定的運(yùn)行計劃，引起運(yùn)輸秩序紊亂。高速鐵路列車運(yùn)行速度快、行車密度高，對運(yùn)輸秩序的波動較為敏感。當(dāng)運(yùn)輸秩序受到干擾時，調(diào)度員需要及時調(diào)整，盡量恢復(fù)按圖行車或減少列車運(yùn)行秩序紊亂帶來的影響[2]。弱干擾下的列車運(yùn)行調(diào)整問題主要目標(biāo)是在盡量短的時間內(nèi)恢復(fù)按圖行車、減少運(yùn)輸干擾波及范圍；強(qiáng)干擾條件下的列車運(yùn)行調(diào)整問題則需對列車運(yùn)行計劃進(jìn)行重新制訂并確定是否需要取消列車，主要目標(biāo)是根據(jù)干擾情況確定受干擾區(qū)段的列車運(yùn)行順序、避免由于線路基礎(chǔ)設(shè)施不滿足列車運(yùn)行而造成列車在途長時間停車[3]。

目前，國內(nèi)外對弱干擾條件下的列車運(yùn)行調(diào)整研究較多，而強(qiáng)干擾條件下的實時調(diào)度問題研究較少[4-5]。高速鐵路在強(qiáng)干擾發(fā)生時的運(yùn)行調(diào)整工作主要依靠調(diào)度員的經(jīng)驗判斷人工指揮，不僅工作強(qiáng)度大而且方案有效性、科學(xué)性難以保證，因而以區(qū)段發(fā)生強(qiáng)干擾為背景，有針對性地對列車運(yùn)行調(diào)整模型及相應(yīng)求解方法進(jìn)行研究。

1 問題描述

考慮在雙線區(qū)段內(nèi)的某區(qū)間單方向線路發(fā)生影響行車組織的強(qiáng)干擾情景，如線路中斷、電氣化鐵路接觸網(wǎng)中斷等，列車無法按圖運(yùn)行，引起列車運(yùn)行秩序紊亂。為明確問題，結(jié)合我國鐵路實際進(jìn)行以下假設(shè)：①區(qū)段為雙線，正常運(yùn)行時上下行線路分別使用；②區(qū)段某區(qū)間單條線路中斷，另一條線路正常行車不受影響；③線路區(qū)段滿足區(qū)間反向行車需求；④區(qū)段內(nèi)各車站上下行到發(fā)線分別使用，忽略列車進(jìn)路排布影響；⑤除強(qiáng)干擾情況發(fā)生區(qū)段外，其余區(qū)段滿足列車正常運(yùn)行條件；⑥在進(jìn)入干擾區(qū)段前各列車按圖運(yùn)行。上述假設(shè)條件可簡化問題建模并不影響問題的一般性。

區(qū)段強(qiáng)干擾示意圖如圖 1 所示，雙線區(qū)段車站 2 和車站 3 間下行線路受強(qiáng)干擾影響中斷，此時該區(qū)間組織雙向行車。由于強(qiáng)干擾，需確定各列車通過該區(qū)段的順序，列車不能運(yùn)行在車站等待，故需根據(jù)干擾預(yù)測時長考慮沿線各站能力限制，決定各始發(fā)站尚未發(fā)出的列車是否取消。

圖 1 區(qū)段強(qiáng)干擾示意圖Fig.1 Example of section strong interference

2 模型構(gòu)建與求解

根據(jù)現(xiàn)有研究[6-7]，結(jié)合我國鐵路實際情況，以事件-活動網(wǎng)絡(luò)為基礎(chǔ)，構(gòu)建混合整數(shù)線性規(guī)劃模型描述強(qiáng)干擾條件下的列車運(yùn)行調(diào)整問題。

2.1 模型構(gòu)建

2.1.1 事件-活動網(wǎng)絡(luò)表述

以集合E表示事件，集合A表示活動，宏觀層面線路網(wǎng)絡(luò)可抽象為事件和活動構(gòu)成的網(wǎng)絡(luò)N=(E，A)，事件-活動網(wǎng)絡(luò)示意圖如圖2所示。根據(jù)事件類型不同，可將集合E分為到達(dá)事件集合Earr?E和出發(fā)事件集合Edep?E；根據(jù)活動類型不同，可將活動分為列車活動a∈Atrain(圖2中實線)和間隔活動a∈Ahead(圖 2 中虛線 )。

圖2 事件-活動網(wǎng)絡(luò)示意圖Fig.2 Example of event-activity network

列車活動a∈Atrain可表示列車在區(qū)間內(nèi)的運(yùn)行a∈Arun或在車站的停站a∈Adwell；間隔活動a∈Ahead表示列車在車站的到發(fā)間隔或反向運(yùn)行時在區(qū)間的運(yùn)行間隔。基于事件-活動網(wǎng)絡(luò)，可將列車在區(qū)段內(nèi)的運(yùn)行、停車等表示為各項事件的集合，顯然列車運(yùn)行圖可以由全圖所包含的所有事件表示，而各類行車間隔約束、車站能力約束等就可以由各類活動表示。于是，列車運(yùn)行調(diào)整可以表示為實際所包含的各類事件，通過實際包含的各類事件與原列車運(yùn)行圖所包含各類事件的比較，實現(xiàn)對運(yùn)行調(diào)整的量化并構(gòu)建數(shù)學(xué)模型對其進(jìn)行優(yōu)化和求解。

2.1.2 相關(guān)符號定義

列車根據(jù)等級不同可以分為不同種類，當(dāng)受強(qiáng)干擾影響時，列車運(yùn)行時刻會偏離原有列車運(yùn)行圖，為明確描述各類約束條件，對相關(guān)符號定義如下。T為列車集合，分為下行列車集合T down?T和上行列車集合T up?T；S為區(qū)段內(nèi)所有車站集合，s∈S；S m為區(qū)段內(nèi)中間站集合，設(shè)區(qū)段內(nèi)共有車站n個，1≤n≤m；Seg為相鄰車站間的區(qū)間集合，seg∈Seg；qe為事件e的圖定發(fā)生時刻；xe為事件e的實際發(fā)生時刻；Ωe為計劃列車運(yùn)行圖，有為實際列車運(yùn)行圖為事件e的晚點時間為事件e的早點時間為事件e的晚點懲罰值為事件e的早點懲罰值；λt為列車t的取消罰數(shù)；te為事件e對應(yīng)的列車；D為時間最大允許偏離值；M1為當(dāng)日運(yùn)行圖周期，有M1= 1 440 ；M2為正整數(shù)參數(shù)，M2＞M1。

2.1.3 目標(biāo)函數(shù)

強(qiáng)干擾情況下的列車運(yùn)行調(diào)整主要目的是使列車盡量按照原圖行車、減少實際運(yùn)行圖與計劃運(yùn)行圖偏離，同時為滿足運(yùn)輸需求及機(jī)車、車輛、動車組等交路需要，盡量減少列車取消。由此確定目標(biāo)函數(shù)為列車偏離計劃運(yùn)行時刻與取消造成罰數(shù)的加權(quán)最小值，計算公式為

2.1.4 約束條件

干擾條件下的列車運(yùn)行調(diào)整模型需滿足一定的邏輯約束及列車在區(qū)段內(nèi)運(yùn)行的行車組織約束。我國列車運(yùn)行圖雖然基本為非周期列車運(yùn)行圖，但為縮減問題規(guī)模，可將列車運(yùn)行圖以天為單位進(jìn)行單元化處理。在建模時考慮一天內(nèi)的列車運(yùn)行調(diào)整問題，對過表列車則順延至下一個周期(后一天)處理。

（1）邏輯約束。表示各事件的基本時間關(guān)系，具體如下。

公式 ⑵ 表示取消列車轉(zhuǎn)移至下一周期(后一天)，從而避免對其他列車的干擾；公式 ⑶ 表示列車實際出發(fā)時刻不早于圖定時刻；公式 ⑷、公式 ⑸ 分別表示事件的晚點、早點時間；公式 ⑹、公式 ⑺ 限制列車的最大晚點及早點允許值；公式 ⑻、公式 ⑼、公式 ⑽ 為相關(guān)變量的取值范圍約束。

（2）行車組織約束。限制列車在區(qū)間的運(yùn)行間隔時間及在站的出發(fā)、到達(dá)間隔時間，并保證同一時間同一閉塞區(qū)間內(nèi)僅允許一列列車運(yùn)行。當(dāng)列車在區(qū)間內(nèi)追蹤運(yùn)行時，區(qū)間運(yùn)行間隔時間由區(qū)間追蹤間隔時間決定；當(dāng)列車在區(qū)間反向運(yùn)行時，不允許對向列車由前方車站發(fā)出駛向該區(qū)間，此時運(yùn)行間隔時間表現(xiàn)為先進(jìn)入?yún)^(qū)間列車在該區(qū)間內(nèi)的運(yùn)行時間，需要根據(jù)具體列車運(yùn)行狀態(tài)確定區(qū)間運(yùn)行間隔時間。相關(guān)約束的具體表現(xiàn)形式如下。

公式 ⑾ 表示占用同一運(yùn)輸資源的相鄰事件e，f間隔時間應(yīng)滿足相應(yīng)時間約束，根據(jù)列車運(yùn)行狀態(tài)不同，該約束可表示同向列車在站的到發(fā)間隔時間或者反向列車在同一站的到發(fā)間隔時間，La為相應(yīng)的列車在區(qū)間內(nèi)的最小運(yùn)行間隔時間，同時由于M2＞M1，因此可保證取消列車與其他列車間的區(qū)間運(yùn)行間隔；公式 ⑿ 規(guī)定了同向列車在同一站出發(fā)或到達(dá)及反向列車在同一站的到達(dá)或發(fā)車需滿足先后順序；公式 ⒀ 中s及s'表示沿列車運(yùn)行方向的兩相鄰車站，即s'為s的前方相鄰站；公式 ⒁表示事件e，e'及事件f，f '分別屬于同一列車，于是公式 ⒀ 至公式 ⒁ 就保證了通向列車在區(qū)間內(nèi)不發(fā)生越行情況；公式 ⒂ 中a= (e，f)表示列車在區(qū)間的運(yùn)行或在站停站活動，對應(yīng)地，當(dāng)其表示列車在區(qū)間運(yùn)行時La表示列車在區(qū)間的最短運(yùn)行時分，當(dāng)其表示列車在車站停站時La表示列車在該站的最短停站時分。

（3）車站能力約束。發(fā)生強(qiáng)干擾條件下列車應(yīng)在車站停車等待干擾結(jié)束，因此需要考慮車站能力的限制。在某列車到達(dá)某站時，該站的停留列車數(shù)可由在此時間之前到達(dá)該站的列車總數(shù)與從該站出發(fā)的列車總數(shù)之差表示，為確定某時刻某站的剩余能力，定義車站活動a= (e，f)∈Astation表示該站某出發(fā)列車與后續(xù)到達(dá)列車之間的活動，La表示同一到發(fā)線列車出發(fā)與后續(xù)列車接入同一股道間的最小接車間隔時間。設(shè)表示列車tf在車站s的到達(dá)事件，間隔活動子集為列車tf到達(dá)車站s與同向列車te到達(dá)車站s之間的間隔活動。同理，定義車站活動子集為列車tf在車站s站出發(fā)與同方向列車te在車站s到達(dá)之間的活動。相關(guān)約束的具體表現(xiàn)形式如下。

式中：φa為0-1變量，為當(dāng)列車te在同向列車tf到達(dá)車站s之前從車站s出發(fā)時為1，否則為0；公式 ⒃ 和 公 式 ⒄ 中 的為車站s在列車tf到達(dá)之前已到達(dá)的同方向列車數(shù)量表示車站s在列車tf到達(dá)之前已發(fā)出的同方向列車數(shù)量分別為車站s的上下行到發(fā)線數(shù)量，于是公式 ⒃ 和公式 ⒄ 就保證在任意時刻任意車站至少有一條到發(fā)線可供列車tf使用為強(qiáng)干擾發(fā)生時刻；公式⒅保證同一到發(fā)線的已發(fā)出列車和后續(xù)到達(dá)列車間的最小間隔時間，La為對應(yīng)間隔時間。

（4）在途列車不可取消約束。根據(jù)我國現(xiàn)有的調(diào)度規(guī)則，在強(qiáng)干擾發(fā)生時已經(jīng)從始發(fā)站發(fā)出的列車應(yīng)安排在中間站停車等待干擾結(jié)束后繼續(xù)運(yùn)行，而尚未從始發(fā)站發(fā)出的列車可根據(jù)實際情況和強(qiáng)干擾預(yù)測持續(xù)時間由調(diào)度部門決定是否發(fā)出或取消。為此需限制已發(fā)出列車的取消。相關(guān)約束可表示為

式中：t dep為列車t在始發(fā)站的發(fā)車時刻。

（5）列車取消均衡約束。當(dāng)線路區(qū)段發(fā)生強(qiáng)干擾時，部分在強(qiáng)干擾發(fā)生時未從始發(fā)站發(fā)出的列車可能由于線路及沿途車站能力限制需要取消運(yùn)行。由于發(fā)生強(qiáng)干擾的區(qū)段僅能維持單線運(yùn)行，因此相較于取消雙方向列車，顯然取消單方向列車從線路通過能力角度更為有利。但是，由于考慮交路需要，取消單方向列車會嚴(yán)重影響運(yùn)輸秩序，甚至造成移動運(yùn)營設(shè)備周轉(zhuǎn)困難，從而進(jìn)一步擴(kuò)大運(yùn)輸秩序影響范圍與時間。因此，從實際生產(chǎn)角度考慮，在考慮取消列車時應(yīng)均衡考慮上下行方向列車?；诖?，針對上下行不同方向同種類列車構(gòu)成的集合p及p'，提出列車取消的均衡約束。

式中：公式⒇、公式(21)分別表示上下行同種類列車取消數(shù)量的差值限制，其中參數(shù)δ1，δ2分別為給定的上下行列車取消數(shù)量差值允許值，可根據(jù)實際情況設(shè)定。

（6）干擾前按圖行車約束。根據(jù)假設(shè)條件，在強(qiáng)干擾發(fā)生之前列車應(yīng)按照原有列車運(yùn)行圖運(yùn)行，由此提出干擾發(fā)生前的按圖行車約束為：

2.2 模型求解

目標(biāo)函數(shù) ⑴ 式及相應(yīng)約束條件公式 ⑵ 至公式(22)構(gòu)成一個混合整數(shù)線性規(guī)劃模型。該類問題可由商業(yè)優(yōu)化軟件在較短時間內(nèi)得到高質(zhì)量的解。根據(jù)模型特點，采用CPLEX對所提出的模型進(jìn)行求解，以便在較短的時間內(nèi)得到較高質(zhì)量的解。

3 實例分析

3.1 算例概況

以鄭西高速鐵路(鄭州東—西安北)為例，驗證模型的有效性。該線路全長538 km，區(qū)段內(nèi)始發(fā)站為鄭州、鄭州東、洛陽龍門、西安北站(跨線列車視為接入站始發(fā)列車，以簡化問題處理)，考慮到鄭州端有多個始發(fā)站且部分列車需經(jīng)由既有線轉(zhuǎn)入鄭西高速鐵路，算例以鄭州西站為實際起點，共包括車站10個，區(qū)間9個,列車運(yùn)行線125條，存在300 km/h (G類高速列車)和250 km/h(D類高速列車) 2種運(yùn)行標(biāo)尺，選取其中曹古寺—西安北的27對長途高速動車組列車運(yùn)行線為例(G類高速列車26對，D類高速列車1對)進(jìn)行驗證。鄭西高速鐵路中間站到發(fā)線數(shù)量如表1所示，各區(qū)間列車運(yùn)行時分如表2所示。

表1 鄭西高速鐵路中間站到發(fā)線數(shù)量 條Tab.1 Number of station lines of intermediate stations in Zhengzhou-Xi’an high-speed railway

3.2 計算實驗

（1）強(qiáng)干擾場景設(shè)置。由于強(qiáng)干擾類型及發(fā)生地點具有一定隨機(jī)性，因此假設(shè)強(qiáng)干擾表現(xiàn)形式為區(qū)間某方向線路中斷，同時假設(shè)發(fā)生強(qiáng)干擾區(qū)間及持續(xù)時間如表3所示。

表3中場景1表示鞏義南至洛陽龍門方向區(qū)間于10 ∶ 00起發(fā)生強(qiáng)干擾，持續(xù)時間分別為30 min、60 min，期間區(qū)間相反方向線路、信號設(shè)備運(yùn)轉(zhuǎn)正常，其他場景參照上述描述。

（2）計算結(jié)果?；赩isual Studio平臺以C語言編程實現(xiàn)所述模型，調(diào)用ILOG CPLEX12.6以內(nèi)置分支切割算法求解。相關(guān)參數(shù)設(shè)置為：對D類高速列車，取消懲罰值設(shè)為3 000，列車在站到達(dá)晚點罰數(shù)設(shè)為2，早點罰數(shù)設(shè)為1；對G類高速列車，取消懲罰者設(shè)為5 000，列車在站到達(dá)晚點罰數(shù)設(shè)為3，早點罰數(shù)設(shè)為2；事件最大允許偏離時間D設(shè)為30 min，考慮到實際調(diào)度指揮對時效性的要求，將求解時間上限設(shè)置為10 min，運(yùn)行調(diào)整結(jié)果如表4所示。

表2 鄭西高速鐵路區(qū)間運(yùn)行時分 minTab.2 Section operating time of Zhengzhou-Xi’an high-speed railway

表3 強(qiáng)干擾區(qū)間及持續(xù)時間Tab.3 Section strong interference location and duration

3.3 結(jié)果分析

根據(jù)計算結(jié)果可知，不同干擾場景對列車運(yùn)行的影響不同，模型的求解時間及目標(biāo)函數(shù)值亦不同，但各場景下模型均在短時間內(nèi)得到了快速求解，可見模型能夠滿足現(xiàn)場調(diào)度生產(chǎn)對于時效性的需要。綜合分析所得結(jié)果，得到以下結(jié)論。

（1）各場景中鞏義南至洛陽龍門區(qū)間(上下行)接近正午時刻(11 ∶ 00)、干擾時間持續(xù)較長(90 min)情境下對列車運(yùn)行的影響最為嚴(yán)重。

（2）相同區(qū)間內(nèi)干擾持續(xù)時間越長，列車運(yùn)行的影響越嚴(yán)重。

（3）算例所述干擾情境下均無列車取消，有利于移動運(yùn)輸設(shè)備的正常運(yùn)用周轉(zhuǎn)。

表4 列車運(yùn)行調(diào)整結(jié)果Tab.4 Results of rescheduling

（4）所采用模型能夠高效地求解強(qiáng)干擾條件下的列車運(yùn)行調(diào)整問題，所得結(jié)果質(zhì)量良好。

4 結(jié)束語

列車實時調(diào)度需要在短時間內(nèi)綜合各類影響列車運(yùn)行的因素，快速求得可行方案指導(dǎo)列車運(yùn)行進(jìn)行相應(yīng)調(diào)整。通過構(gòu)建強(qiáng)干擾條件下的列車運(yùn)行調(diào)整混合整數(shù)規(guī)劃模型，采用CPLEX對模型進(jìn)行求解，代替以往根據(jù)列車運(yùn)行調(diào)度的經(jīng)驗指揮，是列車運(yùn)行調(diào)度指揮智能化、自動化的重要方向，根據(jù)鄭西高速鐵路實際運(yùn)行圖數(shù)據(jù)進(jìn)行的驗證說明了模型的有效性。值得注意的是，研究假設(shè)上下行到發(fā)線分別獨(dú)立使用，并且忽略了不同進(jìn)路間的沖突，建模層面較為宏觀，同時假設(shè)強(qiáng)干擾持續(xù)時間已知，在后續(xù)研究中，應(yīng)進(jìn)一步考慮車站進(jìn)路排布約束，并考慮干擾持續(xù)時間不確定時的列車運(yùn)行調(diào)整策略[8]。