直达与换乘相结合的旅客行程规划模型与算法研究

郭根材，张军锋

GUO Gencai, ZHANG Junfeng

（中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081)

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

0 引言

旅客行程规划是铁路客运服务的重要内容,根据旅客提供的出发城市、目的城市、出发时间等信息为旅客规划出行乘坐的列车车次、上车站、下车站、上车时间、下车时间等信息。高效的行程规划算法可以为旅客提供更高服务频率或更短旅行时间的乘车方案。

国内学者对旅客行程规划模型及求解算法已经进行了相关研究。史峰等[1]综合考虑换乘距离和换乘次数2个因素建立了旅客换乘方案优化模型,提出求解算法。崔炳谋等[2]根据列车服务网设计了最短路法、列车匹配法2种乘车方案搜索算法,通过实例分析提出列车匹配法搜索效率更高。林冬梅等[3]在列车匹配法基础上提出了换乘节点匹配法,实现不指定换乘地点条件下搜索同城换乘方案。张铱莹等[4]基于客运换乘网络的特点、结构,以旅客总旅行时间最短和总出行费用最低为优化目标,建立了综合客运换乘网络优化模型,采用遗传算法对模型求解。这些研究为换乘方案的搜索提供了有效方法。

随着我国高速铁路快速成网运营,客流呈井喷式增长,旅客对服务频率的要求逐步提高。我国高速铁路大节点OD的客流量大、列车始发终到条件好,服务频率高；中小节点OD的客流量小、列车停站少,服务频率相对较低。在2个直达服务之间,通过搜索旅客在枢纽换乘的乘车方案可以在一定程度上提高服务频率、减少候车时间。为此,研究提出3种直达与换乘相组合的行程规划模式,构建基于列车服务网的行程规划模型,设计了基于帕累托最优与换乘节点匹配法相结合的乘车方案搜索算法,实现直达与换乘组合行程方案的智能推荐。

1 旅客行程规划模型

1.1 直达与换乘相组合的行程规划模式

直达与换乘相组合的行程规划模式是在提供直达方案的同时,提供候车时间或乘车时间更短的换乘方案供旅客选择,从而提高客流OD的服务频率。

直达与换乘相组合的行程规划模式主要有以下3种。①“早发早到”模式。该模式是指在直达方案发车时间之前搜索到达时间早于直达方案的换乘方案,减少“随到随走”旅客的候车时间。②“晚发早到”模式。该模式是指换乘方案的出发时间晚于直达方案,到达时间早于直达方案,缩短了旅客的乘车时间。③“晚发晚到”模式。该模式是指换乘方案的出发时间和到达时间均晚于直达方案,扩大了旅客出发时间的选择范围。直达与换乘相结合的行程规划模式如图1所示。图1a中,旅客在t0时刻到达A站,选择蓝色换乘方案l2→l3的候车时间要小于直达方案l1的候车时间图1b中,旅客选择换乘方案l2→l3的乘车时间要小于直达方案l1的乘车时间图1c中,旅客可以选择比直达方案l1更晚出发时间的换乘方案l2→l3。

图1 直达与换乘相结合的行程规划模式Fig.1 Travel planning model with direct service and transfer service

我国高速铁路大部分换乘枢纽可以实现旅客不出站换乘,提高了换乘的便捷程度,易于旅客接纳换乘行程方案。王爽等[5]基于SP调查与RP调查分析了旅客的直达与换乘出行的选择意愿,研究表明在换乘次数、换乘时间合理的条件下存在一定规模的旅客愿意接受换乘出行。换乘行程方案可以作为直达行程方案的一种补充,对提高中小节点的服务频率具有重要意义。

1.2 旅客行程规划模型

旅客行程规划可以基于列车服务网建模,将旅客行程规划转换为列车服务网的径路搜索问题。列车服务网是根据列车径路、始发终到站、停靠站、旅客换乘等因素设计的有向图,一个合理的乘车方案即为列车服务网上的一条可行径路。

1.2.1 列车服务网络

列车服务网有多种表现形式。史峰等[6]对比分析了无向换乘网络、有向换乘网络、混合换乘网络、完全换乘网络等多种形式的列车服务网特征,提出适合列车开行方案编制、客流分配等业务需求的列车服务网。Schöbel[7]根据列车开行方案编制需求提出了“Change & Go”列车服务网(以下简称“CG列车服务网”),该列车服务网的点由城市节点、列车停站节点构成,边由出发到达边、乘车边、换乘边组成,可用于表达列车开行方案的编制问题。3个城市、3列列车构成的CG列车服务网络如图2所示,蓝色路径描述了旅客从出发地至目的地在出行链的出发、乘车、到达行为。

由于列车在经停车站的到达与出发时间不同,将CG列车服务网中的停站节点扩展为列车到达节点与列车出发节点,并增加列车停站边,CG列车服务网可转换为包含列车时刻表信息的“Time Change & Go”列车服务网(以下简称“TCG列车服务网”)。TCG列车服务网用G= (N,E)表示,其中N为服务网的点集合,由城市节点Nf、列车出发节点Nd、列车到达节点Na3类节点组成；E为服务网的边集合,由出发边Ein、乘车边Erunning、停站边Edwell、换乘边Echange、到达边Eout组成。

图2 CG列车服务网络Fig.2 CG train service network

对于列车服务网络的节点n∈N,标记描述旅客节点行为时间信息,用πn表示。当n∈Na∪Nd时,时间标记πn表示列车的到达时间或出发时间；当n∈Nf时,πn表示旅客的意愿出发时间或到达时间。

列车服务网络的边e∈E有3个权重系数ωe,te,pe,分别用于记录行程方案的换乘次数、旅行时间、票价,各权重系数的取值方法如下。

（1）换乘次数权重系数ωe。换乘次数权重系数ωe根据边的类型取值,当边e∈Echange时,换乘权重系数ωe取1,否则取0。

（2）时间权重系数te。时间权重系数te根据边两端点的时间标记计算,可以表示为

式中：i∈N表示边e的起点,j∈N表示边e的终点。

（3）票价权重系数pe。考虑到旅客的行程总费用与出行里程有关,边的票价权重系数pe采用单位里程计价方式设置,可以表示为

式中：de为乘车边e的物理距离；φ为票价率。

构建TCG列车服务网的换乘边时应考虑旅客在枢纽的最小换乘时间,只有列车到发间隔大于最小换乘时间时才构建换乘边。TCG列车服务网的换乘边数量要远小于CG列车服务网,有利于提高行程方案搜索效率。最小换乘时间根据是否同站换乘、市内交通条件、车站换乘条件等设定。图2中CG列车服务网转换成后的TCG列车服务网络如图3所示。

1.2.2 旅客行程规划模型

图3 TCG列车服务网络Fig.3 TCG train service network

根据网络流平衡原理,建立给定客流源点o、客流汇点d、旅客意愿乘车时间td与到达时间ta的旅客行程规划模型。决策变量xe表示客流od的行程规划方案是否使用列车服务网的边e∈E,使用时xe取1,否则取0。结合TCG列车服务网的边权重系数,构建模型目标函数。

式中：F1为旅客的总换乘次数；F2为旅客的总旅行时间；F3为旅客的总旅行费用。

设计目标权重系数φ1,φ2,φ3,将多目标规划转换为单目标规划,基于TCG列车服务网的旅客行程规划模型可表示为

公式⑹为广义目标函数,表示旅客的广义费用最小；公式⑺表示客流源点流量守恒；公式⑻表示客流汇点流量守恒,约束从客流源汇点间的最优路径有且只有一条；公式⑼为网络流平衡约束,即除去客流源汇点的其他节点流入量等于流出量；公式⑽为意愿乘车时间约束,行程方案的乘车时间大于旅客的意愿乘车时间；公式⑾为到达时间约束,行程方案的到达时间小于旅客的意愿到达时间；公式⑿限制客流径路不使用客流源汇点不相关联的出发边与到达边；公式⒀为决策变量约束。

2 旅客行程规划算法设计

不同的旅客对旅行时间、换乘次数、票价等因素的敏感度不同,模型目标权重的设置有较大差异,在搜索行程规划方案时应尽可能提供满足多类旅客意愿的乘车方案。为避免函数权重对求解结果的影响,采用帕累托最优思想设计模型求解算法。

帕累托最优解集是由任一个目标函数值的提高都必须以牺牲其他目标函数值为代价的解集合,即帕累托最优解至少有一个目标函数比最优解集之外的解好,并且其他目标函数不比集合之外的解差[8]。铁路服务多种类型的客流,某个帕累托最优解是某一特定类型旅客的最出行方案,旅客行程规划模型的帕累托最优解集更适合作为旅客的行程规划方案。考虑到我国铁路尚未执行折扣票价,不同乘车方案的价格差异不大,因而暂且不考虑票价对行程方案的影响。利用帕累托最优思想,在换乘节点匹配法[3]基础上设计直达与中转相结合的旅客行程方案搜索算法(以下简称“DTA算法”),搜索满足“早发早到”“晚发先到”“晚发晚到”模式的帕累托最优解集,即为旅客提供的行程规划方案至少保证总旅行时间最短或总换乘次数最少。DTA算法核心思想是深度搜索与枚举搜索,并利用到发时间排序减少搜索次数。DTA算法流程由直达方案搜索、一次换乘方案搜索、二次换乘方案搜索组成,并可根据李金梅等提出的枢纽衔接评价方法进一步评价枢纽的换乘接续水平。DTA算法流程如图4所示。

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

3 案例分析

选取2017年7月我国高速铁路列车时刻表作为案例研究对象,设置同站换乘的最小换乘时间为15 min,采用C#语言编程验证DTA算法,搜索任意2个车站间的直达与换乘相组合的行程方案。青岛—上海间旅客直达乘车方案如表1所示。青岛—上海间直达与换乘相组合的行程方案如图5所示。图5中显示了18个乘车方案,由4个直达方案与14个换乘方案组成。直达与换乘相结合行程方案有效提高了服务频率,并将乘车时间范围由6 : 46—16 : 22扩大到6 : 33—17 : 11。

表1 青岛—上海间旅客直达乘车方案Tab.1 Direct service plan between Qingdao and Shanghai

对我国高速铁路服务的客流OD搜索行程方案,组合行程方案与直达行程方案的服务频率比较如图6所示。从图6可以看出,直达与换乘相结合的行程规划降低了服务频率在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 结束语

基于带时刻表信息的列车服务网构建包含意愿乘车时间与到达时间的行程规划模型,并利用帕累托最优原理设计了直达与换乘相组合的行程方案搜索算法,实例验证可以有效搜索出符合“早发早到”“晚发早到”“晚发晚到”模式的换乘行程方案,对于实现不增开列车条件下铁路服务频率的大幅提高具有重要意义,可以为铁路12306系统行程规划功能的优化提供参考。列车时刻表的编制质量直接影响旅客行程方案质量,尤其是旅客在枢纽的换乘时间,下一步可以加强在列车运行图编制阶段列车接续关系设计的研究,优化换乘枢纽存在大量旅客换乘的列车到发时间间隔,尽可能地减少旅客换乘时间,从而进一步减少旅客总旅行时间。