轨道养护计划多目标模型及求解

许玉德， 刘一鸣， 沈坚锋， 邱俊兴

(1.同济大学 道路与交通工程教育部重点实验室，上海 201804;2.中交投资有限公司，北京 100029)

由于列车运行速度的提高、运行密度和通过总重的增加，铁路线路恶化趋势加快，养护维修作业量不断加大，但相应可用来进行养护维修的天窗时间却不断减少，运输需求和线路养修的矛盾日益突出.为实现线路状态的可控，根据轨道状态检测结果，制定优化的轨道养护维修计划是国内外铁路部门养护维修模式发展的趋势[1].合理的铁路轨道养护维修计划必须在确保运输安全的同时也要能兼顾到节约养护维修成本的问题，因此轨道养护计划制定中，决策者所面对的问题常常是多目标的[2-6]，而对多目标问题的求解，非支配排序遗传算法(NSGA-Ⅱ算法)[7-9]是被应用得最为广泛的算法之一.

对求解轨道养护计划多目标模型来说，标准的NSGA-Ⅱ算法还存在着一些不足之处，主要体现在：

(1) 全局解空间较大庞大，年度养护计划中将一年分36旬，1 km线路对应的决策变量为36个，如果是某个铁路局管内的所有线路进行轨道养护计划的编制，那决策变量的数量是惊人的，模型计算的时间和空间复杂度都将增加；

(2) 标准NSGA-II算法中没有处理约束条件的算子，约束条件需要通过添加约束算子来对非支配解集进行搜索；

(3) 传统的遗传算法通常采用固定遗传参数的办法，但参数的设置是否恰当将直接影响到算法的搜索效果，过大或者过小的参数将会使算法无法收敛或者后期收敛速度过慢.

因此，本文根据轨道几何不平顺的增长特点及轨道养护的现实背景，建立了轨道养护计划多目标模型，通过对标准的NSGA-II算法的改进实现了所建多目标模型的求解，选取既有沪昆上行线区段的数据，编制了养护维修计划，验证了模型及算法的效果.

1 轨道养护计划多目标模型

当线路几何不平顺标准差达到某一管理目标值时，为保证列车运行安全，就需要使用大型养路机械进行养护维修作业使几何不平顺数值恢复到合理范围内.大型养路机械在一个作业天窗时间内只在一个计划区段进行作业，作业方案的选择影响着轨道的总体状态和投入成本.因此作业方案的决策是多目标的，包括轨道状态最优和成本费用最小两个目标.

1.1 轨道状态最优

我国轨道不平顺管理中，采用不平顺的标准差来表征不平顺状态.国内外研究表明[10-13]，在不进行养护维修作业的情况下，轨道几何不平顺标准差会呈指数形式增长，表示如下：

σi(T)=σ0·ekit+ε(t)

(1)

式中：σi(T)为计划区段i在时间T的轨道不平顺标准差，mm；σ0为计划区段i在时间T=0的轨道不平顺标准差，mm；ki为服从对数正态分布的待定随机变量参数[10]；ε(t)为服从正态分布的随机噪声[10]，mm.

养护维修作业后，轨道几何不平顺标准差得到降低，但不能完全恢复到初始状态，始终存在着残留，残留率定义为g.以所有区段年末轨道几何不平顺之和作为指标，得到轨道状态最优的目标函数如下：

(2)

式中：O1为成本费用目标函数值；u为某个区段，以1 km将计划区间划分为若干区段，区段集合U={1，2，3，…}，u∈U；j为大型养路机械作业时间点，养护计划中一年分36旬，旬集合J={1，2，3，…，36}，j∈J；guj为区段u上在第j旬进行养护后的几何不平顺标准差残留率g；σu0为区段u的初始几何不平顺标准差，mm；kun为区段u上在第n次恶化阶段时的参数k；T为恶化模型预测步长，取T=10(一旬)；εnj为第n次恶化阶段第j旬时的随机噪声ε，mm；wuj为决策变量，是整数(0-1)型变量，表示是否进行计划性养护.

从式(2)可以看到，由于每个计划区段在一年中只能安排一次维修作业，因此，对于一个固定的计划区段而言，在不同的时间段进行养护维修，对其年末的几何不平顺有不同影响：过早进行养护，虽然降低了几何不平顺值的超限概率，但由于残留率g的大小与养护作业前的几何不平顺标准差成近似反比关系，因此养护维修效果将大打折扣；过晚进行养护，几何不平顺值的超限概率则会显著提高，但养护维修的效果却十分明显的。

1.2 成本费用最小

所建的成本费用最小目标函数中，主要包括以下4部分成本费用：计划性养护费用、养护固定费用、舒适性损失费用和事后养护费用.成本费用最小的目标函数如式(3)所示：

(3)

式(3)中，舒适性损失费用和事后养护费用是随着轨道不平顺标准差降低而减少的费用，而对多目标函数进行优化时，通常子目标函数之间要求是互为矛盾、此消彼长的关系。因此，在式(3)中，将这两种费用以负的惩罚性费用表示，其值越大就越需要用各种养护维修手段去保持良好的轨道状态，以提高舒适度和安全性。

1.3 轨道养护计划约束条件

针对铁路养护作业特点，轨道养护计划还应满足下述约束条件.

(1) 养路机械总量约束

制定的养修计划模型只考虑一套大型养路机械在区段上作业的情况，须满足式(4)：

Wuj≤1

(4)

(2) 定点定时养护约束

有些特殊情况，需要使用大机在特殊旬u1对特殊区段j1进行作业，须满足式(5)：

Wu1j1=1

(5)

式中：Wu1j1为整数(0-1)型变量，表示是否在特殊旬u1对特殊区段j1进行计划性养护，Wu1j1=1表示进行，Wu1j1=0表示不进行。

(3) 区段上限个数约束

大型养路机械不是每天的养护维修天窗点都能进行，某旬j内的作业量存在上限Aj，须满足式(6)；

∑uWuj≤Aj,j∈J

(6)

(4) 同一区段养护次数约束

线路的养修作业的效果一般都较为明显，在周期修为主的体制下线路捣固周期为1～1.5年.因此，维修的最大次数定为一年一次，须满足下式(7)：

∑jWuj≤1

(7)

(5) 恶化状态上限约束

各区段几何不平顺在超过事后养护限度前都需要立即投入大型养路机械进行养护，须满足式(8)：

(8)

式中：u∈U2，U2为{年度计划期中，预测几何不平顺达到上限值的区段},j∈J；Ju表示区段u最迟需进行养护的旬；

(6) 养护成本总量约束

轨道养护计划多目标模型中，仅对养护成本总量设置最大值，须满足式(9)：

∑u∈U∑j∈JCuj≤Cmax

(9)

式中，某区段某旬的养护总成本Cuj=Ct·wuj+Cd-Lb·Pb-Lcft·Ebad.

2 轨道养护计划多目标模型求解

2.1 改进的NSGA-II算法

标准的NSGA-II算法对求解轨道养护计划多目标模型来说，存在着决策变量过多、缺少处理约束条件的算子、遗传参数固定等问题，因为初始种群远小于解空间，算法早期可能出现超级个体，其适应度远大于当前种群的平均适应度，使得该个体在种群中迅速占据绝对比例，种群多样性迅速降低，种群进化能力丧失，算法过早收敛，陷入局部最优，这种现象也称为算法“早熟”.

针对本文多目标模型的特点，对算法进行改进，使其在求解轨道养护计划多目标问题时能更好地保持种群多样性，避免“早熟”，并在后期加速收敛得到全局最优解，改进的NSGA-II算法与标准算法的不同点见表1.

表1标准NSGA-II算法和改进NSGA-II算法的不同点

Tab.1DifferentpointsofstandardNSGA-IIalgorithmandimprovedNSGA-IIalgorithm

不同点 算法标准NSGA-II算法改进的NSGA-II算法1二进制或实数二维矩阵编码二进制的三维矩阵编码,方便处理更多决策变量,并进行直观表示2无约束条件处理算子构建违反约束度函数,在种群生成和进化阶段对约束条件进行处理3交叉和变异概率为定值交叉和变异概率随进化代数会自适应改变

2.1.1编码设计改进

二进制编码和实数编码是现有遗传算法中主要的两种编码方式，其中前者在编码和解码的操作上都极为简单，也十分容易在交叉、变异阶段进行各种遗传操作[15].

本文构建的轨道养护计划多目标模型中将决策变量已经定义为了整数型的0-1变量，在编码形式上将采用二进制编码的方法，但1 km线路对应的36个决策变量在计划线路变长、种群规模扩大的时候将会产生一个很大的矩阵，后续比如约束条件处理、目标函数计算、快速非支配排序、拥挤度比较和遗传操作都将在此矩阵中进行，将给计划的编制带来很大困难.

因此，本文首先采用矩阵编码的形式对单个个体进行编码，矩阵的行向量代表旬，表示每个计划区段在一年中对应的养护时间，矩阵的列向量代表区段，表示每一旬中大机的具体作业地点，如表2所示；其次，将N个这样的个体放入一个三维数组中组成一个种群，而对应数组的页数1-N则被编在适应度计算的二维矩阵中.

三维数组的矩阵编码形式能使后续的优化选择过程在两个不同维度的数组中进行，例如：约束条件处理、遗传操作都能在三维数组中展开，而目标函数计算、快速非支配排序、拥挤度比较可以在二维矩阵中进行，且用对应的的页数作为联系，便于进化选择后进行种群保留和最后的计划安排矩阵的输出；另一方面，该编码形式更为直观，不但方便约束条件的处理阶段对整行整列数据的矩阵运算，而且使得年度养护计划中大型养路机械在何时何地进行养护作业变得一目了然.

表2 计划区段0-1矩阵编码形式Tab.2 0-1 matrix coding form in planning segments

2.1.2全过程约束

构建违反约束度函数H主要是为了在进行进化迭代的时候来选择非支配解，但本文改进的NSGA-II算法在初始种群的生成阶段就对约束条件进行预处理，在初始种群生成阶段，为了使初始种群多样性更好、在解空间上分布尽量广，随机生成比初始种群规模大的个体群，然后通过计算违反约束度H和两个目标函数值，通过计算它们的优胜关系，选出适应度值大的个体组成初始种群，这样不但增加了初始种群的有效性，也加快了非支配解集的搜索效率.

2.1.3遗传系数自适应

标准NSGA-II算法中，在完成快速非支配排序和拥挤距离计算后需要根据个体之间的层级Rank和拥挤距离的区别进行排序，用以选取优秀个体进行下一次寻优.对属于不同层级的个体，首选层级编号小的个体，而当层级相同时，就首选拥挤距离大的个体.

在寻优循环刚开始时，个体在解空间中分布较为离散，层级间的个体差异较大，很容易就能对优劣个体进行区分；而随着寻优过程的进行，更多优秀的个体被保留下来，此时较大的交叉概率Pc和变异概率Pm反而会使得新个体的产生速度加快，但新产生的个体其适应度往往会低于原先种群内的个体，使已经具有较高适应度的种群个体被破坏，从而减缓算法的收敛速度，会使整个改进NSGA-II算法变成一个随机搜索、毫无目的的过程.因此，对遗传算子中交叉概率Pc和变异概率Pm这两个遗传系数的选择是影响多目标遗传算法能否收敛并且获得最优非支配解集的关键因素.

在一般的遗传算法操作中，交叉概率Pc会取0.2～0.7之间的定值，而变异概率Pm的取值一般相对较小，会取0.01～0.1之间的定值.基于交叉概率Pc和变异概率Pm选择取值的重要性，同时，考虑到通过反复试算来确定两个系数的繁琐性，本文基于非支配排序时的层级编号Rank建立自适应的遗传算子，具体算子如式(10)所示：

(10)

式中：P为交叉概率和变异概率;Ravg为该代种群的平均层级;Rind为参与遗传选择个体的层级;为了使得交叉概率Pc在0.2～0.7之间取值，变异概率Pm在0.01～0.1之间取值，对交叉操作而言，P1c=0.7，P2c=0.2，对于变异操作而言，P1m=0.1，P2m=0.01.

通过式(10)中自适应遗传算子的操作，可以做到在快速非支配排序后，层级较大的劣势个体以较大的概率进行交叉和变异操作，以期能产生较好适应度的个体；而层级较小的优秀个体则以较小的概率进行交叉和变异操作，以期能将优秀个体保留的同时，也可以获得更深度的全局搜索.通过自适应遗传算子的操作，不但保持了种群的多样性，避免算法前期的“早熟”，也能更好地进行局部搜索并在后期快速收敛.

2.2 轨道养护计划编制

利用改进NSGA-II算法求解轨道养护计划多目标模型，流程主要包括以下几步：

步骤1：设置和输入初始参数，其中包括模型参数和算法参数两类.模型参数：σu0、guj、kun、T、εnj、Ct、Cd、Lcft、Lb、Cmax、Aj、u1、j1、U2和Ju等.算法参数：循环迭代次数gen、种群规模pop、交叉概率自适应参数：P1c=0.7，P2c=0.2、变异概率自适应参数：P1m=0.1，P2m=0.01；

步骤2：生成初始种群.采用二进制矩阵编码，随机的生成比初始种群规模大的个体初始种群Aini；

步骤3：计算初始种群Aini中所有个体的轨道状态最优目标函数值O1，成本费用目标函数值O2和违反约束度H，并和三维数组Aini的页数ZAini一起写入二维矩阵Dini；

步骤4：以Dini中三个参数O1、O2、H为依据，对初始种群Aini进行非支配排序并计算拥挤距离，并根据每个个体的层级和拥挤距离，在对应的三维数组中选出最优的满足种群规模的个体组成初始父代种群Afar；

步骤5：通过锦标赛选择法在初始父代种群Afar中选择一半个体进行自适应遗传操作，交叉操作形成种群Ac，变异操作形成种群Am，合并Ac和Am组成子代种群Aoff，合并初始父代种群Afar和子代种群Aoff为中间代种群Ainter；

步骤6：计算中间代种群Ainter中所有个体的O1、O2和H，得到Dinter，对种群Ainter进行非支配排序并计算拥挤距离，并根据每个个体的层级和拥挤距离，依次选出pop个满足种群规模的个体作为新的父代Afar；

步骤7：进行迭代运算，并判断是否达到最大次数，若达到，则终止运算，输出结果，否则，返回步骤5.

图1是第2.2节轨道养护计划编制的实现流程图.

3 算例分析

选取既有沪昆上行线K230+600～K240+600的10 km区段作为算例对象进行年度养护维修年度计划的编制工作.国内目前大型养路机械主要采用“捣固车+动力稳定车”模式，捣固效果与高低不平顺直接相关，因此选择高低不平顺作为几何不平顺选择的代表.

初始参数中，T=10，σε(n)=0.01 mm，Ct=1 万元·km-1，Cd=8 万元·km-1，Lcft=0.01 万元·km-1，Lb=0.5 万元·km-1，Cmax=70 万元，Aj=3，gen=200，pop=700，，P1c=0.7，P1m=0.1，P1m=0.1，P2m=0.01，以上参数取值依据模型条件及算法假定.

高低不平顺可能达到上限值的区段集合U2、U2各区段对应的最迟需进行养护的旬集合Ju、养护后的高低不平顺标准差残留率guj、恶化阶段时的参数kun和初始高低不平顺标准差σu0等线路参数来源于2009年3月6日至2015年6月29日期间的轨检车数据.

图1 轨道养护计划的实现流程图Fig.1 Flow chart of annual maintenance plan for track

单目标决策问题只有一个绝对最优解，但对于多目标决策问题来说，由于每个子目标之间可能是相互冲突的关系，这就导致没有一个绝对最优解可以使全部目标同时达到最优，因此，只能在所有子目标之间进行相互妥协折中，做出一个平衡的综合效果最优的方案.帕累托最优解表示了问题解的各个子目标不能够再同时继续优化的状态，帕累托最优解集的图像被称为帕累托最优前沿[16-17].输入初始参数及线路参数，按照图1流程得到帕累托最优前沿如图2所示，图中共有43个点，即代表了在最优前沿上有43种不同的养护作业计划安排，这43种方案不被其他方案支配，即不存在其他方案比这43种方案的成本小且养护效果更优.

从图2中可以看到，这43种不同的养护作业计划，其高低不平顺标准差在0.916～0.935 mm之间变动，而养护成本则在61.1 万元～67.14 万元范围以内浮动.

图2 养护年度计划的帕累托最优前沿Fig.2 Pareto optimal frontier of annual maintenance plan

在图2中，选取帕累托最优前沿中高低不平顺标准差最小和养护成本最小的两个端点，以及中间数据较为集中区域的两个点作为所得的维修计划，4种维修计划的高低不平顺标准差和养护成本见表3.

表3帕累托最优前沿中4个代表点的高低不平顺标准差和养护成本

Tab.3StandarddeviationandmaintenancecostoffourrepresentativepointsinParetooptimalfrontier

养护维修计划编号高低不平顺标准差/mm养护成本/万元10.90267.14420.91065.39330.92063.49340.93561.101

以计划1为例介绍养护维修计划安排，如图3所示，其中，行代表区段序号，列为对应的时间(旬)的编号，时间起点为2015年7月上旬，若某空格为黑色，则相对应的区段在该旬进行养护维修.

计划中各区段的养护维修时间均安排在了年度计划中后期，即第14～31旬，避免了在恢复效果较差的年度计划初期进行养护。又由于多目标模型建立中将列车运行的舒适性和安全性都转化为费用考虑在内，避免了过度养护和临近事后养护限度时才进行养护的情况。

图3 养护维修计划1的作业安排Fig.3 Arrangement of maintenance plan 1

通过实施图2所示4种不同的养护维修计划，各区段的高低不平顺标准差相比于不进行任何养护维修的情况都将会有一定的改善，如图4所示.

图4 不同养护维修计划下各区段的高低不平顺标准差对比图Fig.4 Comparison of standard deviation of longitudinal irregularity in each segment under different maintenance plans

从图4可以看到，如果未进行养护维修作业，这10 km的计划区的高低不平顺标准差在年末都将超过或者即将超过事后养护限度值1.5 mm，而若实施了养护维修计划，经过作业的区段上高低不平顺标准差年末值都有不同程度的降低，平均降低了0.916 mm，其中计划1的年末轨道状态最好，全部区段比未进行养护维修作业平均降低了0.973 mm，另外区段5上由于进行了养护维修作业，其年末的高低不平顺标准差基本上恢复到了年初的水平，可见，轨道养护计划的效果十分明显.

以计划1为例，各区段全年的高低不平顺标准差变化如图5所示.

图5 计划1条件下各区段全年的高低不平顺标准差变化图Fig.5 Variation of standard deviation of longitudinal irregularity in each segment of plan 1

可以看到，计划1安排下各区段在全年36旬时间内，其高低不平顺标准差均未超过事后养护维修限度1.5 mm，存在养护维修作业的区段，平均都在高低不平顺标准差达到1.3 mm左右时进行养护作业，且这些区段的改善效果都很好，基本上都能恢复到0.7 mm以下.其余3种计划下情况类似.

4 结论

本文建立了轨道养护计划多目标模型，通过对标准的NSGA-II算法的改进实现了所建多目标模型的求解，并选取既有沪昆上行线区段作为案例验证了模型及算法的效果，结论如下：

(1) 建立的轨道状态-成本费用多目标优化模型能将轨道几何状态最优及成本费用最省两个目标作为一个整体进行考虑.轨道养护计划多目标模型能在确保列车安全运行的同时，减少“过度维修”现象的发生.

(2) 通过采用0-1编码将个体放入三维数组、全过程控制约束条件以及遗传系数自适应这三种方法建立了改进的NSGA-II算法，使之求解所建立的轨道养护计划多目标优化模型.改进的NSGA-II算法在求解轨道养护计划多目标问题时能更好地保持种群多样性，避免“早熟”，并在后期加速收敛得到全局最优解.

(3) 选取既有沪昆上行线K230+600～K240+600区段对模型和算法进行了验证分析，所得的养护维修计划中：对于初始不平顺较大且高低不平顺标准差恶化较快的区段给予了优先养护维修，而对于初始不平顺较小且高低不平顺标准差恶化较慢的区段，则都安排在了年度计划的后期，或者不予安排养护维修作业；存在养护维修作业的区段，不论养护维修时间被安排在哪一旬，一般都会在高低不平顺标准差在1.3 mm左右时得到养护作业，且其恢复效果都很好，基本上能恢复到0.7 mm以下.