分析基于列生成算法的动车组检修计划优化

孟迎

【摘 要】随着我国社会经济整体形式的良好发展，我国社会交通运输行业也实现了快速发展，尤其是在火车客运方面实现了动车发展。动车组在客运方面的应用给我国人民的生活带来了很大的方面，甚至提高了我国经济发展的速度。那么，在这种情况下，如何保证动车组的良好运行与发展就成为了有关部门关心的重点，即要尽量优化动车组的检修方案，这也是本文所要探讨的主要内容。

【关键词】列生成算法；动车组；检修计划

【中图分类号】 F287.3【文献标识码】 A【文章编号】1672-5158（2013）07-0054-02

动车组已经成为了我国人民出行良好的选择，而动车组检修计划的好坏对于动车组运行效率的高低、动车组维修费用的高低等都有着重要的意义，最总要的是良好的动车组检修计划能够在很大程度上提高我国动车组车辆的优化配置。但是从研究角度来讲，对动车组检修计划的维修还相对较少，研究力度和深度都严重不足，直接限制了我国动车组的整体发展。正因如此，本文要总结国内外先进的维修经验，结合自身的实际情况，建立具有特色的动车组检修计划，实现检修计划的优化。

一、问题概述

对于动车组检修而言其需要一个完善的检修计划，这样的计划就是我们保证动车组检修质量的关键，而其中检修计划的编制是进行检修的主要依据，而检修计划的编制主要是指“考虑作业时间在一天以上的动车组检修约束，根据动车组当前的工作状态，提前一天到三天安排需要进行二级以上检修的动车进入到待检状态，并生成动车组的运用计划”。

具体而言动车组检修计划的基本特征分为以下几点，第一点，已知的信息条件。其一，交路段状况，主要是指该交路段的起始点，动车在该交路段的起始时间以及运行的总时间、总里程等等。其二，检修基地状况，是指动车组维修所在的车站或者整个线路所连接的线路，检修的能力以及所需要的检修时间，所需要的备用车数量等等。其三，动车组状况，这种状况主要是动车组总运行里程以及所历史所行使的时间等等，同时通过检测，也能够了解到该动车组是否需要维修，也就是说能够判断出该动车组是否为待检车辆。第二点，需要进行约束的信息条件。要优化动车组检修计划就要从条件约束开始，只有这样才能够保证检修的实际效果。要限制动车组相邻的两个路段之间的时间；相邻路段中的交叉点同时为两个交路段的起点和终点；动车上次检修到这次检修之间的时间一定要控制在安全运行时间之内，路程也需要控制在一定的范围之内；使用中的动车组数量也要保证守恒，这样才能够真正保证车辆的正常运行。

二、建构检修网络

检修网络的建构需要借助于很多参数，不同参数存在着不同的意义，其中H表示的是检修计划的整个周期，K则表示在检修期间动车组现在的检修级别，而M表示的是检修基地的集合，初次之外还存在很多小的参数。而检修网络的建构需要从以下几个步骤进行。

第一步，建结点。结点的建立需要从不同的方便进行，首先，要建立检修基地的结点，在整个网络中这个结点可以用ovm表示，以同样的方式要将该结点进行H次的复制，这样所获得的检修结点就记做mhv，各个不同检修结点放到一起的整体就记为集合MV。其次，夜间结点的建立，夜间结点主要建立在那些不是检修地点，但是却是交路段中的起始点的位置，该位置的结点都记做sov，同样也要进行N此的复制，这样所生成的结点标记以及夜间结点的整体集合分别为shv、Vs。而在这一步骤中所有建立的结点都可以用集合V来表示。

第二步，建接续弧。在接续弧中主要包括交路段弧、检修弧以及等待弧等内容，不同类型的弧所表示的内容是不同的，其标记方式也是不同的，但是，从总体而言，所有弧都可以用集合A表示。

第三部，建网络。检修网络图是进行动车组安全检修的关键内容，是一种计划上的保障，这种网络图建立起来之后可以用N（V，A）表示，而建立起来的网络图大致如图1所示：图1 动车组检修连续网络图

三、列生成算法在动车组检修中的应用

在动车组检修中存在着很多充满了变动性质的条件，这样就为动车组检修计划的优化造成了很大的障碍，所以，面对如此多的变量，我们需要运用一种行之有效的运算方法，而其中列生成算法就是一种有效的模型求解方式。

列生成算法能够很直接的找到问题的下界，“其常常被嵌入分枝定界算法中进行求解”，这种方法就比较适合与动车组检修计划中各种计算模型的求解。从总体而言，列生成算法的基本思路为，对于变量的考虑，每次只限于其中的一小部分，并不是对计算中的所有变量都考虑入内，而所求得的内容也是其中的一个限制问题，这样就能够较轻松的收获单纯乘子，同时要善于利用价格中的问题以及其子问题来实现对限制主问题的解决。

首先，生成可行解。可行解的生成也是需要通过几个步骤实现的，第一步是要复制所构件的网络，这样就形成了总网络N。第二步，主要是对需要进行检测的动车组进行排列，排列的顺序主要是以动车组的剩余运行里程进行排序，方向是从少到多，同时，要制定一个可行的运行计划。同时要根据“深度优先”的原则，从待检动车组初始结点开始进行搜索，一直要搜索到在检修周期内到达可行的动车组检修基地，同时还要根据该动车组的实际情况确定所需要的检修时间来选择等待弧。而在检修工作完成之后，还需要选择一个担当交路，从而形成一个新的行驶路径，同时删除除了等待弧以外的所有弧。第三步，复制接续网络，形成完整的网络N，第四步，对于那些非检测动成要保证其能够在原有的交路段进行基本担当工作，同时也要适当删除无用的弧，对于剩余弧以及剩余非待检动车重新进行线路的生成。

其次，确定分枝策略。对于动车组检修计划的优化而言，是一个对线性问题的规划，这种类型常用的分枝策略主要是把求解结果中的分数解变量强行的设置为1与零，最后划分解空间，对分数解进行删除处理。但是从实际工作角度来讲，采用这种列生成法对整个模型进行求解，0分枝方法对问题的解决来说并没有很大的实际意义，问题的收敛率也会受到限制，所以，最好只选择1分枝进行求解。

最后，算法的流程。对于动车组这样一个高科技含量的现代化交通工具，其检修计划必然也需要以现代化的运算方式计算机进行，所以，进行动车组检修计划的求解过程中，也应该利用计算机来实现，经常采用的软件以及程序都会随着计算机技术的发展而不断更新，而大致的算法流程如图2所示：

素有很多种，我们需要不断的进行总结与综合运用，更重要的是对于动车组的检修工作而言，我们还需要在不断的实践工作中进行研究，以提高检修计划的实用性。

结束语：

本文主要对动车组计算过程中所需要解决的问题，以及网络的构件等内容进行了简单的论述，主要目的就是提高我国动车组检修工作的共组效率以及工作质量，尽量减少动车组检修次数，提高动车组的经济价值与社会价值。同时通过以上分析还简单认识到了列生成算法在我国动车组检修计划优化中的应用方式，这种方式的应用有其非常适合的一面，也存在不适应的一面，所以需要我们再日后的实际工作中进一步总结动车组检修计划的优化方式。

参考文献

[1] 张才春，陈建华，花伟.基于不同检修能力的动车组运用计划研究[J].中国铁道科学，2010（05）

[2] 苗建瑞，王莹，杨肇夏.基于最优接续网络的动车组交路计划优化模型与算法研究[J].铁道学报，2010（02）

[3] 花伟，张才春，范振平，徐利民.动车组动态备用方式研究[J].铁道运输与经济，2011（01）

[4] 苗建瑞，王莹，杨肇夏.基于最优接续网络的动车组交路计划优化模型与算法研究[J].铁道学报，2010（02）

[5] 周爱生，高文佳，闫文立.提高CRH2型动车组三级修检修效率的几点建议[J].铁道机车车辆，2011（03）