摘要：轨道交通的节能研究在环保与经济方面具有重要的意义.以最小化单列车运行过程中产生的能耗为目标，基于列车的非线性动力学模型构建离散的速度距离网络，将列车运行曲线优化问题转化为一个整数规划问题，采用拉格朗日松弛和最短路径算法优化列车运行曲线.在此基础上，提出在粗粒度网络最优解的小邻域内重构细粒度的速度距离网络的方法，可有效提高运算速度.基于北京地铁亦庄线的线路和车辆数据，设计仿真案例对上述算法进行评估，并与遗传算法、基于CPLEX的整数规划算法和混合整数规划算法的求解效果进行对比.结果表明：提出的基于速度距离网络的求解算法可生成能耗更优且误差较小的列车速度曲线，并精准满足运行时间与终点速度约束.
关键词：交通信息工程及控制;城市轨道交通;列车运行曲线;速度距离网络;拉格朗日松弛
轨道交通具有高速、节能、环保、可靠性高的优点，适应城市发展的需要，能够有效缓解交通压力、促进经济的发展.列车自动运行系统使列车操作自动化，能有效降低司机劳动强度、提高乘客舒适度、提升运输效率.而最优化速度距离运行曲线是列车自动运行(AutomaticTrainOperation，ATO)系统的基础之一[1]，在节能方面发挥着重要的作用.
自1968年Ichikawa[2]首次采用最大值原理对列车运行曲线优化以来，研究学者对列车运行曲线优化展开了广泛而深入的研究.列车通常的行驶模式为牵引-巡航-惰行-制动，可转换为最优控制问题.文献[3]采用极大值原理，对连续时间的列车动力学模型进行求解，画出了控制切换图，求出了列车在完全牵引、部分牵引、惰行、部分制动和完全制动这些控制之间切换的条件.文献[4]则采用伪谱法(Pseudospectralmethod)对列车运行对应的最优控制问题进行求解，与列车时刻表规划相结合，起到了很好的节能效果.若巡航中存在过于陡峭的轨道，需要中断巡航模式，进行牵引或制动.文献[5]使用了综合扰动分析法，证明了能耗函数的凸性，设计了确定陡峭坡道上最优速度转换点的策略.
与此同时，智能优化算法也在列车速度曲线优化问题上得到广泛应用[6].文献[7]采用遗传算法对列车运行曲线进行优化，研究了能耗指标与迭代次数的关系.文献[8]同样选择遗传算法，以触发惰行的速度、牵引力比例、制动力比例为参数，进行了列车运行曲线的优化，结果表明加速比率与制动比率会影响列车运行的能耗.文献[9]针对列车运行过程中存在干扰的情况，建立了以节能为目标的速度运行曲线优化模型，并采用遗传算法进行求解，最后得到了良好的节能效果.文献[10]以能耗、舒适性等指标形成多目标优化函数，采用粒子群优化算法计算ATO目标曲线.文献[11]使用了动态规划、遗传算法和蚁群算法这3种算法对列车运行曲线进行优化，并对3种算法的性能进行分析和比较，其中蚁群优化算法在稳定性与能耗方面具有较好的优化效果.文献[12]则对遗传算法进行了改进，通过准点调整和局部搜索，引导种群进化方向，提高了收敛速度.智能算法在优化过程中需要大量的迭代计算，用时较长，无法满足ATO车载设备在线或实时优化的应用需求，但可离线生成目标速度曲线提前存储于ATO的车载设备中[13].
此外，文献[14]以能耗和舒适度为目标函数，采用混合整数线性规划(MixedIntegerLinearPro-gramming，MILP)和伪谱法对列车运行速度曲线进行求解，结果表明了混合整数规划算法能得到与伪谱法相近的优化效果，且计算时间非常短，可满足在线优化的时间要求.文献[15]将速度、距离划分为多个等间隔的区间，构造了两个相邻站之间的速度距离网络，建立了随机约束最短路径模型，通过基于采样的方法描述运行过程中的一些不确定性，利用拉格朗日松弛(LagrangianRelaxiation，LR)算法求解.并通过仿真测试了对算法的效果，结果表明算法运算时间与采样数呈近似线性的正相关.
相比于连续的列车运行模型，离散的速度距离网络模型便于计算.本文作者对列车于两站之间的运行过程建立速度距离网络，将列车运行曲线优化问题转化为整数规划问题，采用拉格朗日松弛与最短路径算法对问题进行求解，与成熟的优化软件CPLEX的求解效果进行比较.此外，本文还与文献[13]提出的混合整数规划算法进行对比，证明基于速度距离网络模型的可行性和优越性.由于速度离散步长对网络复杂度的影响较大，为提高运算速度，提出了基于粗粒度网络最优解的小邻域细粒度网络构建.并基于北京地铁亦庄线的线路数据设计了测试案例，评估网络重构方法的有效性.
2离散速度距离网络构建
为求解上一节提出的优化问题，同时将距离和速度进行离散化，建立一个离散的速度距离网络，如图1所示.这里采用等间隔离散的方式对距离与速度进行离散，并根据列车的连续动力学模型确定各个节点的可行弧段(对于网络中两个距离坐标相邻的节点，如果其速度变化符合列车动力学模型，则添加连接该两节点的弧段)，并将列车在每个离散距离区段内的运行过程均近似为匀加速、匀速或匀减速运动，线路限速、基本阻力和附加阻力等均在构建速度-距离弧段时予以考虑.此外，列车在各离散距离区段内可根据实际情况选择对应的工况以最小化列车运行能耗.因此，本文所构建的速度-距离网络符合列车的连续动力学特性，且满足不同工况之间的对于速度距离网络模型，设每个离散距离区段的长度为δs，每个速度区段的长度为δv，将列车在离散区段中的运动近似为匀加速、匀速或匀减速运动，则对于速度距离网络上的一条连接节点i与j的弧()i，j，节点i与j速度分别为vi，vj，位置分别为si，sj，由式(2)可得弧上运行时间为
3求解算法
通过速度-距离网络的构建，列车运行曲线优化问题转化为整数规划问题，其中决策变量yi，j为0-1整数变量，约束条件和目标函数均为线性.针对此优化问题，采用拉格朗日松弛与最短路径算法进行求解，并与优化软件CPLEX的求解效果进行对比.
4仿真案例
4.1参数设置
北京地铁亦庄线运行DKZ32型列车，编组方式为B型车6节编组，列车质量为194.295t[16]，旋转质量因子为1.06.全线最高时速不超过80km/h.本文根据亦庄线的线路和车辆数据，对宋家庄站至肖村站区间内的列车运行曲线进行优化.宋家庄站与肖村站的站间距为2631m，站间坡度变化如表1所示.
本文用C++语言实现基于拉格朗日(LR)算法的列车运行曲线优化，并采用CPLEX12.8直接对基于速度距离网络的0-1整数规划问题进行求解(ILP).配置为：计算机内存为16GB，处理器主频为3.40GHz，操作系统为Windows7(64位).计划运行时间为180s，以等间隔方式将路程离散为20个区间，离散步长为131.55m.速度距离网络模型以0.2m/s为速度离散步长，ILP算法调用离线生成的速度距离网络，而LR算法采用在线生成速度距离网络的策略，并分别计算重构与不重构网络的结果，重构网络的速度离散步长为0.02m/s.
为分析本文所提出模型与算法的效果，将其与遗传算法(GA)和混合整数线性规划算法(MILP)进行结果对比.GA基于文献[8]，本文将列车的运行工况分为牵引、巡航、惰行与制动，对牵引最高速度、隋行最低速度、巡航距离、牵引过程中牵引力占最大牵引力的比例、制动过程中制动力占最大制动力的比例进行编码.MILP基于文献[14]，将列车曲线优化问题建立成线性近似的距离离散模型并求解.
4.2模型结果对比
目标运行时间为180s情况下，4种不同方法得到的列车运行曲线和牵引力/制动力曲线如图4所示.可见，速度距离网络模型的求解结果能完全满足限速约束，而线性近似的距离离散模型则有略微超过限速的部分.除遗传算法有多次牵引以外，其他四种方法求解出的结果具有相近的控制切换点.
为分析运行时间变化对能耗的影响，调整两个站间的列车计划运行时间，具体为160、170、180、190s和200s，得到的列车运行曲线和牵引力/制动力曲线如图5所示，具体计算结果如表2所示.从结果中可以看到，相较于线性近似的距离离散模型，速度距离网络能更好地满足限速、运行时间、起点与终点速度约束，说明速度距离网络具有误差较小的优势.对比未使用重构的LR算法与ILP算法的结果，可见相同离散步长情况下，使用离线生成的速度距离网络的ILP运算时间更快，且能耗更小.从重构网络的LR算法的结果可以看到，降低速度离散步长，能使运行能耗更低.当速度离散步长较小时，在运行时间小于目标运行时间的情况下，即使MILP存在超速现象，重构网络的LR算法所得能耗仍比MILP的结果更好.遗传算法生成的列车速度曲线能耗相对较高，计算时间较长，因此，基于距离离散模型的MILP算法、基于速度距离网络的拉格朗日松弛算法、ILP算法的求解效果比传统的遗传算法更好.
为了评估速度离散步长对速度距离网络模型的影响以及重建速度距离网络策略的效果，使用不同的速度步长进行测试.测试的结果见表3.计算结果表明，在运算速度方面，速度离散步长较大时，ILP运算速度较快;而离散步长较小时，ILP计算时间显著提高，采用重建网络策略的LR运算较快.在能耗方面，相比于同离散步长的LR，ILP有一定优势.对于使用重建网络策略与未使用该策略的LR，前者重建的离散步长与后者离散步长相同时，能获得相近的能耗.由此可见，重建策略在降低计算时间的同时能保证解的质量.
5结论
1)采用速度-距离网络模型实现了节能列车运行曲线求解，并对不同算法进行了对比.将列车在两站间运行时的速度、距离离散化，建立了速度距离网络.由此，将列车运行曲线优化问题转化为最短路径问题，进而使用ILP与基于LR的算法对问题进行求解.由于缩短速度离散步长会使得弧段数大量增加，采用了基于粗粒度网络的解，重建细粒度网络并求解的策略，使速度距离模型的求解速度得到提高.
2)基于北京地铁亦庄线的数据进行了仿真.结果表明，相比与用MILP解距离离散并线性近似的模型，速度-距离网络模型的优点在于误差更小，能精确满足各项约束，且在运行时间小于目标运行时间、速度离散步长较小的情况下，其能耗更小.相比于传统的遗传算法，速度距离网络模型节能性更好.证明速度距离网络模型在列车运行曲线优化方面有一定优势.对于速度距离网络模型，相同速度离散步长情况下，ILP能耗比LR稍小.速度离散步长较大时，ILP运算速度较快，比MILP稍慢;步长较小时，采用重建网络策略的LR比未采用此策略的LR与ILP更快，且解的质量相近.
由于调用离线建立的速度距离网络数据的ILP算法速度较快，有望应用于列车运行曲线的实时优化中.后续的研究中，可以对算法与模型进行优化，提升运算速度，以满足实时计算的要求.此外，可分析雨雪条件对列车运行的影响，通过修改速度距离网络，模拟雨雪情况，对列车运行进行鲁棒性优化.——论文作者：王义惠1，朱松巍1，刘硕2，于柯2，宿帅1，
相关期刊推荐：《北京交通大学学报》(社会科学版)是经国家新闻出版总署批准，由教育部主管，北京交通大学主办的人文社会科学期刊。主要刊登人文社会科学和经济管理科学领域及文、理、工、管结合的交叉学科等方面的学术研究论文和问题讨论等。设有：产业经济研究、物流研究、管理研究、哲学研究、德育研究、法学研究、语言文学研究、教育研究等。其中物流研究、产业经济研究是重点建设的特色栏目。
