陈 韬，王文宪，吕红霞，吕苗苗，刘晓伟

(1.西南交通大学 交通运输与物流学院，四川 成都 610031；2.西南交通大学 全国铁路列车运行图编制研发培训中心，四川 成都 610031；3.综合交通运输智能化国家地方联合工程实验室，四川 成都 610031；4.五邑大学 轨道交通学院，广东 江门 529020)

高速铁路(以下简称高铁)枢纽站是指位于高铁的起讫点或衔接两(多)条高铁，开行大量始发、终到高速列车的车站，附近一般设有动车所(段)，两者由动车走行线联通[1]。为了确保列车运行计划的可实施性，高铁枢纽站需要编制技术作业计划，动车所需要编制调车作业计划。由于高铁枢纽站非立折始发、终到列车通常都要安排到相邻动车所进行整备、停留和检修，因而，高铁枢纽站技术作业计划与动车所调车作业计划具有强耦合性，具体表现为：一方面，高铁枢纽站非立折始发、终到列车需及时出入动车所，以减少高铁枢纽站的到发线占用，提升车站的通过能力；而另一方面列车密集出入动车所以及动车所作业安排不当，可能会超过动车所通过能力和作业能力，造成动车所的拥堵，从而制约列车出入动车所的数量和时间，引发高铁枢纽站技术作业计划的再调整。因此，高铁枢纽站技术作业计划与动车所调车作业计划在编制过程中需要多次协调、共同确定非立折始发、终到列车的出入动车所时间，并在此基础上编制可行的高铁枢纽站技术作业计划与动车所调车作业计划。

既有研究大多将高铁枢纽站技术作业计划[2-5]与动车所调车作业计划[6-8]分开单独研究，且非立折始发、终到列车的出入动车所时刻常作为定值[9]处理。朱昌锋[10]将出入所时刻作为列车占用到发线的可调整要素，并假设动车所能力充分大。郭彬[11]在高铁大站技术作业计划编制中从减少非立折始发、终到列车的股道占用时间以及出入所与接发车进路冲突的角度探讨了列车出入所时刻的确定方法，但没有考虑动车所调车作业计划的可行性。目前，研究高铁枢纽站技术作业计划与动车所调车作业计划相互协同编制的文献较少，使得此两种计划的编制效率和能力利用优化受到限制。

本文在分析高铁枢纽站技术作业计划与动车所调车作业计划的协同编制过程基础上，提出了将作业计划编制对象由列车映射为车底，并通过优化调整非立折始发、终到列车出入所时刻，实现两个计划一体化编制的思想。研究建立了基于动车组车底的高铁枢纽站与动车所作业计划协同编制模型，引入瓶颈工序的确定，设计了启发式分配规则与并行禁忌搜索算法(PTS)相结合的混合优化算法，并通过实例验证了相关理论。

1 问题分析

1.1 高铁枢纽站技术作业计划与动车所调车作业计划协同编制过程分析

高铁枢纽站技术作业计划、动车所调车作业计划是在列车运行图、动车组运用计划等路网层运输计划的基础上编制的微观节点层运输计划。高铁枢纽站技术作业计划在保证列车到发次序、到发时刻、列车接续关系、作业流程与时间标准的前提下，确定车站内各次列车所占用的到发线、咽喉进路以及这些设备的占用起止时刻。动车所调车作业计划在保证高铁枢纽站非立折始发、终到列车的检修和整备作业流程与时间标准前提下，确定动车所内各列车车底各项作业所占用的股道、转线进路以及这些设备的起止时刻。其中，非立折始发、终到列车的出入所时刻一般由高铁枢纽站编图人员负责确定，但仍需获得动车所编图人员的认同，尤其是高峰期能力紧张时，需要共同协商确定出入所时刻，如果双方调整后仍然无法正常安排作业，需反馈给列车运行图及动车组运用计划编图人员，通过微调列车到发时刻或改变动车交路来提升计划的可行性。高铁枢纽站技术作业计划与动车所调车作业计划协同编制过程见图1。研究发现，若将高铁枢纽站与动车所看作一个系统，将作业计划编制对象由列车映射为车底，通过优化调整非立折始发、终到列车出入所时刻，就可实现高铁枢纽站技术作业计划与动车所调车作业计划的一体化编制，是高效率实现两个计划协同编制的有效方法。

1.2 协调编制中列车与动车组车底作业计划的对应关系特点分析

高铁枢纽站的非立折终到、始发列车通常以空车底列车的方式出入动车所进行作业，如图2所示，非立折终到列车J1的空车底列车是0J1，非立折始发列车J2的空车底列车是0J2。就高铁枢纽站而言，列车J1与0J1、J2与0J2分别对应两个独立的动车组车底，可当高铁枢纽站与动车所作为一个系统时，列车J1、0J1、0J2、J2两两接续对应同一个动车组车底。因此，枢纽站与动车所作业计划协同编制时，将计划编制对象由所有列车映射为对应的动车组车底，可降低计划编制对象的规模，能完整的体现枢纽站及动车所作为一个系统的技术作业流程，有利于计划协同方案的确定。

本文中，将非立折终到、始发列车对应的车底称为非立折动车组车底，立折终到、始发列车对应的车底称为立折动车组车底(如图2中J3 与J4对应的动车组车底)，通过列车在枢纽站无接续列车，自身就对应一个动车组车底(如图2中J5对应的动车组车底)，因此，图2中共有3个动车组车底需要进行作业安排。由此可见，通过映射关系，两个计划编制对象由7个列车减少为3个动车组车底。

图2 高铁枢纽站技术作业计划与动车所调车作业计划协同编制方案图

1.3 非立折始发、终到列车出入所时刻确定

(1)

当冗余时间为正值时，非立折动车组车底出入所时刻就分别存在时间窗(如图2的点画线所示)为

(2)

(3)

综上可见，高铁枢纽站技术作业计划与动车所调车作业计划协同编制思路为：将高铁枢纽站与衔接的动车所作为一个系统，所有列车映射为对应的动车组车底，通过在时间窗内合理确定非立折动车组车底出入所时刻，使得所有动车组车底在枢纽站及动车所的技术作业(到达、停站、入所、各种检修整备、出所、发车等)所需股道设备能正确安排，同时满足各种设备能力、作业规则、时间标准的约束。

2 数学模型

高铁枢纽站与动车所作业计划协同编制的本质是：对高铁枢纽站与衔接动车所中，一昼夜内接发列车所对应的动车组车底所有技术作业所需的股道、进路设备及其占用起止时刻、出入所时刻进行决策。下面基于这些决策变量，给出满足各种约束的高铁枢纽站与动车所作业计划协同编制模型。

2.1 条件及变量假设

对于高铁枢纽站衔接的动车所：XZD为动车出入段线数；SD为作业场库数；GD为股道数；LD为转线调车进路数；动车所共有ND种动车组检修流程(日常存车、一级检修、二级检修等)，根据动车组运用计划，动车组车底i若是非立折动车组都将对应一种检修流程N(i)，每种检修流程有RN(i)个需安排股道的检修作业任务，每个作业任务都需在特定的场库完成；F′(i)、F″(i)分别为动车组车底i的接车方向和发车方向；G(i,j)为动车组车底i的第j个作业任务安排的股道，i∈J,j∈Wi。

2.2 模型建立

2.2.1 优化目标

列车运行图及动车运用计划确定了一昼夜内接发列车对应的动车组车底在高铁枢纽站及动车所的停留总时间及技术作业内容，但是枢纽站与动车所可能能力不足，不能完全安排技术作业。因此，本文提出的优化目标为，尽可能多的安排动车组车底在枢纽站及动车所需安排的技术作业(到达、停站、入所、各种检修整备、出所、发车等)，即所有动车组车底在枢纽站及动车所的技术作业安排效益值最大化。模型的优化目标为

(4)

式中:Z为效益值；xijk为0-1变量，动车组车底i的第j个作业任务安排在股道k上则为1，否则为0；cijk为动车组车底安排在股道上的效益；A为自定义的常数[2]。

2.2.2 约束条件

(1)动车组车底作业股道时空占用的唯一性约束，即枢纽站及动车所任何一条股道在任意时间内只允许被一个车底占用，而动车组车底作业只能占用一个股道，可表示为

(5)

(6)

(7)

式(5)表示车底的每个作业任务仅能安排一条股道；式(6)表示每个作业任务的股道实际停留时间应大于占用时间标准；式(7)表示所有车底作业任务占用股道的时间不允许重合。

(2)动车组的每项作业在时间安排上存在严格先后次序，不能早于动车组车底到达时刻、不能迟于动车组车底出发时刻，不能占用天窗时间，且每项作业的起止时刻必须满足其前项、后项作业时间的约束，可表示为

(8)

(9)

式(8)表示立折动车组车底的股道占用起止时刻等于车底到发时刻；式(9)的分式一表示非立折动车组车底第一项股道占用起止时刻分别等于车底到达时刻和入所时刻，且入所时刻不能占用天窗；式(9)的分式三表示最后一项股道占用起止时刻等于车底出所时刻和出发时刻，且出所时刻不能占用天窗；式(9)的分式二表示其余的股道占用起止时刻需满足前后项时刻约束，即是不能早于前一项股道占用终止时刻，不能晚于后一项股道占用始发时刻。

(3)非立折动车组车底出入所时刻须满足时间窗约束，即

Ri≠0

(10)

(11)

Ri≠0

(12)

式(10)表示非立折动车组车底的股道冗余时间；式(11)、式(12)分别表示动车组车底出入所时刻应在时间窗内。具体说明可见1.3节。

(4)动车组车底须满足进路时空占用的唯一性约束，即任一动车组车底在任意时间内只允许占用一条接发车进路，且任何一组敌对进路，在任意时间内只允许被一个车底占用，可表示为

(13)

(14)

式(13)表示动车组车底i接发车进路仅能安排在一条接发车进路上；式(14)表示动车组车底i与动车组车底i′的进路存在冲突时，其接发间隔应不小于间隔时间标准。

(5)动车组车底须满足转线时调车进路时空占用的唯一性约束，即任何一个动车组车底在任意时间内只允许占用一条调车进路，且任何一组敌对进路，在任意时间内只允许被一个车底占用，可表示为

(15)

(16)

式(15)表示动车组车底i的第j个作业任务安排调车进路时，仅能安排在一条调车进路上；式(16)的第一分式表示动车组车底的转线进路占用时间等于前后任务股道占用起止时间之差，第二分式表示动车组车底i与动车组车底i′的调车进路存在冲突时，其调车间隔应大于等于间隔时间标准，第三、四分式分别表示动车组车底i的调车进路与动车组车底i′的接、发车进路存在冲突，其进路安排应大于等于间隔时间标准。

此外，如果没有特别标注，则上述公式中的角标取值范围为

i,i′∈J,j∈(Wi+RN(i)),j′∈(Wi′+RN(i′)),

k,k′∈(GZ+GD)

(17)

3 算法设计

把动车组车底看作加工工件，高铁枢纽站及动车所的股道或进路看作加工设备，则高铁枢纽站与动车所作业计划协调编制是典型的多阶段Job-shop车间调度问题，该问题已经被证明是NP问题，其解空间随着动车组车底数量的增加、站场规模的扩大呈现“组合爆炸”[12-13]。本文提出了启发式分配规则与并行禁忌搜索算法(Parallel-TS，PTS)相结合的混合优化算法进行模型求解。其中，启发式分配规则来源于长期实际编图过程中的人工决策经验，可以快速生成较为可靠的初始解。并行禁忌搜索算法(PTS)在传统禁忌搜索算法(TS)中引入并行化策略，并运行在计算机分布式并行计算环境中，实现空间换时间有效提高搜索效率，已被广泛的运用于解决NP问题[14]。此外，本文在算法中引入瓶颈工序的确定，以进一步加快解的搜索。

3.1 瓶颈工序的确定[15]

瓶颈工序是指制约整个作业流程加工速度的环节，通常表现为设备能力不足或加工耗时过长造成的工件排序现象。观察到本问题中非立折动车组需安排的作业任务多且往往由于设备能力不足存在瓶颈制约现象(如动走线、洗车线、检修库的能力不足)，此时，动车组车底需要在存车线、临修线等处进行等待，因此，判断瓶颈工序并优先瓶颈工序的资源分配，可减少无效搜索。瓶颈工序是根据设备负荷率来确定的，具体为

(18)

式中：ηSj为场站设备Sj的负荷率；TSj为第j个作业任务所用的Sj类设备可用的最大时间。

式(18)是一个估算，表示动车组车底在每类设备上作业停留占用的时间比率，ηSj越大，则表示被占用时间越大，设备的负荷越大。

3.2 PTS算法设计及实现

借鉴贺一[14]的研究成果，本文采用粗粒度主从进程模式的PTS策略。计算机中的主进程负责生成一定规模的初始解，然后将每个初始解分发给一个从进程，每个从进程由此独立的执行一个TS算法，迭代足够的次数后，每个从进程将搜索当前最优解发给主进程，主进程比较并记录全局最优解，根据一定的交叉策略，生成新初始解，重新发送给从进程进行TS搜索，直到终止条件成立。

3.2.1 初始解排序规则设计

本文设计动车组车底在车站及动车所的作业安排规则，可快速生成初始解，并在此基础上构造初始解种群，包括：

(1)动车组车底安排次序规则：优先安排担当高等级列车的动车组车底作业，当等级相同时，按照先到先服务的原则安排，优先保证重点列车的安排。

(3)动车组车底到发线安排规则：优先按照固定使用方案安排到发线，当固定使用方案无空闲到发线选择，按照先到先排、均衡使用原则选择到发线安排。

(4)动车组车底调车股道安排规则：按照先到先排、均衡使用原则安排动车组每项检修作业所在的股道。

(5)动车组车底进路安排规则：按照出发进路优先到达进路、出场库调车进路优先入场库调车进路、最大平行进路优先的规则安排调车进路。

(6)动车组车底股道占用起止时刻安排规则：动车组车底到发线占用起止时刻由动车组车底担当列车的到发时刻以及出入所时刻来确定。动车组车底调车作业股道占用的起止时刻以出入所时刻为界，根据作业工序需求，遵循最小作业时间标准，作业时间连续规则来推定。

(7)动车组车底作业冲突解决规则：动车组车底每项作业将通过遍历股道、进路设备，寻找空闲的时段按照规则进行安排，但是如果找不到合适的空闲时段则出现作业冲突的现象，对作业冲突进行如下处理：

①到发线冲突：设置虚拟到发线GZ0，当车底的到发线找不到合适股道时，将直接安排在GZ0上，效益系数c为0。

②动走线冲突：改变出入所时间，来调整冲突，这时若引起到发线冲突，则回到①解决。

③调车股道冲突：若是在安排非存车工序如洗车、检修等出现冲突，则增加存车线工序进行等待，调整非存车工序的起止时间，进行工序安排，如果还是冲突，取消存车线工序直接安排到虚拟股道GD0上，效益系数c为0，继续安排下一工序。

以上步骤中虚拟股道的安排，虽然对实际问题而言不是有效的可行解，但是对于整个模型来说就能快速构造每个动车组车底的初始可行解，便于在此基础上的迭代优化，而且由于其效益系数c为0，所以不会影响模型的目标函数值。

3.2.2 PTS主进程初始解构造

按照3.2.1小节中的“动车组车底安排次序规则”对动车组车底J进行排序，随机调换同等级的车底顺序，得到Q个不同排序组合，依次从中取出排序好的动车组车底集合，按照3.2.1中(2)～(7)的规则，对每一个动车组车底顺序安排车底的各项作业，形成一个作业计划，得到一个初始解，见图3，将初始解随机分配给一个从进程。

3.2.3 PTS从进程TS算法实现

PTS从进程执行传统的TS算法，具体操作为：

(1)从主进程得到一个初始解Qi。

(2)基于Qi产生邻域解。本文提出工序所在的股道2-opt(两两交换)和时间调整两个操作，然后调用排序规则，生成新的作业安排计划，构成邻域解，具体操作如下：

图3 多个初始解构造过程

①股道设备占用调整：若某个工序存在未被安排的车底作业，则随机选择一个已经被安排的车底作业，选择一个除虚拟股道GZ0、GD0外的可选的权值尽可能大的可行股道替换其当前的股道，当有多个可替换股道时，选择被利用率最高的股道。

②到发线作业股道时刻占用调整：立折动车组车底的到发线作业起止时刻不能改变，非立折动车组车底的到发线起止作业时刻可以改变，这时随机选择一个非立折动车组车底，在时间窗范围内，改变出所或入所时刻，使其不会引起紧前和紧后工序作业的时间冲突，同时修正紧前和紧后工序的起止时刻。

③动车所内作业股道时间占用调整：随机选择一个非立折动车组车底，若其存在未被安排的车底作业，且该作业为非存车作业，则通过在时间窗范围内，整体前移或后移作业至时间移动量最小且权值尽可能大的空闲时间段内，同时修正紧前和紧后工序的起止时刻；若该作业为存车作业，则改变转线时刻或增加转线作业来解决时间冲突，同时修正紧前和紧后工序的起止时刻。

然后，遍历虚拟股道GZ0、GD0上的工序，按照3.2.1小节的(3)、(4)、(5)、(7)规则，尽量安排到可用股道上。整个调整按照到发线、瓶颈工序、次瓶颈工序的顺序进行，如果某个工序上所有动车组车底都安排好了，没有多余作业的冲突则无需进行调整。

(3)评价函数：以目标函数值进行对每个邻域解进行评价。

(4)禁忌表：将邻域解中生成的作业方案及其评价值进行禁忌，贮存在禁忌表内，本文根据频率信息动态控制禁忌的长度，采用动态禁忌长度。

(5)特赦条件：找不到领域解及迭代一定次数后，特赦禁忌表中最优值为当前解继续进行迭代搜索。

3.2.4 PTS主进程交叉操作及初始解再构造

整个算法流程见图4。

图4 算法流程图

4 算例验证

某高铁枢纽站及动车所站场设备布置见图5，有A、B两个接发车方向，各作业项目的最小时间标准见表1，选取该站某天的列车时刻表，包含到发列车140列，即有70个动车组车底，其中有 18个非立折动车组车底需进入动车所检修整备(15个进行一级检修作业，3个进行存车作业)，假设每个股道的效益值都一样，按照上述算法流程并用计算机编程计算。

根据动车组车底数及作业流程数，必须安排全部作业工序为166项：88项枢纽站到发作业、36项出入动车所作业、15项检修作业、15项洗车作业、15项库前吸污作业、最少18项的存车作业(可能由于作业排队，需要增加存车线上的等待作业)。按照表1的作业时间标准、动车所各车场设备数、非立折动车组数，代入式(16)计算非立折动车组主要工序负荷率为：存车线负荷率0.073、洗车线负荷率0.208、库前吸污线0.091、检修线0.417。可知瓶颈工序为检修线。由于到发线安排更为关键，因此，从进程TS算法优化调整时，将按照“到发线→动车走行线→检修线→洗车线→库前吸污线→存车线”的工序顺序进行作业调整安排。

图5 高铁枢纽站及动车所站场图

设计1个主进程和3个从进程运用PTS进行解搜索。为了方便，用未安排作业错误数进行优化目标统计。本文首先主进程生成不同安排次序的3个车底组合，然后根据排序规则分别生成3个初始解方案，这时3个方案的在虚拟股道上未安排作业错误数分别为52项、40项、50项，全局最优解是40项的作业方案。将3个方案分别分给3个从进程，然后按照3.2.3的TS算法不断调整优化作业方案，直到最大迭代次数。这时3个从进程的当前最优解分别为未安排作业错误数分别为17项、11项、13项，将当前全局最优解11项的作业方案传给主进程，主进程对3个从进程进行交叉操作后，产生新的初始方案，这时未安排作业错误数分别为19项、11项、12项，在此基础上3个从进程继续寻优。如此往复在主进程第4次分配后逐渐收敛，最终得到4项未安排作业错误数的作业方案，整个搜索过程见图6。由于这4项未安排作业都是存车作业，最后通过人工调整，增加转线作业，完成作业安排，高铁枢纽站技术作业计划与动车所调车作业计划最终协调方案见图7。

实例证明PTS算法比单纯的TS算法节省2/3以上的时间，且高铁枢纽站与动车所作业计划的一体化编制能生成保证协调性和可行性的精确方案，比实际现场中人工分开单独编制两个计划后再协调的工作重复性和复杂性显著降低。

表1 各项作业时间标准

图7 高铁枢纽站技术作业与动车所调车作业计划协同编制方案

图6 高铁枢纽站及动车所作业方案PTS搜索过程

5 结论

长期以来，高铁枢纽站技术作业计划与动车所调车作业计划编制都被孤立成单独的两个问题进行研究，使得两个计划在编制协同效率和能力优化利用上存在制约。本文分析了高铁枢纽站技术作业计划与动车所调车作业计划的协同编制过程，提出了以到发列车所对应的动车组车底为协同编制对象，动车组车底出入所时间为协同编制关键的高铁枢纽站与动车所作业计划协同编制模型，设计了瓶颈工序、启发式分配规则、并行禁忌搜索算法(PTS)相结合的混合优化算法，最后通过实例验证了相关理论的有效性。结果表明高铁枢纽站技术作业计划与动车所调车作业计划的一体化编制比分开编制在方案可行性和效率上更具优势。下一步可拓展到多个高铁枢纽站衔接一个动车所的情形，探求效率更高的计算方法。