混合交路模式下城市軌道交通交路計劃與時刻表綜合優(yōu)化研究

張 慧，蔣佳錕，鮮楚逸，4，陳釘均

（1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.西南交通大學(xué) 綜合交通運(yùn)輸智能化國家地方聯(lián)合工程實驗室，四川 成都 610031；3.西南交通大學(xué) 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室，四川 成都 610031；4.四川省城鄉(xiāng)建設(shè)研究院 市政建設(shè)研究所，四川 成都 610041）

0 引言

混合交路指線路上兩條或多條交路并存，不同交路共用軌道某一區(qū)段，是城市軌道交通行車組織的新模式。相比單一交路，當(dāng)線路里程較長、客流分布不均時，混合交路通過合理可行的交路組合安排列車輸送能力，達(dá)到充分利用設(shè)備設(shè)施資源的目的。目前混合交路運(yùn)營線路多采用固定開行比例的交路計劃和均勻發(fā)車間隔的時刻表，運(yùn)力供給不能滿足時變客流需求。基于混合交路模式下乘客路徑選擇行為，研究混合交路模式下城市軌道交通交路計劃與時刻表綜合優(yōu)化，有助于提升運(yùn)輸能力對于客流的適應(yīng)性，防止客流擁擠推攘引發(fā)的安全事故，降低列車空跑導(dǎo)致的運(yùn)營虧損。

城市軌道交通交路計劃優(yōu)化包含折返站及交路開行列車比例優(yōu)化。梁強(qiáng)升等[1]分析Y 型線分支段的運(yùn)能分配、行車進(jìn)路的安全風(fēng)險及客運(yùn)組織的管理難點，綜合比選交路折返站；李得偉等[2-3]以Y型線列車交路的組合優(yōu)化問題為導(dǎo)向，建立考慮乘客對直達(dá)列車偏好的列車交路計劃編制模型；劉猛等[4-5]以乘客出行時間最小為目標(biāo)函數(shù)，考慮列車滿載率、最小追蹤間隔、折返站能力、運(yùn)用車數(shù)量等約束，構(gòu)建Y型線折返站優(yōu)化模型；Yang等[6]提出一種跨站停車及跨線行車結(jié)合的復(fù)雜運(yùn)營方式，實現(xiàn)停站方案及交路計劃的綜合優(yōu)化；方開莎等[7]以乘客等待時間、車輛走行公里和列車運(yùn)行時間最小化為目標(biāo)，在列車編組可變前提下構(gòu)建多目標(biāo)大小交路開行方案，以均衡乘客等待時間和城市軌道交通運(yùn)營企業(yè)效益。

城市軌道交通時刻表優(yōu)化包括行車間隔優(yōu)化、折返能力優(yōu)化、區(qū)間運(yùn)行時分及停站時分優(yōu)化等，優(yōu)化內(nèi)容不同，建模方式也不同。戚建國[8]分析列車時刻表、停站方案和旅客需求之間的內(nèi)在關(guān)聯(lián)，構(gòu)建滿足旅客需求的列車時刻表與停站方案協(xié)同優(yōu)化的混合整數(shù)線性規(guī)劃模型；譚麗等[9]調(diào)整列車開行頻率，針對輸送能力與客流需求匹配度，建立Y型交路模式下列車開行方案優(yōu)化模型；吳婷婷[10]研究列車在換乘站的協(xié)同接續(xù)優(yōu)化，構(gòu)建以路網(wǎng)內(nèi)全體旅客換乘等待總時間最小化為目標(biāo)的城市軌道交通列車開行方案與運(yùn)行圖一體化編制模型；H?gdahl等[11]優(yōu)化均勻發(fā)車間隔的時刻表，最小化計劃出行時間及期望延誤，提升運(yùn)輸服務(wù)的快捷性和可靠度；Wang 等[12]研究動態(tài)客流條件下的列車時刻表及車底運(yùn)用的協(xié)同問題，并提出迭代非線性規(guī)劃、等效多約束線性規(guī)劃、近似多約束線性規(guī)劃3 種解決方法；Zhou 等[13]以減少乘客延誤、總旅行時間和列車運(yùn)行成本為目標(biāo)函數(shù)，提出不確定客流需求下列車節(jié)能調(diào)度的近似動態(tài)規(guī)劃方法；Yin 等[14]同時考慮列車運(yùn)行速度的選擇和車站客流的動態(tài)需求，提出一種以運(yùn)行能耗及乘客候車時間最小化為目標(biāo)的時刻表優(yōu)化方法；段凌林等[15]以乘客出行成本與企業(yè)運(yùn)營成本最小為目標(biāo)，考慮列車停站時間與客流需求的關(guān)系，在大小交路模式的基礎(chǔ)上引入快慢車模式，優(yōu)化開行方案。

既有的研究均是假定不同交路列車的發(fā)車頻率存在倍數(shù)關(guān)系，或設(shè)定單位時段內(nèi)(往往為1 h及以上)列車的發(fā)車間隔一致，這在一定程度上影響了運(yùn)輸能力對時變客流的適應(yīng)性。為提升運(yùn)輸能力對時變客流的適應(yīng)性，研究構(gòu)建混合交路模式下基于乘客行為差異性的城市軌道交通交路計劃及時刻表綜合優(yōu)化模型，為實現(xiàn)城市軌道交通高品質(zhì)的快捷運(yùn)輸服務(wù)提供參考。

1 問題分析及說明

基于復(fù)雜交路運(yùn)營線路，根據(jù)分時段客流OD需求，選擇非固定開行比例的交路計劃和靈活發(fā)車間隔的時刻表，以滿載率均衡度為目標(biāo)函數(shù)，以停站關(guān)系、服務(wù)水平、到發(fā)時刻、行車間隔、滿載率為約束條件，構(gòu)建混合交路模式下交路計劃及時刻表綜合優(yōu)化模型，并設(shè)計分層優(yōu)化算法求解。符號說明如表1所示。

表1 符號說明Tab.1 Symbols

2 模型構(gòu)建

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

混合交路模式下交路計劃與時刻表綜合優(yōu)化，實質(zhì)是根據(jù)分時段客流OD 數(shù)據(jù)，調(diào)整交路列車開行比例及行車間隔，達(dá)到滿載率均衡度最優(yōu)的過程。為使乘客需求與運(yùn)力供給的比值保持在穩(wěn)定區(qū)間，選擇列車滿載率均衡度(方差)fload_var作為目標(biāo)函數(shù)。

2.2 約束條件

2.2.1 停站關(guān)系約束

任意一列車只能選擇一個交路，則有

列車只能在所選交路包含的車站停站，則有

2.2.2 服務(wù)水平約束

對于非固定開行比例的混合交路運(yùn)營線路，相鄰列車車次編號難以形成周期性規(guī)律，為解決相鄰列車搜索問題，引入停站變量εk，i及服務(wù)水平參數(shù)Nsvc，停站變量εk，i表示列車k是否在車站Si進(jìn)行乘降作業(yè)，服務(wù)水平參數(shù)Nsvc表示兩相同子交路列車間最多間隔Nsvc-1 列其他子交路列車，即當(dāng)Nsvc-1輛列車未開行此交路時，為避免該分支段的乘客候車時間過長，保證服務(wù)水平，下一趟開行列車就必須是相同子交路的列車，即

2.2.3 到發(fā)時間約束

列車在車站的發(fā)車時間應(yīng)滿足約束

列車區(qū)間運(yùn)行時間應(yīng)滿足約束

2.2.4 行車間隔約束

行車間隔約束為

對于共線段有

對于分支段有

2.2.5 滿載率約束

滿載率是直接影響乘客舒適度的指標(biāo)，如果滿載率過高，擁擠的車廂會降低乘客的舒適度，導(dǎo)致乘客出行體驗較差，因此應(yīng)當(dāng)對滿載率進(jìn)行限制。

利用車站到站人數(shù)求得客流到達(dá)率，再積分求得客流乘降人數(shù)，通過乘降人數(shù)差值求得列車實載人數(shù)，進(jìn)而求得滿載率。

（1）客流到達(dá)率。處理乘客進(jìn)出站AFC 數(shù)據(jù)，得到OD為i，j的到站人數(shù)關(guān)于時間的分段函數(shù)為

則觀測時段內(nèi)OD 為i，j的乘客的到達(dá)率φi，j(t)可以表示為

（2）客流乘降人數(shù)?？土鞒私蛋ㄕ九_客流上車及在乘客流下車。一般城市軌道交通線路默認(rèn)乘客選擇自身到達(dá)站臺后的首輛到站列車，而混合交路運(yùn)營線路的部分區(qū)段是多交路套跑，乘客需要甄別進(jìn)站列車的行駛方向，因此乘客選擇的是自身到達(dá)站臺后的首輛去往目的站的到站列車，研究引入乘降變量εk，i，j來判別候車乘客的乘車選擇。εk，i，j表示列車k與車站Si，Sj的停站關(guān)系，同時也表示OD為i，j的乘客與列車k的選擇關(guān)系，只有當(dāng)列車k既在車站Si停站又在車站Sj停站，OD為i，j的乘客才會選擇該列車。需要說明的是，在處理客流數(shù)據(jù)時，以換乘點為切割點將換乘客流等效成2段直達(dá)客流。

設(shè)定同時在車站Si及Sy停站的列車為“目標(biāo)方向列車”，則每當(dāng)目標(biāo)方向列車到站，OD為i，y的候車乘客就進(jìn)行一次清空，因此上車人數(shù)實際是目標(biāo)方向列車離站間隔［dk'，i，dk，i］內(nèi)，站臺積累的到站人數(shù)，k’，k為相鄰“目標(biāo)方向列車”的編號。

那么，列車k在車站Si的上車人數(shù)Lboardk，i可以表示為

列車k在車站si的下車人數(shù)可以表示為

列車k在車站si的實載人數(shù)Lk，i為

用Ctrain表示列車的定員人數(shù)，則列車k在車站si的滿載率μk，i可以表示為

3 分層優(yōu)化算法

3.1 算法選擇

由上述建模過程可知，混合交路模式下交路計劃與時刻表綜合優(yōu)化模型為混合非線性規(guī)劃模型，可以采用分支切割算法求解。分支切割算法在每一步換基迭代過程中，需要進(jìn)行大量的矩陣運(yùn)算，而每一次迭代只可能有一個變量引入基內(nèi)，因此存在非直接運(yùn)算，約束條件越多，引入的松弛變量也越多，間接計算量就越大，因而求解效率低。針對該問題，采取以下2種求解策略。

（1）分層優(yōu)化策略。優(yōu)化模型的決策變量主要分為2 類：第一類為交路計劃變量，包括停站變量εk，i及交路變量λk，l，用于確定不同交路列車在共線段的運(yùn)行順序及?？寇囌?；第二類為時刻表變量，包括離站時刻dk，i及到站時刻ak，i，用于確定各列車的到發(fā)時刻。針對模型特性，設(shè)計分層優(yōu)化方法，外層采用禁忌搜索(TS)算法獲得較優(yōu)的交路計劃，內(nèi)層采用分支切割算法獲得交路計劃對應(yīng)的列車時刻表，逐層減少約束數(shù)量、縮小搜索空間。

（2）約束線性化策略。由于計算滿載率時使用了積分函數(shù)，在提取交路計劃變量后，內(nèi)層模型依然包含非線性約束，難以直接用分支切割算法求解。然而，積分中被積函數(shù)客流到達(dá)率φi，j(t)是一個分段函數(shù)，且分段的區(qū)間長度均為T，因此可以將該積分函數(shù)轉(zhuǎn)化為線性表達(dá)式。方法如下。

假設(shè)列車k到達(dá)車站si前，OD 為i，j的乘客的候車人數(shù)為

式中：dk'，i，dk，i分別為列車k'，k在車站si的離站時刻，k'為k在該目標(biāo)方向上相鄰列車的編號。

定義0-1 變量αk，i，t表示列車k在車站si的離站時刻是否在時間段)[t，t+T內(nèi)，公式為

根據(jù)定義，αk，i，t滿足約束為

且定義變量βk，i，t=αk，i，tdk，i，滿足約束為

至此，完成非線性表達(dá)式向線性表達(dá)式的轉(zhuǎn)化。

3.2 算法設(shè)計

求解混合交路模式下交路計劃與時刻表綜合優(yōu)化模型的算法基本步驟如下。

步驟2：生成當(dāng)前解Γnowroute的Γnowroute個鄰居對應(yīng)的鄰居產(chǎn)生方式為{moveneb，1，moveneb，2，…，moveneb，Nneb}，movebest=?，令i=1。

步驟4：判斷movenow?H是否成立，如果成立，轉(zhuǎn)步驟5，如果不成立，轉(zhuǎn)步驟6。

步驟5：判斷fnow≤fbest是否成立，如果fnow≤fbest成立，令fbest=fnow，movebest=movenow，轉(zhuǎn)步驟6；如果fnow≤fbest不成立，直接轉(zhuǎn)步驟6。

步驟6：判斷i≤Nneb是否成立，如果成立，轉(zhuǎn)步驟3，如果不成立，轉(zhuǎn)步驟7。

步驟7：判斷TS算法的終止條件是否滿足，如果滿足，轉(zhuǎn)步驟8，如果不滿足，將movebest加入禁忌表H，轉(zhuǎn)步驟2。

步驟8：輸出結(jié)果。

各交路輪流發(fā)車的運(yùn)行順序可以較好地平衡乘客候車時間及列車滿載率，因此選擇其作為初始解。同時，在鄰域生成函數(shù)上選擇了突變，即搜索找到滿載率最大的列車，隨機(jī)更換其交路，從而構(gòu)成新的交路選擇解。最后，選擇了迭代指定步數(shù)的終止規(guī)則。

4 算例分析

選取開行3 條子交路的復(fù)雜交路運(yùn)營線路，對混合交路模式下交路計劃及時刻表綜合優(yōu)化模型進(jìn)行算例分析。比較優(yōu)化前后線路的滿載率均衡度，驗證模型的有效性，設(shè)置不同的列車總開行數(shù)，測試模型的通用性，調(diào)節(jié)旅行時間節(jié)省值的臨界點，說明交路換乘的意義。

4.1 基礎(chǔ)數(shù)據(jù)

4.1.1 線路條件

某城市軌道交通線路A為一條混合交路運(yùn)營線路，該線穿城而過，連接著城市市郊區(qū)與中心區(qū)。A線線路如圖1所示。A線共21站，其中車站8至車站12為共線段，車站1至車站8、車站12至車站17、車站12 至車站21 為分支段。A 線共3 條交路，即R={r1，r2，r3}，A線交路如圖2所示。

圖2 A線交路Fig.2 Route of Line A

具有折返能力的車站共4個，包括車站1、車站8、車站17及車站21。3條交路途經(jīng)的車站分別為

數(shù)據(jù)觀測時間設(shè)置為7：00—11：30，共分為18 個時間段，以秒為單位，每段的時間長度為900 s，則觀測時段依次為[0，900 )，[900， 1800 )，…，[ 15300， 162000 )。觀測時段內(nèi)客流OD 總數(shù)如圖3所示。列車區(qū)間運(yùn)行時分如表2 所示。列車停站時分如表3所示。

圖3 觀測時段內(nèi)客流OD總數(shù)Fig.3 Total number of passenger flow OD during observation period

表2 列車區(qū)間運(yùn)行時分sTab.2 Running time of train intervals

表3 列車停站時分sTab.3 Stop time of station

4.1.2 參數(shù)設(shè)置

外層算法的決策變量為交路變量λk，l，λk，l為0-1 變量，用于分配列車交路；內(nèi)層算法的決策變量為離站時刻dk，i和到站時刻ak，i，線性化算子αk，i，ta和βk，i，t，dk，i和ak，i用于確定列車到發(fā)時刻，αk，i，t及βk，i，t用于轉(zhuǎn)化非線性約束，其中αk，i，t為0-1 變量，其余為實值變量。算例中所有變量都為非負(fù)整數(shù)，該模型為混合整數(shù)非線性規(guī)劃模型。參數(shù)設(shè)置如表4所示。

表4 參數(shù)設(shè)置Tab.4 Parameter setting

由于相鄰列車的車次編號不確定，為計算行車間隔及滿載率，在優(yōu)化列車前后各設(shè)置6列虛擬列車，編號為{-5，-4，-3，-2，-1，0}及{51，52，53，54，55，56}，其中列車0 及列車51 的停站變量全部為1，即εk，i=1，k=0或51，?i∈ids，并設(shè)置d0，1=0，d51，1= 16200作為發(fā)車時間基準(zhǔn)。

4.2 優(yōu)化結(jié)果分析

4.2.1 結(jié)果分析

為了驗證模型的優(yōu)化效果，將固定開行比例均勻發(fā)車間隔、非固定開行比例均勻發(fā)車間隔、非固定開行比例靈活發(fā)車間隔的時刻表進(jìn)行比較。時刻表比較如圖4所示。圖4a為優(yōu)化前時刻表，3條交路輪流發(fā)車，r1∶r2∶r3=16∶17∶17，行車間隔為5 min20 s；圖4b 為僅優(yōu)化交路計劃得到的時刻表，優(yōu)化后r1∶r2∶r3=14∶18∶18，小交路r3數(shù)量增加；圖4c為綜合優(yōu)化交路計劃及時刻表得到的時刻表，優(yōu)化后r1∶r2∶r3=16∶17∶17，小交路r3數(shù)量未變。

將各時刻表對應(yīng)的滿載率相關(guān)指標(biāo)進(jìn)行比較，不同運(yùn)營計劃類型滿載率相關(guān)指標(biāo)如表5 所示。可以看出，綜合優(yōu)化后，相比優(yōu)化前滿載率最大值下降0.397，滿載率均衡度(方差)下降15.5%，相比部分優(yōu)化滿載率最大值下降0.320，滿載率均衡度下降7.8%。

表5 不同運(yùn)營計劃類型滿載率相關(guān)指標(biāo)Tab.5 Indicators for full load rates of different operation plans

將各時刻表對應(yīng)的區(qū)間滿載率進(jìn)行比較，滿載率比較如圖5所示。優(yōu)化前時刻表圖5a滿載率大于80%的區(qū)間18個，大于90%的區(qū)間8個；僅優(yōu)化交路計劃時刻表圖5b 滿載率大于80%的區(qū)間13 個，大于90%的區(qū)間6個，優(yōu)化效果為27.8%及25%；綜合優(yōu)化時刻表圖5c滿載率大于80%的區(qū)間0個，優(yōu)化效果100%?？梢园l(fā)現(xiàn)，綜合優(yōu)化可以根據(jù)客流需求的方向及數(shù)量，相應(yīng)調(diào)整列車的開行交路及行車間隔，達(dá)到運(yùn)力與需求的匹配，因而優(yōu)化效果較好。

圖5 優(yōu)化后滿載率比較Fig.5 Comparison of full load rates

4.2.2 列車開行數(shù)量影響分析

為了驗證模型的通用性，將列車開行總列數(shù)分別設(shè)置為45，50和60，得到綜合優(yōu)化后的時刻表，優(yōu)化后時刻表比較如圖6 所示。將各時刻表對應(yīng)的區(qū)間滿載率進(jìn)行比較，優(yōu)化后滿載率比較如圖7所示。

圖6 優(yōu)化后時刻表比較Fig.6 Comparison of timetables

圖7 優(yōu)化后滿載率比較Fig.7 Comparison of full load rates

將各時刻表對應(yīng)的滿載率指標(biāo)進(jìn)行比較，不同總開行列數(shù)滿載率指標(biāo)比較如表6 所示。比較不同總開行列數(shù)下的滿載率，可以明顯看到隨著線路運(yùn)力增加，滿載率最大值及均衡度都在減小，同時隨著列車數(shù)量增加，交路計劃及時刻表優(yōu)化的靈活度也增加，在均衡度最小化的目標(biāo)下，滿載率最小值甚至有小幅度提升。

表6 不同總開行列數(shù)滿載率指標(biāo)比較Tab.6 Indicators for full load rates of different number of operation trains

5 結(jié)束語

在城市軌道交通行車組織多樣化背景下，為提升運(yùn)輸能力對于時變客流的適應(yīng)性，實現(xiàn)高品質(zhì)的快捷運(yùn)輸服務(wù)，以混合交路運(yùn)營線路為研究對象，圍繞交路計劃及時刻表綜合優(yōu)化。結(jié)果表明，相較于傳統(tǒng)的固定開行比例的交路計劃、均勻發(fā)車間隔的時刻表，非固定開行比例、靈活發(fā)車間隔的交路計劃及時刻表對時變客流的適應(yīng)性更好，運(yùn)輸能力更大。通過分層優(yōu)化算法，對原問題求解更加便捷，外層采用禁忌搜索獲得較優(yōu)的交路計劃，內(nèi)層采用分支切割算法獲得交路計劃對應(yīng)的列車時刻表，逐層減少約束數(shù)量，提升大規(guī)模混合整數(shù)非線性規(guī)劃模型的求解速度。