基于均衡运用原则的列车运营日计划编配研究*

臧 瑶 徐 刚 黄 瑛 邢宗义

(1. 南京理工大学自动化学院， 210094， 南京；2. 中车青岛四方机车车辆股份有限公司专项办， 266111， 青岛//第一作者，硕士研究生)

在确定了第二日列车运营日计划模板后，为模板中相应的列车车次编配状态良好的车组，称为列车运营日计划编配。目前传统的人工编配方式存在生产效率低下、安全隐患大等问题，因此，科学地进行列车运营日计划编配具有重要现实意义。

目前，针对城市轨道交通列车运营日计划编配的研究甚少。由于动车组运用计划编制和城市轨道交通列车运营日计划编制的目的都是为运输生产提供状态良好的车辆，因此，对动车组运用计划编制问题的研究对于城市轨道交通列车运营日计划编制具有一定的借鉴意义[1]。文献[2]在已知列车运行图的基础上，建立求解动车组运用问题的整数规划模型，将动车组的接续运行与检修计划制定过程转化为动车组运用网络上的TSP(旅行商问题)问题，借鉴蚁群算法求解。文献[3]建立了动车组运用计划编制数学模型，采用遗传算法使生成的交路段数最少，利用交路段互换的方法实现各基地动车组使用的均衡性。文献[4]对韩国KTX动车组的运用计划优化问题进行了研究，以列车运用时间最低为优化目标，基于交换生成满足检修约束的最优动车组交路。文献[5]以运用列车数最少、总运行里程最低为优化目标，在动车组运用顺序和列车定员等约束下建立动车组运用优化模型。

本文以车组号与车次匹配度最高为目标函数建立列车运营日计划编配模型，实现列车检修与运用的解耦和，使列车在规定时限内得到检修，在提高列车运营可靠性的同时保障行车安全。

1 问题描述

表1为某城市轨道交通列车运营日计划表。早高峰车次为0202、0402、0702、1002，晚高峰车次为1702、1802、1902、2002；每个车次都有其发车方向， 0102、0302、0402、0602、0902、1102为上行方向，其余车次为下行方向。

表1 某城市轨道交通列车运营日计划表

回库车次与出车车次数相差越多，代表车次对应的列车的日运行里程数越大。以编号为1的计划为例，出库车次为0102，回库车次为0135，即需要跑34个单趟。晚班调度只对除晚高峰之外的车次进行安排，晚高峰车次由早班调度在出车前根据车组实际状况进行安排。

列车运营日计划编配问题可表述为：在时刻表/车次信息、股道信息、车组信息已知情况下，对列车运营日计划表进行编配。列车运营日计划要满足道岔转换最小时间约束、早高峰指定车次约束、出库便捷性约束和唯一性约束，选用合适的良好车组去担当特定的列车车次。

2 基于改进BWAS(最优-最差蚁群算法)的列车运营日计划编配算法设计

2.1 解构建图的表示及解的构建

解构建图的实质是对解空间的一种描述，通常为点-边结构的拓扑结构。蚂蚁可在该拓扑结构中根据路径的信息素与局部启发式信息以不同概率对下一节点进行选择，重复直至完成路径构建。任何优化问题的解均可经处理后分解为构造块并映射为解构建图中的节点;该节点与连接的有限集合通过网络拓扑结构组合出问题的解空间[6]。

在传统的TSP问题中，解构建图为所有城市节点的连接网，边的权值为两城市节点间的距离。在本文中，首先需确定所有待编配车组与除晚高峰外的待编配车次的成本矩阵Cij，其中行代表车组号，列代表列车车次；车次按时间从早到晚依次排列，成本矩阵中的每一个值都作为一个节点vij(第i个车组担任第j个车次)。在进行计划编制时需按照车次时间顺序依次进行编配，故将所有节点按从左到右的方向依次连接，当前节点仅可与右侧相邻列的所有节点连接，如图1所示。

图1 路径构建示意图

所有蚂蚁均从起始点出发，依据状态转移策略在第一列的可选节点中选择转移节点，选择完毕后对信息素进行更新，重复直至到达最后一列完成解的构建。在解构建过程中，若出现某一列可使用车组集为空的情况，即对当前解舍弃，返回第一列重新解的构建。解构建完毕后为所有经过节点的集合vij，解析后得到车组号与列车车次的对应关系。

2.2 目标函数与约束

2.2.1 约束条件

对列车运营计划表编配问题的约束进行分析。

(1) 唯一性约束：由于一个车次唯一对应一列列车，故需满足唯一性的原则：

(1)

式中:

Xij——决策变量;

n——除晚高峰外所有车次的总数;

k——有早高峰或指定车次任务的车组数。

同时，一列车唯一对应一个车次，因此有：

(2)

式中：

m——所有状态良好车组的总数。

(2)早高峰指定车次约束：早高峰与指定车次的任务完成率Pm有如下约束：

Pm=Mf/Mtotal=1

(3)

式中：

Mf——完成的早高峰指定车次任务数；

Mtotal——早高峰指定车次任务总数。

(3) 道岔转换最小时间约束：当前车次的道岔状态要求与当下的道岔状态不一致时需要进行道岔转换，因此需考虑道岔转换的最小时间间隔约束。

Tl>60,l∈[2,3,…,n]

(4)

式中：

Tl——当次列车与上次列车的时间间隔；

l——需要进行道岔转换的车次序号。

(4) 出库便捷性约束：当同一停车库A、B股道均停放车组时，分别记停放在A、B股道上的车组为Ti1和Ti2，按车次顺序进行编配时满足如下约束：

(5)

其中，Ai表示车组Ti是否可以安排车次，当Ai=0时，代表该车组Ti暂时不能安排车次；当Ai=1时，代表该车组Ti可以安排车次。

因此，列车运营计划编配的数学模型为：

j=1,2,…,n-k

(6)

式中：

Cij——状态良好的车组与待配车次的匹配程度。

2.2.2 目标函数的选择

可以将列车运营日计划编配看成一个指派问题，其中：担任车次任务的车组集合为{Ti，i=1,2,…,m}；待分配车次集合为{Fj，j=1,2,…,n}。Cij代表车组Ti与车次Fj的匹配程度，Cij值越小代表匹配程度越高；决策变量Xij∈[0,1]，当Xij=0时，代表车组Ti未担当车次Fj，当Xij=1时，代表车组Ti担当车次Fj。

在进行列车运营日计划编配时，需使全部车次的总成本最低，即全部车次与车组的总匹配度最高，目标函数见式(6)。

其中，Cij的计算步骤如下：

(1) 将有早高峰或指定车次任务的车组号填入运营计划对应车次。

(2) 对所有未安排车次(除晚高峰车次)所对应的里程由小到大进行排序，记为rj=a，a=1,2,…,n-k,rj表示车次Fj在排序后位于第a个位置，其中里程数相同的车次排名也相同。

(3) 对未安排车次的车组按规则进行排序。若某项检修作业的检修周期固定且为t,在一般情况下，所有车组两次检修作业之间的时间间隔也随之确定。 由于检修周期的确定与车组走行里程有关，因此要求两次检修时间间隔内所车组的走行里程接近。

将车组与车次按顺序进行匹配。首先根据步骤(2)与步骤(3)对车组号及车次进行排序，然后按照排名先后进行匹配。尽量安排日均走行里程小的车组去担任里程数大的车次，但由于股道约束、车组停放位置等因素的影响，车组与车次往往无法实现最佳匹配。

由于车次数一般少于车组数，因此，首先需将车组号对应的最佳匹配车次进行补全，依次加1，作为车组号最佳匹配车次参考。车组Ti与车次Fj的匹配度Cij的计算公式如下：

Cij=|Rj-Rbest|

(7)

式中：

Rj——车次Fj在所有车次中的排名；

Rbest——车组Ti的最佳匹配车次在所有车次中的排名。

2.3 信息素的表示、初始化及更新

由于本问题的解构建图基于成本矩阵构建，每个元素均为一个节点，故将信息素τij置于每个节点上，代表第i个车组担任第j个车次的期望程度。在初始时刻设τij(0)=K(K为常数)。

在建立一个解决方案过程中，蚂蚁每选中一个节点vij，即应用式(8)的局部更新规则对所选择的节点进行信息素更新。

τij=(1-ρ)τij+ρτij(0)

(8)

式中：

ρ——信息挥发系数，0<ρ<1。

蚂蚁从上一个节点向vij移动时，局部更新规则使得vij的信息素含量减少，从而有效避免蚂蚁收敛到同一路径。

当所有蚂蚁完成一次循环后，为使搜索过程更具指导性，让蚂蚁的领域集中在当前循环为止的最好路径领域内，需对全局最优及全局最差路径的信息素轨迹量进行更新。

首先找到当前循环为止的全局最优路径，应用式(9)的全局更新规则对所有节点上的信息素进行更新。

τij=(1-ρ)τij+γΔτij

(9)

式中：

γ——参数；

Lbest——当前循环找出的全局最优路径长度。

然后找到当前循环最差蚂蚁所经过的路径，应用式(10)的全局更新规则对属于最差路径但不属于全局最优路径中的节点的信息素进行更新。

(10)

式中：

ε——参数；

Lworst——当前循环最差路径长度。

2.4 状态转移策略的选择

与经典TSP问题中蚂蚁状态转移策略不同，本文路径上的能见度由当前车组与车次的匹配度确定。此外，蚂蚁下一步可选择的节点集合也不同，需考虑已选择的车站、股道约束及未选车站状态，具体状态转移策略如下：

(1) 根据当前车次的股道约束确定可选车组停放位置，并结合车组停放位置表确定第k个可选车组中当前状态为1的车组集合Tallowedk1。

(2) 查看当前车辆禁忌表，筛选出第k个可选车组中当前状态为2的车组集合Tallowedk2。

(3) 为使初始解集中在最优解附近，假设:若路径上的信息量刺激未达到蚂蚁的感觉阈限时，蚂蚁忽视该刺激的存在，仅依赖节点间的能见度进行路径选择，即在初始若干代N中，车组Ti与以概率S担当车次Fj。在初始N代中，不需对信息素进行局部更新，只需进行全局更新。

(11)

式中：

t——时间;

Tallowedk——蚂蚁下一步可选车组的集合,Tallowedk=Tallowedk1∪Tallowedk2；

q——在区间[0,1]均匀分布的随机数；

q0——参数(0≤q0≤1)，其大小决定利用已知条件确定节点与探索新路径之间的重要程度；

ηsj——节点vsj的能见度；

(4) 在后续的循环中，选择合适车组担任下一车次，转移概率如下：

(12)

式中：

pij,k——在第k个可选车组中，车组Ti担任车次Fj的概率；

τsj——节点vsj上的信息素；

β——能见度的相对重要性(β≥0);

α——轨迹上残留信息素的相对重要性(α≥0)。

3 仿真分析

采用Java开发语言、Myeclipse开发工具建立城市轨道交通列车运营日计划编配仿真平台。

首先，统计车次信息。车次信息包含车次、出车方向、时间、股道约束、里程、是否为早/晚高峰等，如图2所示。

图2 车次信息统计表截图

其次，统计股道信息。股道信息包括股道号、是否占用、车号等，如图3所示。

图3 股道信息统计表截图

最后，统计车组信息。车组信息包括车号、状态、担任车次、当前总走行里程、距离测量基准时间的天数及测量基准时间对应的车组总走行里程等，如图4所示。

其中，只能为状态良好的车组编配车次。指定任务包括早高峰与指定车次两类，若B股道车组有早高峰任务，也应为A股道状态良好的车组编配车次。

图4 车辆信息统计表截图

利用改进的最优-最差蚁群算法求解。设初始蚂蚁种群数为50，信息素因子为1，期望启发因子为5，信息素挥发系数为0.2，τij(0)=0.5，q0=0.2，以及最大循环代数为80。该算法每次循环执行80代，从多次执行情况可知，其平均在30代至40代之间收敛。算法收敛情况如图5所示。

图5 列车运营日计划编配算法收敛情况

列车走行里程变化情况趋势如图6所示。由图6可见，列车运用的均衡性有了小幅度的提升。为更好地说明执行列车日走行里程的变化趋势，本文假设在车组信息、股道信息、车次信息等条件不变的情况下，重复执行该方案19次。列车日走行里程的变化情况如图7所示。

在应用此方案约19 d后，所有运用列车的日走行里程基本趋于一致。该算法可在短时间内收敛并使车组运用的均衡性得到显著提升。

图6 执行方案一次后的列车日走行里程变化趋势图

图7 运用方案19 d后的列车日走行里程变化趋势图

4 结 语

本文针对列车运营日计划编配问题，提出一种基于改进的最优-最差蚁群算法的车次与车组号匹配算法，实现车组均衡运用，为后续的列车运营日计划安排提供依据。