基于差异化换乘感知的轨道交通末班车衔接优化

袁振洲，魏 来，吴玥琳，代鲁峰，肖清榆

(北京交通大学 交通运输学院，北京 100044)

随着城市轨道交通建设的不断推进，轨道交通线路日益增多，路网结构日渐复杂，网络化运营模式逐渐成为规划者的重点关注内容之一.在网络化运营模式下，各线路间的协同组织优化研究对减少乘客换乘等待时间、增加乘客换乘满意度，从而提高轨道交通服务水平有广泛的应用价值.末班车通常运能充足，几乎不会存在因为拥挤导致乘客无法实现换乘的情况.与高峰时段相比，末班车时段列车发车间隔较长，乘客的换乘等待时间普遍长于高峰时段；由于末班车时段的特殊性，如果末班车衔接不当，列车时刻表安排不合理，很可能出现乘客无法实现换乘，从而被迫改乘其他交通工具的情况，结果更为严重.因此，合理制定末班车时段的列车衔接协调方案成为目前亟待解决的重点问题.

多年来，国内外学者对城市轨道交通各线路衔接协调优化问题的研究多集中在考虑高峰时段.Vansteenwegen等[1]考虑不同类型等待时间的权重，使用线性规划模型降低乘客等待时间.Hadas等[2]采用动态规划模型减少乘客总体旅行时间.白广争等[3]以网络中乘客总体换乘等待时间最少及换乘站间列车运行时间调整量最小为目标建立双目标优化模型，采用非支配排序进化算法求解.周艳芳等[4]考虑换乘不满意度最低及大客流优先的原则，提出城市轨道交通列车换乘站到发时间协调控制方法.刘宏杰等[5]提出列车时刻表优化模型使系统的再生能源利用最大化，达到节能的目标.Hassannayebi等[6]以乘客总等待时间和最长等待时间最小化为目标，建立了混合整数线性规划模型和非线性规划模型并进行求解.

近年来，学者们逐步认识到末班车的重要性，开始着眼于末班车衔接优化问题的研究，其中多以国内学者的研究为主.徐瑞华等[7]根据早晚间客流特点和线网协调下列车的时序衔接关系，推算首末班列车的发车时间域的计算方法.郭建媛等[8]分析了随着末班车的运行，整个路网中OD两点间的可达路径逐渐变少即动态可达性，并提出了路网可达性与OD最晚可达时间的计算方法.胡智敏[9]分别以特定换乘方向的末班车客流量最大和基于双向换乘的衔接成功客流量最大为目标函数建立模型，利用遗传算法求解.Kang等[10-12]提出了冗差时间的概念，分别以末班车成功衔接方向最多，乘客换乘等待时间最小，冗差时间最大作为目标函数建立模型，设计了遗传算法，模拟退火算法，两向分解算法进行求解.宁丽巧等[13]通过引入0-1变量和换乘惩罚系数，构建以总乘客换乘等待时间最小化为目标的末班车时段时刻表衔接优化模型，利用CPLEX对混合整数线性规划模型求解.唐国议[14]对城市轨道交通末班车时段可达性进行研究，并面向乘客最大可达性对末班车时刻表进行优化.陈垚等[15]通过延长换乘站停站时间，建立以换乘站成功换乘客流量最大为目标的末班车时刻表优化模型，利用CPLEX分支切割算法求解.姚恩建等[16]以路网动态可达性为目标，建立末班车时刻表优化模型，并设计遗传算法求解.

在末班车衔接问题的既有研究中，学者们通常采用平均换乘走行时间代替所有乘客的实际换乘走行时间以简化模型，显然这种处理并不符合实际；另外，通常以成功换乘人数最大或乘客总体等待时间最小为目标函数，对乘客在不同换乘情形下的换乘满意度即差异化的换乘感知考虑不足.末班车时段为运营结束前列车时刻表对路网可达性起决定性作用的一段时间，也称为晚间时间.本文作者通过协调各线列车的发车时刻，对末班车时段的轨道交通列车衔接问题进行优化.考虑乘客换乘走行时间差异，引入乘客等待时间因子及末班车换乘失败惩罚系数，以乘客总的换乘感知费用最小为目标函数，构建末班车时段列车时刻表衔接优化模型.针对传统算法精度差、求解效率低，而现有智能算法易早熟收敛无法得到全局最优解的问题，构建了优化的多种群遗传算法对模型求解.

1 问题描述

1.1 条件假设

1)末班车时段列车运能充足，乘客不存在因为拥挤错过列车的情况，且乘客均搭乘到达站台后遇到的首班列车.

2)末班车时段内列车采取均匀发车方式，即同一线路列车发车间隔相同且已知.

3)不考虑列车延误的影响，即列车的区间运行时间和各站的停站时间固定且已知.

1.2 列车接续关系与乘客感知费用分析

影响乘客换乘接续列车的主要因素为换入线路列车到达时间、乘客换乘走行时间、换出线路列车发车时间.对于任意换乘站，列车接续关系示意见图1.

考虑末班车时段[Ta,Tb]，在换乘站s，乘客m从线路i的第k列车换到线路j的接续过程.乘客m到达线路j站台的时刻为换出线路i的第k列车到达时刻加上乘客m在换乘站s从线路i到线路j的换乘走行时间，该时刻若早于列车p的发车时刻且晚于列车p-1的发车时刻，乘客m可成功换乘到线路j的第p列车；若乘客到达线路j站台的时刻晚于线路j末班列车发车时刻，则换乘失败，换乘等待时间用一个足够大的正整数T来表示.乘客m的换乘等待时间为

(1)

在不同换乘情况下乘客的换乘感受不同：乘客到达站台恰逢列车即将进站时(即just in time)乘客的满意度最高；随着等待时间的增加乘客的满意度逐渐下降；而当乘客到达车站时刚好看到列车离开(即just miss)的失落导致乘客满意度大幅下降；显然乘客由于错过末班车导致不得不换乘其他交通工具时的满意度最低.本文定义不同情况下乘客对换乘等待时间长短或换乘成功与否的不同感受为差异化换乘感知，并用换乘感知费用来定量计算.根据换乘等待时间的不同，乘客换乘感知费用分为以下4种情况讨论：

1)乘客到达换入线路站台，看到站台显示屏显示“列车即将进站”以及列车刚好处于停站等待时满意度最高.调查发现，从站台显示屏显示“列车即将进站”到列车停稳的时间平均为40 s，如图2所示.

乘客走行时间与列车到发时间关系为

(2)

根据列车到发时间关系：

(3)

式(2)等价于：

(4)

(5)

令该种情况下及列车停站时间内到达乘客的换乘感知费用为0，即

(6)

2)根据已有文献，等待时间因子通常取2.5，乘客1 min的等待时间等同于2.5 min的在途时间[17]，即1 min的乘客等待时间导致2.5个单位的总体等待成本，即

(7)

3)考虑客流到达换入线路站台，列车刚好离开“just miss”情况，研究表明“just miss”时间少于30 s时，乘客不满度最高[4]，如图3所示.

乘客走行时间与列车到发时间关系为

(8)

根据列车到发时间关系：

(9)

式(8)等价于：

(10)

(11)

令该种情况下等待时间因子取3.5，代表乘客1 min的等待时间等同于3.5 min的在途时间，即1 min的乘客等待时间会导致3.5个单位的总体等待成本，即

(12)

4)若乘客到达线路j站台的时刻晚于线路j末班列车发车时刻导致换乘失败，换乘感知费用用一个足够大的正整数A来表示.

乘客m的换乘感知费用为

(13)

换乘感知费用与等待时间关系如图4所示.

2 模型构建

2.1 优化目标

以末班车时段，所有乘客的换乘感知费用总和最小为目标，选取各线路末班车时段内第一趟列车的发车时间为决策变量，构建末班车时段时刻表衔接优化模型.通过等待时间因子和换乘失败惩罚费用的引入，可以达到缩短乘客等待时间，减少末班车换乘失败人数的综合目标.

(14)

2.2 约束条件

1)列车到发时间关系约束.

(15)

(16)

(17)

(18)

(19)

2)末班车时间域约束.

(20)

(21)

3)乘客换乘走行时间约束.

(22)

因为乘客的走行速度与乘客的属性(如性别、年龄、携带行李数量等)相关，所以对同一换乘站、同一换乘通道，不同乘客的换乘走行时间不同.

(23)

(24)

可得

(25)

3 算法设计

列车时刻表的制定是一个NP-hard问题[19]，难以用常规方法求解.而遗传算法是一种借鉴生物界自然选择和进化机制发展起来的全局优化搜索算法，具有搜索能力强、鲁棒性强、高度并行、随机的特点，对NP-hard问题是一种较理想的解决方法.而遗传算法也有很多缺陷与不足，其中早熟收敛现象是遗传算法不可忽略的问题.早熟收敛现象是指在遗传算法的运行过程中，群体中的所有个体过早地丧失多样性而停止进化，导致算法的搜索停留在局部最优解，无法得到全局最优解.为了克服早熟收敛现象，许多学者对遗传算法的改进进行了研究，其中包括分层遗传算法、混合遗传算法、自适应交叉和变异率[20]等.本文采取多种群遗传算法(Multiple Population Genetic Algorithm，MPGA)，引入多个种群同时进行搜索优化，不同种群赋予不同的参数，实现不同的搜索目的.各个种群之间采用移民算子进行联系，实现多种群协同进化过程，从而保证最优解的获取是多种群协同优化的综合结果，实现全局最优.算法步骤设计如下：

1)编码策略.

对末班车时段内，各条线路在始发站第一列车的发车时间采用整数编码形式编码，染色体长度由第一列车发车时间的取值范围和线路总数共同决定，一条染色体代表问题的一个解.

2)初始化种群.

在发车时间范围内，随机产生MP个初始种群，每个种群规模为M.

3)目标函数计算.

根据列车接续关系函数、乘客换乘感知函数等确定目标函数，即末班车时段所有乘客的换乘感知费用总和.

4)适应度计算.

考虑文中目标函数的设定为求解最小值，故分别对每一子种群利用函数ranking进行基于排序的适应度分配.函数ranking按照个人目标函数值从小到大的顺序进行排序，并返回一个包含对应个体适应度值的列向量.

5)交叉和变异.

对每个子种群都采用标准遗传算法(Standard Genetic Algorithm，SGA)进化机制，采用随机遍历抽样选择、单点交叉、基本位变异.考虑到交叉算子是产生新个体的主要算子，决定了遗传算法的全局搜索能力；变异算子是产生新个体的辅助算子，决定遗传算法的局部搜索能力，一般采取较大的交叉算子和较小的变异算子.本文中每个子种群的交叉、变异算子由预先设定的取值范围内随机产生，使每个子种群采用不同的算子组合，达到不同的搜索效果.

6)移民条件.

移民算子将各个子种群在进化过程中出现的最优个体，每隔一定的进化代数引入其他子种群中，实现各个独立的子种群之间的信息交换.具体操作为将目标种群中的最差个体由原种群最优个体代替.

7)进化终止条件.

引入精英种群，在进化的每一代，通过人工选择算子选出各个子种群中的最优个体放入精英种群保存，精英种群不进行交叉变异等遗传操作，以保证最优性.将精英种群中的最优个体看作当前代数的最优解，将最优解保持代数作为算法的终止条件.该判断方式相较于常用的达到预先设定的最大遗传代数，考虑了进化过程中的知识积累，更为合理.

4 案例分析

以2018年8月成都市运营中的轨道交通网络作为研究对象，进行案例分析.为方便研究，省略各线路中间站，简化的线网结构见图5.成都市轨道交通线网由1、2、3、4、7、10号线路构成，其中7号线为环线，含9个首末站，14个换乘站，而太平园站既为3、10号线的首末站，又为3、7、10号线换乘站.

将22:00—24:00作为末班车时段，列车时刻表现状方案由成都轨道交通集团官网得到；各换乘站停站时间均设为1 min，通过计算得到各换乘站区间运行时间；列车发车间隔、乘客平均换乘走行时间根据实际测量统计得到；换乘客流量根据2017年12月地铁AFC数据借助Access软件整理计算、预测得到.

参照四阶段法，获得换乘客流量的具体方法如下：首先将地铁AFC系统内储存的大量出行OD数据进行筛选，剔除无效数据(员工卡数据、只包含进站或出站单个信息的数据、同站进出的数据、出行时间过长或过短的数据等)；其次利用增长系数法对未来年的OD交通量进行预测；接着利用Dijkstra算法求出OD点间的最短路径，最短路径的求解函数见式(26)、式(27)，出行阻抗用路径通行时间(到站时间与进站时间差值)表示，利用全有全无分配法将OD交通量分配到具体路径上；最后将经过某换乘站的所有路径的客流量求和，得到末班车时段该换乘站的换乘客流量.

(26)

(27)

从轨道交通网络、换乘站两个层面分析优化结果，验证模型有效性.

1)轨道交通网络层面.

两种算法的迭代过程见图6.由图6可见，SGA经过52代遗传后陷入早熟收敛，进化速度较慢且无法得到最优解；而MPGA克服了SGA的早熟收敛现象，在30代开始最优解趋于稳定，可以得到更优解.

两种算法的优化结果见表2.由表2可以看出，通过MPGA、SGA优化后，末班车时段全网成功换乘客流量分别增加了3.1%、2.7%，乘客换乘感知费用总和分别减少了29.7%、25.0%.

表1 末班车时段各线路第一列车发车时刻及优化结果Tab.1 Optimization results and departure time of the first train during the last train period

2)换乘站层面.

以换乘站为单位进行统计分析，各换乘站现状及两种算法优化后的末班车时段成功换乘客流量及乘客换乘感知费用见图7.由图7可以看出：①经过MPGA优化后，14个换乘站中有9个换乘站的成功换乘客流量增加；经过SGA优化后，14个换乘站中有8个换乘站的成功换乘客流量增加.②经过MPGA优化后，14个换乘站中有12个换乘站的乘客换乘感知费用减少；经过SGA优化后，14个换乘站中有11个换乘站的乘客换乘感知费用减少.

表2 优化前后成功换乘客流量及换乘感知费用总和

综上所述，本文构建的优化模型通过牺牲个别换乘站的乘客满意度以得到全网范围内更多换乘站的乘客实现成功换乘及换乘等待时间的减少，从而提高全网范围内的换乘乘客总体满意度.

5 结论

1)针对城市轨道交通末班车时段各线路衔接协调优化问题，以末班车时段内各线路第一列车的发车时间为决策变量，以全网乘客的换乘感知费用总和最小为目标，构建末班车时段时刻表衔接优化模型.

2)模型考虑了不同乘客的换乘走行时间差异，分析不同情况下乘客的换乘感知，相对于既有研究更加贴合实际，并且更加准确地达到提高乘客换乘满意度的效果.采用多种群遗传算法对模型进行优化求解，对比标准遗传算法，多种群遗传算法可以有效克服早熟收敛现象，得到更优解.验证结果表明，所构建模型可有效降低乘客换乘感知费用.

3)列车延误对末班车时段乘客换乘存在很大影响.后续工作中，将针对列车延误情况下后续列车的衔接方案调整进行深入的研究.