基于动态规划的列车节能操纵优化方法

高 豪， 张亚东， 郭 进， 查 志

(西南交通大学 信息科学与技术学院，四川 成都 610031)

城市轨道交通作为一种便捷环保的运输方式，能够有效改善城市发展过程中的拥堵问题。中国城市轨道交通行业已进入了高速发展的快车道，截至2017年12月31日，我国共计34个城市开通城市轨道交通并投入运营，已开通城市轨道交通线路165条，运营线路里程5 033 km，随着城市轨道交通的迅速发展，进一步减少列车运行牵引能耗，成为近年来各界关心的问题。据资料反映，我国城市轨道交通全年线网总电耗高达251.2亿kW·h，其中牵引能耗占比总能耗49.2%[1]。因此，在不影响服务质量的前提条件下，通过优化列车运行操纵策略可有效减少城市轨道交通系统能耗，降低碳排放量，对促进我国绿色交通发展，推动低碳经济建设有着重大意义。

列车节能操纵优化问题是一个多目标优化问题，既要保证列车行驶速度，按图正点运行，又要通过改进列车操纵策略，降低列车牵引能耗。针对列车节能操纵优化问题，国内外学者开展了广泛的研究。文献[2-4]基于极大值原理，建立了理想条件下的列车节能操纵模型，利用代数法对其进行求解。然而实际的列车运行过程包含了大量非线性及不确定因素，极大增加了代数法求解实际问题的难度。文献[5-6]构建了以惰行点位置为求解变量的列车节能操纵模型，利用遗传算法对其进行求解。文献[7-8]采用粒子群算法计算列车节能操纵策略。上述基于启发式的搜索算法具有随机性质，大量迭代过程中产生的随机解因不满足约束条件而被舍弃，算法收敛速度慢，模型求解时间长，搜索结果多为局部最优解。文献[9-12]利用动态规划方法来求解单列车节能操纵优化问题，将列车运行全过程分解为一系列离散的单阶段决策问题，顺序求解各阶段的最优控制决策，最终组合成全局最优操纵策略。相较于启发式搜索算法，动态规划更易获取全局最优解，但是动态规划的维数灾难限制了其对大规模问题的求解效率。

文献[9-10]在构建动态规划求解模型时，将列车运行全过程在时间域上划分阶段，这样保证了其优化结果能够满足正点运行目标，但也使得动态规划寻优过程需要在基于“时间-位置-速度”的三维状态空间内展开。在动态规划寻优初期，由于状态空间庞大导致大量新生成的最优子路径无法进行占优操作而被保留下来，占用大量的计算资源，模型求解效率极低。文献[9]中利用动态规划方法对案例进行仿真计算，时间长达22 s。文献[10]的实验结果表明，相较于启发式算法，动态规划能够获取更优解，但需花费数倍的运算时间。文献[11]提出的动态规划求解模型不再基于时间划分阶段，其寻优过程约束在基于“位置-速度”的二维有向图上，大大减小了算法搜索空间，提高了求解效率。实验结果表明，算法求解时间能够控制在2 s以内。然而，文献[11]的动态规划求解模型并没有能够充分地考虑到列车正点运行目标。文献[12]在“位置-速度”二维状态空间内进行动态规划寻优，为了兼顾列车正点运行目标，引入权重因子，将单阶段求解模型中的节能指标和正点指标进行归一化处理。然而，归一处理后的阶段指标是否能够确切描述节能运行和正点运行两个全局优化目标并未在文献中得到有效分析。且在上述模型中，因子的精确数值无法通过经验或计算直接得出，需通过多次全局动态规划过程对其进行反复修正，耗费大量计算资源。

利用动态规划方法求解列车节能操纵优化问题的挑战在于如何合理地设计求解模型，既要减小模型状态空间，提高求解效率，又使阶段指标能够有效体现全局求解目标，从而实现整体最优决策。本文提出一种基于动态规划的列车节能操纵优化模型，将列车运行全过程在空间域上划分为若干阶段，选取各阶段上的离散速度点，组合形成二维的状态空间；兼顾节能运行和正点运行两个全局目标，构建包含多个指标及约束的阶段求解模型；针对列车节能操纵优化模型多目标的特点，为各状态点建立Pareto最优解集，并引入拥挤算子对其进行维护以减少算法搜索空间，提高求解效率。本文提出的列车节能操纵优化方法只需完成一次动态规划全过程遍历便能获得全局最优解，极大地缩减了计算时间。

1 问题描述

列车区间运行过程包含牵引、巡航、惰行和制动四种运行模式。列车牵引能耗通常产生在牵引和巡航阶段，用以提升或保持列车运行速度。为了减少牵引能耗，司机通常将列车控制在低速运行状态，这也额外增加了运行时间。列车区间运行时间由运行图预先给定，且给定的运行时间总是大于区间最短运行时间，最短运行时间对应的列车运行曲线有且仅有一条，被称为最速曲线。如图1所示，存在多条列车运行曲线可保证列车按图正点运行，且同时满足线路限速等约束条件。在上述曲线中，牵引能耗最小的列车运行曲线将作为列车最优速度曲线。

图1 列车运行曲线示意

文献[2]面向水平坡度和固定限速条件下的列车运行场景，基于Pontryagin极大值原理证明了“最大牵引、巡航、惰行、最大制动”4种最优控制工况组合构成了列车最优速度曲线，优化问题简化为寻找上述最优控制工况之间的转换点。面向连续变化坡度和多个限速条件下的列车运行场景，列车最优操纵策略应该包含多种“最大牵引、巡航、惰行、最大制动”的最优控制工况组合。因此，列车节能操纵优化问题就转化为确定这些最优控制工况之间的组合顺序及其对应的转换点。该优化问题的计算复杂度取决于线路长度，以及线路坡度和限速条件的复杂度。

假设指定列车在时刻t=0时离开站台，该列车需在时刻表规定的站间运行时分Tset到达下一站。列车出发和到站的速度均为0。线路长度、坡度、曲率及限速值都通过线路基础数据表预先给定。同时，列车重量、牵引制动特性及基本阻力参数也都作为已知条件。假设列车在运行过程中只采用上文所述的4种最优控制工况。通过优化最优控制工况之间的组合顺序以及对应的工况转换点来获取最优操纵策略，列车最优操纵策略需满足两个全局目标，即列车正点运行和牵引能耗最小，同时需满足线路限速等约束条件。

本文还提出以下假设：假设列车装备有ATO系统，能够连续输出牵引力和制动力以实现列车巡航工况，部分未装备ATO系统而采用手柄控制的列车，其巡航过程也可以通过组合的牵引工况和惰行工况完成近似模拟；假设列车运行线路上不存在陡坡，牵引和制动系统能够保证列车在线路任意位置实现巡航控制；本文只针对单列车在区间上的运行操纵序列进行优化，再生制动不在本文考虑范围内。

2 优化模型

2.1 列车动力学分析

对运行过程中的列车进行受力分析，结合运动学方程，建立基于单质点的列车牵引制动计算模型为

( 1 )

( 2 )

( 3 )

r(x,v)=Mg[ω0(v)+ω1(x,v)]×10-3

( 4 )

式中：x为列车运行位置，m；v为列车运行速度，m/s；t为列车运行时间，s；M为列车总质量，t；α为列车回转质量系数；u为列车控制工况且u∈{-1,0,1,2}，“-1”表示制动工况，“0”表示惰行工况，“1”表示牵引工况，“2”表示巡航工况；F(x,v,u)为列车运行时受到的合力，kN；Fp(v)为施加在列车上的牵引力，kN；Fb(v)为施加在列车上的制动力，kN；r(x,v)为列车受到的运行阻力，kN。在不同控制工况条件下，列车合力F(x,v,u)与牵引力Fp(v)、制动力Fb(v)、运行阻力r(x,v)的关系如式( 3 )所示。r(x,v)包括基本阻力和和附加阻力两部分，如式(4)所示。ω0(v)为列车单位基本阻力，N/kN；ω1(x,v)为列车单位附加阻力，N/kN。

由文献[13]可知，ω0(v)由轴承摩擦运行阻力、车轮滚动运行阻力、轮轨间滑动阻力、冲击和振动阻力、空气阻力五个部分组成，可近似由戴维斯方程式来表示，其方程系数y1、y2及y3根据列车型号、编组状况而设定。ω1(x,v)主要取决于线路条件。

ω0(v)=y1+y2v+y3v2

( 5 )

ω1(x,v)=ωi+ωr+ωs

( 6 )

ωi=i

( 7 )

ωr=600/R

( 8 )

ωs=0.000 13L

( 9 )

式中：ωi为单位坡道附加阻力，N/kN；ωr为单位曲线附加阻力，N/kN；ωs为单位隧道附加阻力，N/kN；i为坡度的千分数；R为曲线半径，m；L为隧道长度，m。

2.2 全局目标及约束条件

不考虑列车在区间运行时产生的再生制动能，将列车正点到达和牵引能耗最小作为全局目标，为

(10)

式中：X为列车区间运行长度，m；ETotal为列车区间总牵引能耗，kJ；Tset为时刻表规定的区间运行时分，s。同时，列车在运行时还需满足以下线路限速约束条件

0≤v(x)≤Vlimit(x)

(11)

式中：Vlimit(x)为位置x处的限速值，m/s。

2.3 动态规划求解模型

列车在区间上的运行过程是由一系列离散的操纵序列所决定的，从某阶段往后的列车运行过程只与该阶段的列车运行状态及往后的操纵序列有关，与历史的运行状态及操纵序列无关，因此列车运行过程具有马尔可夫性，适于用动态规划方法来求解。利用动态规划方法求解复杂决策问题前，需要将问题改造成符合动态规划求解要求的形式，分为以下几个步骤：

Step1把复杂决策问题划分出多个相互联系的求解阶段。

Step2确定各阶段的输入状态和输出状态集合。

Step3确定各阶段决策变量集合。

Step4建立各阶段输入状态和输出状态之间的状态转移方程。

Step5构建包含指标和约束的阶段求解模型。

2.3.1 划分阶段

将列车运行全过程在空间域上进行离散化处理，将列车运行区间划分成K个子区段，保证各子区段的线路条件(限速、坡度、曲率)唯一，且区段长度不超过Δx。将区段视作动态规划求解模型中的阶段，阶段划分完成后生成一系列离散的位置点{x1,x2,…,xK+1}，构成各阶段起始和结束位置集合。

2.3.2 确定状态

图2 动态规划求解模型状态空间示意

2.3.3 确定决策变量

假设列车运行控制模型中包含最大牵引、巡航、惰行和最大制动4种控制工况，第k阶段只施加其中一种控制工况uk，将其作为该阶段的决策变量，如图3所示。各阶段的控制工况序列{u1,u2,…,uK}作为动态规划求解模型的全过程策略。

图3 不同决策下的状态转移关系

2.3.4 建立状态转移方程

(12)

(13)

(14)

(15)

(16)

图4 状态转移近似过程示意

(17)

(18)

2.3.5 构建阶段求解模型

(19)

为求得全局最优操纵策略，采用后向动态规划的求解方式，从最后一个阶段K开始逐段前推计算，直至第1阶段，求解流程如图5所示。

图5 动态规划求解流程

以k阶段为界，列车牵引总能耗和总时间可表达为两部分，为

(20)

(21)

(22)

(23)

图6 最优牵引能耗与时间的关系特性

(24)

(25)

(26)

(27)

(28)

图计算原理图

图计算原理图

综上所述，满足节能运行和正点运行两个全局优化目标，考虑线路限速条件，对于任意阶段k，构建该阶段求解模型为

(29)

3 求解算法

上述阶段求解模型中包含两个目标函数，且目标之间存在冲突。对于这类多目标优化问题，通常存在一个最优解集，该解集包含了所有多目标优化问题的非支配解，下面对非支配解进行定义。

定义：已知f:Rn→Rl，x∈Ω,Ω为可行域。考虑优化问题

(30)

对于一个点x*∈Ω，如果不存在x∈Ω，使得对于，有fi(x)≤fi(x*)成立；且至少对于一个i，有fi(x)

如图3所示，阶段k的每个输入状态点都与多个输出状态点存在连接关系，在动态规划由后往前地逐阶段递进过程中，阶段输入和输出状态的解集容量呈倍数递增关系。为了提高搜索效率，需对解集容量R进行限制以减少搜索空间。本文引入拥挤度D来对Pareto解集进行维护，个体的拥挤距离是指该个体周围不被任何其他的解所占有的搜索空间的度量。如图9所示，Pareto最优解集中给定解r的拥挤度Dr表示为r周围包含r但不包含其余解的最大长方形半周长，即Dr=|T*r+1-T*r-1|+|E*r+1-E*r-1|。

图9 拥挤度示意

根据拥挤度Dr对Pareto解集中的各解进行递减排序，保留拥挤度最大的R个解。通过这种处理方式既能提高算法的收敛速度，又能保证Pareto最优解集的多样性以及解的均匀分布。

面向多目标的动态规划求解步骤为：

Step1读入线路参数及列车参数，计算列车最速曲线，在空间域划分阶段，确定每个阶段的输入和输出状态集合，完成动态规划求解模型的初始化，令k=K。

4 算例分析

基于面向多目标的动态规划优化方法MODP，采用运行处理器为Intel(R) Core(TM) i5-2 530 M @ 2.40 GHz、内存容量4 GB的笔记本电脑作为仿真计算平台，基于VC++6.0的编程环境，开发了列车节能操纵优化程序。选取文献[15]中亦庄线线路和列车数据，运行程序前对模型参数进行如下设定：速度离散间隔Δv=1 m/s、位置离散间隔Δx=30 m、最优策略集容量R=30，优化计算列车各站间的节能操纵策略。保持基础数据和模型参数设置不变，基于文献[12]中面向加权目标的动态规划优化方法WODP对列车节能操纵策略进行了优化计算，两种方法的优化计算结果见表1。

表1 实验结果

如表1所示，将亦庄线13个站间区间作为算例，列出各算例的运行距离以及时刻表规定的运行时分，计算列车在最速运行条件下的站间牵引能耗。根据给定的站间运行时分和线路参数，分别利用MODP方法和WODP方法对列车区间运行操纵策略进行优化，将优化结果分别和站间运行时分、最速牵引能耗进行比对，计算得到的运行时间偏差和节能率将被用来评价正点运行目标和节能运行目标。同时，表1还列出了两种方法求解算例的运算时间。

首先分析MODP方法的有效性。从整体来看，MODP方法获得了更好的节能效果，其平均节能率在WODP方法的基础上进一步提升了2.54%，除了“荣京东街—万源街”和“万源街—亦庄文化园”算例以外，MODP方法都获得了更好的节能效果。同时，MODP方法优化后的平均运行时间偏差仅为0.48 s，小于WODP方法的3.52 s，满足列车正点运行需求。通过MODP方法优化后，绝大部分算例的运行时间偏差都控制在1 s以内，“经海路—同济南路”算例的运行时间偏差为2.28 s，高于平均值。经过调查发现，该算例在动态规划寻优过程中，受到最优策略集容量R的限制，部分状态点中的优质解由于分布密集，不满足拥挤度需求而未被保留下来。将容量R提升至50，该算例的运行时间偏差降至0.38 s。

在列车运行过程中，总运行时间和总能耗存在着不可忽视的关联性，对比表1算例中MODP方法和WODP方法的优化结果，可以观察到两者之间的一般规律：运行时间越长牵引能耗越低。同样对牵引能耗存在不可忽视的影响因素还有线路条件。据文献[15]反映，在列车上行运行方向上，“旧宫—小红门”站间中存在一段近24 ‰的长下坡，“次渠—次渠南”站间中存在一段20 ‰的长上坡。优化结果显示，列车在站间距离较长的“旧宫—小红门”区间上反而消耗了更少的牵引能耗。

此外，本文提出的MODP方法具有更高的求解效率，在Δv=1 m/s、Δx=30 m、R=30的模型参数设置条件下，算例求解平均用时5.02 s，远低于WODP方法的69.65 s。WODP方法运算耗时长的主要原因在于其需要利用二分法反复多次地对权重因子进行修正处理。

速度离散间隔Δv和位置离散间隔Δx决定了动态规划求解模型的状态空间大小，最优策略集容量R决定了动态规划寻优过程中阶段最优策略的保存个数，上述模型参数直接影响了模型的求解精度及求解效率。通过一组仿真实验，分析模型参数Δx和R改变后对 MODP方法优化结果产生的影响。保持Δv=1 m/s不变，将Δx在10～100 m范围内以10 m的步长递进，将R分别设置为10、20和30，求解亦庄线13个算例的平均节能率及平均计算时间，计算结果如图10和图11所示。

图10 不同模型参数设置条件下的平均节能率

图11 不同模型参数设置条件下的平均计算时间

由图10可知，随着位置离散间隔Δx的递增，模型求解精度降低，平均节能率总体呈下降趋势。然而，位置离散间隔Δx和节能效果并不总是呈单调递减关系，平均节能率峰值位于Δx=30 m处。经过调查发现，Δx的减小导致动态规划寻优阶段的增多，一方面提高了求解精度，另一方面也增加了拥挤比较操作的次数，造成更多的优质解在寻优过中未被保留下来。从图10还可以看到，最优策略集容量R越大，节能效果越好。当Δx较小时，R的增大使得更多的优质解能够在拥挤比较操作中被保留下来，节能效果提升明显；当Δx较大时，拥挤比较操作次数大大减少，R增大带来节能率提升的效果不大。

由图11可知，模型平均计算时间与位置离散间隔Δx成单调递减关系，与最优策略集容量R成单调递增关系。仿真实验结果显示，上述模型参数Δx和R的30种排列组合条件中，有10种组合的平均计算时间在1 s以内，可满足列车运行实时调整需求。利用MODP方法优化列车节能操纵策略之前，可根据不同的优化需求，选择合适的模型参数。当列车站间运行过程中受到干扰偏离原定优化运行曲线时，选择求解效率高的模型参数组合，对当前列车操纵策略进行实时优化调整；当列车抵达站台后，适当减小模型离散间隔、提高最优解集容量，利用列车停站时间充分挖掘列车在下一站间的节能运行潜力。

分析MODP方法的实用性，选择速度离散间隔Δv=1 m/s、离散间隔Δx=30 m、最优策略集容量R=30的模型参数。挑选出亦庄线中两个典型区间进行优化计算，其中“旧宫—小红门”站间具有一段860 m的长下坡，“次渠南—经海路”站间具有一段1 050 m的长上坡，优化结果分别如图12与图13所示。图12中，列车进入长下坡区段后，利用惰行策略将其速度逐渐提升，列车将速度保持在较高水平的同时几乎不消耗牵引能量，符合日常的司机操纵经验。图13中，列车在进入长上坡之前，全力牵引将速度提升至限速值，列车在进入长上坡区段后，尽量多地采用惰行策略来减少牵引能耗，也符合日常的司机操纵经验。

图12 “旧宫站—小红门”站间优化列车运行曲线

图13 “次渠南—经海路”站间优化列车运行曲线

5 结束语

由于任意阶段的列车操纵决策只与当前运行状态有关，与历史操纵策略和运行状态均无关。因此，基于动态规划的离散组合寻优思路，建立由一系列离散的单阶段求解模型组合而成的列车节能操纵优化模型是一种有效、可行的方法。

针对列车节能操纵优化问题，本文提出一种面向多目标优化的动态规划求解模型。同时兼顾节能运行和正点运行两个全局目标，建立一系列包含多个指标及约束的阶段求解模型。同时，结合多目标优化理论，给出一种能够高效求解该模型的算法。

选择北京亦庄线作为本文模型的求解算例，在基础数据和模型设置参数一致的前提下，与其他动态规划方法进行对比。实验结果表明，本文模型能够保证其优化结果满足列车正点运行需求，且具有更好的节能效果。同时，本文动态规划优化方法的求解效率与其他动态规划方法相比显著提升。其次，通过一组仿真实验，分析了本文动态规划优化方法模型参数对节能效果和求解效率的影响。最后，结合地铁列车司机的驾驶经验，验证了本文动态规划优化方法的实用性。

此外，本文动态规划优化方法主要适用于单列车区间运行操纵优化问题，并未考虑多列车追踪运行场景下的再生制动能量利用，这也是本文接下来的研究方向和研究重点。