白廣爭,郭 進*,石紅國,楊 揚,張?zhí)?/p>

(西南交通大學a.信息科學與技術(shù)學院;b.交通運輸與物流學院,成都610031)

基于離站時刻協(xié)調(diào)的地鐵換乘站列車銜接優(yōu)化研究

白廣爭a,郭 進*a,石紅國b,楊 揚a,張?zhí)╝

(西南交通大學a.信息科學與技術(shù)學院;b.交通運輸與物流學院,成都610031)

通過協(xié)調(diào)城市軌道交通網(wǎng)絡中換乘站各方向列車的離站時刻,實現(xiàn)減小旅客的換乘等待時間.分析了多條線路以不同形式相交情況下?lián)Q乘站列車的到發(fā)接續(xù)關(guān)系,得出換乘接續(xù)方向總數(shù)的計算公式.在此基礎上,以協(xié)調(diào)時段內(nèi)各個換乘接續(xù)方向上所有換乘旅客總等待時間最少為目標建立了模型.結(jié)合丟棄法,設計針對模型的簡單遺傳算法(SGA).最后,以兩線路相交為例做模型驗證,并根據(jù)設計的算法求解,得出部分優(yōu)化解.計算結(jié)果表明,文中模型能有效減少旅客換乘等待時間.本研究可為網(wǎng)絡化運行條件下列車開行方案的制定及優(yōu)化調(diào)整提供支持.

城市交通;換乘銜接優(yōu)化;簡單遺傳算法;換乘站;協(xié)調(diào)模型

1 引 言

換乘站是旅客在相交線路間進行換乘的場所,是軌道交通網(wǎng)絡中的節(jié)點,決定著網(wǎng)絡客流的流暢度.另外,旅客在換乘站滯留時間的長短直接影響旅客出行時間及企業(yè)提供的服務水平.因此,提高換乘效率,對城市軌道交通網(wǎng)絡化運營發(fā)展有重要意義.然而,當換乘站建成以后,換乘站站臺大小、換乘通道數(shù)及換乘方式等都已基本確定,這些因素決定了車站的最大換乘能力,在此基礎上,只有合理進行行車組織,加強線路間的運營協(xié)調(diào)性,才能達到提高換乘效率的目的.

為了使線路輸送到換乘站的換乘客流快速被接續(xù)線列車運走,以減小旅客的換乘等待時間,需要對各線路上下行方向列車的離站時刻進行協(xié)調(diào),使換乘接續(xù)方向上列車能夠達到良好的接續(xù)關(guān)系[1-5].但是,由于換乘站存在多種換乘接續(xù)關(guān)系[6],其客流輸送線同時承擔著客流接續(xù)線的角色,且要考慮客流的到達分布等因素,因而,要使得各個方向的換乘客流接續(xù)同時達到最優(yōu)很難實現(xiàn).只有根據(jù)“按流開車”的行車組織理念,結(jié)合客流的實際特征,通過協(xié)調(diào),使所有乘客的換乘等待時間總和最小,這樣才能達到優(yōu)化的目的.

本文首先分析了一個換乘站中所有存在的換乘接續(xù)方向數(shù)的計算方法,然后對單個換乘站各方向列車的發(fā)車時刻進行協(xié)調(diào),再以站內(nèi)換乘乘客總候車時間最小為目標建立模型,最后設計簡單遺傳算法,并做實例驗證.

2 換乘站換乘接續(xù)計算

乘客在換乘站從一條線路的某個方向,換乘到另一條線路的某個方向,這就形成了一個接續(xù)方向.設存在n條線路在換乘站相交,同一線路的上、下行之間不形成換乘關(guān)系,則換乘站共存在的換乘接續(xù)方向數(shù)分兩種情況計算.

(1)換乘站為n條線路的中間站.

每條線路分為上行和下行兩個方向,每條線路需要和另外(n-1)條線路的上下行產(chǎn)生雙向的換乘關(guān)系,由此,可通過式(1)描述換乘站共產(chǎn)生的換乘接續(xù)方向數(shù)f1.

(2)換乘站為n1條線路的中間站,為(n-n1)條線路的終端站.

當換乘站作為一條線路的終端站時,該線路缺少了某一方向的客流輸送能力和另一方向的客流接收能力,造成接續(xù)關(guān)系減少2×[2×(n-1)]個,而這樣的線路存在n1條.由此,得出換乘站共存在換乘接續(xù)方向數(shù)f2如式(2).

3 換乘站列車離站時刻協(xié)調(diào)模型

列車在相交線路中各自采取均衡行車的方法運行,形成穩(wěn)定的“銜接周期”[2],即當銜接方向上的兩條線路的列車行車間隔固定時,分別為h1和h2,則該兩條線路以lcm(h1,h2)為周期形成銜接關(guān)系.文獻[2]即以“銜接周期”內(nèi)旅客總換乘候車時間最短為目標.但是,在實際運營過程中,每趟列車帶來的換乘旅客量各不相同,旅客在每個“銜接周期”內(nèi)的到站量分布并不一定相同,因此,在一個“銜接周期”內(nèi)換乘旅客總等待時間最少并不能代表在其他“銜接周期”內(nèi)的換乘旅客總等待時間也最少.鑒于此,為了保證模型的普適性,本文以整個協(xié)調(diào)時段內(nèi)所有旅客的換乘總等待時間最少為優(yōu)化目標建立模型.

3.1 條件假設

設所協(xié)調(diào)時段為[ta,tb],為了降低問題復雜度,對運行條件作如下假設:

(1)線路上、下行列車獨立運行,各自到達及離開換乘站的時刻相互沒有制約關(guān)系.

(2)旅客均能乘上所遇到的第一趟換乘列車,不會因為擁擠而錯過,即運能是充足的.

(3)協(xié)調(diào)時段內(nèi),同一線路的同一方向上列車等間隔運行.

(4)同一線路的上、下行之間不產(chǎn)生換乘關(guān)系.

3.2 符號說明

為了方便問題描述,對運行過程中的參數(shù)作如下符號說明.

n——經(jīng)過換乘站的線路數(shù).

Rij——線路i的j方向,j=1,2.其中j=1表示上行;j=2表示下行;i=1,2,…,n.

Lij——[ta,tb]內(nèi)Rij上各列車駛離換乘站的時刻集合.

Dij——[ta,tb]內(nèi)Rij上各列車在換乘站的停站時間集合.

Aij——[ta,tb]內(nèi)Rij上各列車到達換乘站的時刻集合.

hij——[ta,tb]內(nèi)Rij上各列車的行車間隔.

M——[ta,tb]內(nèi)換乘站所有接續(xù)關(guān)系集合.即M={Rij→Rpq｜i≠p;i,p∈{1,2,…,n};j,q∈{1,2}}.

3.3 離站時刻協(xié)調(diào)模型

模型建立過程中,首先確定與換乘站相關(guān)的列車運行基本參數(shù),包括到站時刻及離站時刻的表示及相關(guān)約束;然后計算一種換乘接續(xù)關(guān)系下所有旅客的換乘等待時間;最后得出換乘站中所有換乘旅客的等待時間表達式,并以此值最小作為模型的目標.

3.3.1 換乘站列車到發(fā)關(guān)系分析

在所協(xié)調(diào)時段[ta,tb]內(nèi),由于列車的行車間隔hij保持不變,因此,對于線路i的j方向上各列車在換乘站的離站時刻可以根據(jù)時段內(nèi)第一趟列車的離站時刻確定,如式(3)所示:

式(3)中nij滿足如下約束:根據(jù)式(3)知,決定了協(xié)調(diào)時段內(nèi)線路i的j方向上后續(xù)列車的離站時刻.列車發(fā)車的周期性使得對于的取值只需探討在一個行車間隔[ta,ta+hij)內(nèi)的分布即可,即滿足式(5)約束.

根據(jù)線路i的j方向列車的離站時刻集合Lij和列車停站時間集合Dij,可以確定列車的到站時刻集合Aij,如式(6)所示:

在平行運行圖中,停站時間Dij根據(jù)高峰小時客流量大小計算設定.通過以上分析可知,各基本運行參數(shù)均可以由協(xié)調(diào)時段內(nèi)各方向第1趟列車離開換乘站的時刻表示,因此,換乘站列車的換乘協(xié)調(diào)可轉(zhuǎn)化為針對時段內(nèi)各方向第1趟列車的離站時刻協(xié)調(diào). 3.3.2 換乘接續(xù)關(guān)系分析

以協(xié)調(diào)時段內(nèi)旅客由線路i的j方向第y趟列車向線路p的q方向第x趟列車換乘為研究對象.該接續(xù)方向能否銜接成功由與決定.要建立這種換乘接續(xù)關(guān)系,旅客由線路i的j方向第y趟列車下車,走行至線路p的q方向站臺的時刻(+應不晚于線路p的q方向第x趟列車的離站時刻,且晚于第x-1趟列車的離站時刻,如式(7)所示.根據(jù)線路中行車間隔約束,得出式(8).

式(9)求得一名旅客產(chǎn)生的換乘候車時間.該對列車y→x共產(chǎn)生名換乘旅客,且在該接續(xù)方向上,協(xié)調(diào)時段內(nèi)有多趟輸送車和接續(xù)車形成接續(xù)關(guān)系,由此,可以求得在協(xié)調(diào)時段內(nèi)該接續(xù)方向上所有換乘乘客產(chǎn)生的候車時間,如式(10)所示:

3.3.3 換乘站總候車時間計算

以上討論了在協(xié)調(diào)時段內(nèi)一個換乘接續(xù)方向上所有換乘旅客候車時間的計算方法.根據(jù)第1節(jié)的分析,一個換乘站通常存在多個換乘接續(xù)方向.為了使換乘站換乘協(xié)調(diào)總體得到優(yōu)化,需要對換乘站內(nèi)所有接續(xù)方向旅客總候車時間進行計算,如式(11)所示:

換乘站列車到站時刻的協(xié)調(diào)目標即為使本站所有換乘旅客等待時間最小.由此,得出模型的目標函數(shù)F如式(12)所示:

根據(jù)以上分析,式(3)～式(12)共同構(gòu)成換乘站列車離站時刻協(xié)調(diào)優(yōu)化模型,其中式(12)為模型的目標函數(shù),其余各式分別描述了各參數(shù)之間的關(guān)系及相關(guān)約束.

4 算法設計

由于模型中可行解空間非常大,涉及參數(shù)較多,如果對解空間進行枚舉,尋找最優(yōu)解的效率較低,因此,設計算法進行模型求解是必要的.

在優(yōu)化求解算法中,遺傳算法理論和方法較為完善,以模式定理為支撐的簡單遺傳算法(SGA)在應用領(lǐng)域取得了比較好的效果,本模型采用SGA求解,算法具體設計過程如下.

4.1 編碼

采用二進制編碼方式,編碼對象為協(xié)調(diào)時段內(nèi)各方向初始列車在換乘站的離站時刻.編碼的總長度L由的取值范圍及經(jīng)過換乘站的線路數(shù)量確定,其中取值范圍參見模型中式(5)約束.

4.2 生成初始種群

利用計算機隨機產(chǎn)生規(guī)模為M的初始種群.為了提高初始種群的質(zhì)量,對隨機產(chǎn)生的個體進行篩選,避免不符合約束條件的個體進入初始種群中.M的取值通常根據(jù)模型解空間的大小確定.當解空間較大時,M的取值也相應較大;反之,M的取值較小.一般M取值范圍為200～1 000.

4.3 確定適應度函數(shù)

適應度函數(shù)用于判斷個體優(yōu)劣的程度,為非負數(shù).一般適應度函數(shù)值與個體優(yōu)劣呈正相關(guān)關(guān)系,考慮文中模型目標函數(shù)為求最小值,因此可以以目標函數(shù)的倒數(shù)作為適應度函數(shù)f,如式(13),式中F為目標函數(shù)式(12).

另外,對于不滿足模型中約束條件的個體,將其適應度值設置為0,阻止其進入下一代.

4.4 遺傳算子設置

遺傳算子主要包括選擇、交叉和變異三方面.選擇操作是實現(xiàn)種群進化過程中優(yōu)勝劣汰的重要機制,設計選擇算子為輪盤賭法,為了提高進化速度及穩(wěn)定性,在選擇時,采取精英保留策略.即,將前一代的最優(yōu)個體保存到下一代,替代后代中的最差個體,且不參與交叉和變異.交叉分為單點交叉、多點交叉和均勻交叉,本算法采用單點交叉的方法.變異分為局部變異和全局變異兩種,本算法采用全局變異的方法,即種群的每個個體隨機選擇一個位置進行變異.交叉概率Pc和變異概率Pm通常根據(jù)實際案例確定.一般Pc建議的取值范圍是0.4～0.99,Pm取值范圍為0.0001～0.5[7].在實際操作中采取分別對Pc和Pm取不同的值組合,根據(jù)適應度值變化規(guī)律確定參數(shù)的合理值.

4.5 算法終止

算法在迭代若干次后終止,終止條件一般設置為:進化代數(shù)限制、計算耗費時間限制等.本算法設置終止條件為確定的進化代數(shù)P.即當進化達到代數(shù)P時,算法自動終止.P通常設置為100～1 000.

5 案例分析

如圖1所示,線路L1與線路L2相交于換乘站St1.分別以平峰時段10:00～12:00和早高峰時段7:00～9:00為例驗證模型.

圖1 兩線相交換乘站示意圖Fig.1 Two lines intersection diagram

5.1 平峰時段案例

5.1.1 初始數(shù)據(jù)準備

取協(xié)調(diào)時段10:00～12:00,為了計算方便,將協(xié)調(diào)時段的起始時刻10:00作為0時刻.協(xié)調(diào)時段內(nèi)各線路行車間隔h11=300 s,h12=270 s,h21=330s,h22=300 s.線路間純換乘時間均為100 s.停站時間D11=D12=40 s,D21=D22=35 s.假設各線路各方向每趟列車帶來的換乘客流由協(xié)調(diào)時段內(nèi)該線路該方向總換乘客流除以開行的列車對數(shù)計算得出,如表1所示.表1中“L1上”表示線路1上行,“L1下”表示線路1下行,其他同理.單元格中數(shù)據(jù)表示所在行方向的一列車所帶來的要換乘到所在列方向的客流量.

根據(jù)算例中h11、h12、h21、h22的取值均不超過29=512 s,因此,每個初始離站時刻可以采用9位二進制編碼,共4個列車運行方向,則L=36.種群規(guī)模N=1 000,進化代數(shù)P=200.本例中取Pc分別為0.9和0.1,Pm分別為0.1和0.9,以做相互對比.

表1 每列車運送的換乘客流量數(shù)據(jù)(人)(平峰)Table 1 Transfer count of each train(non-peak-hours)

5.1.2 計算結(jié)果及分析

通過在Pentium 4雙核處理器計算機(2.00 GHz主頻,2 GB內(nèi)存)上運行,各設置參數(shù)對應最優(yōu)解及各代平均適應度f隨代數(shù)的變化規(guī)律如圖2 (a)～圖2(d)所示.

圖2 進化過程Fig.2 The evolutionary process

圖2中(a)、(c)對應每代平均適應度值隨代數(shù)變化基本在一個水平,這是由于變異概率Pm取值較大,使進化過程中每代均破壞了前一代種群接近最優(yōu)解的積木塊,主要依靠隨機性搜索最優(yōu)解,而(b)、(d)平均適應度基本隨著進化代數(shù)呈現(xiàn)逐漸遞增的態(tài)勢,并最終趨于穩(wěn)定,即種群中個體的綜合水平不斷提高.同時,由于采取精英保留策略,因此各圖中最優(yōu)解均呈現(xiàn)單調(diào)遞減性.本文采用圖(b)中對應參數(shù)Pc=0.9,Pm= 0.1計算.

通過對St1協(xié)調(diào),計算獲得一些優(yōu)化解,對應各方向第一趟列車離站時刻如表2所示.作為對照,將式(13)改為f=F,則可以求得部分較劣解,如表3所示.需要指出的是表2、表3中只列出部分優(yōu)化解和較劣解.

表2 St1站的協(xié)調(diào)優(yōu)化解(平峰)Table 2 Optimal solutions in St1(non-peak-hours)

表3 St1站的協(xié)調(diào)較劣解(平峰)Table 3 Bad solutions in St1(non-peak-hours)

由于遺傳算法使用概率搜索法,因此不易找出最優(yōu)解,可以通過多次運算,對結(jié)果做篩選,并作為全局最優(yōu)解.根據(jù)優(yōu)化結(jié)果,假設取表2中第3行數(shù)據(jù)做為協(xié)調(diào)依據(jù),則在協(xié)調(diào)時段內(nèi)各線路各方向第1趟列車離開換乘站的時刻分別為:線路1上行為10:02,下行為10:01:59;線路2上行為10:03: 01,下行為10:03:01.以后各趟列車的離站時刻分別為在首趟車離站時刻的基礎上各自增加本方向整數(shù)個行車間隔.以此為基礎,利用區(qū)間運行時間及各站停站時間,可反推各線路列車在始發(fā)站的發(fā)車時刻.

5.2 早高峰時段案例

同理對早高峰時段7:00～9:00分析,設置各線路行車間隔h11=200 s,h12=180 s,h21=200 s, h22=190 s.線路間純換乘時間均為100 s.停站時間D11=D12=45 s,D21=D22=40 s.客流量如表4所示.

表4 每列車運送的換乘客流量數(shù)據(jù)(人)(早高峰)Table 4 Transfer count of each train(morning-peak-hours)

計算過程同平峰時段案例,計算得出優(yōu)化結(jié)果如表5,相對較劣的結(jié)果如表6.

表5 St1站的協(xié)調(diào)優(yōu)化解(早高峰)Table 5 Optimal solutions in St1(morning-peak-hours)

表6 St1站的協(xié)調(diào)較劣解(早高峰)Table 6 Bad solutions in St1(morning-peak-hours)

假設取表5中第1行數(shù)據(jù)做為協(xié)調(diào)依據(jù),則早高峰時段各方向第1趟車離開換乘站的時刻分別為:線路1上行為07:01:02,下行為07:02:22;線路2上行為07:02:01,下行為07:01:11.以后各趟列車的離站時刻分別為在首趟車離站時刻的基礎上各自增加本方向整數(shù)個行車間隔.

5.3 案例結(jié)果對比分析

根據(jù)表2和表3,平峰時段協(xié)調(diào)后,旅客換乘候車相對優(yōu)化比率,即較劣解與較優(yōu)解對應的總候車時間之差再與較劣解對應的總候車時間的比值,約為44%;而根據(jù)表5和表6,早高峰時段協(xié)調(diào)后,旅客換乘候車相對優(yōu)化比率約為28%.同時還可以得出,影響協(xié)調(diào)效果的關(guān)鍵因素為協(xié)調(diào)時段內(nèi)的客流量和行車間隔.客流量影響優(yōu)化的絕對減小值,即較劣解與較優(yōu)解對應的總候車時間之差,客流量越大,協(xié)調(diào)后旅客換乘總候車時間的絕對減小值就越大,即整體社會效益越明顯;行車間隔影響優(yōu)化的相對值,行車間隔越大,協(xié)調(diào)后旅客換乘候車時間相對優(yōu)化比率就越大,即旅客服務水平提升幅度越大.

6 研究結(jié)論

本文分析了線路不同相交形式情況下?lián)Q乘站存在換乘接續(xù)方向總數(shù)的計算方法;以換乘站旅客總換乘候車時間最少為目標建立了基于離站時刻協(xié)調(diào)的列車銜接優(yōu)化模型,實現(xiàn)了列車在地鐵換乘站的離站時刻優(yōu)化調(diào)整;設計簡單遺傳算法,并對算例求解,結(jié)果驗證了本模型能夠減少旅客的換乘候車時間,具有一定的應用價值.本文只是研究了各列車在換乘站的離站時刻協(xié)調(diào)問題,而在網(wǎng)絡中存在多個換乘站情況下,各換乘站之間的相互協(xié)調(diào)問題將作為進一步的研究內(nèi)容.

[1] 周艷芳,周磊山,樂逸祥.城市軌道網(wǎng)絡換乘站列車銜接同步協(xié)調(diào)優(yōu)化研究[J].鐵道學報,2011,33 (3):9-16.[ZHOU Y F,ZHOU L S,YUE Y X. Synchronizedandcoordinatedtrainconnection optimization for transfer stations of urban rail networks [J].Journal of the China Railway Society.2011,33 (3):9-16.]

[2] 張銘,杜世敏.基于遞階偏好的軌道交通網(wǎng)絡化運營換乘協(xié)調(diào)優(yōu)化[J].鐵道學報,2009,31(6):9-14. [ZHANGM,DUSM.Transfercoordination optimization for network operation of urban rail transit based on hierarchical preference[J].Journal of the China Railway Society.2009,31(6):9-14.]

[3] 徐瑞華,張銘,江志彬.基于線網(wǎng)運營協(xié)調(diào)的城市軌道交通首末班列車發(fā)車時間域研究[J].鐵道學報, 2008,30(2):7-11.[XU R H,ZHANG M,JIANG Z B. Study on departure time domain of the first and last trains of urban mass transit network based on operation coordination[J].Journal of the China Railway Society. 2008,30(2):7-11.]

[4] Rachel C,W Wong.et al.Optimizing timetable synchronization for rail mass transit[J].Transportation Science.2008, 42(1):57-69.

[5] Chung Min Kwan,C S Chang.Timetable synchronization ofmassrapidtransitsystemusingmutiobjective evolutionary approach[J].IEEETransactionson Systems,Man,and Cybernetics Part C:Applications and Reviews.2008,38(5):636-648.

[6] 孫鵬,趙佳虹,丁宏飛.基于換乘協(xié)調(diào)的城市軌道交通列車開行方案優(yōu)化[J].鐵道運輸與經(jīng)濟,2011, 33(12):67-70.[SUN P,ZHAO J H,DING H F.The optimization of urban rail transit operation scheme based on coordinated transfer[J].Railway Transport and Economy.2011,33(12):67-70.]

[7] 徐宗本.計算智能(第一冊)——模擬進化算法[M].北京:高等教育出版社,2005[XU Z B. Computational intelligence(1)—simulated evolutionary algorithm[M].Beijing:HigherEducation Press,2005.]

Optimization of Convergence based on the Coordination of Train Departure Time in the Subway Transfer Station

BAI Guang-zhenga,GUO Jina,SHI Hong-guob,YANG Yanga,ZHANG Tai-huaa
(a.School of Information Science and Technology;b.School of Traffic and Transportation, Southwest Jiaotong University,Chengdu 610031,China)

By coordinating the trains'departure time in the transfer station,optimized scheme is proposed to reduce the waiting time of transfer passengers in the transfer station of the urban traffic network.The transfer relationship between two trains in different lines which intersect with different forms in a transfer station is analyzed,and the formulas are derived to describe these connecting relationships.Based on the analysis,a model which minimizes the total waiting time of all transfer passengers during the coordinating period is established.Simple genetic algorithm(SGA)with the discard method is designed to solve this problem.Finally,an example with two lines'intersection is given to verify the model and partial optimized solutions are obtained by using the proposed algorithm.The results show that the model can reduce transfer passengers'waiting time.This study can provide some theoretical reference for the design and optimization of the train operation scheme under the urban traffic network operating scenario.

urban traffic;transfer connecting optimization;simple genetic algorithm;transfer station; coordination model

U292.4+1

: A

U292.4+1

A

1009-6744(2013)05-0134-07

2013-03-08

2013-06-09錄用日期:2013-06-20

中央高校基本科研業(yè)務費專項資金資助(SWJTU11CX44);鐵道部科技研究開發(fā)計劃項目(2012X010-A).

白廣爭(1986-),男,山東曹縣人,博士生.

*通訊作者:gj60@sina.com