基于網(wǎng)絡(luò)可控性的地鐵客流控制站點(diǎn)識別研究

吳開信，吳子航，馮家匯

（1.五邑大學(xué) 軌道交通學(xué)院，廣東 江門 529020；2.深圳地鐵運(yùn)營集團(tuán)有限公司，廣東 深圳 518040）

地鐵在優(yōu)化城市空間布局、緩解道路交通擁堵、改變居民出行方式等方面發(fā)揮了重要的作用，已成為城市居民出行的首選，但在北上廣深等一線城市早晚高峰期，地鐵有限的運(yùn)輸能力與迅猛增長的客流需求之間的矛盾日漸突出，給車站運(yùn)營和乘客安全帶來了嚴(yán)重挑戰(zhàn).對部分站點(diǎn)實(shí)施客流控制，使其服務(wù)水平保持在合理的范圍之內(nèi)是城軌系統(tǒng)高峰期采取的常見措施之一.控流方案的制定主要是基于對客流時(shí)空特征的分析，從單個(gè)站點(diǎn)[1-2]、整條線路[3-4]、關(guān)聯(lián)網(wǎng)絡(luò)[5-6]等角度對站點(diǎn)選擇、控流時(shí)間、控流強(qiáng)度等指標(biāo)進(jìn)行優(yōu)化，這種采取優(yōu)化模型的方法在遇到大規(guī)模問題時(shí)，需要以較大的計(jì)算代價(jià)來獲得問題的滿意解，其控流效果有待提升.

地鐵運(yùn)營線路和客流加載過程可用賦權(quán)的復(fù)雜網(wǎng)絡(luò)描述，而目前網(wǎng)絡(luò)科學(xué)與工程的研究對象集中于隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)，多基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)的脆弱性、魯棒性、可靠性等結(jié)構(gòu)特性進(jìn)行研究，將控制理論與網(wǎng)絡(luò)科學(xué)相結(jié)合的研究起步較晚，且其中的控制策略也由傳統(tǒng)控制理論中的蜂擁控制轉(zhuǎn)到現(xiàn)在的牽制控制[7].Kalman[8]指出，一個(gè)動(dòng)態(tài)系統(tǒng)只需找到合適的驅(qū)動(dòng)節(jié)點(diǎn)集并加以控制，就能從初始狀態(tài)到達(dá)任意理想狀態(tài).Liu等[9-10]首次將線性時(shí)不變系統(tǒng)的可控性應(yīng)用于網(wǎng)絡(luò)控制，并提出復(fù)雜網(wǎng)絡(luò)控制中心分布取決于網(wǎng)絡(luò)的度分布.Meng[11]基于改進(jìn)的LB模型研究了鐵路列車服務(wù)網(wǎng)絡(luò)在出現(xiàn)應(yīng)急情況下的可控性問題，但對網(wǎng)絡(luò)節(jié)點(diǎn)和邊權(quán)等屬性特征的探討不夠深入.綜上，既有文獻(xiàn)大多是基于復(fù)雜網(wǎng)絡(luò)的物理結(jié)構(gòu)、側(cè)重于網(wǎng)絡(luò)特性指標(biāo)分析，從系統(tǒng)可控性角度提出網(wǎng)絡(luò)控制方法和應(yīng)對策略并應(yīng)用于實(shí)際的文獻(xiàn)較少；另外，既有研究的網(wǎng)絡(luò)多數(shù)是靜態(tài)網(wǎng)絡(luò)，對節(jié)點(diǎn)之間的交互作用和時(shí)效特征等缺乏考慮.選擇合適的站點(diǎn)進(jìn)行客流控制有利于提高城軌系統(tǒng)高峰期客流時(shí)空分布均衡度和運(yùn)力資源的有效利用率，本文基于網(wǎng)絡(luò)可控性原理采取定量分析方法，從有向網(wǎng)絡(luò)結(jié)構(gòu)特性分析入手，綜合考慮各車站客流狀態(tài)及其動(dòng)態(tài)變化過程，以有效識別客流控制站點(diǎn)的個(gè)數(shù)與具體站點(diǎn).

1 模型的構(gòu)建

1.1 有向客流網(wǎng)絡(luò)的動(dòng)力學(xué)建模

根據(jù)地鐵物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及客流特性，構(gòu)建有向網(wǎng)絡(luò)圖G=（V,E），圖中節(jié)點(diǎn)集V=｛v1,v2,…,vi,…,vj,…,vN｝對應(yīng)于車站集 ｛1,2,…,i,…,j,…,N｝，如果從車站i去往車站j存在客流量，則連接一條有向弧E（vi,vj）.定義網(wǎng)絡(luò)中幾個(gè)指標(biāo)：節(jié)點(diǎn)vi的度是0-1變量，當(dāng)nij=1時(shí)，表示E（vi,vj）存在，否則表示不存在；度的值反映了網(wǎng)絡(luò)節(jié)點(diǎn)之間的可達(dá)性，值越大說明乘客有更多的出行路徑選擇.網(wǎng)絡(luò)平均路徑長度表示i站和j站之間的最短路徑距離，L反映了從車站i去往車站j平均經(jīng)過的車站數(shù)，是網(wǎng)絡(luò)連通性的一個(gè)指標(biāo).pij（t）分別表示t時(shí)刻i站的進(jìn)站乘客數(shù)、出站乘客數(shù)以及從i站去往j站的乘客數(shù).由于高峰期常態(tài)大客流通常以通勤通學(xué)為目的，乘客起訖點(diǎn)相對固定，的值可由AFC實(shí)時(shí)數(shù)據(jù)統(tǒng)計(jì)分析獲得，設(shè)為常數(shù).考慮地鐵對居民職住地選擇和通勤出行行為的影響，本文利用在路網(wǎng)規(guī)劃中常用的基于旅客空間相互作用的重力模型對pij（t）進(jìn)行估計(jì)，即：

大多數(shù)復(fù)雜網(wǎng)絡(luò)雖然具有非線性特征，但是在結(jié)構(gòu)上與線性系統(tǒng)有相似性質(zhì)[9].假設(shè)對限流的時(shí)間段進(jìn)行細(xì)分，在一個(gè)充分小的Δt時(shí)間段內(nèi)，系統(tǒng)參數(shù)不隨時(shí)間的變化而變化，則客流網(wǎng)絡(luò)系統(tǒng)可用線性時(shí)不變動(dòng)力系統(tǒng)微分方程表示為：

模型具有線性和時(shí)不變性兩個(gè)特征，向量x（t）=（x1（t）,x2（t）,…,xN（t））T表示t時(shí)刻網(wǎng)絡(luò)內(nèi)各車站的客流狀態(tài)，xi（t）可看作車站i實(shí)際客流強(qiáng)度；A=（aij（t） ）N×N為基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的客流轉(zhuǎn)移矩陣，其中aij（t）≠ 0 表示網(wǎng)絡(luò)圖中存在從節(jié)點(diǎn)vj指向節(jié)點(diǎn)vi的邊，其值表示站間的客流轉(zhuǎn)移情況；式（2）刻畫了Δt時(shí)間段內(nèi)客流變化過程.

在［t,t+Δt］區(qū)間內(nèi)，若存在一個(gè)分段連續(xù)的輸入u（t），使系統(tǒng)由初始狀態(tài)x（t）轉(zhuǎn)移到期望狀態(tài)x（t+Δt），則稱系統(tǒng)在此狀態(tài)是可控的.若所有狀態(tài)皆可控，則稱系統(tǒng)可控.高峰時(shí)段的客流分布和運(yùn)能之間通常不匹配，若以外界實(shí)施的控流措施作為輸入條件，則控流效果可表示為：

其中，輸入矩陣B=（bij（t） ）N×M表示t時(shí)刻被選擇進(jìn)行客流控制的M（M≤N）個(gè)車站；輸入信號u（t）=若t時(shí)刻j站限流，則取b（t）=1 （i=j），否則為0；u（t）為j ijj站的控流強(qiáng)度.

1.2 客流網(wǎng)絡(luò)可控性分析

在有向網(wǎng)絡(luò)中，帶有控制輸入的節(jié)點(diǎn)為控制節(jié)點(diǎn)，只有單一輸入的控制節(jié)點(diǎn)為驅(qū)動(dòng)節(jié)點(diǎn)，如果從控制節(jié)點(diǎn)到狀態(tài)節(jié)點(diǎn)至少存在一條鏈，則稱此狀態(tài)節(jié)點(diǎn)為被控節(jié)點(diǎn).系統(tǒng)可控情形下，輸入信號可通過某條路徑到達(dá)所有的節(jié)點(diǎn).基于系統(tǒng)可控性優(yōu)化主要解決兩個(gè)問題：最少需要多少驅(qū)動(dòng)節(jié)點(diǎn)數(shù)Nd使系統(tǒng)可控；如何進(jìn)行驅(qū)動(dòng)節(jié)點(diǎn)的選擇以使控制效果更好.

文獻(xiàn)[8]提出，線性系統(tǒng)完全可控的充分必要條件是由A和B構(gòu)成的 Kalman判別矩陣c的行秩是滿秩，即滿足：

以圖1的網(wǎng)絡(luò)為例，在圖1-a中：

圖1 有向網(wǎng)絡(luò)可控性判別

此時(shí)rank（c）=4，網(wǎng)絡(luò)可控.而圖1-b中 rank（c）=3＜4，網(wǎng)絡(luò)處于不可控狀態(tài).

文獻(xiàn)[9]提出了網(wǎng)絡(luò)可控性與最大匹配相關(guān)聯(lián)的最小輸入理論，即控制一個(gè)有向網(wǎng)絡(luò)所需的最少輸入數(shù)量(驅(qū)動(dòng)節(jié)點(diǎn)數(shù))等于二分圖的最大匹配中未匹配節(jié)點(diǎn)數(shù)量.若存在完全匹配，則最少驅(qū)動(dòng)點(diǎn)Nd=1；如果不存在完全匹配，則Nd為網(wǎng)絡(luò)最大匹配集所對應(yīng)的未匹配節(jié)點(diǎn)的個(gè)數(shù).

本文將地鐵客流控制站點(diǎn)的識別問題轉(zhuǎn)化為：如何從網(wǎng)絡(luò)中找出有限個(gè)驅(qū)動(dòng)節(jié)點(diǎn)，使不可控網(wǎng)絡(luò)轉(zhuǎn)化為可控網(wǎng)絡(luò).基于以上分析，可采取如下思路：將圖G（V,E）轉(zhuǎn)化為二分圖，節(jié)點(diǎn)vi分為由此構(gòu)成兩個(gè)不同的節(jié)點(diǎn)集邊集E=設(shè)M為二分圖邊集的一個(gè)子集，若M中的任意兩條邊都沒有公共的起點(diǎn)和終點(diǎn)，則稱M是一個(gè)匹配，如果一個(gè)節(jié)點(diǎn)是M中的一條邊的終點(diǎn)，則該節(jié)點(diǎn)就是匹配節(jié)點(diǎn)，否則為非匹配節(jié)點(diǎn)，非匹配節(jié)點(diǎn)即為驅(qū)動(dòng)節(jié)點(diǎn).網(wǎng)絡(luò)的所有邊沒有共享的頭節(jié)點(diǎn)或尾節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)達(dá)到最大匹配.圖2給出了圖1-b所示網(wǎng)絡(luò)到二分圖之間的映射關(guān)系，根據(jù)最大匹配原理求得非匹配節(jié)點(diǎn)為｛v1,v4｝.對非匹配節(jié)點(diǎn)（驅(qū)動(dòng)節(jié)點(diǎn)）給予相同數(shù)量的輸入信號，可實(shí)現(xiàn)對整個(gè)網(wǎng)絡(luò)的有效控制.

圖2 網(wǎng)絡(luò)到二分圖的映射關(guān)系

從示例可以看出，系統(tǒng)可控與否主要取決于其拓?fù)浣Y(jié)構(gòu)和外界輸入條件，但在實(shí)踐運(yùn)用中會(huì)遇到以下問題：1）對于簡單有向網(wǎng)絡(luò)，可以利用枚舉法通過不斷添加和判斷兩個(gè)過程尋找最少控制點(diǎn)，計(jì)算其復(fù)雜度為2N-1，對于大型網(wǎng)絡(luò)此方法在理論上可行，實(shí)際卻不可行；2）由于客流是動(dòng)態(tài)變化的，aij（t）的實(shí)時(shí)數(shù)據(jù)具有滯后性，只能取得近似值.針對以上兩種情形，本文進(jìn)一步提出優(yōu)化算法.

2 基于最小驅(qū)動(dòng)點(diǎn)集的控流車站識別優(yōu)化方法

由于在地鐵網(wǎng)絡(luò)高峰期，不同線路、同一線路的上下行方向以及線路各斷面之間會(huì)存在客流空間分布不均衡現(xiàn)象；另外由前面分析可知，客流的實(shí)時(shí)精確數(shù)據(jù)難以獲得.為了解決問題的主要矛盾，針對有向弧上的流量引入閾值q0，基于q0對初始網(wǎng)絡(luò)矩陣中的有向弧進(jìn)行刪減，當(dāng)pij≥q0時(shí)，取aij（t）=pij（t），保留弧E（vi,vj）；當(dāng)pij（t）＜q0時(shí)，取aij（t）=0，剔除弧E（vi,vj），將初始網(wǎng)絡(luò)轉(zhuǎn)化為骨干網(wǎng)絡(luò).

當(dāng)r ank （c）=ra nk （B,AB,A2B,…,AN-1B） ＜N時(shí)，說明系 統(tǒng)處 于不可 控狀 態(tài)，此 時(shí)添 加新的 虛 擬輸入節(jié)點(diǎn)vk，連接有向弧E（vi,vk），新系統(tǒng)的輸入-輸出模型可定義為：

其中B'=（Ek），Ek為單位矩陣的第k列的列向量，u'（t）為新增的輸入信號.令 r ank （c'）=rank([B,B'],A[B,B'],A2[B,B'],…,AN-1[B,B'])，稱f（i）=ra nk(c')-r ank（c）為節(jié)點(diǎn)vi的控制能力.若f（i）≠ 0，則稱節(jié)點(diǎn)vk的添加為節(jié)點(diǎn)vi的有效添加，否則為無效添加.遍歷vk的所有有效添加的節(jié)點(diǎn)，稱max{f(i)i=1,2,…,N}對應(yīng)的連接為節(jié)點(diǎn)vk的最優(yōu)連接.

具體算法如下：

步驟1：構(gòu)造骨干網(wǎng)絡(luò)矩陣A.

步驟2：對化簡后的骨干網(wǎng)絡(luò)求最小驅(qū)動(dòng)點(diǎn)集.

1）初始化，令S=0,U=[ ],b=[ ],v={}.計(jì)算節(jié)點(diǎn)vi（i=1,2,…,N）的控制能力f（i），按值的降序?qū)?jié)點(diǎn)進(jìn)行排列.

2）添加新的輸入節(jié)點(diǎn)vk，按下列規(guī)則尋找最優(yōu)連接：若vk是關(guān)于某節(jié)點(diǎn)的無效添加，則考慮下一個(gè)點(diǎn)，直至找到所有有效添加節(jié)點(diǎn)集合，選擇vk的最優(yōu)連接E（vi,vk）.此時(shí)有：S=vi,U=

3）循環(huán)，直到所有添加的輸入節(jié)點(diǎn)都找到最優(yōu)連接.

4）終止條件：判別矩陣行秩為滿秩.

高峰期客流控制時(shí)間設(shè)為[0,T]，將其等分成長度為δ的個(gè)小時(shí)間段，滿足=T.在每個(gè)δ時(shí)間段內(nèi)，依據(jù)本文提出的算法對控制站點(diǎn)進(jìn)行識別，重復(fù)上述過程，可得出整個(gè)高峰時(shí)段的最優(yōu)控流策略.由于車站客流強(qiáng)度是時(shí)間的函數(shù)，因此，控流車站的選擇在實(shí)施過程中也是一個(gè)動(dòng)態(tài)的過程.

3 算例實(shí)驗(yàn)

深圳地鐵目前已運(yùn)營線路共設(shè)有283座車站，為減少問題復(fù)雜度，本文以客運(yùn)量較大的3號線為例.3號線全長42 km，共30座車站，采用6節(jié)編組的B型地鐵列車，早晚高峰期列車追蹤間隔時(shí)間已縮減至150 s，區(qū)間最高運(yùn)營速度85 km/h.某4個(gè)連續(xù)工作日18:30到18:45實(shí)測15 min斷面客流分布如圖3所示，沿線潮汐客流特征明顯，小時(shí)客流不均衡系數(shù)和區(qū)間斷面客流不均衡系數(shù)皆較大，其下行方向部分區(qū)間擁擠度峰值高達(dá)121%.

圖3 晚高峰斷面客流分布

根據(jù)換乘節(jié)點(diǎn)所通過線路的條數(shù)，針對所有換乘節(jié)點(diǎn)，添加相應(yīng)個(gè)數(shù)相關(guān)聯(lián)的虛擬節(jié)點(diǎn)，以表示線網(wǎng)間存在的客流轉(zhuǎn)換關(guān)系.基于沿線各站進(jìn)出的平均數(shù)據(jù)及站間距離，依據(jù)式（1）估計(jì)出晚高峰15min內(nèi)客流OD數(shù)據(jù)，可得狀態(tài)矩陣：

取車站日均客流量15 min內(nèi)的平均值為閾值(q0=0.0213)，算得骨干矩陣為：

根據(jù)Kalman可控性判別條件可知系統(tǒng)處于不可控狀態(tài)，主要原因在于：當(dāng)q0的值逐漸增大時(shí)，骨干網(wǎng)絡(luò)中有向弧逐漸減少，許多點(diǎn)會(huì)變成孤立點(diǎn)，對應(yīng)的驅(qū)動(dòng)節(jié)點(diǎn)數(shù)也將隨之增多；其次，該線路有11個(gè)換乘節(jié)點(diǎn)，由最大匹配理論可知，換乘節(jié)點(diǎn)周圍的不匹配節(jié)點(diǎn)較多，所需驅(qū)動(dòng)節(jié)點(diǎn)的數(shù)量不夠.

根據(jù)本文提出的搜索算法，當(dāng)添加的輸入節(jié)點(diǎn)達(dá)到7個(gè)及以上時(shí)，系統(tǒng)處于可控狀態(tài)，此時(shí)限流車站達(dá)到 23%以上，路網(wǎng)在可控狀態(tài)下的最優(yōu)連接，即最小控流車站集合為{蓮花村、老街、曬布、翠竹、田貝、布吉、六約}，這與該線路目前常態(tài)化限流車站的站點(diǎn)數(shù)量和實(shí)際站點(diǎn)基本吻合.

4 結(jié)論

本文結(jié)合圖論和系統(tǒng)可控性原理研究了地鐵高峰期客流控制站點(diǎn)的選擇問題，給出了網(wǎng)絡(luò)可控與否的判別方法，針對不可控情形，基于節(jié)點(diǎn)的控制能力提出最小驅(qū)動(dòng)節(jié)點(diǎn)集合的搜索算法，算例驗(yàn)證了算法的合理性和有效性.

本文對客流控制只作了宏觀方面的研究，具體的控流強(qiáng)度和控流措施沒有涉及；在將原始客流網(wǎng)絡(luò)轉(zhuǎn)化為骨干網(wǎng)絡(luò)時(shí)，閾值的選取也帶有一定的主觀性；另外，驅(qū)動(dòng)節(jié)點(diǎn)數(shù)目與節(jié)點(diǎn)的度分布之間的關(guān)系值得進(jìn)一步探討.這三個(gè)方面在今后的地鐵客流控制量化分析中再作深入研究.