直達(dá)與換乘相結(jié)合的旅客行程規(guī)劃模型與算法研究

郭根材，張軍鋒

GUO Gencai, ZHANG Junfeng

（中國鐵道科學(xué)研究院集團(tuán)有限公司 電子計(jì)算技術(shù)研究所，北京 100081)

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：i∈N表示邊e的起點(diǎn),j∈N表示邊e的終點(diǎn)。

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

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

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

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

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

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

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

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

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

2 旅客行程規(guī)劃算法設(shè)計(jì)

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

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

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

3 案例分析

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

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

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

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

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

4 結(jié)束語

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