基于量子计算的城市轨道交通网络末班车衔接优化

本文发布已获得《都市快轨交通》授权

原文发表于《都市快轨交通》

第 37 卷  第 2 期  2024 年 4 月

如有转载请联系版权方，标明出处

袁也1，徐皓1，王悉2，王振明3，魏艳2，徐辉章3

0引言

城市轨道交通以其大运量、低能耗、安全、快速等特点，成为缓解地面交通压力的重要手段之一[1-2]。随着轨道交通网络规模的快速扩大，在末班车时段，各条线路运营时间存在差异性，经常有乘客无法换乘至相交线路末班车的情况。因此，制定衔接良好的网络末班车时刻表具有重要的现实意义。近年来，国内外学者针对城市轨道交通网络末班车衔接优化问题展开了研究。CHEN等[3]为末班车时刻表优化问题构建了混合整数规划模型，以最大化城市轨道交通在末班车时段的网络可达性为目标，使用遗传算法对问题进行求解；GUO等[4]针对末班车时刻表优化问题设计了一种基于排序的启发式算法；ZHANG等[5]拓展了优化时域以实现末班车和非末班车时刻表的综合协同；郑亚晶等[6]建立了以换乘人数最大化为目标的末班车衔接优化模型，并设计了遗传算法求解；通过考虑乘客换乘走行时间差异，袁振洲等[7]以全网乘客换乘感知费用总和最小为目标，建立了末班车时段多趟列车的时刻表衔接优化模型；卢亚菡等[8]为末班车衔接优化问题建立了一种分布鲁棒机会约束规划模型以最小化换乘失败乘客数量。对于城市轨道交通网络末班车衔接优化问题，已有文献主要基于传统优化算法进行求解。然而，随着线网规模的增大，传统的优化算法很难实现对大规模问题的快速高效求解。因此，开展基于量子计算技术的网络末班车衔接优化问题研究，探索数学模型转换方法并验证应用量子计算解决复杂网络优化问题的可行性，具有重要的理论意义和现实价值。

1问题描述

本文考虑一个包含若干条线路的城市轨道交通网络。L代表研究网络中的线路集合，Il代表线路l的站点集合，Ul代表线路l的换乘站集合，Xl,i代表线路l在换乘站i相交的线路集合。聚焦于不同线路末班车在换乘站的到发衔接情况，着重研究列车及乘客在换乘站的行为。为便于建模，考虑以下假设：

①乘客在同一换乘站相同线路间的换乘走行时间为常量；

②末班列车有充足的运输能力；

③乘客路径通过换乘路径和换乘站的选择提前给定。本研究没有将换乘路径(最短路约束)和换乘站的选择寻优纳入到末班车时刻表衔接模型中，而是利用这些要素来计算换乘乘客需求，并将其作为模型输入。具体来说，依据自动售检票系统(AFC)提供的乘客始发地—目的地的计数信息，以及乘客路径来反推换乘乘客的数量。而这些乘客路径的确定是由所需乘坐距离和换乘次数决定的，涉及换乘路径和换乘站的选择寻优。

2数学模型

2.1列车运行动态建模

公式(1)和(2)描述列车的到发时间：

式中，al,i，dl,i，sl,i分别表示线路l末班车在车站i的到达、出发及停站时间；rl,i指线路l末班车在车站i到i+1的运行时间。在列车运行过程中，列车区间运行时间应控制在上下限范围内，即：式中，min,rli表示线路l末班车在车站i到车站i+1的最短运行时间；max,rli表示线路l末班车在车站i到车站i+1的最长运行时间。列车停站时间应控制在上下限范围内，即：

式中，min,sli表示线路l末班车在车站i的最短停站时间；max,sli表示线路l末班车在车站i的最长停站时间。为保证列车运行安全，相邻车次间的发车间隔需要大于或等于最小发车间隔，即：

式中，hlmin表示线路l的最短发车间隔；,dli- 为线路l末班车的前一列车在车站i的出发时间

2.2乘客换乘行为建模

为了清晰地描述乘客换乘行为，图1给出了末班车衔接示意。线路1末班车(即列车1)进站，换乘乘客下车，通过一段时间的走行抵达换乘线路2列车所在站台。

此时，若列车还未到站(即列车3情况)，则等待其到站后乘客上车，并随列车一同离站；若列车已经离站(即列车2情况)，则从列车1下车的乘客将没有机会换乘至该列车。基于上述描述，乘客换乘过程建模为

式中，ylil,¢ 是0–1决策变量，若线路l′末班车换出的乘客在车站i可以成功换乘至线路l，则ylil,¢ =1，否则为0；,olil¢ 表示乘客在车站i由线路l′换出走行至线路l站台的时间；M为充分大的正数。

2.3目标函数

为了提高末班车时段乘客换乘效率，目标设置为最小化换乘失败的乘客数量，即：

式中，plil,¢ 表示在车站i由线路l′末班车换乘至线路l的客流需求。另外，考虑成功换乘乘客等待时间最小化的目标有助于提升乘客出行体验，增加用户满意度。然而，建模换乘乘客等待时间会涉及非线性项，并且将其线性化处理需要引入更多的约束，这会导致问题变得更复杂，从而影响求解的效率。鉴于此，为了简化问题并确保高效的求解，我们目前的研究只关注失败换乘乘客数量的最小化。

2.4优化模型

根据上述描述，构建混合整数线性规划模型如下：

3模型重构

考虑到末班车衔接优化模型(10)涉及不同线路的列车时刻表变量、运行安全约束以及换乘衔接耦合约束，随着线网规模的增大，计算耗时将随之迅速增加。因此，本节对模型(10)简化处理，将问题拆分成两阶段优化，其中阶段1为换乘站的到发时刻优化，阶段2为其他普通车站到发时刻的递推优化。后续研究仅需对阶段1的模型进行求解，阶段2利用贪心算法快速生成一组可行解。阶段1模型如下：定义合并的区间从i–1站出发到达i站对应的运行时间为Rl,j；定义换乘站/始发站i的停站时间为Sl,i，则有

将模型改为适配量子计算的二值模型，将Sl,i和Rl,j定义为一系列二值变量Sl,i,n和Rl,j,n的表达，式中n=0,1,…,N+1为需要的二进制变量位数，即可满足S和R上下界约束。

换乘站的到发时间表示为

式中，i–1为换乘站i之前的换乘站；1为始发站。模型总结如下：

式中，Rl,j和Sl,i为满足上下界(11)(12)(13)的二进制变量表示之和(14)(15)。鉴于量子计算机可用比特数和精度限制，本文对该模型的求解借鉴了增广拉格朗日算法(augmentedlagrangianmethod，ALM)，将问题迭代求解，对每次求解更新系数，直到找到理论最优解且各约束得到满足。算法如下：输入：初始化μ>0，初始化λ，初始化增加系数ρ>1。输出：最终的μ，l 以及增广拉格朗日函数whilec(x)>0or遍历次数未达上限

在每一步求解中，只需要关注原问题的不等式约束，将其表示为c(x)≤0形式。ALM每一次迭代求解模型如下：

在阶段1问题求解完成后，已知末班车在换乘站到发时刻等信息，需要递推出列车在每一个非换乘站的到发时刻，阶段2问题可等价为求解一组多元线性方程。阶段2方程组如下：

4量子计算方法

量子计算以量子比特为基本单元，利用量子叠加、纠缠、干涉等物理特性进行高速运算，可对组合优化问题进行指数级求解加速。

其中，基于光量子系统的相干伊辛计算架构(coherentisingmachine，CIM)在全连通100000节点的最大割问题中的算法优势已经得到了证明[9]。本文使用的光量子计算机是基于测量反馈的CIM[10]。

作为一种混合量子计算系统，测量反馈型CIM的光学部分采用飞秒脉冲光纤激光器，形成简并光学参数振荡(degenerateopticalparametricoscillators，DOPO)在光纤环路中传输[11]。CIM可被用作求解优化Ising模型的专用计算机。Ising模型的自旋变量取值±1，哈密顿量表示为：

式中，Jij和hi分别为二次系数和线性系数。QUBO模型变量x取值0或1，QUBO模型可以表示为：

基于xi=(1+σi)/2关系，将目标问题的QUBO模型映射到全连通Ising哈密顿量，将Ising模型中的系数输入CIM，通过可控的量子相变过程使哈密顿量最小化，问题即可被CIM有效求解。

5算例分析

为验证所提出模型和方法的有效性，本节选取北京地铁部分网络作为仿真背景，如图2所示。

设置最短停站时间为30s，最长停站时间为60s，换乘走行时间为120s，三条线路的最小运行间隔分别设置为110s、120s和120s。区间运行时间在初始值前后20s范围内浮动。各换乘站的乘客换乘需求量如表1所示。

使用ALM对案例求解的参数设定如表2所示。每次迭代用模拟退火求解，模拟退火参数如表3所示。模型平均迭代约129次得到最优解。

迭代次数分布见图3。

以其中一次为例，迭代次数316次。在得到最优解的最后一次迭代中，λ和μ参数取值如表4所示。

对最终找到最优解的一次迭代使用真机测试。在第371圈找到原问题的最优解，一圈运行时间是10.91μs，量子计算机在4ms求到最优解。相比模拟退火算法，CIM真机在求解的过程中可以更快地找到原问题的最优解。对最后一次迭代对应的问题分别用CIM和模拟退火求解100次，其中最快找到原问题最优解的哈密顿量演化对比如图4所示。

算例模型的时间相关参数以10s为单位，1号线、4号线、5号线的初始站到达时间分别设置为100、200、300个时间单位。对于CIM的求解结果可以验证，在换乘站1217，1号线到达时间为369个时间单位，出发时间为375个时间单位；4号线到达时间为292个时间单位，出发时间为295个时间单位，乘客从4号线可以成功换乘至1号线。在换乘站167，1号线到达时间为438个时间单位，出发时间为444个时间单位；5号线到达时间为365个时间单位，出发时间为368个时间单位，乘客从5号线可以成功换乘至1号线。列车在换乘站的运行和停站时间如表5所示。

量子计算与商业求解器Gurobi计算效率对比如表6所示。

Gurobi在0.3s内得到了模型(10)的最优解，相比之下，量子计算方法的单次迭代可以在更短时间内得到最优解，平均迭代129次能够找到最优解，则期望的求解时间为4ms*129=0.516s，在这个问题上的总体计算时间略长于原整数规划问题的求解器求解。进一步，比较使用Gurobi和量子计算方法来求解转换后的QUBO模型，可以发现Gurobi需要接近102s才能搜索到最优解，而CIM方法仅用0.516s就可以完成求解，说明当模型规模变大时CIM方法更有效率。

6结论与展望

目前轨道交通领域多使用传统的优化算法以及商业解法器进行求解。这些算法和求解器都是基于CPU/GPU等经典计算机研发的，而量子计算机利用了量子系统的物理能量演化实现优化计算，两种计算机的实现原理不同导致目前的优化模型和算法无法直接平移到量子计算机上进行使用。本文对现有数学模型进行重构并转换到量子模型，进一步开发对应的量子算法来实现优化问题的求解，从而验证了应用量子计算解决复杂网络优化问题的可行性。

6.1结论

1)以最小化末班车换乘失败乘客人数为优化目标，构建了面向末班车衔接的混合整数线性规划模型。将原始模型重构为计算规模更小的两阶段模型，并将第一阶段优化模型转化为QUBO模型，提出了面向量子计算的模型重构方法。

2)基于QUBO模型完成了量子计算算法开发和真机实测，从而率先验证了量子计算用于轨道交通优化问题的可行性。考虑到算法具有一定的通用性，这意味着一旦量子计算机硬件成熟，本方法为应用于更大规模和复杂的问题提供了技术支撑。

6.2展望

在未来的研究中，可以进一步把乘客换乘路径和换乘站的选择优化纳入到末班车时刻表衔接模型中，使模型能够更准确地识别不同时间段内的换乘需求，并基于此制定更合理的末班车时刻表衔接方案。此外，受当今量子计算机的硬件规模限制，无法进行更大规模的算例验证。考虑到量子计算的原理，随着问题规模的增加，求解速度优势就会逐步体现出来，考虑到量子计算时间的稳定性，应用量子计算解决轨道交通网络优化问题的算力优势将会不断显现。

BanmenArts & Chinametro