考虑列位合理占用的动车所调车作业计划编制优化

户佐安 ，郑 磊 ，周 姝

（1.西南交通大学交通运输与物流学院, 四川 成都 611756；2.西南交通大学综合交通大数据应用技术国家工程实验室, 四川 成都 611756；3.西南交通大学综合交通运输智能化国家地方联合工程实验室, 四川 成都 611756；4.中铁二院工程集团有限责任公司, 四川 成都 610031）

动车所调车作业计划是根据动车所检修能力、场库布局形式、出入所时刻、作业项目等编制的动车所运用组织指导性文件.它保证了动车组按时入所和上线运行，并在规定时间内利用各功能股道，实现检修、整备、调移等作业的高效协同进行.随着我国高速铁路规模增大，上线运用动车组数量增加，传统人工编制的动车所调车作业计划存在很大的局限性，难以满足现实需求，如何自动化编制高质量的动车所调车作业计划成为动车组运用管理中亟须解决的问题.

国内外学者对动车所调车作业优化问题进行了大量研究，取得了较好成果.王忠凯等[1]以减少关键检修线区的无效占用时间和降低调车路径费用为目标，基于动车组转线作业拓扑图，建立调车作业计划编制优化模型，采用改进蚁群算法进行求解；张惟皎等[2]考虑了存车线的列位占用，以提高存车线运用效率和减少调车走行距离为目标建立存车线运用优化模型，采用模拟退火法进行求解；王家喜等[3]考虑动车所的股道占用和进路占用冲突问题，以调车钩数最小为目标建模，并采用粒子群算法进行求解；郭小乐等[4]把动车组总延误时间最小作为优化目标，设计微进化算法进行模型的求解；Broek[5]提出了一种可自动构建分流计划的综合局部搜索方法，整合了动车组出入进路、作业任务、股道停放、列车路线，在交通规划软件和真实场景中的应用证明了该方法优于当时最先进的混合整数规划算法；Haahr等[6]首次将动车组调车优化问题和列车单元重组优化问题相结合，通过基于分枝切割的方法求解这一综合优化问题，并且对比了股道分配领域不同求解算法的性能，通过反例说明了传统最优化方法的启发式性质.陈韬等[7]提出了将高速铁路枢纽站技术作业与动车所调车作业计划协同编制的思想，以作业效率最大化为优化目标构建模型，设计了一种基于并行禁忌搜索策略的混合算法进行求解.韩宝明等[8]以最小化最晚完工时间为目标，建立动车所一级修灵活作业顺序的数学模型，考虑动车组作业先后顺序、单个动车组作业流程等条件，设计改进遗传算法进行求解.

综上，动车所调车作业计划编制可归结为一类多目标、多约束的大规模复杂优化问题，既有文献多是基于旅行商、多商品流等问题的思想，建立混合整数规划模型，采用启发式算法进行求解，有较好的效果，但针对某些具体场景的研究尚有不足.一是部分研究忽略了调车作业进路安排，在较大规模案例中进路冲突问题将会凸显，可能降低解的质量；另一方面，既有研究较少考虑动车组的长短编之分和股道双列位占用对调车作业计划编制的影响.本文基于我国动车所设施设备布局及动车组调车作业特点，考虑动车所股道两个列位的合理占用，建立调车作业计划编制优化模型，基于动车组可行路径生成和作业优先次序交换设计模拟退火算法，并采用某动车所实际运营数据对模型和算法进行验证.

1 问题分析

1.1 动车所内动车组作业项目及特征

为提高动车所内动车组的检修整备效率，我国采用动车组一体化检修制度，作业项目包括：出所和入所、一级修和二级修、联合检查、镟轮和临修、吸污和洗车、存车和热备、解体和编组、转线等.其中，一些作业具有前后衔接关系，例如一级修完成后需进行联合检查.动车所进行作业有白班和夜班之分：夜班多为一级修，作业时间较短但作业动车组数量多；白班多为是二级修或临修与一级修结合，作业时间较长，但作业动车组数量少.

《铁路动车组运用维修规则》[9]规定动车组的检修作业原则上在其配属的动车所内进行.因此，根据配属关系和作业项目可将入所作业的动车组分为三类：本所配属的需入库作业动车组、本所配属的不需入库作业动车组和非本所配属的动车组.由于动车所库内检修线相对库外存车线数量较少，通常情况下需入库作业动车组在所有入所动车组中占比最大，对该类动车组进行合理作业安排，提高检修线的利用率，是动车所调车作业计划编制中的重点.非本所配属的动车组作业较简单，通常只在存车线上过夜或进行吸污、上水作业.

1.2 动车所场库布局对调车作业的影响

动车所调车作业计划编制的影响因素较多，从动车所场库布局角度来看，动车所平面功能区域的布置会直接影响动车组的作业流程，进而影响调车作业计划的编制.例如，场库布局为“检查库 + 库前场 + 存车场”的动车所，如图1（a）所示，动车组的检修整备流程一般为“入所→（存车）→洗车→吸污→检修→存车→出所”；场库布局为“检查库 +存车场”的动车所，如图1（b）所示，动车组的检修整备流程一般为“入所→（存车）→检修（可含洗车、吸污）→存车→出所”.动车所的股道类型和功能区域布置的多样性使动车组的作业次序较为灵活，如洗车和检修作业的先后次序可互换.此外，对于兼具存车线功能的洗车线和镟修线，在股道后续占用不冲突的前提下，可安排已完成作业的动车组停放在该股道上以提高股道的利用率.

图1 动车所场库布置示意Fig.1 Layout schematic diagram of EMU depots

1.3 动车组编组状态和列位占用的影响

我国铁路动车组按编成辆数有短编动车组和长编动车组之分，按编组状态可分为短编动车组单编、短编动车组重联和长编动车组.短编动车组在编组上具有灵活性，根据出入所呈现的不同编组状态，可划分为不同情形，如表1所示.

表1 短编动车组编组状态Tab.1 Marshalling state of short-form EMUs

为满足长编和重联动车组的检修、整备、存车等作业需求，我国动车所股道的有效长均按照可以停放一列长编或重联动车组的标准而设计的.事实上，动车所的每条股道均有两个列位，若设有分割信号，则可停放两列未重联的短编动车组；若无分割信号，则可以选择任一列位停放一列短编动车组.重联动车组待解体、短编动车组待重联、空闲存车线数量较少时，均会出现两列短编动车组占用同一股道相邻两列位的情况.由于该两列动车组的存放时间和作业项目可能存在差异，其调车作业次序及下阶段的股道占用情况会受到较大影响.因此，编制动车所调车作业计划应考虑股道列位的合理占用，尽力避免进路冲突、存车线占用冲突等问题.

一方面，由于未重联短编动车组的出入所时刻、各作业完成时刻可能存在差异，若盲目地将两列未重联短编动车组停放在同一条股道，可能产生额外的转线，降低调车作业效率.另一方面，动车所各功能区的股道数量固定，在动车组检修任务日益繁重的情况下，若实现短编动车组对股道两个列位的合理占用，且避免产生多余的转线和进路冲突，则能够提高股道的利用率，从而提高动车所的检修能力和调车作业效率.

1.4 关键技术问题描述

目前，我国动车组运用组织有以下特点：动车组通常在白天上线运行，日常的一级检修、洗车等一系列所内作业大多在夜间进行.在白班计划中动车组的调车作业时间相对宽松，而对于作业较繁忙的夜班计划，动车组出入所时刻、空闲股道状态等对调车作业计划编制的限制更显著.基于此，本文研究的动车所调车作业计划编制优化有以下两个关键技术问题：一是如何在动车组出入所时刻及作业项目不同的情况下，合理确定动车组调车作业的先后次序及股道占用的具体情况，保证动车组按时出入所并能完成所有作业；二是如何在编制调车作业计划时考虑实时的动车组编组状态和股道及其列位占用情况，从而合理利用股道及其列位以提高调车作业效率.

2 模型建立

2.1 建模说明与假设

基于我国动车所的设施设备布局形式、动车所现行调车作业的特点及其计划编制实际情况，对本文模型建立做以下说明：

1）针对单一类型动车所的调车作业计划编制问题进行建模，编制周期为一个班计划，即白班计划或夜班计划；

2）在动车所内进行检修整备作业的动车组，从编组形式上包括短编动车组单编、短编动车组重联和长编动车组，从动车组配属上分为本所动车组和外所动车组；

3）动车所内的进路包括入所进路、调车进路和出所进路；

4）各动车组到达和出发时刻已知，即动车组在动车所内的停留总时间确定，必须在该时间内完成检修整备作业；

5）本班计划开始时，可能存在上一班计划中入所但未出所的动车组；

6）满足动车组转线所需的实际最大时间，所有动车组均采用相同的最小转线时间标准.

考虑到动车所调车作业的复杂性，为突出重点，降低模型复杂度及求解难度，做以下假设：

1）动车所的检修班组的数量充足，每条检修线可同时进行检修作业；

2）动车所的股道均带分割信号，即各股道都可停放两列短编动车组.

2.2 模型参数

模型主要参数定义和说明如下：

E为动车组集合，E=EL∪ES=EW∪EO，其中：EL为短编动车组集合；ES为长编动车组集合；EW为本所动车组集合；EO为外所动车组集合.e为动车组索引，对于同一股道上先后紧邻作业的动车组，定义后行车组e的前行车组为e′， ∀e,e′∈E.

D为动车所股道集合, 由检修线和其他股道两大部分组成，D=DM∪DN=DM∪DS∪DW1∪DW2∪DX∪DI，其中：DM为检修线集合；DN为除检测线外的其他股道集合；DS为普通存车线集合；DW1和DW2分别为机洗线和人工洗车线集合；DX和DI分别为镟修线和临修线集合.d为股道索引, ∀d∈D，特别地，用d1和d2表示股道的两个列位，d1,d2∈d.

R为动车所内的进路集合，R=RA∪RD∪RS，其中：RA为白日交路集合；RD为夜晚交路集合；RS为调车作业进路集合.r为进路索引， ∀r∈R.

Nr为不同咽喉区域的平行进路数量.

Ts为转线作业的时间标准.

τ为同一进路上避免冲突的列车间隔时间.

ter,s、ter,f分别为动车组e执行进路r的开始时刻、结束时刻.

Pe为动车组e的作业项目集合，p为作业项目索引， ∀p∈Pe，对于动车组e后紧邻两项作业，定义后项作业p的前项作业为p‘， ∀p′∈Pe′.

Ne为常量，其值等于动车组e的作业项目数量.p=Ne时表示最后的作业项目，p=1 时表示最开始的作业项目.

Pd为动车所股道d可进行的作业项目集合.

Tep为动车组e执行作业项目p的时间标准.

tedp,s、tedp,f分别为动车组e在股道d上执行作业项目p的开始时刻、结束时刻.

te,a、te,d分别为动车组e的入所时刻、出所时刻.

ts、tf分别为本班调车计划的开始时刻、结束时刻.

Ted为辅助变量，表示前行车组e‘离开股道d后，该股道可供后行车组e作业的时间.

θpp′为0-1辅助变量，动车组e作业p和p‘需要转线取1，否则取0.

yedr为0-1辅助变量，股道d满足动车组e承担进路r的任务功能时时取1，否则取0.

sedp为0-1辅助变量，股道d满足动车组e执行作业p功能时取1，否则取0.

cedp为0-1决策变量，考虑约束动车组e能在股道d进行作业p时取1，否则取0.

xedp为0-1决策变量，动车组e执行在股道d进行作业p时取1，否则取0.

2.3 优化模型

已知动车所班计划中需进行各项作业的动车组数量，通过减少动车组不必要的转线作业，降低调车进路发生时间冲突的几率，有利于提高动车所的调车作业效率.采用本班计划内的动车所股道占用次数来衡量动车所的调车作业效率，以减少动车所股道占用次数作为优化目标，如式（1）所示.

约束条件包括：

式（2）、（3）表示动车组任一作业项目均应在本班时间内完成；式（4）表示动车组某项作业在股道上的停留时间不小于该作业的时间标准；式（5）、（6）为考虑动车组进行后项作业是否需要转线的前、后项作业的时间接续约束；式（7）、（8）表示动车组不同类型的作业必须在具备相应作业功能的股道上进行；式（9）为动车所某股道及其列位不发生占用时间冲突的约束；式（10）、（11）为考虑列车间隔时间的咽喉进路不发生占用时间冲突的约束；式（12）、（13）为动车组是否在某股道进行作业的决策约束；式（14）为动车组是否进行转线调车的决策约束；式（15）为平行进路数量约束；式（16）表示动车组某项作业时只占用一条股道；式（17）表示某股道在同一时刻最多停留两列动车组.

3 算法设计

上述模型属于大规模的混合整数规划模型，约束条件较多且复杂.在运输组织优化建模中，此类模型比较普遍，一般结合模型特点，采用启发式算法进行求解[10-11].模拟退火算法是一种经典的启发式算法，具有易于实现、鲁棒性高、计算过程简单等特点，被广泛用于求解复杂的非线性优化问题.在结构设计上，根据实际情况和输入数据特点设置合适的状态函数和退火策略，符合本文模型的特点和求解需求.

本文模型中，当动车所的股道数目、动车组的数量、作业任务量增大，模型的求解难度会急剧上升.求解得到的调车作业计划需确定每列动车组进行各项作业的起止时间和占用的股道，即反映各动车组在所内完成调车作业走行的全过程.模型的求解过程分为以下3个阶段：

1）生成单列动车组的检修整备可行路径.

2）生成包含全部动车组可行路径的调车作业计划可行解.

3）采用模拟退火算法在可行解中寻优.

3.1 模型的编码和可行解

动车所调车作业计划包含的信息涉及各动车组入所、检修整备、出所等作业过程和动车所各股道的占用情况，因此，本文分别对上述两种信息进行实数编码.由于动车组调车作业时间标准通常为5 min的整数倍，按5 min的整数倍为单位时间，划分本班计划得到编码长度.例如以15 min为一段进行编码，动车组编码片段如图2所示，0表示未进行检修整备作业，正整数表示作业项目类型（2、9分别为检修整备作业、转线），-1表示存车.股道编码片段如图3所示，0表示股道空闲状态，3表示占用该股道的动车组序号为e3，-1表示某动车组转线时占用该股道.模型求解完成后，解码两套编码得到完整的动车所调车作业计划方案.

图2 动车组的个体编码片段Fig.2 Individual code fragments of the EMU

图3 股道的个体编码片段Fig.3 Individual code fragments of the tract

根据某动车组入所时各股道的占用和剩余可作业时间状态对其各项作业的顺序、时间、股道占用作出合理安排，即得到该动车组的检修整备可行路径.对于全部动车组，由于出入所时间不一，在动车所的实际停留时间也不同，为尽量避免无法生成调车作业计划可行解，应制订合理的动车组间进行检修整备作业的优先级顺序.同时考虑将动车组按照作业项目先分类再生成可行解，在求解过程中不同分类的动车组仅与具有相应功能的股道集合双向匹配，有利于降低方案组合数量，提高求解速率.

本文中模型的可行解生成算法如下：

步骤1输入各动车组入所、出所时刻、作业项目和编组状态，本班计划开始、结束时刻，各股道的功能和初始占用状态，各类型作业时间标准等；

步骤2根据各动车组具体作业项目生成其合理作业顺序，并将全部动车组分为上文所述三类，根据各动车组在所实际停留时间从小到大排列生成检修作业初始优先级顺序；

步骤3按照动车组检修作业优先级顺序选取一列动车组，根据股道当前列位占用状态和剩余可用作业时间等信息及各约束条件，对该动车组按照其作业项目顺序随机选取具有相应功能且空闲的股道进行检修整备作业，每项作业结束后更新该动车组和占用股道的时空状态；

步骤4重复步骤3，遍历该动车组的作业项目，若能在其停留时间内完成全部的检修整备作业，则得到该动车组完整的个体编码，即生成该动车组的检修整备可行路径，否则该路径不可行；

步骤5重复步骤4，遍历该班计划内的所有动车组，得到各动车组个体编码和各股道个体编码，若能在班计划时间内生成全部动车组的检修整备可行路径，则该解可行，若无法生成则表明产生了作业的时空冲突，应舍弃该不可行解；

步骤6对于可行解，根据各动车组个体编码和各股道个体编码的信息，得到完整的动车所调车作业计划，计算该可行解的目标值；

步骤7采用模拟退火算法产生随机扰动，得到新的动车组检修作业优先级顺序，重复步骤3 ～ 6，生成新的动车所调车作业计划可行解.

3.2 模拟退火算法寻优

在可行解中进行寻优的关键是邻域解的生成，对于动车所调车作业计划，一种邻域构造方法是随机交换可行解中两列动车组对股道的占用，但这种方法在作业动车组数量较多、问题求解规模较大时具有一定的盲目性，求解效率不高.

动车组检修优先级顺序对调车作业计划编制结果有影响，在实践中，当作业动车组数量较多时，按照动车组在所实际停留时间从小到大排列的动车组检修优先级顺序可能无法得到可行的调车作业计划.例如图4（a）所示，图中：t1～t3为动车所入所时间，t4～t6为完成调车作业后的出所时间；S1、S2 和M1分别表示机洗线、人工洗车线和运用检修线.按该排序方式的动车组检修优先级顺序为e2，e1，e3，而e3无法按图中时间出所，原因是M1在e2检修前的可用检修时间被浪费.将优先级顺序调整为e1，e2，e3时，e3可顺利完成检修整备，如图4（b）所示.

图4 调车作业安排Fig.4 Arrangement of shunting operation

鉴于此，本文的邻域结构设计为：对初始可行解的动车组检修作业优先级排序，在非重联的短编动车组中随机选择两列，交换其在检修作业优先级顺序中的位置.这种邻域结构有较好的随机扰动性能，有利于可行解的优化，同时能保证重联的短编动车组同步作业，有利于提高调车作业的效率.本文的模拟退火算法采用线性降温方式，依据Metropolis接受准则接受新解，其他规则不再赘述.完整的动车所调车作业计划编制优化模型的算法流程如图5所示.

图5 动车所调车作业计划编制优化算法流程Fig.5 Flow chart of optimization algorithm for shunting operation plan of EMU depot

4 实例分析

4.1 数据准备

国内某尽端式动车所，采用“存车场 + 检查库”的场库布局，如图6所示，检查库设有4条检修线JC1～JC4，存车场设有12条股道，均可用于动车组存放，其中S1道为机洗线，S2道为人工洗车线，S11道为镟轮线，S12道为临修线，动车所内所有股道均带有分割信号，调车作业的平行进路为2条.

图6 动车所平面示意Fig.6 Schematic plan view of EMU depot

该动车所承担本所配属动车组的检修整备及部分外所动车组的过夜任务，进行各项作业的时间标准如表2所示.

表2 动车组作业时间标准Tab.2 EMU operating time standards

某个夜班（20：00—08：00）中需要进行检修整备作业的动车组的各项信息如表3所示，其中e1 ～e12为本所配属动车组，e13 ～ e15为外所过夜动车组.“线存”“库存”表示本班开始时或结束时动车组在存车线或检修线上，本班开始时e1在S5道，e2、e3分别在S9道两列位.作业项目中“检修”表示在检查库进行一级修及其他作业，“机洗”“人工洗车”“吸污”表示对应作业不在检查库进行.

表3 作业动车组基本信息Tab.3 Basic information of operating EMU

4.2 求解与结果分析

采用Python语言在Spyder开发环境上实现优化模型的求解.取初始温度100，降温速率0.98，终止温度为1，最大迭代次数500，同温迭代次数1，经多次测试，均能在4 s内求得该算例的最优解.取其中一次求解结果，迭代收敛曲线如图7所示.将求解结果进行整理，得到该算例的最优调车作业计划如表4所示.

表4 最优调车作业计划Tab.4 Optimal shunting operation plan

图7 迭代收敛曲线Fig.7 Iterative convergence curve

在本例中，一级修作业时间15 min及转线时间15 min，动车组入库一级修用时约 3 h，本班计划为12 h，检修线为4条，则不考虑检修线双列位占用时理论最大检修能力为16列.本班计划实际入库检修的动车组为10列，且检修线JC4利用了双列位，从编制结果来看检修线的能力也有较多富余.该动车所存车线为12条，占用存车线的动车组为15列，本算例中存车线恰好满足一股道一列车的停放需求，但当动车组数量增加或停留时间延长时，充分利用股道列位具有求解优势.

在迭代过程中，股道占用次数最多为41次，其产生原因是为避免股道时空占用冲突，部分动车组进行了不必要的转线，最低为34次，对应的方案中没有动车组不必要的转线.在需要入库作业的10列动车组中，有8列实现了入所后快速入库作业，对于检修线作业效率和利用率的提高有较好的效果.可以看出，本文的模型和算法在求解动车所调车作业计划的有效性和实用性得到了一定提高.

5 结 论

本文根据我国现行动车组运用管理和动车所调车作业的特点，在上线运用动车组数量增加的背景下，着眼于动车所调车作业效率和实际检修能力的提高，考虑动车所股道双列位的合理利用，建立调车作业计划编制优化模型，设计基于动车组作业优先次序的模拟退火算法进行求解，结合算例对其进行验证，得到如下结论：

1）合理利用动车所股道双列位有利于提高股道利用率和动车所调车作业效率.

2）合理的动车组作业优先次序能够提高调车作业计划的编制速率和质量.

针对不同类型的动车所，考虑调车作业白班计划和夜班计划的联合协调编制，是需要进一步研究的方向.