基于时空网络的动车所调车与检修排程计划编制方法

Methods of Shunting and Maintenance Scheduling Plan at EMU Depots Based on Time-Space Network

摘要

在我国动车组数量不断增长、动车所调车和检修压力与日俱增的背景下，以动车所的调车与检修排程计划编制为研究对象，综合考虑进路冲突疏解和双列位因素、灵活存车策略，构建可适应不同布局形式的双层时空网络，并以总费用最小化为目标建立0-1整数线性规划的多商品流模型；设计启发式规则，分别采用优化求解器和动态规划2种方法求解该模型；依托某动车所设计不同规模的算例，对比2种方法的求解效果。结果表明：2种方法各有优劣，但均能在1 h内得出可行的调车和检修排程计划；时空弧的费用设置直接影响模型目标函数的优化方向，时变作业弧费用能够鼓励列车优先进行检修作业，调车固定惩罚费用可以降低调车作业和调头作业的次数，该算例中时变费用下的列车平均检修作业开始时间较恒定费用下的提前了16.5%，调车作业和调头作业的次数平均降低了11.6%和31.3%。

Abstract

With the continuous growth of EMUs in China, many high-speed railway depots are facing increasing pressures in terms of shunting and maintenance. Under this background, the shunting and maintenance scheduling plans at EMU depots are taken as the research objects, comprehensively considering the resolution of routing conflicts, the factors of double-position tracks and the strategy of flexible storage, thereby a double-layer time-space network that can adapt to different layout forms is established. Meanwhile, a multi-commodity flow model of 0-1 integer linear programming is constructed with the goal of minimizing the total operating cost. Heuristic rules are designed, and the optimization solver and dynamic programming are employed respectively to solve the model. Based on different scales of examples designed by a specific EMU depot, the solution results of these 2 methods are compared. Results indicate that both of them have their pros and cons, but can produce feasible shunting and maintenance scheduling plans within 1 hour. The cost settings for time-space arcs directly influence the optimization direction of the model's objective function. The cost of time-varying operational arcs can encourage the trains to give priority to maintenance tasks, and the fixed penalties for shunting can reduce the frequency of shunting and U-turn operations. In this example, the average start time of train maintenance under time-varying costs is 16.5% earlier than that under constant costs, and the frequency of shunting and U-turn operations are reduced by 11.6% and 31.3% on average.

Graphical abstract

关键词

动车所 / 调车作业计划 / 检修作业 / 时空网络 / 动态规划

Key words

EMU depot / Shunting operation plan / Maintenance operation / Time-space network / Dynamic programming

截至2024年底，我国高速铁路营业里程达4.8万km，全国铁路动车组已超过4 400标准组、35 000辆。随着高铁的进一步建设发展，动车组保有量还将持续快速增加，部分动车所检修能力瓶颈作用日益凸显。如何优化动车组的调车作业和检修流程调度的联合计划，提高动车所的检修能力是当前高铁运输组织中亟须解决的重要问题。

国内外学者围绕动车所调车计划编制开展了大量的研究。VAN Den BROEK等^［1-2］将该问题分解为列车单元（整列列车由1~3个列车单元编组而成）重组、股道运用、作业排程和进路排列4个子问题。HAAHR等^［3］针对列车单元配对和股道运用子问题进行了分析。KAMENGA^［4］基于股道电路构建了整数线性规划模型，通过求解器求解模型时，设计了顺序求解各子问题的启发式算法以加快求解速度。王忠凯等^［5］考虑了股道之间的联通关系，设计了最大最小蚁群算法进行求解。陈韬等^［6］将枢纽站与动车所作业计划进行联合编制，应用禁忌搜索算法进行求解。Wang等^［7］针对尽端横列式动车所，考虑了股道的双列位配置关系，构建整数规划模型并用Gurobi求解。户佐安等^［8］设计了基于调车作业可行路径生成和作业优先次序交换的模拟退火算法来求解动车所调车计划问题。史锦堂等^［9］以最小化关键线区总占用时间为首要目标，以最小化总存车次数为次要目标，以动车所内的所有待开展作业为主要索引构建了整数规划模型。He等^［10-11］以最小化关键线区总占用时间为目标，针对尽端式动车所设计了启发式粒子群算法求解；并在此基础上考虑不确定扰动下的调车计划优化，提出自适应迭代局部搜索算法进行求解。Xu等^［12］根据尽端式动车所的实际联通情况设置物理节点并离散化，构建双层时空网络，用于描述动车组的检修、清洗作业和移动过程，并设计了拉格朗日启发式算法进行求解。总结现有文献发现，在动车所调车计划优化问题上，优化目标一般为最小化作业线区占用时间^{［5，9-11］}、最小化调车作业路径费用^［5，7］、最小化存车次数（调车次数）^［8-9］等单一目标，或者以上优化目标的复合^{［1—2，4，12］}；问题输出为完整的调车计划，保证动车组在进出动车所的时间段内完成所有既定的检修任务，并在任何股道停留和转线时都不与其他动车组发生冲突。虽然国内外均对动车所调车问题进行了多方面的研究，但国外的大部分研究侧重于列车单元配对子问题，并且列车检修任务远没有国内的繁重；国内大部分研究针对特定布置的动车所进行分析，并对问题进行了较大幅度的简化，例如忽略了股道的双列位配置^{［10-11，14，17］}、忽略了进路冲突^［13-15］、忽略了列车调头^［16］的额外耗时和费用等。

针对既有研究的不足，本文考虑了股道列位关系和股道联通关系，基于离散型时空网络构建动车所调车作业和检修排程计划编制0-1整数线性规划模型。为了支撑动车所日常调车作业计划和检修流程调度计划的高效编制，设计2种基于启发式规则的求解方法，分别是求解器求解策略和适用于多种检修项目的动态规划算法。

1 问题描述

将动车所调车与检修排程计划编制问题看作是1类极其特殊的并行开放车间调度问题，并定义已知信息如下：①计划起讫时间；②动车所内，所有股道的功能、列位配置信息和联通关系等基础设施信息；③动车所内所有联通股道之间，进路占用道岔的资源信息和列车在股道上的平均移动时间；④所有动车组的编组信息、进出动车所时刻、检修任务、标准作业时长；⑤动车所内所有股道和道岔的安全间隔时间。需要注意的是，检修任务不局限于检修和清洗，检修任务顺序灵活，存车次数也不固定^［7，9］，在完成如检修等作业后，列车无须立即离开该作业股道，可以在标准作业时间之外超时停留；双列位股道可供一列16节/17节长编动车组、或最多同时供两列8节短编动车组停留。

对这一特殊的并行开放车间调度问题做出合理假设如下：①动车所内有足够的调车司机和检修作业人员；②检修作业一旦启动，就无法中断；③2个相邻的联通股道之间仅考虑1条主进路。

我国高铁动车所通常由存车场、清洗场、检修场以及车轮镟修场等车场组成，每个车场都有1条或多条股道用于动车组的调车相关作业。其中，存车股道供动车组停留；清洗股道提供动车组清洗服务，配备有自动清洁动车组外表面的洗车机；检修股道作为动车所的核心资源，配有用于车体检查和维修的设备；车轮镟修股道提供动车组轮对镟修服务，配备了用于车削动车组轮对的车床。存车股道和检修股道通常设有2个列位（双列位），双列位股道按列车的占用情况又可分为五种状态，分别是：空闲；仅占用列位1；仅占用列位2；双列位同时被不同的短编动车组占用；双列位被1列长编动车组占用。

图1为拓扑视角下我国高铁动车所的典型布局，考虑列车到达和离开动车所行为，在布局中设置了到达和离开节点。图中：S1—S6表示不同存车股道编号；R1—R2表示不同检修股道编号；C1和WT1表示清洗股道和车轮镟修股道编号，这两条股道未配置双列位，可视为普通股道节点；L1表示调车股道编号；io1和io2表示到达、离开节点编号；t1—t11表示除到达与离开之外的各作业节点编号，后缀数字表示双列位股道不同列位占用状态，“-1”“-2”分别表示列位1和列位2被占用，“-0”表示双列位同时被1列长编动车组占用。

为确保动车组顺利检修并避免股道/列位或道岔冲突，调车作业必须经过精心规划，尽量避免以下两种情况。一是当2个相邻的进路共享同1个道岔且未满足道岔的安全间隔时间时，可能发生进路冲突，此时需要疏解微观道岔区域的进路冲突。二是列车在移动过程中若要调转前进方向（简称“调头”），通常会比普通调车作业多耗时5~8 min，这不仅导致股道占用时间的延长，还需要额外考虑调头行为所需的司机作业时间和体力耗费^［1］；但检修线或存车线上调头只发生在作业或者存车之后，无须考虑额外的司机作业时间和体力耗费。

2 基于时空网络的优化模型构建

2.1　时空网络构建

时空网络建模技术是1种解决时空资源占用冲突的成熟方法，已被广泛应用于列车时刻表、乘务排班和机车车辆周转等优化问题中。该技术将物理网络进行时间维度的拓展并离散化，根据时空节点之间的关系构建不兼容约束关系和其他定制化约束。

为了便于建模，将列车在移动过程中调头的节点拆分成2个虚拟调头节点，在规定各节点上途经列车的移动方向后，通过虚拟调头节点之间的有向物理弧表示调头过程及调头前后的方向变化。例如可将节点“io1”拆分为“io1-in”和“io1-out”，物理弧“io1-out→io1-in”表示列车在节点“io1”进行调头，从“out”方向变为“in”方向。将具有联通关系的节点用单向或双向物理弧连接节点后，得到与图1动车所布局对应的短编和长编的动车组调车作业物理网络如图2所示。

将图2物理网络复制为2份，分别表示列车在调车、停留2种状态下占用的网络。对2个网络进行时间维度扩展，并根据人工经验、现在作业实际规章和安排、股道之间联通关系、动车组和股道之间的利用关系等，将2个网络中关联的时空节点通过有向联弧进行连接，得到双层时空网络，这是时间-空间-状态^［18］网络的一种特例。

图3展示了某长编动车组在动车所作业时的完整时空路径，图中各弧表示列车开展相应作业时在节点间的移动过程。由图3可知：动车组在计划到达时间先经过调车节点io1-in和t3-0，再通过作业弧到达停留层的检修节点t10并进行检修作业；结束后在检修节点进行额外停留后返回到调车层，移动到清洗作业节点进行清洗；清洗作业完成后需要进行镟修作业，因此司机需更换到另一端的驾驶室进行调头；镟修作业结束后，移动到存车节点进行存车，并按计划离开时刻离开动车所。

2.2　符号定义

根据动车所的设备资源、联通关系和作业时间等因素，以V为时空节点集（u,v为索引）、A为时空弧集合，构建动车所时空网络G=(V,A)，并定义模型所需的集合、索引、参数及变量。

E为动车组集合，e为索引；N为物理节点集合，n,m,i_{\mathrm{1}}\mathrm{和}{i}_{\mathrm{2}}为索引；p_n为节点n的作业类型；N_{\mathrm{1}}和N_{\mathrm{2}}分别为调车层和停留层节点集合，i_{\mathrm{1}}\in N_{\mathrm{1}}，i_{\mathrm{2}}\in N_{\mathrm{2}}，且有N=N_{\mathrm{1}}\bigcup N_{\mathrm{2}}，即时空节点的空间维度所有节点的集合；N^{\mathrm{i}\mathrm{n}}，N^{\mathrm{o}\mathrm{u}\mathrm{t}}，N^{\mathrm{p}\mathrm{o}\mathrm{s}}，N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}，N^{\mathrm{s}\mathrm{a}\mathrm{w}}和N^{\mathrm{s}\mathrm{t}\mathrm{o}}分别为到达节点集合、出发节点集合、列位节点集合、双列位股道节点集合、转线调头节点集合和存车节点集合；N_e为动车组e的节点集合，对于短编动车组e，N_e=N\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}；对于长编动车组e，N_e=N\backslash N^{\mathrm{p}\mathrm{o}\mathrm{s}}；P为作业类型集合，p为索引；P_e为动车组e的作业类型集合，P_e\subseteq P；B为关键道岔集合，即1个道岔区域内最多调车进路（物理弧）共同经过的道岔，b为索引；B_{(i,j)}表示物理弧（i,j）包含的关键道岔集合；T为计划时间范围内的离散时间集合T=\left\{\mathrm{0,1},\dots ,\left|T\right|\right\}，即时空节点时间维度所有节点的集合，t为索引，时间粒度可以根据需要设置，根据动车段所计划安排的时间要求，可将时间粒度设置为1 min。时空网络中的所有时空节点集合可以表示为V=\left\{\overline{o},\overline{d}\right\}\bigcup\left\{\left(i_w,t\right)|i_w\in N,w=\mathrm{1,2},t=\mathrm{0,1},\dots ,\left|T\right|\right\}；又因u，v为时空节点集V的索引，a或弧（n，t）\to \left(m,\tau \right)（以符号“\to”表示节点与节点之间的前后连接关系）为时空节点\left(n,t\right)到时空节点\left(m,\tau \right)的时空弧，可将\left(n,t\right)\to \left(m,\tau \right)简写为u\to v。

由于动车组的编组长度、到发时刻和作业内容的差异，单个动车组的时空网络是动车所时空网络的一部分，因此定义集合A_e为动车组e的时空网络中的弧集合。为避免超出股道使用能力或发生进路冲突，对节点和道岔设置不兼容的时空弧集，限制时空节点的占用。A_{nt}^{\mathrm{1}}为当存在n\in N_{\mathrm{2}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}时节点（n，t）的不兼容弧集；A_{nt}^{\mathrm{2}}为当存在n\inN_{\mathrm{1}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}时节点（n,t）的不兼容弧集；A_{bt}为关键道岔b在时刻t的不兼容弧集合，b\in B。

t_{\mathrm{a},e}和t_{\mathrm{d},e}分别为动车组e的到达时刻和出发时刻；t_{ij}为列车行驶经过物理弧i\to j所需的时间；{\tau }_n^{\mathrm{h}}，{\tau }_b^{\mathrm{h}}分别为2列列车先后通过同一节点n\in N、同一关键道岔b\in B的安全间隔时间；t_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}为动车组e的作业类型为p时的标准作业时间；c_{ea}为动车组e使用时空弧a的费用（为了简化模型的求解过程，对所有费用进行标准化处理，以便时间成本和资源成本等不同维度的费用能够在同一尺度下进行比较，因此费用项无具体物理单位）；x_{u,v}^e为布尔变量，时空弧u\to v被动车组e使用时取值为1，否则取值为0。

2.3　时空弧描述

在动车组e的双层时空网络中，各种弧的描述如下。

（1）起始弧。对于任何i_{\mathrm{1}}\in N^{\mathrm{i}\mathrm{n}}\bigcap N_e，动车组通过1个或多个起始弧a=\overline{o}\to \left(i_{\mathrm{1}},t_{\mathrm{a},e}\right)进入网络（其中\overline{o}为虚拟源点），对应的费用c_{ea}为0。

（2）结束弧。对于任何i_{\mathrm{1}}\in N^{\mathrm{o}\mathrm{u}\mathrm{t}}\bigcap N_e，动车组通过1个或多个结束弧a=\left(i_{\mathrm{1}},t_{\mathrm{d},e}\right)\to \overline{d}离开网络（其中\overline{d}为虚拟汇点），此时对应的费用c_{ea}仍为0。

（3）调车弧。列车经过1条调车弧意味着列车通过调车作业经过1条对应的实际物理弧，例如t10-0₁→t8-out₁。对于任何i_{\mathrm{1}},j_{\mathrm{1}}\in N_{\mathrm{1}}\bigcap N_e，存在连接节点i_{\mathrm{1}}和节点j_{\mathrm{1}}的调车弧

a=\left(i_{\mathrm{1}},t\right)\to \left(j_{\mathrm{1}},t+t_{ij}\right)t_{\mathrm{a},e}\le t\le t_{\mathrm{d},e}-t_{ij}（1）

此时对应的费用为

c_{ea}=c_{ea}^{\mathrm{s}\mathrm{h}\mathrm{u}}{t}_{ij}（2）

式中：c_{ea}^{\mathrm{s}\mathrm{h}\mathrm{u}}为单位时间内动车组e使用调车弧a的费用。

特别地，若i_{\mathrm{1}}和j_{\mathrm{1}}是同1个物理节点的调头节点，那么弧（i_{\mathrm{1}},t）\to（j_{\mathrm{1}},t+t_{ij}）就是调头弧，t_{ij}等于司机从一端驾驶室走到另一端驾驶室的时间，此时费用c_{ea}等于单次调车操作的固定惩罚费用c^{\mathrm{f}\mathrm{i}\mathrm{x}}。

（4）作业弧。动车组经过作业弧意味着完成作业。对于任何i_{\mathrm{1}}\in N_{\mathrm{1}}\bigcap N_e\backslash N^{\mathrm{s}\mathrm{t}\mathrm{o}}，i_{\mathrm{2}}\in N_{\mathrm{2}}\bigcap N_e\backslash N^{\mathrm{s}\mathrm{t}\mathrm{o}}，存在连接节点i_{\mathrm{1}}和节点i_{\mathrm{2}}的作业弧

a=\left(i_{\mathrm{1}},t\right)\to \left(i_{\mathrm{2}},t+t_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}\right)t_{\mathrm{a},e}\le t\le t_{\mathrm{d},e}-t_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}（3）

1个调车操作可能包含多个调车弧，而固定惩罚费用不能划分并添加到单个调车弧的费用中，因此将作业前调车作业的固定惩罚费用计算到作业弧的费用中，此时对应的费用为

c_{ea}=c_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}{t}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}+c^{\mathrm{f}\mathrm{i}\mathrm{x}}（4）

式中：c_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}为单位时间内动车组e进行作业p的作业费用。

（5）存车弧。动车组经过存车弧意味着进入存车股道并开始存车。对于任何i_{\mathrm{1}}\in N_{\mathrm{1}}\bigcap N_e\bigcap N^{\mathrm{s}\mathrm{t}\mathrm{o}}，i_{\mathrm{2}}\in N_{\mathrm{2}}\bigcap N_e\bigcap N^{\mathrm{s}\mathrm{t}\mathrm{o}}，存在连接节点i_{\mathrm{1}}和节点i_{\mathrm{2}}的存车弧

（5）

此时对应的费用为

c_{ea}=c^{\mathrm{f}\mathrm{i}\mathrm{x}}（6）

（6）停留弧。对于任何i_{\mathrm{2}}\in N_{\mathrm{2}}\bigcap N_e且允许停留，都有停留弧

a=(i_{\mathrm{2}},t)\to (i_{\mathrm{2}},t+\mathrm{1})（7）

式（7）中，如果i_{\mathrm{2}}\notin N^{\mathrm{s}\mathrm{t}\mathrm{o}}，即动车组完成作业股道上的作业后将继续停在当前位置，那么此时对应的费用为

c_{ea}=c_{e,p}^{\mathrm{d}\mathrm{w}\mathrm{e}}p=p_{i_{\mathrm{2}}}（8）

式中：c_{e,p}^{\mathrm{d}\mathrm{w}\mathrm{e}}为单位时间内动车组e在作业p的股道上的停留费用。

如果i_{\mathrm{2}}\in N^{\mathrm{s}\mathrm{t}\mathrm{o}}，即动车组停在存车股道上，因清洗节点和车轮镟修节点均不允许额外停留，此时相关停留弧不存在，对应的费用为

c_{ea}=c_e^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{o}}（9）

式中：c_e^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{o}}为单位时间内动车组e的存车费用。

（7）状态转移弧。动车组经过状态转移弧意味着结束停靠并开始调车。对于任何i_{\mathrm{1}}\in N_{\mathrm{2}}\bigcap N_e，i_{\mathrm{2}}\in N_{\mathrm{1}}\bigcap N_e，存在连接节点i_{\mathrm{1}}和节点i_{\mathrm{2}}的状态转移弧

（10）

此时对应的费用c_{ea}为0。

（8）虚拟弧。动车组经过虚拟弧意味着由于动车所的能力限制，该动车组的作业任务无法执行。对于任何i_{\mathrm{1}}\in N^{\mathrm{i}\mathrm{n}}\bigcap N_e,j_{\mathrm{1}}\in N^{\mathrm{o}\mathrm{u}\mathrm{t}}\bigcap N_e，存在连接节点i_{\mathrm{1}}和节点j_{\mathrm{1}}的虚拟弧

a=\left(i_{\mathrm{1}},t_{a,e}\right)\to \left(j_{\mathrm{1}},t_{d,e}\right)（11）

由于取消1个动车组的作业的费用很高，所以此时令费用为

c_{ea}=c_e^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{o}}\left(t_{\mathrm{d},e}-t_{\mathrm{a},e}\right)+\sum _{p\in P_e}\left(c_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}{t}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}+c^{\mathrm{f}\mathrm{i}\mathrm{x}}\right)（12）

2.4　数据预处理

先定义属于集合N的节点的不兼容节点集，再定义时空节点和道岔的不兼容时空弧集。通过以上数据预处理，便可在建模之前枚举所有不兼容的时空弧集。

2.4.1　不兼容的节点集

为了在同一股道的列位节点和双列位股道节点之间建立映射关系，设w∈\left\{\mathrm{1,2}\right\}，定义{\Psi }_{{\mathrm{i}}_{\mathrm{w}}}为节点i_w的不兼容节点集合，以图2为例，节点i及对应的不兼容节点集合有如下4种情况。

（1）节点i是列位节点，不兼容节点集包含节点i_w以及同一股道i_w的双列位股道节点，但不包括同一股道的另一个列位节点。以编号为t3-1₁的节点为例，{\Psi }_{\mathrm{t}\mathrm{3}-{\mathrm{1}}_{\mathrm{1}}}包含t3-1₁，t3-1₂，t3-2₁和t3-2₂。

（2）节点i是双列位股道节点，不兼容节点集包含节点i_w以及同一股道的2个列位节点。以编号为t3-0₁的节点为例，{\Psi }_{\mathrm{t}\mathrm{3}-{\mathrm{0}}_{\mathrm{1}}}包含t3-1₁，t3-1₂，t3-2₁，t3-2₂，t3-0₁和t3-0₂。

（3）节点i是普通股道节点且不允许调头，不兼容节点集包含节点i_{\mathrm{1}}和节点i_{\mathrm{2}}。以编号为\mathrm{t}{\mathrm{11}}_{\mathrm{1}}的节点为例，{\Psi }_{\mathrm{t}{\mathrm{11}}_{\mathrm{1}}}包含\mathrm{t}{\mathrm{11}}_{\mathrm{1}}和\mathrm{t}{\mathrm{11}}_{\mathrm{2}}。

（4）节点i是普通股道节点且允许调头，不兼容节点集包含节点i_{\mathrm{2}}（若物理节点i具有停留状态）和物理节点i的所有虚拟调头节点。以编号为t7-in₁的节点为例，{\Psi }_{\mathrm{t}\mathrm{7}-\mathrm{i}{\mathrm{n}}_{\mathrm{1}}}包含t7-in₁，t7-out₁，t7-in₂和t7-out₂；以编号为t8-in₁的节点为例，\Psi \mathrm{t}\mathrm{8}-\mathrm{i}{\mathrm{n}}_{\mathrm{1}}包含t8-in₁和t8-out₁。

2.4.2　时空节点的不兼容弧集

1）停留层节点i_{\mathrm{2}}\in N_{\mathrm{2}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}的安全间隔约束

由于{\Psi }_{i_{\mathrm{2}}:i_{\mathrm{2}}\in N_{\mathrm{2}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}}包含双列位股道节点，因此不需要对双列位股道节点i_{\mathrm{2}}\in N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}的不兼容弧集进行重复定义和计算，这里只考虑i_{\mathrm{2}}\in N_{\mathrm{2}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}。将停留层节点i_{\mathrm{2}}分为存车节点i_{\mathrm{2}}\in N_{\mathrm{2}}\bigcap N^{\mathrm{s}\mathrm{t}\mathrm{o}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}和非存车节点i_{\mathrm{2}}\in (N_{\mathrm{2}}\backslash N^{\mathrm{s}\mathrm{t}\mathrm{o}})\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}，在时刻t，时空节点（i_{\mathrm{2}},t）的不兼容弧集包含停留弧、作业弧、调车弧3种类型的弧。考虑列位节点与双列位股道节点之间的安全间隔和映射关系，建立时空节点的不兼容弧集时，所有通过不兼容弧集的总动车组数量不应超过1，以避免时空资源占用冲突。

对于停留层非存车节点，不兼容弧集A_{i_{\mathrm{2}}t}^{\mathrm{1}}定义为

（13）

对于停留层存车节点，不兼容弧集A_{i_{\mathrm{2}}t}^{\mathrm{1}}定义为

\begin{array}{l}{A}_{i_{\mathrm{2}}t}^{\mathrm{1}}=\left\{\left(j_{\mathrm{2}},t\right)\to \left(j_{\mathrm{2}},t+\mathrm{1}\right)|j_{\mathrm{2}}\in {\Psi }_{i_{\mathrm{2}}}\right\}\bigcup \left\{\left(j_{\mathrm{1}},t+\right.\right.\\ \left.{\mathrm{1}}_{}^{}\right)\left.\to \left(j_{\mathrm{2}},t+\mathrm{1}\right)|j_{\mathrm{1}},j_{\mathrm{2}}\in {\Psi }_{i_{\mathrm{2}}}\right\}\bigcup \left\{\left(j_{\mathrm{1}},t\right)\to \left(q_{\mathrm{1}},t+t_{jq}\right),\left(q_{\mathrm{1}},t+{\tau }_{i_{\mathrm{2}}}^{\mathrm{h}}+\mathrm{1}-t_{qj}\right)\to \left(j_{\mathrm{1}},t+{\tau }_{i_{\mathrm{2}}}^{\mathrm{h}}+\mathrm{1}\right)|j_{\mathrm{1}}\in {\Psi }_{i_{\mathrm{2}}},q_{\mathrm{1}}\in N_{\mathrm{1}}\right\}\\ \forall i_{\mathrm{2}}\in \left(N_{\mathrm{2}}\bigcap N^{\mathrm{s}\mathrm{t}\mathrm{o}}\right)\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}},\\ t=\mathrm{0,1},\dots ,T-{\tau }_{i_{\mathrm{2}}}^{\mathrm{h}}+\mathrm{1}\end{array}（14）

2）调车层节点i_{\mathrm{1}}\in N_{\mathrm{1}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}}的安全间隔约束

同理，对于调车层节点(i_{\mathrm{1}},t)的不兼容弧集A_{i_{\mathrm{1}}t}^{\mathrm{2}}，所有通过该集的总动车组数量不应超过1，以避免时空资源占用冲突。不兼容弧集A_{i_{\mathrm{1}}t}^{\mathrm{2}}定义为

（15）

2.4.3　关键道岔的不兼容弧集

以“共同道岔”表示多个调车进路（物理弧）共同经过的道岔，则判断1个道岔是否为关键道岔的条件如下。选定道岔b₁，筛选出包含道岔b₁的所有物理弧，对于这些物理弧上所有道岔构成的道岔集合来说，①如果集合中没有其他共同道岔，则道岔b₁为关键道岔，可被视为这些物理弧上所有道岔的代表；②如果存在另1个共同道岔b₂，且包含道岔b₂的物理弧数量大于包含道岔b₁的，则道岔b₁不为关键道岔。

对于每个关键道岔b\in B，则该道岔的不相容弧集A_{b,t}为

（16）

为了限制瓶颈处的占用，对于每个b\in B，所有通过不兼容弧集A_{b,t}的总动车组数量应不超过1。需注意文中允许平行进路，如图1中2条绿色的进路虽然同时占用交分道岔，但交分道岔被视为若干个普通道岔，2条进路不共享相同的轨道电路，可以被同时执行，即这2条进路为平行进路。

2.5　多商品网络流模型

构建双层时空网络并经过数据预处理得到不兼容弧集合后，可将原问题转化为具有不相容约束的最小费用多商品网络流问题。为简便建模，令T^{\text{'}}=\left|T\right|-t_h+\mathrm{1}，构建基于时空网络的动车所调车与检修排程计划编制优化多商品网络流模型见式（17）—式（25）。

Z=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{e\in E}\sum _{u\to v\in A_e}{c}_{u\to v}^e{x}_{u\to v}^e（17）

s.t.

\sum _{v:\overline{o}\to v\in A}{x}_{\overline{o},v}^e=\mathrm{1}\forall e\in E（18）

\sum _{u:u\to \overline{d}\in A}{x}_{u,\overline{d}}^e=\mathrm{1}\forall e\in E（19）

\begin{array}{l}\sum _{u:u\to v\in A}{x}_{u,v}^e-\sum _{w:v\to w\in A}{x}_{v,w}^e=\mathrm{0}\forall v\in V\backslash \left\{\overline{o},\overline{d}\right\},\\ \forall e\in E\end{array}（20）

\sum _{u\to v\in A_e\bigcap A_p^{\mathrm{o}\mathrm{p}\mathrm{e}}}{x}_{u,v}^e=\mathrm{1}\forall e\in E,\forall p\in P（21）

\begin{array}{l}\sum _{e\in E}\sum _{u\to v\in A_e\bigcap A_{nt}^{\mathrm{1}}}{x}_{u,v}^e\le \mathrm{1}\forall n\in N_{{}^{\mathrm{2}}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}},\\ t=\mathrm{0,1},\dots ,T^{\text{'}}\end{array}（22）

\begin{array}{l}\sum _{e\in E}\sum _{u\to v\in A_e\bigcap A_{nt}^{\mathrm{2}}}{x}_{u,v}^e\le \mathrm{1}\forall n\in N_{{}^{\mathrm{1}}}\backslash N^{\mathrm{i}\mathrm{n}\mathrm{t}-\mathrm{t}\mathrm{r}\mathrm{a}},\\ t=\mathrm{0,1},\dots ,T^{\text{'}}\end{array}（23）

\sum _{e\in E}\sum _{u\to v\in A_e\bigcap A_{bt}}{x}_{u,v}^e\le \mathrm{1}\forall b\in B,t=\mathrm{0,1},\dots ,T^{\text{'}}（24）

x_{u,v}^e\in \left\{\mathrm{0,1}\right\}\forall u\to v\in A,e\in E（25）

目标函数式（17）为最小化总运营费用，包括作业弧的作业费用、作业股道和存车股道的停留费用，调车弧的调车费用，调车作业的固定惩罚费用和取消动车组的惩罚费用。约束式（18）—式（20）为流量守恒约束；约束式（21）为动车组作业次数约束，表示每种作业只需要进行1次；约束式（22）—式（24）为不兼容弧使用限制约束，保证每种时空资源最多同时只能被一列列车占用，以避免长、短编动车组在同一股道、同一时间段的冲突以及动车组在调车路径上的相互阻挡。

多商品网络流模型虽能将复杂的约束融合到网络的构建过程中，但一旦将双层时空网络合并为一层时空网络，将导致时空弧的接续混乱，以及调车固定惩罚费用的计算困难。此时，可将服务弧和存车弧看作沟通2层网络的桥梁，动车组在经过停留弧之前必须经过调车弧→服务弧/存车弧到达停留层，这能够保证动车组的移动顺序；可将调车次数看作从调车层移到停留层的次数，每次调车的固定惩罚费用加入服务弧/存车弧的费用，便能够精准“惩罚”调车次数。

3 求解方法

构建的多商品网络流模型属于0-1整数线性规划模型，可使用如Gurobi和Cplex等商用求解器求解，但时空网络模型具有复杂决策变量及约束的数量都十分庞大的缺点，会导致求解困难。经过求解器测试，规模比较小的算例也无法在可接受的时间内得到可行解。考虑到Gurobi和Cplex等求解器的求解过程是针对广泛的整数规划问题设计的，并不专门为某一类问题（如时空网络模型）进行深度优化，因此使用求解器求解时需要针对具体问题设计求解策略以减小求解难度。考虑到动态规划方法是求解时空网络模型的一种经典方法，能够克服商用求解器在求解完整时空网络模型时的效率瓶颈及潜在版权问题，采用2种求解方法进行对比求解，提供多样化方法选择空间。采用求解器求解时，通过股道预分配策略来减少决策变量和约束的复杂性，以及利用动车组分组求解策略问题分解等启发式技术，使模型能够在合理的时间内获得可行解；采用动态规划方法时，通过改进标号法使其更好地适用于多种检修项目，并通过变换列车顺序等技术，对逐个列车求得可行解。

3.1　求解器求解

为加速求解器对问题的计算，设计如下求解策略。

3.1.1　股道预分配策略

动车所一般拥有较多的存车股道，大量同质化股道导致每列动车组的求解空间较大，从而影响求解速度。在股道预分配策略中，每列动车组都被随机分配或手动分配1组候选股道，例如2条存车股道和2条检修股道，动车组仅限于停放在选定的股道子集上。文献［3—4］也使用了类似的方法，称之为“列车和轨道分解”。

在股道预分配策略的应用下，若出现无解情况，则将当前的求解列车的股道备选集替换为所有可供使用的股道资源。这一“补救措施”有助于修复股道预分配策略缩小可行解空间的缺陷。

3.1.2　动车组分组求解策略

即使在采用股道预分配策略下，通过求解器同时为所有动车组求解可行的计划是非常耗时的，因此提出动车组顺序分组求解策略。定义{\lambda }_e为定量计算得到的动车组优先级，即

{\lambda }_e=w_{\mathrm{1}}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}+w_{\mathrm{2}}Q+w_{\mathrm{3}}\frac{\sum _{p\in P_e}{c}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}{t}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}}{t_{\mathrm{d},e}-t_{\mathrm{a},e}}（26）

式中：w_{\mathrm{1}},w_{\mathrm{2}}\mathrm{和}{w}_{\mathrm{3}}分别为计算权重；V_{\mathrm{m}\mathrm{a}\mathrm{x}}为列车最高运行速度，km · h^－1；Q为列车编组数量，按实际通常取8，16或17节；\frac{\sum _{p\in P_e}{c}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}{t}_{e,p}^{\mathrm{s}\mathrm{e}\mathrm{r}}}{t_{\mathrm{d},e}-t_{\mathrm{a},e}}为列车检修任务总时长占在动车所停留时间的比例，表示该列车检修任务的繁重程度。

先根据{\lambda }_e值的高低确定动车组优先级的高低并进行分组，每组列车的数量为平均分配后向上取整的整数；再按照顺序，依次对每组动车组进行求解。当1组动车组求解完毕后，根据决策变量x_{u,v}^e的取值，遍历这组动车组占用的时空弧u\to v，对于不兼容弧集A_{i_{\mathrm{2}}t}^{\mathrm{1}}，A_{i_{\mathrm{1}}t}^{\mathrm{2}}和A_{b,t}包含联弧u\to v的时空资源（i_{\mathrm{2}},t），（i_{\mathrm{1}},t）和（b,t），标记为后序列车组不可用状态，以避免后序列车组与当前列车组发生冲突。对后序列车组进行求解时，分别将不可用时空资源对应的约束式（22）—式（24）的运算符和右边项（即约束式中的“\le \mathrm{1}”）改为“=0”，以表示时空资源不可用。当求解完所有组的列车后，判断所有动车组的排程计划是否可行，若是，则输出当前解；若否，则重新生成动车组顺序，进行新一轮的求解。新的动车组优先级计算式是在式（26）基础上增加1项w_{\mathrm{4}}{\phi }_e，用来表现上一轮求解中动车组的求解情况（其中{\phi }_e为0-1变量，表示该列车在上一轮求解中是否得到了可行计划，取值为0表示得到可行计划，取值为1表示没有可行计划）。完整的求解流程如图4所示。

3.2　动态规划方法求解

对于多商品流模型，每个动车组可以被看成“商品”，调车计划可以被看成是动车组在时空网络中的时空路径。若暂时不考虑不兼容弧使用限制约束式（22）—式（24），则剩余的约束都是针对单个动车组的。因此可将剩余的约束视为一个针对单个动车组进行调车计划求解的模型，模型的最优解即可视为单个动车组的时空最短路。

最短路问题一般使用经典的标号法进行求解^［19-20］，标号法是1种动态规划方法，但动车组作业次数约束即式（21）的存在使得一般的标号法无法适用。因此使用带有多标签的标号法^［16］进行求解。

对于每列动车组，每个时刻t作为动态规划的1个阶段，每个时空节点（n,t）可以具有多个标签，每个标签\mathit{L}（n,t）中存储了每个作业任务的完成次数向量{\mathit{K}}^{\mathrm{o}\mathrm{p}\mathrm{e}}（n,t）以及累积费用c（n，t），即

\begin{array}{l}{\mathit{K}}^{\mathrm{o}\mathrm{p}\mathrm{e}}\left(n,t\right)=\left({\pi }_{\mathrm{1}},{\pi }_{\mathrm{2}},\dots ,{\pi }_{\left|P_e\right|}\right){\pi }_{\mathrm{1}},{\pi }_{\mathrm{2}},\dots ,{\pi }_{\left|P_e\right|}\in \\ \left\{\mathrm{0,1},\mathrm{2}\right\}\end{array}（27）

特别地，{\mathit{L}}^{\mathrm{n}\mathrm{e}\mathrm{w}}\left(n,t\right)=\left({\mathit{K}}^{ope},c^{new}\right)为新的候选标签，{\mathit{L}}^{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}=\left({\mathit{K}}^{ope},c^{current}\right)为现有的标签。

首先，设初始值{\mathit{K}}^{\mathrm{o}\mathrm{p}\mathrm{e}}\left(n,t\right)=\left(\mathrm{0,0},\dots ,\mathrm{0}\right)，如果动车组经过了属于其作业任务p的作业弧，将相应的{\pi }_{{}^p}的值增加1，表示进行了1次作业p；当{\pi }_{{}^p}=\mathrm{2}时，表示进行了2次作业p，超出作业次数限制，标签将被剔除，不会进一步探索；当某时空节点出现1个新的候选标签{\mathit{L}}^{\mathrm{n}\mathrm{e}\mathrm{w}}\left(n,t\right)=\left({\mathit{K}}^{ope},c^{new}\right)时，查找该时空节点标签中具有相同{\mathit{K}}^{\mathrm{o}\mathrm{p}\mathrm{e}}\left(n,t\right)的标签{\mathit{L}}^{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}=\left({\mathit{K}}^{ope},c^{current}\right)；如果c^{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}\left(n,t\right)>c^{\mathrm{n}\mathrm{e}\mathrm{w}}(n,t)，则令{\mathit{L}}^{\mathrm{n}\mathrm{e}\mathrm{w}}取代{\mathit{L}}^{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}；如果不存在这样的{\mathit{L}}^{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}，则让{\mathit{L}}^{\mathrm{n}\mathrm{e}\mathrm{w}}成为该时空节点的1个当前标签；对于虚拟汇点\overline{d}的每个标签，满足动车组作业次数约束即式（21）的标签为最终标签；通过回溯最终标签，可以获得最短路径。

当每个动车组搜索完时空最短路后，为了约束后序列车不占用前序列车已经占用的时空资源，需要遍历当前动车组占用的时空弧u\to v，对于不兼容弧集A_{i_{\mathrm{2}}t}^{\mathrm{1}}，A_{i_{\mathrm{1}}t}^{\mathrm{2}}和A_{b,t}包含联弧u\to v的时空资源（i_{\mathrm{2}},t），（i_{\mathrm{1}},t）和（b,t），不兼容弧集A_{i_{\mathrm{2}}t}^{\mathrm{1}}，A_{i_{\mathrm{1}}t}^{\mathrm{2}}和A_{b,t}中的所有联弧均标记为后序列车组不可用状态，以满足之前暂时不考虑的不兼容弧使用限制约束式（22）—式（24），避免后序列车与当前列车发生冲突。当所有动车组按照既定的顺序求解完最短路后，更新最优计划。然后打乱动车组的顺序，再次对所有动车组求解时空最短路，直到达到设定的最大求解时间后，输出最优计划并结束。

完整的动态规划方法求解流程如图5所示。

4 算例及分析

4.1　算例信息

某动车所平面布置图如图6所示。该动车所拥有存车线24条、清洗线2条、轮对镟修线3条和检修线6条。所有的存车线和检修线都设置有双列位。算例的计划期为夜晚20：00到第二天早晨10：00，以分钟为时间粒度，可将这一时间段划分为840个时间单元。为便于计算，计划期设置为整数格式，即0~840，动车组的作业时刻也相应转化为整数格式。

根据长、短编动车组数量及检修作业量的不同设置6个算例，分别编号为L-1—L-6，不同规模的算例信息见表1。根据该动车所作业实际，长、短编组动车组的检修作业时间标准分别为150和80 min，清洗作业时间标准分别为20和15 min，镟修作业时间标准为180和120 min。长、短编组列车停留在作业股道的每分钟费用分别为6和3，停留在存车股道的每分钟费用分别为4和2。调车作业固定惩罚费用为200，调车每分钟可变作业费用为10。1次调头按2次调车作业计算。长、短编组列车调头的额外耗时分别是8和5 min。股道和道岔的安全间隔时间为2 min。

4.2　求解结果

分别采用商用求解器和动态规划方法对算例进行求解，求解环境为Intel i9-13900HX处理器和40 G运行内存的笔记本电脑，编程环境为C#。为了便于比较，每个算例最大求解时间统一设为1 h。最大求解时间可以根据案例规模来适当调整测试以满足实际生产需要。通过求解器求解时，假设为每列动车组预分配2条检修线；动车组优先级计算权重w₁，w₂，w₃和w₄分别取0.01，0.5，10和5；按照优先级变量{\lambda }_e的值进行先后排序，每2列动车组视为1组。每组动车组的最长求解时间设为180 s。Cplex和Gurobi求解器以及动态规划方法得到的求解结果见表2。

由表3可以发现：所提出的双层时空网络模型能够准确地反映动车所调车与检修排程的复杂性。该模型充分考虑了调车与检修过程中的各类时间和空间约束，为制定高效、合理的排程方案提供了坚实的数学基础。基于双层时空网络模型的2种求解方法各有优劣，从最优目标值角度无法得出某1种方法更优的结论，但只看重调车次数的话，Cplex求解结果的调车次数和调头次数最少；动态规划方法的缺点是每次只能为1列动车组求解（搜索时空最短路），总目标值是所有列车的最优目标值相加得到，会导致后序列车产生额外的调车作业；在列车数量相同的情况下，长、短编列车的数量会影响目标值和占用检修线的总时间，这是由于单位时间占用股道的费用更高，且长编列车检修耗时更长；在求解效率方面，列车数量较少时，求解器的求解速度更快，但列车数量较多时，动态规划方法更快。

以Cplex求解L-6算例为例，将求解得到的最终结果整理成甘特图，如图7所示。图中：不同颜色表示不同的动车组；矩形中的数字表示动车组索引；粗矩形表示占用普通股道或长编动车组占用双列位股道；细矩形表示短编动车组占用列位；带有数字的短矩形表示列车调头；占用股道上半、下半部分分别表示占用列位1和占用列位2。由图7可以看出：得益于双层时空网络的设计，模型输出的可行计划包括每列动车组的停留和移动过程，以及进出所进路、占用股道过程、调车进路以及调头过程的具体情况，计划期内在T1，T2，T3和T4处共进行调头16次，而这些都以甘特图的形式直观展示出来。

4.3　灵敏度分析

时空弧的费用设置直接影响着目标函数的优化方向，并影响最终输出的作业计划。调车作业计划有2个重要评价指标，一是平均检修作业开始时刻，二是调车作业次数。因此进行针对性的敏感性分析，从时变作业弧费用和调车固定惩罚费用2方面，探究不同时空弧费用设置方式对计算结果的影响。

1）时变作业弧费用

对于作业弧，决策者可在计划期的不同阶段设置不同的费用，通过时变费用鼓励列车尽早开始作业，例如设置计划期前1/3时为恒定费用的1/2，后1/3时为恒定费用的2倍。在其他参数不变的情况下，对比前述“时变费用”和“恒定费用”下的列车平均检修作业开始时刻，如图8所示。由图8可以看出时变费用下列车的平均检修作业开始时刻较恒定费用下的开始时刻提前了16.5%，达到了鼓励列车优先开展检修作业的目的。

2）调车固定惩罚费用c^{\mathrm{f}\mathrm{i}\mathrm{x}}

调车作业的繁重程度决定着调车司机的工作强度，而调整调车固定惩罚费用c^{\mathrm{f}\mathrm{i}\mathrm{x}}可以优化调车次数和调头次数。令c^{\mathrm{f}\mathrm{i}\mathrm{x}}分别取100，200和400，用动态规划方法进行求解，设置最长求解时间为1 h。不同c^{\mathrm{f}\mathrm{i}\mathrm{x}}取值下的调车次数和调头次数分别如图9所示。由图9测试结果发现，随着c^{\mathrm{f}\mathrm{i}\mathrm{x}}的增大，无论是调车次数和调头次数均呈降低的趋势，分别平均降低11.6%和31.3%。实际工作中，调度员可以根据调车司机的数量来确定c^{\mathrm{f}\mathrm{i}\mathrm{x}}的取值。

5 结语

本文对动车所调车与检修排程计划编制进行研究，考虑了股道列位关系和股道联通关系以适应不同布局形式，不仅允许列车进行除检修、清洗外的其他作业，允许列车在2次检修作业的间隔进行存车，还考虑了列车调头的时间和费用以及调车作业的固定惩罚费用。基于双层时空网络构建0-1整数规划的多商品流模型。由于此类时空网络模型具有复杂决策变量及约束的数量十分庞大的特点，基于启发式规则，设计了商用求解器和动态规划2种方法进行求解，并提供方法比选。依托某动车所，根据长、短编动车组数量的不同设置6个算例，分别采用2种方法求解并对比结果。所提双层时空网络模型能够完整而准确地描述动车所调车与检修排程计划的问题。该模型能够充分考虑到动车所调车与检修过程中可能的各类时间和空间约束条件，为制定高效的排程计划提供可靠的数学工具。2种方法均能够在1 h内对不同规模的问题生成可行的调车与检修排程计划，验证了所提出的模型和求解方法的实用性和可行性。最后，通过灵敏度分析探究不同时空弧费用的设置效果，若其他参数不变，采用时变的作业弧费用能够鼓励列车优先进行检修作业，调车固定惩罚费用可以降低调车作业和调头作业的次数。具体到本算例中，列车的平均检修作业开始时间较恒定费用下的提前了16.5%，调车作业和调头作业的次数平均降低了11.6%和31.3%，能够为决策者提供指导，使其结合具体情况对模型参数进行调整和优化。

本文仅仅考虑了动车所调车与检修排程计划编制，如何在动车所排程计划中额外融合考虑检修人员排班和司机任务调配，将是下一步的研究重点。

参考文献

[1] VAN DEN BROEK R. Train Shunting and Service Scheduling： an Integrated Local Search Approach ［D］. Holland： Utrecht University， 2022.

[2] VAN DEN BROEK R， HOOGEVEEN H， VAN DEN AKKER M， et al. A Local Search Algorithm for Train Unit Shunting with Service Scheduling ［J］. Transportation Science， 2022， 56 （1）： 141-161.

[3] HAAHR J T， LUSBY R M， WAGENAAR J C. Optimization Methods for the Train Unit Shunting Problem ［J］. European Journal of Operational Research， 2017， 262 （3）： 981-995.

[4] KAMENGA F. Combinatorial Optimization for Integrating Rolling Stock Management and Railway Trac Scheduling in Passenger Stations ［D］. France： Université de Lille， 2020.

[5] 王忠凯，史天运，张惟皎，等.动车运用所调车作业计划优化编制模型与算法［J］.铁道学报，2013，35（8）：1-9.

[6] WANG Zhongkai， SHI Tianyun， ZHANG Weijiao， et al. Model and Algorithm for Optimized Formulation of Scheduled Shunting Operation Plans of Electric Multiple Units Depots ［J］. Journal of the China Railway Society， 2013， 35 （8）： 1-9. in Chinese

[7] 陈韬，王文宪，吕红霞，等.高速铁路枢纽站技术作业计划与动车所调车作业计划协同编制研究［J］.铁道学报，2020，42（4）：17-26.

[8] CHEN Tao， WANG Wenxian， Hongxia LÜ， et al. Coordinative Planning between Technical Operation of High-Speed Railway Hub Station and Shunting Operation of EMU Depot ［J］. Journal of the China Railway Society， 2020， 42 （4）： 17-26. in Chinese

[9] WANG J X， ZHAO Y N， GRONALT M， et al. Synchronized Optimization for Service Scheduling， Train Parking and Routing at High-Speed Rail Maintenance Depot ［J］. IEEE Transactions on Intelligent Transportation Systems， 2022， 23 （5）： 4525-4540.

[10] 户佐安，郑磊，周姝.考虑列位合理占用的动车所调车作业计划编制优化［J］.西南交通大学学报，2022，57（1）：65-73．

[11] HU Zuoan， ZHENG Lei， ZHOU Shu. Optimization of Shunting Operation Plan at Electric Multiple Units Depot Considering Train Position Proper Occupancy ［J］. Journal of Southwest Jiaotong University， 2022， 57 （1）： 65-73. in Chinese

[12] 史锦堂，黎浩东，曹恒，等.考虑灵活存车和列位占用的动车所调车作业计划编制［J］.中国铁道科学，2022，43（1）：152-162.

[13] SHI Jintang， LI Haodong， CAO Heng， et al. Shunting Operation Planning at EMU Depots Considering Train Flexible Storage and Position Occupation ［J］. China Railway Science， 2022， 43 （1）： 152-162. in Chinese

[14] HE M， TANG Q H， GUPTA J N D， et al. The Shunting Scheduling of EMU First-Level Maintenance in a Stub-End Depot ［J］. Flexible Services and Manufacturing Journal， 2022， 35 （3）： 754-796.

[15] HE M， TANG Q H， GUPTA J N D， et al. Robust Scheduling of EMU First-Level Maintenance in a Stub-End Depot under Stochastic Uncertainties ［J］. Engineering Applications of Artificial Intelligence， 2023， 123： 106398.

[16] XU X M， DESSOUKY M M. Train Shunting with Service Scheduling in a High-Speed Railway Depot ［J］. Transportation Research Part C： Emerging Technologies， 2022， 143： 103819.

[17] LI H D， JIN M Z， HE S W， et al. Optimal Track Utilization in Electric Multiple Unit Maintenance Depots ［J］. Computers & Industrial Engineering， 2017， 108： 81-87.

[18] 郭小乐，宋瑞，黎浩东，等.动车运用所调车作业计划编制优化［J］.中国铁道科学，2016，37（1）：117-123.

[19] GUO Xiaole， SONG Rui， LI Haodong， et al. Optimization of Shunting Operation Plan of Electric Multiple Unit Running Shed ［J］. China Railway Science， 2016， 37 （1）： 117-123. in Chinese

[20] SHI J T， LI H D. Optimization of the Shunting Operation Plan at Electric Multiple Units Depots ［J］. Journal of Advanced Transportation， 2019， 2019 （1）： 9120239.

[21] SHI J T， LI H D， WANG D Q， et al. Reschedule the Shunting and Service Scheduling Plan after Disturbances at a Chinese High-Speed Railway Depot ［J］. IEEE Access， 2024， 12： 38615-38630.

[22] 刘毅，唐秋华，何明.基于增强模拟退火算法的动车所调车作业计划多目标优化方法［J］.铁道运输与经济，2024，46（2）：10-19.

[23] LIU Yi， TANG Qiuhua， HE Ming. Multi-Objective Optimization for Shunting Schedule of Electrical Multiple Unit Depot via Enhanced Simulated Annealing Algorithm ［J］. Railway Transport and Economy， 2024， 46 （2）： 10-19. in Chinese

[24] MAHMOUDI M， ZHOU X S. Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows： a Dynamic Programming Approach Based on State-Space-Time Network Representations ［J］. Transportation Research Part B： Methodological， 2016， 89： 19-42.

[25] ZHANG B J， ZHANG Y X， D’ARIANO A， et al. Optimal Platforming， Routing， and Scheduling of Trains and Locomotives in a Rail Passenger Station Yard ［J］. Transportation Research Part C： Emerging Technologies， 2023， 152： 104160.

[26] ZHONG M X， YUE Y X， ZHOU L S， et al. Parallel Optimization Method of Train Scheduling and Shunting at Complex High-Speed Railway Stations ［J］. Computer-Aided Civil and Infrastructure Engineering， 2024， 39 （5）： 731-755.

基金资助

国家自然科学基金资助项目(U2268207)

中央高校基本科研业务费科技领军人才团队项目(2022JBQY006)

中央高校基本科研业务费资助项目(2022YJS060)