張安英，胡智敏，張冰清

（1.廣東省交通運輸規(guī)劃研究中心，廣東廣州 510101；2.中鐵第四勘察設(shè)計院集團有限公司，湖北武漢 430063）

城市軌道交通末班車時刻表協(xié)調(diào)優(yōu)化研究

張安英1，胡智敏2，張冰清1

（1.廣東省交通運輸規(guī)劃研究中心，廣東廣州 510101；2.中鐵第四勘察設(shè)計院集團有限公司，湖北武漢 430063）

在網(wǎng)絡(luò)運營條件下，以城市軌道交通網(wǎng)絡(luò)線路間的末班車換乘銜接為研究內(nèi)容，以換乘銜接客流量最大為目標，同時考慮特定換乘方向約束，建立了網(wǎng)絡(luò)末班車時刻表優(yōu)化模型，并針對該模型設(shè)計了遺傳算法進行求解。結(jié)果表明，原始列車時刻表只能銜接19個換乘方向?qū)崿F(xiàn)610人換乘，設(shè)定特定換乘方向時可銜接20個換乘方向并實現(xiàn)858人換乘，優(yōu)化率達40.66%，文中設(shè)計的末班車時刻表銜接和優(yōu)化模型及遺傳算法對換乘站末班車的銜接優(yōu)化有效。

城市交通；軌道交通；末班車；時刻表；停站時間；遺傳算法

在城市軌道交通網(wǎng)絡(luò)化運營條件下，隨著換乘站點的增加，原本獨立運營的各條線路通過換乘站產(chǎn)生直接或間接的聯(lián)系，同時軌道交通客流也通過換乘站實現(xiàn)不同線路的銜接。由于各條線路主要依據(jù)本條線路的客流情況確定一天的運營時間，線路結(jié)束運營的時刻不盡相同，使軌道交通網(wǎng)絡(luò)上各車站之間的可達關(guān)系呈現(xiàn)動態(tài)變化的特點。一條線路的末班車時刻不僅會影響本線路乘客的出行，更大程度上會通過換乘站將影響擴大到整個軌道交通網(wǎng)絡(luò)。因此，根據(jù)換乘客流特點及末班車乘客行為特征對網(wǎng)絡(luò)末班車發(fā)車時刻進行協(xié)調(diào)，實現(xiàn)各線路末班車在換乘站的整體合理銜接顯得尤為重要，這也是對網(wǎng)絡(luò)化運營的重要補充。

在末班車時刻表優(yōu)化方面，國內(nèi)外學(xué)者進行了一定研究：Avishal Ceder等建立了在公交網(wǎng)絡(luò)換乘站中各條線路車輛到達同步化模型；Chung EH.等提出了列車銜接關(guān)系維持策略，主要通過改變列車單元對乘客等待時間的影響來界定是否維持該單元銜接關(guān)系；Shafahi Y.等建立了以換乘站換乘等待時間最小為目標的城市軌道交通網(wǎng)絡(luò)時刻表混合整數(shù)規(guī)劃模型，并研究了列車停站時間對換乘銜接的影響；Chowdhury M.S.以減小列車晚點、發(fā)車延誤等總費用為目標，設(shè)計了一套列車實時調(diào)度方法；Guihaire V.等從提高時刻表整體質(zhì)量的角度出發(fā)，提出通過調(diào)整時刻表的方法來使換乘數(shù)量和質(zhì)量達到最好；Alessandro Chierici等提出了多線地鐵列車運行時刻優(yōu)化方法，考慮了乘客等待時問、旅行時間、舒適度等多種因素；房霄虹初步建立了城市軌道交通網(wǎng)絡(luò)化運輸組織協(xié)調(diào)理論研究的基本體系，對不同線路模式下列車開行密度的配置方法及結(jié)合列車到發(fā)時刻在換乘節(jié)點內(nèi)部的銜接與網(wǎng)絡(luò)換乘節(jié)點間的外部協(xié)調(diào)優(yōu)化策略進行了探討；張銘等從換乘時間優(yōu)化入手建立雙層系統(tǒng)，以換乘站作為子系統(tǒng)建立銜接層換乘時間優(yōu)化模型，然后在協(xié)調(diào)層調(diào)整銜接方案，進而推至全局，達到全局最優(yōu)，并設(shè)計了并行協(xié)調(diào)算法；羅欽等分析了首末班車的可達性，將列車的到發(fā)時間定為剛性影響，乘客走行時間定為柔性影響，構(gòu)建了首末班車各自的可達性銜接模型；徐瑞華等建立了以換乘乘客候車時間最小為目標的首末班車銜接模型，利用分層協(xié)調(diào)算法推算了首末班車發(fā)車時間域。該文模擬網(wǎng)絡(luò)運營條件下，以城市軌道交通網(wǎng)絡(luò)線路間的末班車換乘銜接為研究內(nèi)容，以換乘銜接客流量最大為目標，同時考慮特定換乘方向的約束，建立網(wǎng)絡(luò)末班車時刻表銜接模型。

1 換乘站線路銜接過程分析

1.1換乘站換乘客流與列車流到發(fā)時序關(guān)系

對于換乘站k，在線路l和p的發(fā)車間隔確定的前提下，以兩線四向互換乘為例，如圖1所示，線路l各列車到達換乘站k的時間依次為，各列車的到達時間間隔為為乘客在換乘站k由線路l換乘至線路p的換乘走行時間，twk，l，p為乘客在換乘站k由線路l換乘至線路p的換乘等待時間，實線表示線路l，虛線表示線路p。

圖1　換乘站兩線列車到發(fā)時間關(guān)系示意圖

若線路l的第i列車的乘客換乘線路p的第j +1列車，則換乘時間為：

式中：tⅠl，p為由線路l換乘線路p的換乘時間。

又因為線路換乘時間為換乘走行時間與換乘等待時間之和，即

在一個具體的換乘站中，線路間的換乘走行時間依據(jù)不同時段（高峰與平峰）以2個值取代，即換乘走行時間是確定的值，則換乘等待時間為：

twk，l，p=0，表示換乘乘客到達目標站臺不需要等待列車到達，直接上車，是理想中的換乘0，表示換乘乘客需要在目標站臺等待列車到達。

1.2換乘站末班車換乘銜接過程分析

由換乘站內(nèi)換乘流與列車流到發(fā)時序關(guān)系分析可知：末班車的換乘等待時間應(yīng)為換出線路的末班車的客流到達換入線路的站臺的時間與換入線路的列車到達該站臺的時間差。然而換入線路的列車不一定是該線路的末班車，故引入末班車換乘冗余時間。換乘冗余時間指換出線路的末班車的客流到達換入線路的站臺的時間與換入線路末班車到達該站臺的時間差。下面分為3種情況分析末班車換乘等待時間與換乘冗余時間的異同，以在換乘站k線路l的末班車換乘線路p為例。如圖2所示，線路l與p對應(yīng)的末班車分別為i、j。

（1）當線路l的末班車i的客流換乘的是線路p的末班車j時，換乘等待時間與換乘冗余時間相等，即：

式中：trk，l，p為在換乘站k由線路l末班車換乘線路p末班車的換乘冗余時間。

（2）當線路l的末班車i換乘線路p的末班車j之前列車時，換乘等待時間小于換乘冗余時間，即：

圖2　兩線路末班車間換乘關(guān)系示意圖

（3）當線路l的末班車i換乘線路p銜接失敗時，換乘等待時間將為無窮大，換乘冗余時間為負值，即：

換乘冗余時間可用于評價末班車銜接關(guān)系的可靠性：當換乘冗余時間大于等于零時，換出線路末班車與換入線路末班車的到站時間差值變化不能大于換乘冗余時間，否則將導(dǎo)致該方向換乘失??；當換乘冗余時間為負值時，該換乘方向已經(jīng)失敗。

2 網(wǎng)絡(luò)末班車時刻表銜接模型的建立

由于線路具有上下行方向，為方便起見，將各條線上下行方向分為2條線路，建立線路集合L、換乘站集合S、各個換乘站各換乘方向的需求集合Q。

2.1換乘站內(nèi)線路間換乘過程分析

線路i的換乘站集合為Si，線路j的換乘站集合為Sj，如果換乘站k為線路i和j的共同換乘站，由換乘站內(nèi)部銜接過程分析可知：若線路i的末班車在換乘站k換乘線路j，則需在線路j的末班車離開站點k之前線路i的末班車乘客到達線路j的站臺，即有：

將式（7）化為不等式約束：

式中：M為足夠大的正數(shù)。

線路i的末班車在站點k的到站時刻為該車發(fā)車時刻與在到達站點k之前的各站間行駛時間與各站停站時間之和，數(shù)學(xué)表達式為：式中：tOi為線路i的末班車發(fā)車時刻；為線路i的列車在站點p-1到站點p的行駛時間；p為換乘站k在i線路所經(jīng)過換乘站Si的序號；tHp，i為在線路i第p個換乘站點k的停站時間。

同理：

2.2同一換乘站線路間銜接約束

換乘站k為線路i和j的共同換乘站，由換乘站內(nèi)部銜接過程分析可知：在換乘站k，線路i的末班車換乘線路j成功時，則線路j的末班車換乘線路i失敗。在城市軌道交通網(wǎng)絡(luò)中，在同一換乘站內(nèi)線路i和j之間的換乘最多只有一個方向換乘成功，數(shù)學(xué)表達式為：

2.3特定換乘方向銜接約束

若特定換乘方向為在換乘站k，線路Ⅰ換乘線路J，則該方向銜接約束為：

對于給定的末班車發(fā)車區(qū)間：

由線路Ⅰ和J各自的到達換乘k的行駛時間和停站時間，可得線路Ⅰ和J的末班車在換乘站k的到站時間區(qū)間：

若線路J的末班車在換乘站k最晚離站前，線路Ⅰ的末班車在最早到站時，都不能銜接成功，則該特定換乘方向銜接不能實現(xiàn)，即：

故對于特定換乘方向銜接約束，需根據(jù)實際的末班車發(fā)車區(qū)間判斷是否可以銜接成功。

若該換乘方向能銜接成功，則有：

2.4模型構(gòu)建

在考慮特定換乘方向銜接約束后，根據(jù)給定的各線路末班車發(fā)車時間域TO和各個換乘站各換乘銜接方向的需求集合Q，為使銜接成功的客流量最大，建立如下目標函數(shù)：

式中：qkij為在換乘站k，線路i末班車換乘線路j的需求量。

式（17）即為網(wǎng)絡(luò)末班車時刻表優(yōu)化模型，其約束條件為：

3 算法設(shè)計

3.1解空間分析

遺傳算法具有快速尋找全局最優(yōu)解（或準最優(yōu)解）的能力、能處理復(fù)雜非線性系統(tǒng)優(yōu)化問題、執(zhí)行簡單靈活等特點，被廣泛應(yīng)用于優(yōu)化問題求解。遺傳算法的主要步驟包括設(shè)計染色體編碼方法、生成初始種群、適應(yīng)度函數(shù)設(shè)計、評價種群中各個體的適應(yīng)度值、通過遺傳操作（選擇、交叉和變異）產(chǎn)生新的種群直至滿足停止迭代條件。

網(wǎng)絡(luò)末班車時刻表優(yōu)化模型的決策變量為各線路的發(fā)車時間，根據(jù)發(fā)車時間范圍進行二進制編碼來構(gòu)建染色體。染色體由各線路發(fā)車時間的二進制順序排列組成，染色體長度為發(fā)車時間對應(yīng)二進制長度之和。因為特定換乘方向銜接約束的存在使遺傳算法每產(chǎn)生一個個體都需要判斷是否符合約束條件，同時進行每一次進化和變異的解也需要判斷，這會大大降低遺傳算法的效率，同時可能造成遺傳算法的過早收斂，也可能造成種群的快速死亡，所以需對銜接約束作進一步處理。

利用啟發(fā)式算法即遺傳算法搜索最優(yōu)解，將特定換乘方向銜接約束轉(zhuǎn)化為對發(fā)車時間域的約束，在換乘站k的銜接約束下，線路Ⅰ、J的末班車在站點k的到達時間域分別為：

式中：TLⅠ為銜接約束下線路Ⅰ的臨界到站時刻。

以滿足約束的在站點k到達時間域反推線路Ⅰ和J的末班車發(fā)車時間域，在改變后的發(fā)車時間域用遺傳算法搜索最優(yōu)解，該最優(yōu)解可能會在可行域內(nèi)，也可能在非可行域內(nèi)。若遺傳算法搜索出的最終解在非可行域內(nèi)，則用搜索域逼近法處理。操作過程如下：利用2個矩形將可行域分割成兩部分，將線路Ⅰ和J的在站點k的末班車到達時間域切割為2個搜索域，分別為搜索域1：

采用遺傳算法在2個新的末班車發(fā)車時間域繼續(xù)搜索，得到2個解，若2個解均為可行解，則取較大值作為最優(yōu)解；若其中一個解為可行解，另一個為非可行解，且可行解不小于非可行解，則取可行域內(nèi)的解作為最優(yōu)解；其他情況均要進行下一步分割迭代（如圖3所示）。

3.2算法步驟

由網(wǎng)絡(luò)末班車時刻表銜接模型可知：當沒有特定換乘方向約束時，可直接利用遺傳算法求解；當考慮特定換乘方向約束時，需先對發(fā)車時間域進行約束，然后依據(jù)新的發(fā)車時間域制訂搜索域方案。操作步驟如下：

（1）是否存在特定換乘方向約束，若無，直接進入第2步；若存在，則利用式（12）、式（18）計算滿足約束的新發(fā)車時間域，然后將新的末班車發(fā)車時間域取代原始發(fā)車時間域，進入第2步。

（2）在發(fā)車時間域內(nèi)初始化種群。

（3）將各個個體對應(yīng)二進制染色體轉(zhuǎn)化為具體的實數(shù)，依據(jù)各條線路到達各換乘站行程時間與各換乘方向走行時間判斷各換乘方向的銜接情況，代入適應(yīng)度函數(shù)計算各個體的適應(yīng)度。

（4）選出適應(yīng)度最大的個體直接進入下一代種群，不參與種群更新操作。其余個體按照適應(yīng)度大小，利用輪盤賭算子選擇N個染色體（個體）進行交叉操作，取交叉概率P1=0.9對染色體進行兩點交叉，將得到的N個新個體選入新種群，沒有被選中的交叉?zhèn)€體直接進入下一代種群；變異算子利用基本位變異，取變異概率P2=0.03對染色體進行變異，變異后新個體進入下一代，沒有變異的直接進入下一代種群。

圖3　搜索域與可行域關(guān)系示意圖

（5）判斷是否達到最終進化代數(shù)，若達到，則輸出結(jié)果；否則，返回第3步。若是對于特定銜接約束，則進入第6步。

（6）判斷輸出結(jié)果是否在可行域內(nèi)，若在，則跳至第8步；若不在，則分成若干個搜索域，將各個搜索域分別代入第2步。

（7）將各個搜索域?qū)?yīng)的輸出結(jié)果進行比較，取最大值，進入第8步。

（8）輸出結(jié)果即為最優(yōu)解。

4 案例分析

下面以北京市地鐵1號線、2號線、5號線構(gòu)成的網(wǎng)絡(luò)作為算例進行分析。

4.1算例數(shù)據(jù)及相關(guān)參數(shù)

1號線、2號線、5號線構(gòu)成的網(wǎng)絡(luò)有5個換乘站。為了區(qū)分線路上下行，分別對線路及換乘站編號（如圖4所示）。

圖4　城市軌道交通網(wǎng)絡(luò)布局示意圖

各條線路的末班車原始發(fā)車時刻及發(fā)車時間域如表1所示。各條線到達各換乘站的運行時間及各站停站時間如表2所示。各換乘站各換乘方向的換乘走行時間如表3所示，換乘需求如圖5所示。

表1　網(wǎng)絡(luò)中末班車原始發(fā)車時刻與發(fā)車時間域

表2　末班車由起始站到各換乘站的運行時間及停站時間min

4.2算法實現(xiàn)及結(jié)果分析

若在換乘站S3，L3末班車換乘L1的換乘方向是由市區(qū)向市郊方向，為必須實現(xiàn)方向。將該換乘方向約束轉(zhuǎn)化為對L1與L3的末班車發(fā)車時間域的約束。當L3的末班車發(fā)車時刻取22：55：30時，剛好對L1末班車發(fā)車時間域都能實現(xiàn)該方向的銜接；當L3的末班車發(fā)車時刻取23：10：00時，只能銜接L1的發(fā)車時間域為［22：59：30，23：05：00］。由無換乘方向約束求得的最優(yōu)解可知其在非可行域內(nèi)，現(xiàn)利用搜索域逼近可行域方法分成2個搜索域，搜索域1：

表3　各個換乘方向的換乘走行時間min

圖5　各個換乘方向的換乘需求量（單位：人）

搜索域2：

分別用遺傳算法對搜索域1和2求解，得到搜索域1：銜接成功的客流量為858人；搜索域2：銜接成功的客流量為816人。對應(yīng)末班車發(fā)車時刻如表4所示，遺傳算法適應(yīng)度變化如圖6所示。

表4　單個換乘方向約束下末班車最優(yōu)發(fā)車時刻

圖6　單個換乘方向約束下適應(yīng)度變化圖

比較2個搜索域?qū)?yīng)最優(yōu)解，可知搜索域1中的解優(yōu)于搜索域2，因此將搜索域1中的解作為滿足該方向約束的最優(yōu)解。各銜接成功方向的具體情況如表5所示。由輸出的末班車時刻得到各銜接成功的方向，添加換乘方向約束優(yōu)化后結(jié)果為：銜接20個換乘方向，換乘成功的客流量為858人。

表5　單個換乘方向約束下末班車發(fā)車時刻對應(yīng)的銜接情況

續(xù)表5

網(wǎng)絡(luò)采用原始末班車發(fā)車時刻只能銜接19個換乘方向，換乘成功客流量為610人。當對末班車時刻表進行單個換乘方向約束優(yōu)化后，可銜接20個換乘方向，換乘成功的客流量為858人，優(yōu)化率達40.66%。改變的銜接關(guān)系如圖7所示。

圖7　單個換乘方向約束下銜接方向圖

5 結(jié)語

隨著城市軌道交通線路數(shù)量的增加，城市軌道交通網(wǎng)絡(luò)逐步形成，原本的軌道交通單線運營組織模式難以適應(yīng)網(wǎng)絡(luò)化運營需求。在實際運營中，由于各條線路末班車運營時間沒有承接性，經(jīng)常發(fā)生乘客無法經(jīng)換乘抵達目的站的現(xiàn)象，且對于一些換乘站末班車銜接預(yù)留的換乘時間不足，導(dǎo)致部分乘客換乘失敗。該文分析了換乘站列車流與換乘客流的到發(fā)順序關(guān)系，進而分析了換乘站內(nèi)末班車銜接過程的特殊性。針對城市軌道交通網(wǎng)絡(luò)末班車，建立了考慮特定換乘方向的網(wǎng)絡(luò)末班車時刻表銜接模型，并設(shè)計遺傳算法對模型求解。根據(jù)該模型和算法可得到滿足特定方向換乘情況下的網(wǎng)絡(luò)整體最優(yōu)末班車銜接時刻表，對協(xié)調(diào)網(wǎng)絡(luò)中末班車的銜接具有重要現(xiàn)實意義。

該考慮特定換乘方向的網(wǎng)絡(luò)末班車時刻表模型是建立在假設(shè)各換乘站間的行駛時間不變的前提下的，而在實際運營過程中，列車運行延誤的情況經(jīng)常發(fā)生，針對存在延誤情況下末班車時刻表的調(diào)整還有待深入研究。

［1］ A Ceder，B Golanyb，O Talb.Creating bus timetables with maximalsynchronization［J］.Transportation Research Part A：Policy and Practice，2001，35（10）.

［2］ Chung E-H，A Shalaby.Development of a controlstrategy for inter-modal connection protection of timedtransfer transit routes［R］.Transportation Research Record，2006.

［3］ Shafahi Y，Khani A.A practical model for transfer optimization in a transit network：model formulations andsolutions［J］.Transportation Research Part A： Policy and Practice，2010，44（6）.

［4］ Chowdhury M S，Chien S I J.Dynamic vehicle dispatching at intermodal transferstation［R］.Transportation Research Record，2001.

［5］ Guihaire V，HAO J-K.Improving timetable quality inscheduled transit networks［A］.Trends in Applied Intelligent Systems［C］.2010.

［6］ Alessandro chierici，Roberto Cordone.The demand-dependent optimization of regular train timetables［J］.E-lectronic Notes in Discrete Mathematics，2004，17.

［7］ 房霄虹.城市軌道交通網(wǎng)絡(luò)化運輸組織協(xié)調(diào)理論及方法研究［D］.北京：北京交通大學(xué)，2010.

［8］ 張銘，徐瑞華，江志彬，等.軌道交通網(wǎng)絡(luò)列車銜接組織的遞階協(xié)調(diào)優(yōu)化［J］.系統(tǒng)工程，2007，25（9）.

［9］ 羅欽，徐瑞華.基于運行圖的軌道交通網(wǎng)絡(luò)動態(tài)可達性研究［J］.同濟大學(xué)學(xué)報：自然科學(xué)版，2010，38（1）.

［10］ 徐瑞華，張銘，江志彬.基于線網(wǎng)運營協(xié)調(diào)的城市軌道交通首末班列車發(fā)車時間域研究［J］.鐵道學(xué)報，2008，30（2）.

［11］ 白廣爭，郭進.基于離站時刻協(xié)調(diào)的地鐵換乘站列車銜接優(yōu)化研究［J］.交通運輸系統(tǒng)工程與信息，2013，13（5）.

［12］ 趙鵬，張秀媛，孫晚華，等.管理運籌學(xué)教程［M］.第二版.北京：清華大學(xué)出版社，2014.

［13］ 陳團生，毛保華，何宇強.旅客列車發(fā)車時間域優(yōu)化研究［J］.鐵道學(xué)報，2006，28（4）.

［14］ 馬超云.城市軌道交通換乘站列車時刻表的協(xié)調(diào)和優(yōu)化［D］.北京：北京交通大學(xué)，2010.

U492.2

A

1671-2668（2016）05-0042-07

2016-02-24