基于专家系统的网络化动车组运用计划的编制

陈　然，周磊山，乐逸祥，路　超，周　宇

(北京交通大学 交通运输学院，北京　100044)

随着高速铁路新线的开通，动车组的使用数量逐渐增大，但动车组的成本高昂，如何安全、经济地运用动车组越来越受到人们的关注。

国外学者对动车组或机车运用进行了研究[1-6]，主要关注在为旅客提供足够多的客车座席以及保证列车足够牵引动力情况下，尽量减少客车和机车的使用数量。但国外铁路线路里程短、客流量较少、运行线结构规律性明显，而且旅客列车非固定编组，可以通过重联、分解、连挂、无动力回送等方式增减编组辆数或机车数以适应客流变化，动车组运用情况与国内有较大不同，因此借鉴性较少。

国内专家重点研究动车组的交路计划、检修计划和分配计划，目的是减少动车组使用数量或提高动车组使用效率。王莹等研究二级修以上的动车组检修计划，以检修前累计运行里程最大为目标，通过构建接续网络建立数学模型，以广深线为例运用列生成算法求解[7]；在后续的研究[8]中，将动车组周转计划编制问题在列车运行图可作微调的前提下进一步优化，实现动车组运用计划与运行图编制优化的协调。赵鹏等以京沪高铁为实例，利用局域搜索产生单个动车基地的运用计划初始解，再通过列车分组、路段交换形成多动车基地下的动车组运用计划[9]。王忠凯等以动车组运用交路与检修规程为约束，以减少动车组数和检修成本为目标，设计了运用计划与检修计划一体化编制的整数规划模型，先求解约束条件生成可行的运用路径集合，再以此为基础设计模拟退火算法[10]。史峰等为描述动车组运用均匀性，以环形排列为动车交路建立模型，将检修约束以罚值函数代入目标函数用基于三交换法的模拟退火算法求解[11]；在后续的研究中[12]，建立以车站作业时间、动车组接续时间和到发线数为约束条件,以列车旅行时间和动车组接续时间最小化为目标函数的综合优化模型，将动车组周转、到发线运用与运行图整体优化。林柏梁等研究了固定区段和不固定区段动车组二级检修特点，建立了相关模型[13]。李华等以设计接续边的累计时间和里程为约束建立整数规划模型，以武广线为例引入动车组运用最优接续网络为粒子飞行参考，运用粒子群算法求解[14]。张才春提出了基于簇式运用方式和动态备用方式编制动车组运用计划，将动车组运用计划优化问题转化为多个小周期内的优化问题并使用蚁群算法求解[15]。这些研究多数使用智能算法求解单条线路的动车组运用计划，在列车网络化运行背景下可能会出现不适应的情况。

本文借鉴铁路现场使用的机车周转图，突出网络化运行下动车的累计运行里程和时间，以及需要担当的各条运行线的里程和时间，提出网络化动车组运用计划图。以动车组累计运行里程和时间、动车段(所)检修能力、接续作业时间与检修作业时间为约束条件，以动车组运用数量最少为最优目标、检修次数最少为次优目标，建立动车组运用计划双目标规划优化模型；设计基于专家系统的最大最小蚁群算法进行求解。以含有6条高速铁路线的路网为例，求解动车组运用计划。

1　问题描述

1.1　网络化运行下动车组运用计划的编制

随着高速铁路新线的开通，高速铁路线路逐渐形成网络布局，动车组在网状线路间运行，大量跨线列车开行导致运行图结构更复杂，更多不同类型的动车组运行在同一路网上而导致动车组运用计划编制也更困难。然而，动车组运用问题的可优化范围也变得更大。主要表现在：动车组不固定区段运行，将有更多的运行线接续组合，适当选择接续运行线(如采用大小交路套跑模式)可以充分运用动车组；适当选择检修地点和检修时机，让动车组尽量运行到检修里程的上界，在检修次数不变的前提下多担当运行任务。例如图1所示，按线路分别编制动车组运用计划需要4列动车组，若按图2网络化方式编制动车组运用计划，可以让动车组担当更多线路的运输任务，虽增加了动车组运行里程，但可节省2列动车组；由图3(图中数字表示运行线里程)也可知，适当选择检修作业的时间和地点，同样能够达到充分运用动车组、减少检修次数的目的。总之，从路网角度求解动车组运用计划，可以得到更多初始解空间，搜索到更优解，最终使全局优化效果大于各线优化效果之和[16]。

图1　按线路分别编制动车组运用计划

图2　按路网编制动车组运用计划

图3　适当选择检修时机和地点节省用车

1.2　专家系统及其基于专家系统的改进蚁群算法

专家系统拥有某专业领域内大量的专家级知识，通过运用这些知识进行判断及推理，可以解决该领域内的复杂问题。专家系统主要包含知识库和推理机两部分，其中，知识库存储专家的经验知识，推理机负责响应用户的查询[17]。

成网条件下动车组运用计划编制优化模型的求解较复杂，智能算法已经不能满足模型求解的质量和速度，因此引入专家系统，设计基于专家系统的改进蚁群算法。该算法的原理为：若专家系统的知识库中存在相应的经验知识，则采用专家系统求解，否则采用蚁群算法求解；在编制完成动车组运用计划后，对编制过程进行总结，得到新的知识经验，并将其加入知识库，以丰富知识库。该算法的流程如图4所示。

图4　基于专家系统的改进蚁群算法的流程图

2　网络化动车组运用计划图的提出

既有动车组交路计划图的结构与运行图结构较为相似，展示了单条线路的列车运行线信息，以及运行线的接续关系。考虑到在编制动车组运用计划过程中，编制人员更加关注整个路网上动车组运行里程或时间是否超过检修规定，能否继续担当下次运行线任务。因此，基于既有的动车组运用计划图，提出网络化动车组运用计划图。网络化动车组运用计划图包括：运行线车次、担当该车次的动车组车号、到发时刻、到发站、运行里程、运行时间和运行线间的接续关系，以及车站、动车段(所)在物理路网中的相对位置。网络化动车组运用计划图避免了传统绘制多线路动车周转图时需分块铺画的情况，突出了动车组运行的里程、时间，以及累计运行的里程、时间等信息。

图5为含有4座车站(S1，S2，S3和S4)、4条线路和1个动车运用所的路网结构图。图6为该路网图的网络化动车组运用计划图，图中两圆相连的折线表示接续对应的运行线，若折线是虚线则表示为检修接续。图7为图6中数字含义的解释示意图。图7中：圆内字符代表车次/担当此次运行线的动车组车号；与圆相连的箭头代表运行方向，指向圆为到达该车站，背离圆为离开该车站；箭头线上下的4组字符中，靠近圆一侧上方的字符代表该运行线的里程，靠近圆一侧下方的为运行线的运行时间，远离圆一侧上方的为出发或到达时刻，远离圆一侧下方的为出发或到达车站站名；在指向圆的箭头线的另一边，线上方的表示动车组累计运行里程，线下方的表示动车组累计运行时间。

图5　路网结构图(单位：km)

图6　网络化动车组运用计划图

图7　针对图6中数字的含义解释图

图8为图6虚线框内箭头线的解释示意图，图8中各箭头线线段的长短表示对应运行线运行里程的长短，箭头指在竖线上的位置是按照对应运行线在该站到达或从该站出发时间顺序等比例排布的。图9为图6中粗箭头线所表示的动车交路段信息解释图。

图8　针对图6中虚线框内箭头线的解释示意图

图9　对应图6中粗箭头线所包含的动车组交路段信息(以001号动车组为例)

3　动车组运用计划双目标规划优化模型

3.1　前提假设

首先做如下假设：动车组车型不可以混用；2列短编组的动车组重联后不分解，按1列动车组考虑；在每个车站始发的列车数等于终到的列车数，只考虑列车在本站进行接续；在动车段(所)不计调车所用的时间；动车组只在每天的6:00—23:30之间开行；动车组运用采用不固定区段的运行方式。

3.2　集合定义

3.3　参数定义

(1)

(2)

(3)

(4)

3.4　变量说明

(2)决策变量xe,i(e∈E，i∈A)。若动车组e担当运行线i的运输任务，则xe,i=1，否则xe,i=0。

(3)变量xi,j(i,j∈A)。若运行线i为运行线j的紧前接续线，则xi,j=1，否则xi,j=0。

3.5　数学模型

以动车组使用数量最少为最优目标、动车组入段(所)检修次数最少为次优目标，构建动车组运用计划双目标规划优化模型，即

e∈E，i∈A

(5)

i∈A，j∈A，d∈D，e∈E

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

约束条件中：式(7)表示对任意1条运行线，有且只有1列动车组担当；式(8)和式(9)表示动车组最大运行时间和运行里程不允许超过《铁路动车组运用维修规程》的规定；式(10)表示在动车段(所)d进行M检修作业的动车组数量不能大于动车段(所)的检修能力；式(11)表示运行线i和运行线j进行非检修接续时，接续时间必须大于TR；式(12)表示运行线i和运行线j进行检修接续时，接续时间必须大于从车站到动车段(所)往返运行时间与在动车段(所)检修所需的时间之和。

4　求解算法

因为建立的动车组运用计划双目标规划优化模型具有解空间庞大的特点，因此设计基于专家系统的改进蚁群算法对模型求解。

4.1　知识库内经验知识的丰富

在编制完成动车组运用计划后，总结得到如下5条经验知识。

(1)在选择后续运行线时，避免选择节省用车选择范围之外的运行线。

图10　节省用车选择范围示意图

(2)经验知识只考虑动车组的累计运行里程。当选取的动车组的最大检修里程较小时，只考虑紧凑接续，即将满足接续时间要求和检修里程最小的运行线接续。

(3)在节省用车选择范围之内，对于最大检修里程较短的运行线，应优先选择最大检修里程较长的运行线接续；对于最大检修里程较长的运行线，应优先选择最大检修里程较短的运行线接续。

(4)若动车组需入段进行某项检修作业，则判断其他检修作业里程或时间是否也同时达到检修要求，若达到则同时进行检修。

(5)在夜间非行车期间，对到达动车组按最大检修里程从大到小排序，在不超过动车段所检修能力情况下，按照此顺序对动车组进行检修。

4.2　最大最小蚁群算法原理

参照文献[19—20]中的最大最小蚁群算法，将运行线类比为城市，运行线接续时间类比为城市之间的距离，求解所有蚂蚁遍历所有城市后行走总距离最小的问题。该算法的转移概率准则和信息素更新准则如下。

1)转移概率准则

(13)

2)全局信息素更新规则(信息素遗留规则)

(14)

(15)

(16)

3)局部信息素更新规则(信息素挥发规则)

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

(17)

(18)

式中：n为运行线的条数；tnn为在满足接续作业时间要求前提下最短的接续时间；ζ为权重参数，满足0<ζ<1。

增加如下2条防止算法过早收敛或停滞的规则。

(2)当系统接近停滞状态(通过对各条边的信息素大小的统计来测定)，或者在一定数量的迭代过程中不再有更优的路径出现，则所有的信息素都被重新初始化。

4.3　基于专家系统指导的最大最小蚁群算法

动车组运用计划双目标规划优化模型有动车组运用数量最少和检修次数最少2个目标函数，考虑到1列动车组的购置成本远大于其检修成本，因此在求解时首先求解满足动车组使用数量最少的解，多次求解后，若存在相同运用数量的解则比较检修次数，取检修次数较少的解为最优解，若不存在相同的解，则直接取动车组使用数量最少的解。

算法输入：列车运行线的到发时刻、到发站、车次、运行里程和运行时间；动车组的初始运行里程和运行时间。

算法输出：动车组运用计划。

算法参数：可以接续运行线i的后续运行线集合Aallow，蚂蚁数pmax，最大循环次数Kmax；经验知识权重系数λ(一般0.55<λ<1.00)。循环次数K的初始值为0。

算法原理：在确定1条运行线的后续运行线时，先产生1个随机数λ′，若λ′≤λ，则检索知识库中是否有满足条件的经验知识，如果有则按照经验确定接续关系，否则按照智能算法确定接续关系；若λ′>λ，则采用最大最小蚁群算法确定接续关系；直到所有运行线都已确定后续运行线。在算法初期，λ应赋以较大值，以产生较优初始解，后期则应赋以较小值，同时配以较大ρ，以充分利用启发式信息搜索。

具体算法步骤如下。

步骤2：p=p+1，取车站集合S中的1个元素s作为当前车站，取s站第1条到达运行线i为当前运行线。

步骤4：在(0,1)中产生随机数λ′，若λ′≤λ，则采用知识库的经验知识求解，转步骤5；否则采用最大最小蚁群算法求解，转步骤6。

步骤5：检测是否有符合下述经验知识的情况。

(5)将24:00之后到达s站的动车组按最大检修里程从大到小排序，若达到检修里程下限的动车组有nlow个，则取前min{Cd,nlow}个动车组进行检修作业。转步骤6。

步骤7：按式(1)更新动车组各检修的实际运行里程。若后续运行线j的Aallow为空集，则转步骤8，否则转步骤4。

步骤8：若仍存在没有搜索过的车站，则选取下一个未被搜索的车站，记为s，取s站第1条未被接续的到达运行线i，转步骤3；否则，若p

步骤9：按照全局信息素更新规则，对两两接续的运行线进行更新，若存在信息素大于τmax的，则将其修改为τmax；按照局部信息更新规则，对两两能够接续的运行线接续信息素进行信息素挥发，若存在信息素小于τmin的，将其修改为τmin。

步骤10：记录此次循环中的最优解，将当前最优解的动车组使用数量与历史最优解的进行比较。若比历史最优解的少，则将当前最优解赋给历史最优解；若比历史最优解的多，则保留当前历史最优解；若与历史最优解的相等，则再比较检修次数，若比历史最优解的少，则将当前最优解赋给历史最优解，否则保留当前历史最优解。

步骤11：若K=Kmax，则转步骤12；否则K=K+1，转步骤1。

步骤12：总结编制过程，得到新的知识经验，并将其加入知识库。

步骤13：输出历史最优解的动车组运用计划，算法结束。

5　算例分析

本文以京沪、沪杭、宁杭、京津、沪宁、胶济线组成实例路网，以北京、天津、济南、青岛、南京、上海、杭州为始发终到站，各站配备动车段或动车运用所。该路网中有432条列车运行线，始发终到信息见表1。其中北京和上海动车运用段(所)的检修能力均为100列·d-1，南京和天津动车运用段(所)的检修能力为30列·d-1，其余的均为20列·天-1。

表1　车站间始发终到运行线数表

由于动车组车型不可混用，不同车型动车组运用计划需要分别制定，因此本实例只考虑其中的1种车型。考虑到二级检修的大部分作业检修里程较长，因此本实例只考虑二级检修中检修里程相对较短的M1作业，规定的其检修作业里程[21-23]见表2。

表2　动车组检修作业里程表

参数取值：蚂蚁个数pmax=100只，循环次数Kmax=20次，经验知识权重系数λ=0.70， 重要性参数α=1.1，β=1.1，信息素挥发因子ρ=0.2。

计算环境为：64位Win7系统，CPU主频2.80 GHz，开发工具为Visual Studio 2010，开发语言为C#。用基于专家系统的最大最小蚁群算法求解，对模型重复进行5次求解，得到结果分别见表3。表3中动车利用率的计算公式为

(19)

优先选择动车组数最少的解，若存在相同动车组使用数量的解。则再选择检修次数少的解，综合以上2点，选择第1次解或第4次解作为最终算法的解。

为了对比分析本文方法的有效性，仅使用蚁群算法对动车组运用计划双目标规划优化模型求解，结果见表4。

对比表3和表4可知，采用基于专家系统的最大最小蚁群算法可以得到更优的解，并且计算的收敛速度更快。

再按线路分别编制动车组运用计划。将杭州站(宁杭线和沪杭线上到达杭州站的除外)和青岛站的到发的列车分别单独作为1条线路处理，南京与上海间的列车计入沪宁线，北京与天津之间的计入京津线。结果见表5。由表5可知，按照线路分别编制动车组运用计划，则全路网共需要动车组132列，多于网络化编制的113列。

表4　仅使用蚁群算法的求解结果

表5　按线路分别编制动车组运用计划的结果

6　结　语

在动车组网络化运行背景下，提出了强化动车组运用信息的、更直观的“网络化动车组运用计划图”，为编制人员提供一个网络化动车组运用计划编制更便捷的界面。建立动车组运用计划双目标规划优化模型，设计基于专家系统的最大最小蚁群算法对模型求解，编制出网络化条件下动车组使用数和检修次数均较少的网络化动车组运用计划。案例求解结果证明：采用本文模型和算法比仅采用最大最小蚁群算法结果更优；采用网络化编制动车运用计划比分别编制各线路动车组运用计划更优。文中提出的网络化动车组运用计划图和基于专家系统的最大最小蚁群算法可用于开发人机界面更加友好、更加智能化的网络化动车组运用计划编制系统，方便编制人员编制高质量的动车组运用计划。

[1]RAVINDRA K Ahuja, JIAN Liu, JAMES B Orlin, et al. Solving Real-Life Locomotive-Scheduling Problems[J]. Transportation Science, 2005, 39(4)：503-517.

[2]PIETER-JAN Fioole, LEO Kroon, GABOR Maroti, et al. A Rolling Stock Circulation Model for Combining and Splitting of Passenger Trains[J]. European Journal of Operational Research, 2006, 174: 1281-1297.

[3]MARC Peeters, LEO Kroon. Circulation of Railway Rolling Stock: a Brach-and-Price Approach[J]. Computers & Operations Research, 2008, 35:538-556.

[4]ERWIN Abbink, BIANCA van den Berg, LEO Kroon, et al. Allocation of Railway Rolling Stock for Passenger Trains[J]. Transportation Science, 2004, 38(1): 33-41.

[5]TOMOSHI Otsuki, HIDEYUKI Aisu, TOSHIAKI Tanaka. A Search-Based Approach to Railway Rolling Stock Allocation Problems[J]. Discrete Math Algorithm, 2011(3):443-456.

[6]ARIANNA Alfieri, RUTGER Groot, LEO Kroon, et al. Efficient Circulation of Railway Rolling Stock[J]. Transportation Science, 2006, 40(3)：378-391.

[7]王莹，刘军，苗建瑞. 基于列生成算法的动车组检修计划优化[J].中国铁道科学，2010，31(2)：115-120.

(WANG Ying, LIU Jun, MIAO Jianrui. Column Generation Algorithms Based Optimization Method for Maintenance Scheduling of Multiple Units[J]. China Railway Science, 2010, 31(2):115-120. in Chinese)

[8]王莹，刘军，苗建瑞. 基于运行线可调的动车组周转计划优化研究[J].中国铁道科学，2012，33(4)：112-119.

(WANG Ying, LIU Jun, MIAO Jianrui. Optimization of the Circulation Plan for Multiple Units Based on Adjustable Train Path[J]. China Railway Science, 2012, 33(4):112-119. in Chinese)

[9]赵鹏，富井规雄. 基于路段交换的多基地动车组运用计划的编制算法[J]. 铁道学报，2004，26(1)：7-11.

(ZHAO Peng, TOMII Norio. An Algorithm for Multiple-Bases Train-Set Scheduling Based on Path-Exchange[J]. Journal of the China Railway Society, 2004, 26(1):7-11. in Chinese)

[10]王忠凯，史天运，张惟皎，等. 动车组运用计划和检修计划一体化编制模型及算法[J].中国铁道科学，2012，33(3)：102-108.

(WANG Zhongkai, SHI Tianyun, ZHANG Weijiao, et al.Model and Algorithm for the Integrative Scheduling of EMU Utilization Plan and Maintenance Plan[J].China Railway Science, 2012, 33(3):102-108. in Chinese)

[11]史峰，周文梁，郁宇卫，等.客运专线动车组运用计划优化模型与算法[J].铁道学报，2011，33(1)：8-13.

(SHI Feng, ZHOU Wenliang, YU Yuwei, et al. Optimized Model and Algorithm of Motor Train-Sets Scheduling for Dedicated Passenger Lines[J]. Journal of the China Railway Society,2011,33(1):8-13.in Chinese)

[12]史峰，魏堂建，周文梁，等. 考虑动车组周转和到发线运用的高速铁路列车运行图优化方法[J].中国铁道科学，2012，33(2)：107-114.

(SHI Feng, WEI Tangjian, ZHOU Wenliang, et al.Optimization Method for Train Diagram of High-Speed Railway Considering the Turnover of Multiple Units and the Utilization of Arrival-Departure Tracks[J].China Railway Science, 2012, 33(2):107-114. in Chinese)

[13]林柏梁，陈雷，孙卿，等. 动车组二级检修计划优化模型[J/OL].中国科技论文在线， http://www.paper.edu.cn/html/releasepaper/2013/12/470/.

(LIN Boliang, CHEN Lei, SUN Qing, et al.Study on Optimization Model of EMU Grade 2 Maintenance Plan[J/OL].Science Paper Online，http://www.paper.edu.cn/html/releasepaper/2013/12/470/. in Chinese)

[14]李华，韩宝明，张琦，等. 动车组交路计划优化模型与算法研究[J].铁道学报，2013，35(3)：1-8.

(LI Hua, HAN Baoming, ZHANG Qi, et al. Research on Optimization Model and Algorithm of EMU Circulation Plan[J]. Journal of the China Railway Society, 2013, 35(3):1-8. in Chinese)

[15]张才春. 成网条件下客运专线动车组运用的研究[D].北京：北京交通大学，2010.

(ZHANG Caichun. Study on the Train Units Operation Problems of Passenger Dedicated Rail Network[D]. Beijing:Beijing Jiaotong University, 2010. in Chinese)

[16]郑锂，宋瑞，肖赟，等. 网络化运营下城市轨道交通列车车底运用计划编制的优化方法[J].中国铁道科学，2014，35(2)：104-110.

(ZHENG Li, SONG Rui, XIAO Yun, et al. Optimization Method for Working out Vehicle Scheduling Plan of Urban Rail Transit under Network Operation[J]. China Railway Science, 2014, 35(2):104-110. in Chinese)

[17]李焱. 应用软件工程和专家系统的列控中心仿真研究[D].北京：北京交通大学，2012.

(LI Yan. Simulation of Train Control Center Applying Software Engineering and Expert System[D].Beijing:Beijing Jiaotong University, 2012. in Chinese)

[18]中国铁路总公司. TG/CL 127—2013 铁路动车组运用维修规程[S]. 北京：中国铁道出版社，2013.

[19]梁旭，黄明. 现代智能优化混合算法及其应用[M].北京：电子工业出版社，2011.

[20]赵玉新,Xin-She Yang,刘利强. 新兴元启发式优化方法[M].北京：科学出版社，2013.

[21]焦风川，王斌杰. 动车组运用与维修[M]. 北京：北京交通大学出版社，2012.

[22]王连森，连苏宁. 动车组维护与检修[M]. 成都：西南交通大学出版社，2010.

[23]李华，韩宝明，赵鹏. 面向我国铁路实际的动车组运用计划编制问题[J].北京交通大学学报，2012，36(6)：8-14.

(LI Hua, HAN Baoming, ZHAO Peng. Train-Set Scheduling Problem Geared to Practical Production Process of Railway in China[J]. Journal of Beijing Jiaotong University, 2012, 36(6)：8-14.in Chinese)

[24]张惟皎,史天运,陈彦. 动车运用所存车线运用方案优化模型与算法[J].中国铁道科学，2013，34(1)：121-125.

(ZHANG Weijiao, SHI Tianyun, CHEN Yan. Optimization Model and Algorithm for the Operation Plan of the Stabling Track at EMU Running Shed[J].China Railway Science, 2013, 34(1):121-125. in Chinese)