編組站堵塞情況下網(wǎng)絡(luò)車流調(diào)整疏解方案分析

李 響 上海鐵路局上海鐵路股份有限公司籌備組

曲思源 上海鐵路局調(diào)度所

郭 平 上海鐵路局辦公室

車流調(diào)整是鐵路調(diào)度工作的一項重要內(nèi)容。車流結(jié)構(gòu)及車輛分布偏離標(biāo)準(zhǔn)是日常調(diào)整的主要原因。車流結(jié)構(gòu)發(fā)生較大變化時，將造成有些線路或車站的能力緊張甚至形成堵塞。而堵塞流理論，是網(wǎng)絡(luò)流規(guī)劃理論中的非確定性、多值性研究的一個新分支，主要研究對象是網(wǎng)絡(luò)的最大流和最小流，該理論成為研究如何防止交通網(wǎng)絡(luò)堵塞的發(fā)生和在堵塞發(fā)生時如何疏散交通流的理論。本文應(yīng)用堵塞流理論研究鐵路編組站堵塞情況下的網(wǎng)絡(luò)車流的調(diào)整問題，通過防堵塞和改善堵塞控制，為鐵路網(wǎng)絡(luò)車流調(diào)整問題提供新的思路、方法，實(shí)現(xiàn)車流調(diào)整的精細(xì)、動態(tài)、集約化。

1 編組站堵塞及現(xiàn)有網(wǎng)絡(luò)車流調(diào)整分析

為確保網(wǎng)絡(luò)車流流動的有序性，在貨物列車編組計劃中，鐵路部門對各種車流規(guī)定了正常的運(yùn)行徑路，包括最短和特定徑路。為緩解編組站堵塞狀況，車流調(diào)整的一項重要措施就是改變車流運(yùn)行徑路。在日常調(diào)度指揮過程中，正常徑路因提高通過能力技術(shù)改造施工，或因?yàn)?zāi)害和重大事故中斷行車，或因車流增加以致通過能力不能負(fù)擔(dān)時，須經(jīng)過鐵道部批準(zhǔn)后，方可變更車流運(yùn)行徑路。所謂車流迂回徑路就是指在日常運(yùn)輸工作中，進(jìn)行車流調(diào)整時臨時指定的經(jīng)由線路，屬于非正常徑路。要根據(jù)迂回徑路區(qū)段通過能力和機(jī)車供應(yīng)情況，在能力可以負(fù)擔(dān)的情況下，方可實(shí)施，盡量減少對運(yùn)輸秩序的干擾。目前，針對網(wǎng)絡(luò)車流經(jīng)常、實(shí)時且不可預(yù)見的變化，遇有編組站階段性堵塞時，調(diào)度往往憑經(jīng)驗(yàn)處置，車流調(diào)整的措施仍處于粗放和定性管理階段，缺乏對車流調(diào)整的定量研究和精細(xì)、集約管理。特別是在迂回貨列數(shù)量較多時，決策不夠科學(xué)合理，運(yùn)輸效率反而下降，浪費(fèi)迂回徑路的通過能力。

2 堵塞流理論和最小車流控制的思路和方法

2.1 堵塞流理論

定義1 流出網(wǎng)絡(luò)始點(diǎn)的弧 (簡稱入流)的容量之和稱為網(wǎng)絡(luò)的入流，即

其中，F(xiàn)N為網(wǎng)絡(luò)的入流；C(α)為弧α的容量；Vi(α)為弧α的始點(diǎn)。

定義2 當(dāng)網(wǎng)絡(luò)中不存在對于可行流ζ的正向增廣路時，則稱可行流ζ為飽和流：如果該飽和流的流量小于網(wǎng)絡(luò)的入口流量，則稱該網(wǎng)絡(luò)中的飽和流ζ為堵塞流。

定義3 流量值最大的堵塞流稱為最大堵塞流，流量值最小的堵塞流稱為最小堵塞流。

定義4 所謂頂點(diǎn)A的容差φA是指所有以A為始點(diǎn)的有向弧的容量總和與所有以A為終點(diǎn)的有向弧的容量總和之差，即

式中，Vj(α)為弧α的終點(diǎn)。

定義5 網(wǎng)絡(luò)中除始點(diǎn)和終點(diǎn)外，各頂點(diǎn)的每個弧的容量小于或等于進(jìn)入該頂點(diǎn)的各弧容量之和時，該網(wǎng)絡(luò)稱為規(guī)范化網(wǎng)絡(luò)。網(wǎng)絡(luò)規(guī)范化的方法是：當(dāng)在某頂點(diǎn)存在流出弧的容量大于流入該頂點(diǎn)各弧的容量總和時，則將該流出弧的容量改為等于流入該點(diǎn)各弧的容量總和。

定義6 具有最小流量的飽和流稱為網(wǎng)絡(luò)最小流。

定理1從研究網(wǎng)絡(luò)中的堵塞現(xiàn)象來說，在規(guī)范化網(wǎng)絡(luò)中的流動情況與原網(wǎng)絡(luò)中的流動情況是一樣的。

定理2網(wǎng)絡(luò)中出現(xiàn)堵塞的必要條件是規(guī)范化網(wǎng)絡(luò)中存在負(fù)容差的頂點(diǎn)，并將其稱為結(jié)構(gòu)性堵塞點(diǎn)。

2.2 網(wǎng)絡(luò)車流最小控制思路和方法

網(wǎng)絡(luò)中的編組站堵塞實(shí)際上是有結(jié)構(gòu)和流動的隨機(jī)性和動態(tài)性造成的。編組站堵塞分為兩種情況：局部堵塞和全局堵塞。局部堵塞是指網(wǎng)絡(luò)頂點(diǎn)處的堵塞現(xiàn)象。當(dāng)這種堵塞發(fā)生時，在這些堵塞點(diǎn)及相應(yīng)的弧內(nèi)聚集過多的流量，使局部成為不可行流，這時網(wǎng)絡(luò)的總流量變小。將網(wǎng)絡(luò)的飽和流定義為堵塞流，具有最大流值的堵塞流即是網(wǎng)絡(luò)的最大流，它和經(jīng)典網(wǎng)絡(luò)流理論中的最大流是完全相同的一個概念；而具有最小流值的堵塞流（即最嚴(yán)重堵塞情況下的極值流）則定義為網(wǎng)絡(luò)的最小流。通過改變網(wǎng)絡(luò)的結(jié)構(gòu)（關(guān)閉某些弧段）防止或者減少堵塞的發(fā)生，使得網(wǎng)絡(luò)車流最小流盡可能提高。將最小流控制分為兩種，第一種最小流控制是在改變網(wǎng)絡(luò)結(jié)構(gòu)后，最終得到的新網(wǎng)絡(luò)的最大流和最小流相等，稱其為防堵塞控制，最大流可能小于結(jié)構(gòu)改變前的最大流；第二種最小流控制是在改變網(wǎng)絡(luò)結(jié)構(gòu)時，不使新網(wǎng)絡(luò)的最大流減少而盡可能提高網(wǎng)絡(luò)的最小流，稱之為改善堵塞控制。關(guān)于網(wǎng)絡(luò)的最大流和最小流的確定，主要有用標(biāo)號法計算網(wǎng)絡(luò)最大流，分支定界法、雙向增流法和圖單純形法求解網(wǎng)絡(luò)的最小流。

3 實(shí)例分析

現(xiàn)模擬上海局阜陽北和符離集站接入到喬司站及其以遠(yuǎn)重車流的調(diào)整實(shí)例并加以分析，簡化的規(guī)范化網(wǎng)絡(luò)圖由兩個始點(diǎn)和一個終點(diǎn)組成，如圖1所示。s，v1，v2，v3，v4，v5，v6，t分別代表虛擬源點(diǎn)、阜陽北、符離集、合肥東、蚌埠東、蕪湖東、南京東、喬司站。其中，除符離集站為區(qū)段站外，其余均為編組站；s-v2-v4-v6-s通常稱為一通道，s-v1-v3-v5-s為二通道，車流調(diào)整需要一、二通道的配合才能完成；v1v2、v3v4、v5v6 為兩個通道的聯(lián)絡(luò)線，三條聯(lián)絡(luò)線均為單線，通過能力緊張，需要妥善安排車流迂回徑路和列車數(shù)量，車流調(diào)整的方向圖1中已標(biāo)出；弧上的數(shù)字表示(fü，cü)，其中 fü表示由節(jié)點(diǎn)i到j(luò)的流量（單位為：貨物列車列數(shù)目），cü表示由節(jié)點(diǎn)i到j(luò)的容量。目前，因一通道是客運(yùn)通道，主要運(yùn)行旅客列車，需要將部分貨流調(diào)整到二通道；二通道從阜陽北到喬司站全長660 km，是該重車流調(diào)整的主要通道。二通道在路局運(yùn)輸結(jié)構(gòu)中占據(jù)十分重要的地位，沿途五個編組站均不同程度的存在等開情況較多，日常運(yùn)輸組織中不僅要保持二通道的暢通，還要對存在的問題需要進(jìn)一步調(diào)整和優(yōu)化，降低運(yùn)輸成本，提高運(yùn)輸效率。

問題是如何妥善安排一、二通道車流，合理安排好聯(lián)絡(luò)線的使用，達(dá)到車流精細(xì)調(diào)整的目的，確保編組站堵塞情況下網(wǎng)絡(luò)車流的通過能力最大。

圖1 網(wǎng)絡(luò)車流簡化示意圖

用最大流問題的標(biāo)號算法求得最大流Fmax=16（見圖2），用最小流問題的分枝定界法求得最小流Fmin=13（見圖3）。其中，各節(jié)點(diǎn)旁（）內(nèi)數(shù)字表示該節(jié)點(diǎn)的容差，下同。

圖2 網(wǎng)絡(luò)最大流

圖3 網(wǎng)絡(luò)最小流

4.1 防堵塞控制

防堵塞控制只要存在最大堵塞截面，找到堵塞截面上的反向弧就關(guān)閉，停止條件是網(wǎng)絡(luò)最大流與最小流相等。

圖3中堵塞的路段為 v2v4，v3v4，v5v6，v5t，其中 v3v4 和 v5v6 為反向弧。因此，首先考慮關(guān)閉v3v4，其最大流F1max=13，用最小流的分支定界法求得擴(kuò)容后的最小流F1min=13（見圖4）；在考慮關(guān)閉v5v6，其F2max=15，可求得最小流F2min=15（見圖5）；同時關(guān)閉v3v4和v5v6，可求得最小流F3max=F3min=13（見圖 6）。

圖4 關(guān)閉 后的網(wǎng)絡(luò)最小流

圖5 關(guān)閉 后的網(wǎng)絡(luò)最小流

圖6 關(guān)閉 、后的網(wǎng)絡(luò)最大流及最小流

可見，關(guān)閉v5v6后的最小流值最大。圖6中所示的網(wǎng)絡(luò)中，只要從源點(diǎn)s流出的流量不大于13，因?yàn)榫W(wǎng)絡(luò)中最大流與最小流相等，所以網(wǎng)絡(luò)盡管存在堵塞截面，但網(wǎng)絡(luò)不可能再發(fā)生因隨機(jī)流動造成的堵塞，這是車流網(wǎng)絡(luò)也可以稱為"動態(tài)均衡"網(wǎng)絡(luò)，可將13作為網(wǎng)絡(luò)車流調(diào)整的閾值。當(dāng)從源點(diǎn)s流出的流量正好為13時，盡量不采取改變車流徑路的措施（圖4）。存在迂回徑路，主要是因?yàn)楣?jié)點(diǎn)容差存在0的情況，最小完全截集有多解。當(dāng)從源點(diǎn)s流出的流量大于13時，網(wǎng)絡(luò)車流就會不同程度的發(fā)生堵塞現(xiàn)象，就要根據(jù)源點(diǎn)流入車流量的情況，相應(yīng)采取改變車流徑路的措施調(diào)整好相關(guān)車流，確保網(wǎng)絡(luò)通過能力最大。

4.2 改善堵塞控制

改善堵塞控制要求反向弧關(guān)閉必須滿足，該反向弧關(guān)閉后的網(wǎng)絡(luò)最大流等于該反向弧關(guān)閉前的網(wǎng)絡(luò)最大流。停止條件是：當(dāng)存在堵塞截面，卻找不到這樣的反向弧，該弧的關(guān)閉不影響網(wǎng)絡(luò)的最大流。

若采取改善堵塞控制措施，不能同時關(guān)閉v3v4和v5v6，因?yàn)殛P(guān)閉后的最小流值及關(guān)閉v3v4后的最小流值均比單獨(dú)關(guān)閉v5v6后最小流值小，所以應(yīng)當(dāng)關(guān)閉v5v6，在盡量確保原網(wǎng)絡(luò)最大流的基礎(chǔ)上得到網(wǎng)絡(luò)改善堵塞控制措施。

5 結(jié)束語

本文借鑒堵塞流理論，根據(jù)網(wǎng)絡(luò)車流需求提供結(jié)構(gòu)上的冗余，對編組堵塞情況的車流調(diào)整迂回徑路問題做了較為深入的研究，克服經(jīng)驗(yàn)決策，為車流調(diào)整問題提供的理論依據(jù)，確保編組站堵塞情況下車流組織的動態(tài)、集約和精細(xì)化，提高運(yùn)輸組織效率。同時，也是將復(fù)雜問題進(jìn)行簡單化處理的一種嘗試。但鑒于網(wǎng)絡(luò)隨時間變化的時變性，車流調(diào)整問題變得的更為復(fù)雜，時變網(wǎng)絡(luò)的車流調(diào)整問題有待深入研究。