郭根材，張軍鋒

GUO Gencai, ZHANG Junfeng

（中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081)

(Institute of Computing Technologies, China Academy of Railway Sciences Corporation Limited, Beijing 100081,China)

0 引言

旅客行程規(guī)劃是鐵路客運服務的重要內(nèi)容,根據(jù)旅客提供的出發(fā)城市、目的城市、出發(fā)時間等信息為旅客規(guī)劃出行乘坐的列車車次、上車站、下車站、上車時間、下車時間等信息。高效的行程規(guī)劃算法可以為旅客提供更高服務頻率或更短旅行時間的乘車方案。

國內(nèi)學者對旅客行程規(guī)劃模型及求解算法已經(jīng)進行了相關研究。史峰等[1]綜合考慮換乘距離和換乘次數(shù)2個因素建立了旅客換乘方案優(yōu)化模型,提出求解算法。崔炳謀等[2]根據(jù)列車服務網(wǎng)設計了最短路法、列車匹配法2種乘車方案搜索算法,通過實例分析提出列車匹配法搜索效率更高。林冬梅等[3]在列車匹配法基礎上提出了換乘節(jié)點匹配法,實現(xiàn)不指定換乘地點條件下搜索同城換乘方案。張銥瑩等[4]基于客運換乘網(wǎng)絡的特點、結(jié)構(gòu),以旅客總旅行時間最短和總出行費用最低為優(yōu)化目標,建立了綜合客運換乘網(wǎng)絡優(yōu)化模型,采用遺傳算法對模型求解。這些研究為換乘方案的搜索提供了有效方法。

隨著我國高速鐵路快速成網(wǎng)運營,客流呈井噴式增長,旅客對服務頻率的要求逐步提高。我國高速鐵路大節(jié)點OD的客流量大、列車始發(fā)終到條件好,服務頻率高；中小節(jié)點OD的客流量小、列車停站少,服務頻率相對較低。在2個直達服務之間,通過搜索旅客在樞紐換乘的乘車方案可以在一定程度上提高服務頻率、減少候車時間。為此,研究提出3種直達與換乘相組合的行程規(guī)劃模式,構(gòu)建基于列車服務網(wǎng)的行程規(guī)劃模型,設計了基于帕累托最優(yōu)與換乘節(jié)點匹配法相結(jié)合的乘車方案搜索算法,實現(xiàn)直達與換乘組合行程方案的智能推薦。

1 旅客行程規(guī)劃模型

1.1 直達與換乘相組合的行程規(guī)劃模式

直達與換乘相組合的行程規(guī)劃模式是在提供直達方案的同時,提供候車時間或乘車時間更短的換乘方案供旅客選擇,從而提高客流OD的服務頻率。

直達與換乘相組合的行程規(guī)劃模式主要有以下3種。①“早發(fā)早到”模式。該模式是指在直達方案發(fā)車時間之前搜索到達時間早于直達方案的換乘方案,減少“隨到隨走”旅客的候車時間。②“晚發(fā)早到”模式。該模式是指換乘方案的出發(fā)時間晚于直達方案,到達時間早于直達方案,縮短了旅客的乘車時間。③“晚發(fā)晚到”模式。該模式是指換乘方案的出發(fā)時間和到達時間均晚于直達方案,擴大了旅客出發(fā)時間的選擇范圍。直達與換乘相結(jié)合的行程規(guī)劃模式如圖1所示。圖1a中,旅客在t0時刻到達A站,選擇藍色換乘方案l2→l3的候車時間要小于直達方案l1的候車時間圖1b中,旅客選擇換乘方案l2→l3的乘車時間要小于直達方案l1的乘車時間圖1c中,旅客可以選擇比直達方案l1更晚出發(fā)時間的換乘方案l2→l3。

圖1 直達與換乘相結(jié)合的行程規(guī)劃模式Fig.1 Travel planning model with direct service and transfer service

我國高速鐵路大部分換乘樞紐可以實現(xiàn)旅客不出站換乘,提高了換乘的便捷程度,易于旅客接納換乘行程方案。王爽等[5]基于SP調(diào)查與RP調(diào)查分析了旅客的直達與換乘出行的選擇意愿,研究表明在換乘次數(shù)、換乘時間合理的條件下存在一定規(guī)模的旅客愿意接受換乘出行。換乘行程方案可以作為直達行程方案的一種補充,對提高中小節(jié)點的服務頻率具有重要意義。

1.2 旅客行程規(guī)劃模型

旅客行程規(guī)劃可以基于列車服務網(wǎng)建模,將旅客行程規(guī)劃轉(zhuǎn)換為列車服務網(wǎng)的徑路搜索問題。列車服務網(wǎng)是根據(jù)列車徑路、始發(fā)終到站、?？空尽⒙每蛽Q乘等因素設計的有向圖,一個合理的乘車方案即為列車服務網(wǎng)上的一條可行徑路。

1.2.1 列車服務網(wǎng)絡

列車服務網(wǎng)有多種表現(xiàn)形式。史峰等[6]對比分析了無向換乘網(wǎng)絡、有向換乘網(wǎng)絡、混合換乘網(wǎng)絡、完全換乘網(wǎng)絡等多種形式的列車服務網(wǎng)特征,提出適合列車開行方案編制、客流分配等業(yè)務需求的列車服務網(wǎng)。Sch?bel[7]根據(jù)列車開行方案編制需求提出了“Change & Go”列車服務網(wǎng)(以下簡稱“CG列車服務網(wǎng)”),該列車服務網(wǎng)的點由城市節(jié)點、列車停站節(jié)點構(gòu)成,邊由出發(fā)到達邊、乘車邊、換乘邊組成,可用于表達列車開行方案的編制問題。3個城市、3列列車構(gòu)成的CG列車服務網(wǎng)絡如圖2所示,藍色路徑描述了旅客從出發(fā)地至目的地在出行鏈的出發(fā)、乘車、到達行為。

由于列車在經(jīng)停車站的到達與出發(fā)時間不同,將CG列車服務網(wǎng)中的停站節(jié)點擴展為列車到達節(jié)點與列車出發(fā)節(jié)點,并增加列車停站邊,CG列車服務網(wǎng)可轉(zhuǎn)換為包含列車時刻表信息的“Time Change & Go”列車服務網(wǎng)(以下簡稱“TCG列車服務網(wǎng)”)。TCG列車服務網(wǎng)用G= (N,E)表示,其中N為服務網(wǎng)的點集合,由城市節(jié)點Nf、列車出發(fā)節(jié)點Nd、列車到達節(jié)點Na3類節(jié)點組成；E為服務網(wǎng)的邊集合,由出發(fā)邊Ein、乘車邊Erunning、停站邊Edwell、換乘邊Echange、到達邊Eout組成。

圖2 CG列車服務網(wǎng)絡Fig.2 CG train service network

對于列車服務網(wǎng)絡的節(jié)點n∈N,標記描述旅客節(jié)點行為時間信息,用πn表示。當n∈Na∪Nd時,時間標記πn表示列車的到達時間或出發(fā)時間；當n∈Nf時,πn表示旅客的意愿出發(fā)時間或到達時間。

列車服務網(wǎng)絡的邊e∈E有3個權(quán)重系數(shù)ωe,te,pe,分別用于記錄行程方案的換乘次數(shù)、旅行時間、票價,各權(quán)重系數(shù)的取值方法如下。

（1）換乘次數(shù)權(quán)重系數(shù)ωe。換乘次數(shù)權(quán)重系數(shù)ωe根據(jù)邊的類型取值,當邊e∈Echange時,換乘權(quán)重系數(shù)ωe取1,否則取0。

（2）時間權(quán)重系數(shù)te。時間權(quán)重系數(shù)te根據(jù)邊兩端點的時間標記計算,可以表示為

式中：i∈N表示邊e的起點,j∈N表示邊e的終點。

（3）票價權(quán)重系數(shù)pe?？紤]到旅客的行程總費用與出行里程有關,邊的票價權(quán)重系數(shù)pe采用單位里程計價方式設置,可以表示為

式中：de為乘車邊e的物理距離；φ為票價率。

構(gòu)建TCG列車服務網(wǎng)的換乘邊時應考慮旅客在樞紐的最小換乘時間,只有列車到發(fā)間隔大于最小換乘時間時才構(gòu)建換乘邊。TCG列車服務網(wǎng)的換乘邊數(shù)量要遠小于CG列車服務網(wǎng),有利于提高行程方案搜索效率。最小換乘時間根據(jù)是否同站換乘、市內(nèi)交通條件、車站換乘條件等設定。圖2中CG列車服務網(wǎng)轉(zhuǎn)換成后的TCG列車服務網(wǎng)絡如圖3所示。

1.2.2 旅客行程規(guī)劃模型

圖3 TCG列車服務網(wǎng)絡Fig.3 TCG train service network

根據(jù)網(wǎng)絡流平衡原理,建立給定客流源點o、客流匯點d、旅客意愿乘車時間td與到達時間ta的旅客行程規(guī)劃模型。決策變量xe表示客流od的行程規(guī)劃方案是否使用列車服務網(wǎng)的邊e∈E,使用時xe取1,否則取0。結(jié)合TCG列車服務網(wǎng)的邊權(quán)重系數(shù),構(gòu)建模型目標函數(shù)。

式中：F1為旅客的總換乘次數(shù)；F2為旅客的總旅行時間；F3為旅客的總旅行費用。

設計目標權(quán)重系數(shù)φ1,φ2,φ3,將多目標規(guī)劃轉(zhuǎn)換為單目標規(guī)劃,基于TCG列車服務網(wǎng)的旅客行程規(guī)劃模型可表示為

公式⑹為廣義目標函數(shù),表示旅客的廣義費用最??；公式⑺表示客流源點流量守恒；公式⑻表示客流匯點流量守恒,約束從客流源匯點間的最優(yōu)路徑有且只有一條；公式⑼為網(wǎng)絡流平衡約束,即除去客流源匯點的其他節(jié)點流入量等于流出量；公式⑽為意愿乘車時間約束,行程方案的乘車時間大于旅客的意愿乘車時間；公式⑾為到達時間約束,行程方案的到達時間小于旅客的意愿到達時間；公式⑿限制客流徑路不使用客流源匯點不相關聯(lián)的出發(fā)邊與到達邊；公式⒀為決策變量約束。

2 旅客行程規(guī)劃算法設計

不同的旅客對旅行時間、換乘次數(shù)、票價等因素的敏感度不同,模型目標權(quán)重的設置有較大差異,在搜索行程規(guī)劃方案時應盡可能提供滿足多類旅客意愿的乘車方案。為避免函數(shù)權(quán)重對求解結(jié)果的影響,采用帕累托最優(yōu)思想設計模型求解算法。

帕累托最優(yōu)解集是由任一個目標函數(shù)值的提高都必須以犧牲其他目標函數(shù)值為代價的解集合,即帕累托最優(yōu)解至少有一個目標函數(shù)比最優(yōu)解集之外的解好,并且其他目標函數(shù)不比集合之外的解差[8]。鐵路服務多種類型的客流,某個帕累托最優(yōu)解是某一特定類型旅客的最出行方案,旅客行程規(guī)劃模型的帕累托最優(yōu)解集更適合作為旅客的行程規(guī)劃方案。考慮到我國鐵路尚未執(zhí)行折扣票價,不同乘車方案的價格差異不大,因而暫且不考慮票價對行程方案的影響。利用帕累托最優(yōu)思想,在換乘節(jié)點匹配法[3]基礎上設計直達與中轉(zhuǎn)相結(jié)合的旅客行程方案搜索算法(以下簡稱“DTA算法”),搜索滿足“早發(fā)早到”“晚發(fā)先到”“晚發(fā)晚到”模式的帕累托最優(yōu)解集,即為旅客提供的行程規(guī)劃方案至少保證總旅行時間最短或總換乘次數(shù)最少。DTA算法核心思想是深度搜索與枚舉搜索,并利用到發(fā)時間排序減少搜索次數(shù)。DTA算法流程由直達方案搜索、一次換乘方案搜索、二次換乘方案搜索組成,并可根據(jù)李金梅等提出的樞紐銜接評價方法進一步評價樞紐的換乘接續(xù)水平。DTA算法流程如圖4所示。

圖4 DTA算法流程圖Fig.4 DTA algorithm flow

3 案例分析

選取2017年7月我國高速鐵路列車時刻表作為案例研究對象,設置同站換乘的最小換乘時間為15 min,采用C#語言編程驗證DTA算法,搜索任意2個車站間的直達與換乘相組合的行程方案。青島—上海間旅客直達乘車方案如表1所示。青島—上海間直達與換乘相組合的行程方案如圖5所示。圖5中顯示了18個乘車方案,由4個直達方案與14個換乘方案組成。直達與換乘相結(jié)合行程方案有效提高了服務頻率,并將乘車時間范圍由6 : 46—16 : 22擴大到6 : 33—17 : 11。

表1 青島—上海間旅客直達乘車方案Tab.1 Direct service plan between Qingdao and Shanghai

對我國高速鐵路服務的客流OD搜索行程方案,組合行程方案與直達行程方案的服務頻率比較如圖6所示。從圖6可以看出,直達與換乘相結(jié)合的行程規(guī)劃降低了服務頻率在1 ～ 3次/d的客流OD 比例,提高了服務頻率在5 ～ 15次/d的客流OD比例,高鐵客流OD的平均服務頻率由5.74次/d提高到11.57次/d。

圖5 青島—上海間直達與換乘相組合的行程方案Fig.5 Travel plan with direct service and transfer service between Qingdao and Shanghai

圖6 組合行程方案與直達行程方案的服務頻率比較Fig.6 Comparison of Service Frequency between combination service and direct service

4 結(jié)束語

基于帶時刻表信息的列車服務網(wǎng)構(gòu)建包含意愿乘車時間與到達時間的行程規(guī)劃模型,并利用帕累托最優(yōu)原理設計了直達與換乘相組合的行程方案搜索算法,實例驗證可以有效搜索出符合“早發(fā)早到”“晚發(fā)早到”“晚發(fā)晚到”模式的換乘行程方案,對于實現(xiàn)不增開列車條件下鐵路服務頻率的大幅提高具有重要意義,可以為鐵路12306系統(tǒng)行程規(guī)劃功能的優(yōu)化提供參考。列車時刻表的編制質(zhì)量直接影響旅客行程方案質(zhì)量,尤其是旅客在樞紐的換乘時間,下一步可以加強在列車運行圖編制階段列車接續(xù)關系設計的研究,優(yōu)化換乘樞紐存在大量旅客換乘的列車到發(fā)時間間隔,盡可能地減少旅客換乘時間,從而進一步減少旅客總旅行時間。