摘要：合理编制动车组调车作业计划可提高动车运用所作业效率和检修能力。在动车所各功能区域和股道布置确定的前提下，分析动车组编组状态及股道列位占用对调车作业的影响。以减少调车作业过程中股道占用次数为目标，以动车组作业时间、调车作业次序和股道类型为约束，建立考虑股道列位占用的动车所调车作业计划编制优化模型;设计基于调车作业可行路径生成和作业优先次序交换的模拟退火算法进行求解。最后以国内某动车所调车作业计划编制为实例，验证模型和算法的有效性。结果表明：本文提出的方法能够在较短时间内编制动车所调车作业计划，并减少股道占用次数。得到的最优调车作业计划将动车组的转线次数降低为34次;且在需入库列动车组中，有80%的动车组实现了入所后的快速入库作业。考虑列位占用的调车作业计划编制的模型和算法对于提高动车所股道利用率有较好的应用价值。
关键词：铁路运输;动车所;调车作业计划;列位占用;模拟退火算法
0引言
动车所调车作业计划是根据动车所检修能力、场库布局形式、出入所时刻、作业项目等编制的动车所运用组织指导性文件。它保证了动车组按时入所和上线运行，并在规定时间内利用各功能股道，实现检修、整备、调移等作业的高效协同进行。随着我国高速铁路规模增大，上线运用动车组数量增加，传统人工编制的动车所调车作业计划存在很大的局限性，难以满足现实需求，如何自动化编制高质量的动车所调车作业计划成为动车组运用管理中亟需解决的问题。
国内外学者对动车所调车作业优化问题进行了大量研究，取得了较好成果。王忠凯等[1]以减少关键检修线区的无效占用时间和降低调车路径费用为目标，基于动车组转线作业拓扑图建立调车作业计划编制优化模型，采用改进蚁群算法进行求解;张惟皎等[2]考虑了存车线的列位占用，以提高存车线运用效率和减少调车走行距离为目标建立存车线运用优化模型，采用模拟退火法进行求解;王家喜等[3]考虑动车所的股道占用和进路占用冲突问题，以调车钩数最小为目标建模并采用粒子群算法进行求解;郭小乐等[4]把动车组总延误时间最小作为优化目标-，设计微进化算法进行模型的求解;BroekRW[5]提出了一种可自动构建分流计划的综合局部搜索方法，整合了动车组出入进路、作业任务、股道停放、列车路线四项问题，在交通规划软件和真实场景中的应用证明了该方法优于当时最先进的混合整数规划算法;HaahrJ等[6]首次将动车组调车优化问题和列车单元重组优化问题结合考虑，通过基于分枝切割的方法求解这一综合优化问题，并且对比了股道分配领域不同求解算法的性能，通过反例说明了传统最优化方法的启发式性质。陈韬等[7]提出了将高速铁路枢纽站技术作业与动车所调车作业计划协同编制的思想，以作业效率最大化为优化目标构建模型，设计了一种基于并行禁忌搜索策略的混合算法进行求解。韩宝明等[8]以最小化最晚完工时间为目标，建立动车所一级修灵活作业顺序的数学模型，考虑动车组作业先后顺序、单个动车组作业流程等条件，设计改进遗传算法进行求解。
综上，动车所调车作业计划编制可归结为一类多目标、多约束的大规模复杂优化问题，既有文献多是基于旅行商、多商品流等问题的思想，建立混合整数规划模型，采用启发式算法进行求解，有较好的效果，但针对某些具体场景的研究尚有不足。一是部分研究忽略了调车作业进路安排，在较大规模案例中进路冲突问题将会凸显，可能降低解的质量;另一方面，既有研究较少考虑动车组的长短编之分和股道双列位占用对调车作业计划编制的影响。本文基于我国动车所设施设备布局及动车组调车作业特点，考虑动车所股道两个列位的合理占用，建立调车作业计划编制优化模型，基于动车组可行路径生成和作业优先次序交换设计模拟退火算法进行求解，并采用某动车所实际运营数据对模型和算法进行验证。
1问题分析
1.1动车所内动车组作业项目及特征
为提高动车所内动车组的检修整备效率，我国采用动车组一体化检修制度，作业项目包括：出所和入所、一级修和二级修、联合检查、镟轮和临修、吸污和洗车、存车和热备、解体和编组、转线等。其中一些作业具有前后衔接关系，例如一级修完成后需进行联合检查。动车所进行作业有白班和夜班之分：夜班多为一级修，作业时间较短但作业动车组数量多;白班多为是二级修或临修与一级修结合，作业时间较长但作业动车组数量少。
《铁路动车组运用维修规则》[9]规定动车组的检修作业原则上在其配属的动车所内进行。因此根据配属关系和作业项目，可将入所作业的动车组分为三类：本所配属的需入库作业动车组、本所配属的不需入库作业动车组和非本所配属的动车组。由于动车所库内检修线相对库外存车线数量较少，通常情况下需入库作业动车组在所有入所动车组中占比最大，对该类动车组进行合理作业安排，提高检修线的利用率，是动车所调车作业计划编制中的重点。而非本所配属的动车组作业较简单，通常只在存车线上过夜或进行吸污、上水作业。
1.2动车所场库布局对调车作业的影响
动车所调车作业计划编制的影响因素较多，从动车所场库布局角度来看，动车所平面功能区域的布置会直接影响动车组的作业流程，进而影响调车作业计划的编制。例如，场库布局为“检查库+库前场+存车场”的动车所，如图1所示，动车组的检修整备流程一般为“入所→(存车)→洗车→吸污→检修→存车→出所”;而场库布局为“检查库+存车场”的动车所，如图2所示，动车组的检修整备流程一般为“入所→(存车)→检修(可含洗车、吸污)→存车→出所”。动车所的股道类型和功能区域布置的多样性使动车组的作业次序较为灵活，如洗车和检修作业的先后次序可互换。此外，对于兼具存车线功能的洗车线和镟修线，在股道后续占用不冲突的前提下，可安排已完成作业的动车组停放在该股道上以提高股道的利用率。
1.3动车组编组状态和列位占用的影响
我国铁路动车组按编成辆数有短编动车组和长编动车组之分，按编组状态可分为短编动车组单编、短编动车组重联和长编动车组。短编动车组在编组上具有灵活性，在入所检修整备时可能呈现不同编组状态，如表1所示。
为满足长编和重联动车组的检修、整备、存车等作业需求，我国动车所的股道有效长均按照可以停放一列长编或重联动车组的标准设计。事实上，动车所的每条股道均有两个列位，若设有分割信号，则可停放两列未重联的短编动车组;若无分割信号，则可以选择任一列位停放一列短编动车组。重联动车组待解体、短编动车组待重联、空闲存车线数量较少时，均会出现两列短编动车组占用同一股道相邻两列位的情况。由于该两列动车组的存放时间和作业项目可能存在差异，其调车作业次序及下阶段的股道占用情况会受到较大影响。因此，编制动车所调车作业计划应考虑股道列位的合理占用，尽力避免进路冲突、存车线占用冲突等问题。
一方面，由于未重联短编动车组的出入所时刻、各作业完成时刻可能存在差异，若盲目地将两列未重联短编动车组停放在同一条股道，可能产生额外的转线，降低调车作业效率。另一方面，动车所各功能区的股道数量固定，在动车组检修任务日益繁重的情况下，若实现短编动车组对股道两个列位的合理占用，且避免产生多余的转线和进路冲突，则能够提高股道的利用率，从而提高动车所的检修能力和调车作业效率。
1.4关键技术问题描述
目前，我国动车组运用组织有以下特点：动车组通常在白天上线运行，日常的一级检修、洗车等一系列所内作业大多在夜间进行。在白班计划中动车组的调车作业时间相对宽松，而对于作业较繁忙的夜班计划，动车组出入所时刻、空闲股道状态等对调车作业计划编制的限制更显著。基于此，本文研究的动车所调车作业计划编制优化有以下两个关键技术问题：一是如何在动车组出入所时刻及作业项目不同的情况下，合理确定动车组调车作业的先后次序及股道占用的具体情况，保证动车组按时出入所并能完成所有作业。二是如何在编制调车作业计划时考虑实时的动车组编组状态和股道及其列位占用情况，从而合理利用股道及其列位以提高调车作业效率。
2模型建立
2.1建模说明与假设
基于我国动车所的设施设备布局形式、动车所现行调车作业的特点及其计划编制实际情况，对本文模型建立做以下说明：
(1)针对单一类型动车所的调车作业计划编制问题进行建模，编制周期为一个班计划，即白班计划或夜班计划;
(2)在动车所内进行检修整备作业的动车组，从编组形式上包括短编动车组单编、短编动车组重联和长编动车组，从动车组配属上分为本所动车组和外所动车组;
(3)动车所内的进路包括入所进路、调车进路和出所进路;
(4)各动车组到达和出发时刻已知，即动车组在动车所内的停留总时间确定，必须在该时间内完成检修整备作业;
(5)本班计划开始时，可能存在上一班计划中入所但未出所的动车组。
(6)满足动车组转线所需的实际最大时间，所有动车组均采用相同的最小转线时间标准。
考虑到动车所调车作业的复杂性，为突出重点，降低模型复杂度及求解难度，做以下假设：
(1)动车所的检修班组的数量充足，每条检修线可同时进行检修作业;
(2)动车所的股道均带分割信号，即各股道都可停放两列短编动车组;
2.2模型参数
模型主要参数定义和说明如表2所示。
2.3优化模型
已知动车所班计划中需进行各项作业的动车组数量，通过减少动车组不必要的转线作业，降低调车进路发生时间冲突的几率，有利于提高动车所的调车作业效率。采用本班计划内的动车所股道占用次数来衡量动车所的调车作业效率，以减少动车所股道占用次数作为优化目标，如式1所示。
3算法设计
上述模型属于大规模的混合整数规划模型，约束条件较多且复杂。在运输组织优化建模中，此类模型比较普遍，一般结合模型特点，采用启发式算法进行求解[10,11]。模拟退火算法是一种经典的启发式算法，具有易于实现、鲁棒性高、计算过程简单等特点，被广泛应用于求解复杂的非线性优化问题。在结构设计上，可根据实际情况和输入数据特点，设置合适的状态函数和退火策略，符合本文模型的特点和求解需求。
本文模型中，当动车所的股道数目、动车组的数量、作业任务量增大，模型的求解难度会急剧上升。求解得到的调车作业计划需确定每列动车组进行各项作业的起止时间和占用的股道，即反映各动车组在所内完成调车作业走行的全过程。模型的求解过程分为以下三个阶段。
(1)生成单列动车组的检修整备可行路径。
(2)生成包含全部动车组可行路径的调车作业计划可行解。
(3)采用模拟退火算法在可行解中寻优。
3.1模型的编码和可行解
动车所调车作业计划包含的信息涉及各动车组入所、检修整备、出所等作业过程和动车所各股道的占用情况，因此，本文分别对上述两种信息进行实数编码。由于动车组调车作业时间标准通常为5min的整数倍，按5min的整数倍为单位时间，划分本班计划得到编码长度。例如以15min为一段进行编码，动车组编码片段如图3所示，0表示未进行检修整备作业，正整数表示作业项目类型，-1表示存车;股道编码片段如图4所示，0表示股道空闲状态，正整数表示占用该股道的动车组序号，-1表示某动车组转线时占用该股道。模型求解完成后，解码两套编码得到完整的动车所调车作业计划方案。
相关期刊推荐：《西南交通大学学报》(双月刊)创刊于1954年，读者对象主要为国内外科技工作者、工程技术人员、高等院校理工科教师和学生等。设有：理工类理论研究、应用研究、实验研究、学术讨论等方面的学术论文以及科技信息报道等栏目。
根据某动车组入所时各股道的占用和剩余可作业时间状态，对其各项作业的顺序、时间、股道占用做出合理安排，即得到该动车组的检修整备可行路径。对于全部动车组，由于出入所时间不一，在动车所的实际停留时间也不同，为尽量避免无法生成调车作业计划可行解，应制订合理的动车组间进行检修整备作业的优先级顺序。同时考虑将动车组按照作业项目先分类再生成可行解，在求解过程中不同分类的动车组仅与具有相应功能的股道集合双向匹配，有利于降低方案组合数量、提高求解速率。
本文中模型的可行解生成算法如下：
Step0：输入各动车组入所、出所时刻、作业项目和编组状态，本班计划开始、结束时刻，各股道的功能和初始占用状态，各类型作业时间标准等;
Step1：根据各动车组具体作业项目生成其合理作业顺序，并将全部动车组分为上文所述三类，根据各动车组在所实际停留时间从小到大排列生成检修作业初始优先级顺序;
Step2：按照动车组检修作业优先级顺序选取一列动车组，根据股道当前列位占用状态和剩余可用作业时间等信息及各约束条件，对该动车组按照其作业项目顺序随机选取具有相应功能且空闲的股道进行检修整备作业，每项作业结束后更新该动车组和占用股道的时空状态;
Step3：重复Step2，遍历该动车组的作业项目，若能在其停留时间内完成全部的检修整备作业，则得到该动车组完整的个体编码，即生成该动车组的检修整备可行路径，否则该路径不可行;
Step4：重复Step2和Step3，遍历该班计划内的所有动车组，得到各动车组个体编码和各股道个体编码，若能在班计划时间内生成全部动车组的检修整备可行路径，则该解可行，若无法生成则表明产生了作业的时空冲突，应舍弃该不可行解;
Step5：对于可行解，根据各动车组个体编码和各股道个体编码的信息，得到完整的动车所调车作业计划，计算该可行解的目标值。
Step6：采用模拟退火算法产生随机扰动，得到新的动车组检修作业优先级顺序，重复Step2~Step5，生成新的动车所调车作业计划可行解。
3.2模拟退火算法寻优
在可行解中进行寻优的关键是邻域解的生成，对于动车所调车作业计划，一种邻域构造方法是随机交换可行解中两列动车组对股道的占用，但这种方法在作业动车组数量较多、问题求解规模较大时具有一定的盲目性，求解效率不高。
动车组检修优先级顺序对调车作业计划编制结果有影响，在实践中，当作业动车组数量较多时，按照动车组在所实际停留时间从小到大排列的动车组检修优先级顺序可能无法得到可行的调车作业计划。例如图5所示，按该排序方式的动车组检修优先级顺序为(e2，e1，e3)，而e3无法按时出所，原因是M1在e2检修前的可用检修时间被浪费。将优先级顺序调整为(e1，e2，e3)时，e3可顺利完成检修整备，如图6所示。
鉴于此，本文的邻域结构设计为：对初始可行解的动车组检修作业优先级排序，在非重联的短编动车组中随机选择两列，交换其在检修作业优先级顺序中的位置。这种邻域结构有较好的随机扰动性能，有利于可行解的优化，同时能保证重联的短编动车组同步作业，有利于提高调车作业的效率。本文的模拟退火算法采用线性降温方式，依据Metropolis接受准则接受新解，其他规则不再赘述。完整的动车所调车作业计划编制优化模型的算法流程如图7所示。
4实例分析
4.1数据准备
国内某尽端式动车所，采用“存车场+检查库”的场库布局，如图8所示，检查库设有4条检修线，存车场设有18条股道，均可用于动车组存放，其中S1道为机洗线，S2道为人工洗车线，S17道为镟轮线，S18道为临修线，动车所内所有股道均带有分割信号，调车作业的平行进路为2条。
该动车所承担本所配属动车组的检修整备及部分外所动车组的过夜任务，进行各项作业的时间标准如表3所示。
某个夜班(20:00~8:00)中需要进行检修整备作业的动车组的各项信息如表4所示，其中e1~e12为本所配属动车组，e13~e15为外所过夜动车组。“线存”、“库存”表示本班开始时或结束时动车组在存车线或检修线上，本班开始时e1在S5道，e2、e3分别在S9道两列位。作业项目中“检修”表示在检查库进行一级修及其他作业，“机洗”、“人工洗车”、“吸污”表示对应作业不在检查库进行。
4.2求解与结果分析
采用Python语言在Spyder开发环境上实现优化模型的求解。取初始温度100，降温速率0.98，终止温度为1，最大迭代次数500，同温迭代次数1，经多次测试，均能在4s内求得该算例的最优解。取其中一次求解结果，迭代收敛曲线如图7所示。将求解结果进行整理，得到该算例的最优调车作业计划如表5所示。
在本例中，一级修作业时间15min及转线时间15min，动车组入库一级修用时约3h，本班计划为12h，检修线为4条，则不考虑检修线双列位占用时理论最大检修能力为16列。本班计划实际入库检修的动车组为10列，且检修线JC4利用了双列位，从编制结果来看检修线的能力也有较多富余。该动车所存车线为12条，占用存车线的动车组为15列，本算例中存车线恰好满足一股道一列车的停放需求，但当动车组数量增加或停留时间延长时，充分利用股道列位具有求解优势。
在迭代过程中，股道占用次数最多为41次，其产生原因是为避免股道时空占用冲突，部分动车组进行了不必要的转线，最低为34次，对应的方案中没有动车组不必要的转线。在需要入库作业的10列动车组中，有8列实现了入所后快速入库作业，对于检修线作业效率和利用率的提高有较好的效果。可以看出，本文的模型和算法在求解动车所调车作业计划的有效性和实用性得到了一定提高。
5结论
本文根据我国现行动车组运用管理和动车所调车作业的特点，在上线运用动车组数量增加的背景下，着眼于动车所调车作业效率和实际检修能力的提高，考虑动车所股道双列位的合理利用，建立调车作业计划编制优化模型，设计基于动车组作业优先次序的模拟退火算法进行求解，结合算例对其进行验证，得到如下结论：
(1)合理利用动车所股道双列位有利于提高股道利用率和动车所调车作业效率。
(2)合理的动车组作业优先次序能够提高调车作业计划的编制速率和质量。
针对不同类型的动车所，考虑调车作业白班计划和夜班计划的联合协调编制，是需要进一步研究的方向。——论文作者：户佐安1，2，3，郑磊1，4，周姝1
