基于开行方案的高速铁路客流分配方法研究

李文卿，倪少权,2,3，杨渝华，文 迪

(1.西南交通大学 交通运输与物流学院，四川 成都 610031；2.西南交通大学 全国铁路列车运行图编制研发培训中心，四川 成都 610031；3.西南交通大学 综合交通运输智能化国家地方联合工程实验室，四川 成都 610031)

基于开行方案的客流分配方法用以在给定开行方案下估计客流在各条列车服务路径上的分配情况，进而评估票价收入和所有旅客的广义出行费用，是开行方案评估反馈循环的重要组成部分。

国内外学者对客流分配方法进行了大量研究。最早的客流分配方法是在制定开行方案之前，将旅客按照一定的规则预分配至物理路径上[1-2]，此类方法忽略了旅客的自由选择和列车服务对旅客的影响。随着研究者逐渐重视旅客的效用，以及旅客出行选择行为研究的深入，基于列车开行方案的客流分配方法研究受到了更多关注。此类研究多采用基于图论的寻路算法和配流算法结合的求解框架，为描述旅客基于列车服务的旅行过程，需建立一个由节点和加权弧组成的服务网络，节点表示旅客在旅行过程中的不同状态，弧段表示旅客的不同旅行过程，弧的权重表示相应旅行过程的广义费用，通过寻路算法求解各点对之间旅客广义出行费用最小的路径，最后通过配流算法按一定规则将客流量加载到路径上。研究考虑了哪些旅行过程决定了服务网络的结构，进而决定了节点和弧段的数量，最终影响寻路算法的求解效率。文献[3]从适用问题、节点和弧段数量等角度对不同结构的服务网络进行了分析，文献[4-8]建立了不同结构的服务网络进行客流分配。上述研究假设旅客能完全知悉网络中各条路径的阻抗且一定选择广义费用最小的路径，属于单路径确定性配流。文献[9-10]认为旅客对路径阻抗的认知可能有偏差且个人选择行为带有一定的随机性，因此基于广义费用按概率将客流分配至多条备选路径上更加合理。根据是否基于用户均衡定理，配流算法可以分为用户均衡配流和非用户均衡配流两个范畴。基于用户均衡定理的研究认为，列车上旅客数增加会使列车的拥挤度即路径的阻抗增加，因此高速铁路(以下简称高铁)客流分配和公路交通流分配具有相似性，应满足用户均衡定理；文献[11-12]认为高速列车不存在拥挤，并且高铁的旅客出行选择过程并不是实时占用列车能力，而是在购票的一瞬间占用列车能力，因此不满足用户均衡定理的适用条件。是否引入用户均衡定理对配流结果有较大影响，因此有待于进一步研究。

在上述研究的基础上，本文以提高客流分配方法的准确性和求解效率为目的，从寻路算法和配流算法两个维度展开研究。在高铁系统中，路径搜索建立在开行方案即列车服务的基础上，因此本文提出一种直接基于开行方案搜索的两阶段寻路算法，与既有研究相比，避免了建立复杂的服务网络与冗余的节点搜索，算法的求解效率得到了显著提升。由于列车定员与列车运行图的限制，高铁系统中乘车路径的容量和阻抗通常是确定的，因此用户均衡定理不适用于高铁客流分配，本文对此进行了分析与证明。最后使用成渝地区高铁网络客流分配案例验证了方法的有效性。

1 问题分析

客流分配方法的本质是模拟旅客为了实现位移选择乘车方案的过程，要求准确地描述旅客出行选择行为。

现实中，旅客的出行选择分为两个阶段，第一阶段为根据公布的列车运营计划寻找所有可行的乘车方案。如果某一列车的停站包括旅客出行起讫点，则该列车为一个可行的直达乘车方案，如果不存在直达乘车方案，则需要寻找由至少2列车组成的换乘方案。由于换乘不仅会给旅客带来额外的广义费用，还会增加旅途的不确定性，旅客会优先考虑中转换乘次数最少的乘车方案；第二阶段为根据各个备选乘车方案的广义费用确定最佳乘车方案，最后通过购票预订相关的列车服务。上述过程和现有的客流分配方法存在一定的差异，主要体现在以下2个方面。

1.1 与现有寻路算法的差异

现实中旅客的“寻路”是先根据列车运营计划寻找可行的乘车方案，最终选择广义费用最小的方案。而现有的基于图论的寻路算法是在搜索过程中考虑最小化广义费用，即依据旅行过程的广义费用寻找最佳方案。为了全面地考虑旅行过程，后者需要根据开行方案设置大量的虚拟列车节点，在每次搜索过程中获取单个源点到所有其他节点的最短路，但最终仅有OD节点之间的最短路被利用了。换言之，大量的节点搜索是冗余的，因为本质上只有关于OD节点间可行的乘车方案的节点是有意义的，而开行方案本身已充分包含寻找可行的乘车方案的所有信息。由于开行方案问题不涉及时间窗，根据区间运行时间标准，车站乘降、停站、换乘时间标准和票价标准等已知信息即可确定广义费用最小的乘车方案。

1.2 与现有配流算法的差异

现有高铁客流分配方法的核心思想大多为用户均衡理论，该理论的适用环境须满足以下假设：①出行者可以最大限度获知起讫点间各条路径的阻抗信息；②出行者可以在任意情况下自由选择路径；③大多数出行者是理性的，一般会选择阻抗最低的路径；④在一定范围内，路径的阻抗会受到其使用者人数的影响，二者一般呈正比例关系。

与完全满足上述条件的公路系统不同，尽管铁路系统满足条件①和条件③，但显然并不满足条件②和条件④。条件②意味着即使某条路径发生拥堵，但只要该条路径的阻抗低于其他路径，出行者依然可以选择。但在铁路系统中，出行者选择路径体现为通过购票预订列车席位，会受到列车定员和售票策略的制约。为了保证高铁良好的服务质量，一般不允许超员或仅发售少量无座票，因此当某条路径涉及的相关列车的席位售罄时，便不再允许出行者进入；针对条件④，路径阻抗通常表示为使用该路径需支出的广义费用，主要由时间和票价组成，在大多数公共交通系统中，运输工具内部的拥挤度也是考虑因素之一。但在铁路系统中，路径由一列或多列高速列车构成，其时间由列车运行图决定，票价由票价率和运输距离决定，二者基本固定不变，且由于不允许超员，车厢内的拥挤度亦不需考虑，因此，各条路径的广义费用不会受到使用人数变化的影响。

综上所述，由于高铁系统不完全满足用户均衡定理的适用条件，所以高铁客流分配不会达到用户均衡状态，第2节对此推论进行数学证明。

2 关于用户均衡定理不适用于高铁客流分配的证明

铁路系统路径示意见图1：o、d为一对起讫点；l1、l2为o、d之间的两条路径；t1、t2为阻抗函数，A1、A2分别为l1和l2中席位数最少列车的定员；q1、q2为各条路径负载客流量，q1、q2未知；q为总客流需求量，q已知且q1+q2=q。

图1 铁路系统路径示意图

由用户均衡定理可知，在满足所有假设的情况下，当所有出行者均选定自己的路径不做改变时，所有被使用路径的阻抗相同且为最小值，任意出行者改变其选择都会使自身的广义出行费用增加，此时系统达到用户均衡状态。路径流量q1、q2与下列优化问题的最优解等价

(1)

s.t.

(2)

0≤qi≤Ai∀i∈{1,2}

(3)

由于高铁系统的路径阻抗不受出行者选择的影响，阻抗函数t1和t2为常量，由a1和a2表示。

式(1)可以改写为

(4)

将式(2)等价变换为q2=q-q1代入式(4)中，得到新的目标函数

min[(a1-a2)q1+a2q]

(5)

式中：a1、a2、q为已知量且均为正数，若要得到最优解，分为以下3种情况讨论：

(1)当a1>a2时，a1-a2>0，只有当q1取最小值时得到最优解，最优解为q2=min{A2,q},q1=max{0,q-q2}。所有旅客会优先选择阻抗较低的路径l2直至满载，未能成功预订l2列车席位的剩余客流只能选择路径l1。在该状态下，所有旅客均无法通过改变其出行选择降低自身的广义出行费用，但t1和t2显然不相等，且t1>t2恒成立，不满足用户均衡状态。

(2)当a1

(3)当a1=a2时，式(5)等价为常数函数，无论q1取任何值，目标函数均不发生变化，任何满足约束条件式(2)和式(3)的解均可作为最优解。在该状态下，尽管t1=t2恒成立，但任意旅客改变其出行路径均不会使自身的广义出行费用发生变化，不满足用户均衡状态。

综上所述，用户均衡定理并不适用于高铁客流分配。

3 基于开行方案搜索的客流分配算法

3.1 算法思路

算法分为基于开行方案搜索的两阶段k短路算法和全有全无配流算法两部分。

旅客选择高铁出行的必要条件为起讫点间有列车服务，分为直达与换乘两种情况，直达要求至少有一列车的停站序列同时包含起讫点，换乘要求至少有两列车的停站序列中分别包含起点和讫点且相关列车可以组成完整的出行链。将开行方案中的列车集合分为4个子集：a. 同时包含起讫点的列车；b. 包含起点但不包含讫点的列车；c. 不包含起点但包含讫点的列车；d. 不包含起讫点的列车，子集a中的列车可以满足旅客直达的需要，若不存在直达列车，以预期换乘次数递增的规则搜索子集b、 c、 d以寻找可以组成完整出行链的列车集合。搜索出行链的思路为：若预期换乘一次，则在子集b和子集c中各选出一列列车，选取规则为两列车的停站序列的交集非空，代表存在换乘站可使旅客完成换乘出行；若预期换乘两次，则在子集b、c、d中各选取一列列车，选取规则为子集b、c中两列车的停站序列交集为空，子集b、d中两列车和子集c、d中两列车的停站序列交集非空，代表旅客可以从子集b中的列车换乘到子集d中的列车，再换乘到子集c中的列车完成出行；若预期换乘次数大于两次，则需要再从子集d中选择一列车，选取规则与前一情境类似，关键是组成起讫点间的完整出行链。由于换乘会给旅客带来较大不便，一般旅客会偏好换乘次数少的路径。因此在配流过程中，按换乘次数递增的规则，逐步搜索可行的路径集合，根据各时间标准、票价率和站间距等已知信息计算各条路径的广义出行费用。随后对可行路径集中的所有路径按广义出行费用进行排序，利用全有全无法将客流按广义费用从低到高的顺序逐次加载到相应的路径上。

当客流量较大时，需要考虑长途与短途、直达与换乘的旅客出行选择冲突。根据铁路售票策略，本文采用先长途后短途、先直达后换乘的规则。具体思路为：按旅途距离从高到低的顺序，对所有OD对按旅客预期换乘次数递增的顺序优先分配长途和直达旅客的列车席位，再分配短途和换乘旅客的列车席位，每次分配后需要扣除已加载客流列车的可供分配席位，直至配流完毕。完整算法流程见图2。

图2 算法流程图

3.2 符号定义

表1 符号定义

3.3 算法设计

o,d∈Ht

(6)

若t满足

(7)

若t满足

(8)

若t满足

(9)

(10)

(11)

由于高铁成网后直达率较高且旅客一般不考虑换乘次数较高的路径，为了简化表述，在此不考虑m>2的情况。

m={0,1,2}时的o,d之间的备选乘车方案搜索过程见图3。

图3 备选乘车方案搜索过程

(12)

式中：δ和η分别为时间因素和费用因素的权重，δ,μ≥0且δ+μ=1。

(13)

(14)

将所有备选乘车方案按Co,d的升序排列，即可快速枚举出o,d之间k取任意值的k短路。

最后，在满足列车容量约束的条件下将客流依次加载到最优乘车方案中的相关列车上，直至o,d间的总客流加载完毕或席位耗尽。

算法步骤如下：

Step1将所有OD按旅途距离的降序进行排列，设OD总数为N，序号为n，令n=0。

3.4 算法时间复杂度分析与比较

(15)

式中：α,β,γ分别为所有起讫点中可不换乘到达，需换乘1次到达和需换乘2次到达的比例，α+β+γ=1且α,β,γ∈[0,1]。

不同算法时间复杂度的对比结果见表2。

表2 不同算法时间复杂度的对比结果

图4 不同算法的时间复杂度变化对比图

图5 不同参数的算法1时间复杂度变化对比图

4 算例验证

采用2018年4月10日起执行的成渝地区部分高铁网络及列车开行方案进行验算，见图6。包含4种不同速度等级的线路和46个车站，其中包括4个省会始发站、20个非省会始发站和24个普通站，日开行超过250对不同等级的高速列车，为1 035个OD对提供优质的列车服务。经测算，在既有物理网络和开行方案条件下，约72%OD对可以直达，约28%的OD对可经1次换乘到达(α≈0.72，β≈0.28，γ=0)。

图6 成渝地区部分高铁网络拓扑图

4.1 参数设置

按全国平均收入水平设置旅客平均单位时间价值为30元/h。票价按区间距离乘以票价率计算。δ和η分别设为0.6、0.4。G、D字头的高速列车票价率分别设为0.45、0.4元/km。区间运行时间标准为区间距离和列车运营速度之比。车站乘降、停站和换乘时间标准按不同的车站规模确定，见表3。所有算法使用Matlab R2015a优化器进行测试，运行环境为Intel core i7-7700HQ四核处理器、8 GB内存的计算机。

表3 车站时间标准参数设置

4.2 算法测试

分别使用算法1、算法2和算法3求解所有OD对的最短路或k短路(k=3)，结果见表4。

表4 寻路算法运算时间对比

算法2和算法3的运算时间分为2部分：构建服务网络时间和寻路时间。构建服务网络需要遍历1次开行方案，当所有OD对均可直达时，算法1同样只需遍历1次开行方案，因此算法1的运算时间与算法2、3的构图时间相近。由于需要搜索大量节点，算法2的运算时间是算法1的3倍以上。由于算法3需要重复进行k次搜索，所以运算时间远长于算法1和算法2。

按包含车站规模和区间里程对所有OD对进行降序排序，按顺序基于算法1求得各OD对的k短路及其广义出行费用，使用全有全无配流法将客流需求量一次性分配到对应路径上。运算时间约4.5 s，客流分配统计结果见表5。

表5 客流分配结果统计

5 结论

客流分配方法作为铁路运输计划评估反馈循环中的重要组成部分，在开行方案优化过程中需要多次调用，其运算效率和合理性对开行方案优化的速度和质量有重要影响。基于高铁客流分配的特点，本文从寻路算法和配流算法两个维度对高铁客流分配方法进行了研究。

同基于图论的寻路算法相比，本文提出的算法会产生2种时间结余：①无需构建服务网络所节约的时间；②基于开行方案针对OD进行精确搜索而无需搜索冗余节点所节约的时间。此外，当高铁网络的连通性提升时，算法的运算时间会进一步降低。

由于高铁不存在拥挤现象，将适用于公路交通流分配的用户均衡定理直接引入高铁客流分配是不合理的。本文对用户均衡定理不适用于高铁客流分配进行了证明。高铁客流分配实际上是旅客购票的过程，因此全有全无配流更符合实际，且由于避免了为实现均衡而反复迭代，显著提高了算法的运算效率。

通过考虑每列车的时间窗或在售票周期内根据售票策略动态改变列车停站序列，本文提出的算法可以拓展到基于列车运行图的客流分配问题或考虑售票策略的客流分配问题，能否在上述问题中取得较好结果有待进一步研究。