高速夜行列车车底运用及优化方法研究

韩宝明，孙士钊，郑 玢，张 琦

(1.北京交通大学交通运输学院，北京 100044；2.中铁工程设计咨询集团有限公司，北京 100055)

高速夜行列车车底运用及优化方法研究

韩宝明1，孙士钊1，郑 玢2，张 琦1

(1.北京交通大学交通运输学院，北京 100044；2.中铁工程设计咨询集团有限公司，北京 100055)

高速夜行列车在运用时间范围和运用时间跨度方面都与现有高速动车组存在较大差异，因而导致诸多运用条件发生改变。在总结夜行列车车底运用问题特征的基础上，将该问题求解过程划分成基本交路生成和完整循环交路生成两个阶段，其中前者作为后者模型的输入。构建以车底运用不均衡度和非配属地检修次数最小为目标的数学优化模型，通过改进的深度优先搜索算法进行求解，并以京广线为背景对模型和算法进行验证。结果表明，针对我国铁路实际该方法能有效解决夜行列车车底周转运用问题，可为我国夜行列车的开行提供技术支持。

夜行列车；运用模式；交路计划；深度优先搜索算法

近些年，随着国家快速铁路网络日渐完善，在高速铁路上开行夜行列车的基础条件已经具备。由于高速铁路运行速度更快，城市之间的通达时间大大缩短，一些距离短的城市之间已没有开行夜行列车的必要，而另外约有32.8%距离在2 000 km以上的城市之间列车进入夜行列车优势到发时间范围[1]，因此组织开行高速夜行列车尚有很大需求并十分必要。

高速夜行列车也称高速夕发朝至列车或高速夜行动车组(以下简称夜行列车)。由于我国高速铁路综合维修天窗设置在夜间，全线(或分段)双向同时停电检修，从而直接制约了夜行列车在夜间的运行。针对这个问题不少学者做了可行性研究[2-3]，并从压缩天窗时长和调整天窗布置形式等方面提出了解决措施[4-5]，为后续的研究奠定了基础。在此基础上，有学者进一步对夜行列车开行方案进行了探讨[6-7]。此外，针对动车组运用和优化方面的研究大都局限在日间动车组，即动车组在日间运行，夜间检修。这种模式下的动车组运用和优化相关理论成果较为丰硕，其中文献[8-11]进行了较为系统的研究和总结。而目前，对于夜行列车车底运用问题的研究还较为少见。

夜行列车由于其运用时间范围(17：00—次日9：00)和运用时间跨度(6 h以上)与现有高速动车组存在较大差异，导致一系列运用条件发生改变，因此不能简单套用既有的模型和算法。在借鉴既有方法的基础上，提出该问题的分解策略，针对新的运用条件，重新建立双目标优化模型，通过改进的深度优先搜索算法得以求解夜行列车车底周转运用问题。最后以京广高速夜行列车为例进行实例验证，证明了方法的有效性。

1 夜行列车车底运用问题分析

1.1 相关概念解析

(1)夜行列车

夜行列车的具体解释是：当日下午5点以后至12点之前始发，次日上午6点以后至9点到达的高速列车。其运行时间在6 h以上，运行里程一般在1 000～3 000 km。

(2)基本交路

即夜行列车完成一次一级检修后至完成下一次一级检修期间担当的列车任务与进行的各种作业的有序集合称为一条“基本交路”，简称“交路”，等同于运用交路的概念。

(3)完整循环交路

不考虑二级检修条件下，对若干列车运用交路进行组合，在一定时间跨度内列车再次回到原始发地，这个过程夜行列车担当的列车任务与进行各种作业的有序集合称为“完整循环交路”。

(4)运用模式

图1 夜行列车独立运用模式

夜行列车运用模式分为独立运用和日夜套跑运用两种模式。独立运用是指列车只在夜间担任运用任务，白天在动车运用所整备停留，如图1所示。这种模式下的接续较为疏松，出现较大的运行干扰时，列车所受的影响不大，但是运用效率较低，个别时候存在尚未达到修程标准却不得不入库检修的情况，因此这种方式动车组检修次数较多。日夜套跑运用是指列车夜间担任夜行任务后，在车站进行整备，继续担任本线或其他线路日间列车运行任务，如图2所示。这种模式下，列车接续较为紧密，出现较大的运行干扰时，列车所受的影响较大。相比独立运用模式运用效率大大提高，检修次数也在一定程度上有所减少。实际应用中可根据我国铁路现场实际，灵活采用不同的运用模式。

图2 夜行列车日夜套跑运用模式

1.2 问题特征及求解策略

夜行列车车底运用问题特征表现在以下4个方面。

(1)运用时间方面。现有高速动车组可总结为“日间运用(06：00—24：00)，夜间检修(24：00—06：00)”的运用模式，运用时间范围在当日6点至当日24点，运用时间跨度一般在数小时以内。夜行列车与此不同，其运用时间跨度在6 h以上，运用时间范围在当日17点至次日9点。由于夜行列车白天可继续套跑日间运用任务，因此运用时间大大增加，担当下次夜行任务前列车往往就已达到修程而不得不在日间完成一级检修。

(2)交路时间跨度。现有高速动车组运用交路一般由若干交路段组成，时间跨度在2 d以上。夜行列车运用时间和走行距离较长，如果连续2次担当夜行任务势必会超出列车的检修修程。因此其交路时间跨度可缩短至24 h以内。此时，运用交路称为基本交路。

(3)约束因素。由于涉及夜行列车日间套跑，列车时空接续要求更为复杂。同时，为尽可能接近我国铁路实际，特别考虑夜行列车车型、多基地情况下列车配属关系、车型和检修点匹配等约束。

(4)优化目标。现有高速动车组运用问题大多以接续时间最小或动车组使用数量最少为目标函数，从而使管理成本最小化。由于不存在同一列车同一天担当2次夜行任务的情况，因此夜行列车开行方案确定后开行对数往往就决定了运用车底的数量。这里，以车底运用不均衡度和非配属地一级检修次数为优化目标。车底运用不均衡度表现为各列车与所有列车运用距离或运用时间的偏差程度，用标准方差表示。数值越大反映列车之间运用差异越大，从而越不利于日常列车调度的调整。现有管理体制下，由于列车在非配属地检修将会因沟通和协调使管理成本上升，因此希望非配属地检修次数越少越好。

借鉴现有高速动车组运用问题中分步求解[12]的策略，提出将夜行列车交路计划编制过程分成“基本交路生成”和“完整循环交路生成”两个阶段。

基本交路生成主要解决“列车在第一天怎么走”的问题，作为后一阶段模型的输入。它是指根据修程修制，按照一定接续原则生成所有可行的基本交路。主要是通过运行线调整，合理组合，完成计划规定的所有夜行运用任务和检修任务，条件允许的情况下可多次套跑日间运用任务。根据夜行列车夜间运用里程和始发终到站检修条件的不同，套跑可分为以下3种形式。

(1)终到站短交路套跑。列车到达终点站后，合理套跑若干日间短交路，返回后入库进行一级检修。适用于列车夜行运用里程在2 000 km及以上的情形。如图3所示。

图3 终到站短交路套跑

(2)立折套跑。列车到达终点站后，立即套跑日间返程交路。一般情况下不再担当其他短途的日间运用任务。适用于列车夜行运用里程2 000 km以下的情形。如图4所示。

图4 立折套跑

(3)检修套跑。夜行任务的始发或终到站无检修条件，而列车又不得不进行一级检修时，需套跑该站与具备该车型检修条件的检修点所在站之间的短交路。如图5所示。

图5 检修套跑

基本交路生成阶段，若考虑日间套跑，相关约束较为复杂且与实际结合紧密，尤其涉及夜行列车在日间担当的运用任务与现有运行图匹配，列车运行线调整以及由此导致的现有高速动车组运用调整等问题，往往需要现场经验丰富的技术人员完成，本文暂不做深入探讨。作为后一阶段模型的输入条件，将基本交路生成简化为运用任务之间的紧密接续，套跑的日间交路以现有高速动车组开行的区段为依据，暂不考虑现有列车时刻表。这一阶段可转化为经典问题，已有的研究方法[13]即可求解，本文不再赘述。

完整循环交路生成主要解决“列车在接下来几天怎么走”的问题，是本文重点研究的内容。这一阶段列车采用周期性运用方式，列车各天担当的运营任务具有一定规律性，便于列车运用组织与管理。此阶段特别考虑车型、列车配属关系、车型和检修点匹配等约束条件，生成一定时间跨度内列车交路任务的组合序列，通过指定具体的列车来担当该组合序列，并且循环执行，从而形成完整的循环交路。这个时间跨度就是列车的运用周期。主要方法是将该问题归结为多旅行商问题，构建基于MTSP的列车车底运用网络，建立车底运用优化模型，并利用改进的深度优先搜索算法对模型进行求解。

2 模型与求解

2.1 模型建立

构建以基本交路为点，以交路间接续关系为有向弧的列车接续网络，表示为加权有向图D=(V,A)。V和A分别表示图D中的点集合与有向弧集合。

A={aij=(vi,vj),vi,vj∈V}是D的弧集合，弧对应基本交路之间的接续关系。

在列车接续网络基础上，为表述列车与交路的接续关系，定义如下变量

(1)

(2)

则循环周期t内列车k累计运用里程、累计运用时间、非配属地检修次数可分别表示为式(3)～式(5)

(3)

(4)

(5)

基于上述变量，车底运用优化模型可以描述为：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

式(6)表示车底运用不均衡度，即Ne个列车在编制周期t内以里程为标准的修程利用系数的总体标准误差，其中L表示列车一级检修修程；式(7)表示编制周期t内Ne个列车在非配属地一级检修的次数；式(8)为目标函数，表示车底运用不均衡度和非配属地一级检修次数的加权和最小，w1和w2为权重系数；式(9)～式(15)为模型约束条件。其中：式(9)和式(10)保证1天中每个基本交路仅有1个列出担当，并且每个列车一天内仅担当1个基本交路；式(11)保证终到站和所接续的交路的起始站为同一车站；式(12)中Tc表示两个交路之间最小接续时间标准；式(13)、式(14)和式(15)保证列车在一个编制周期结束后回到配属地。模型中也考虑了车型和检修点约束，即某种型号的列车k只能担当终到站具备该型号列车检修条件的基本交路，即模型中的k∈Ex，i∈Vx。

2.2 求解算法

车底运用问题属于典型的NP-hard问题，直接求解比较困难。本文中将这一问题分解为两步。第一步生成列车k在编制周期t内满足模型中约束条件的基本交路序列的可行集，同理依次生成所有列车的基本交路序列可行集，这一步通过计算机遍历基本交路集合V即可求解；由于每个列车交路序列的可行集在同一天可能会有冲突，因此第二步对所有列车的基本交路序列组合生成满足约束条件的列车运用方案，这一步利用改进的深度优先搜索算法求解。

图6 遍历搜索示意

深度优先搜索算法实质上是一种枚举法，如果不加任何约束条件，就是寻找从起点到终点之间的所有可能的组合，对于本问题任意两个起点到终节点之间的组合数量都是非常巨大的，因此这里引入启发函数。所谓启发函数就是增加一部分约束条件，以减少搜索计算量。它的含义主要体现在以下两个方面。

一方面搜索的过程中需要判断前后节点组合时是否存在冲突，如果有冲突则可以终止组合，返回上层节点(回溯)继续搜索。这里的冲突主要指编制周期某一天中出现了相同的两个基本交路编号。

(16)

引入启发函数后搜索计算量往往也非常巨大，因此将解的数量达到Num作为算法的终止条件。

这一阶段模型求解步骤如下。

Step1：数据准备。包括3类数据：交路数据，其属性有交路编号、始发站、终到站、起始时间、终到时间、运用距离、可运行车型；列车数据，其属性有列车序号、配属地点、车型；基础数据，包括接续时间、编制周期、一级检修修程等。

Step3：初始化。确定α、β、w1、w2、Num和其他相关参数的初始值。

Step4：根据启发函数进行深度优先搜索，形成完整循环交路，不断更新最优解，如图7所示。

Step5：输出完整循环交路的组合序列和最优解。

图7 深度优先搜索流程

3 案例研究

本文以京广高速夜行列车开行方案数据[7]为基础，对车底运用方案进行实例研究。

3.1 开行方案及相关参数

开行方案：京广高速铁路夜行列车最高运营速度均为250 km/h，共开行列车11对。其中北京西—武汉1对；北京西—长沙南2对，其中1对经停武汉；北京西—广州南1对；北京西到深圳北1对，经停石家庄和广州南；郑州东到深圳北1对，经停广州南；北京西到西安北2对；西安北—长沙南1对；西安北—深圳北1对，经停广州南；南京南—深圳北1对，经停广州南。

作业参数：列车立折时间取20 min；两交路接续时间Tc取140 min；列车车型均为CRH2E车型；列车一级检修修程为4 000 km。

算法参数：编制周期t取4 d；w1、w2分别取80和0.2；α、β分别取0.02和0.2；Num取100 000，当产生新解的次数为100 000时搜索结束。

车辆及检修条件：全部配属CRH2E车型，共计22组列车。其中7组配属北京西动车运用所，4组配属广州南动车运用所，5组配属武汉动车运用所，4组配属西安北动车运用所，1组配属郑州东动车运用所。对于无检修条件的长沙南(有检修点，无技术条件)和深圳(无检修点)，通过套跑形式分别安排到武汉和广州南检修点进行检修。同时增加广州CRH2型车的运用检修技术条件。

3.2 计算结果

基本交路生成阶段共有22个基本交路，平均运行里程为2 938.045 km，如表1 所示。利用C#编程求解得到的完整循环交路，车底运用不均衡度为5.93%，非配属地检修次数为25次，完整交路计划如表2所示。

3.3 结果评价

编制结果表明，车底运用不均衡度5.93%和异地检修次数25次已接近理论最优解上界的5.87%和20次，如表3所示。由此可见，在暂不考虑对日间列车影响的情况下，本文所提出的模型和算法可有效解决夜行列车车底在日间和夜间综合运用和优化等问题，从而为我国高速夜行列车的开行提供一定的技术支持。

表1 基本交路

注：①表示列车进行一级检修任务，检修地点为接续车站所在的动车运用所。

表2 完整交路计划

表3 编制结果

注：1.理论最优解上界的确定方法为：分别将不均衡度和异地检修次数作为单目标条件进行求解所得结果。

2.理论最优解下界的确定方法为：分析计算在接续条件最差的情况下的不均衡度和异地检修次数。

4 结语

本文对夜行列车车底运用问题这一新的研究方向进行了初步探索，重点研究了完整循环交路阶段模型构建和求解算法，提出了夜行列车运用的两种模式，并对周期性运用方式下的交路计划求解策略进行了分析；针对完整循环交路阶段，建立以车底运用不均衡度和列车在非配属地一级检修次数为目标函数的优化模型，利用改进的深度优先搜索算法进行求解；最后以京广高速夜行列车车底运用方案为例进行验证，表明了模型和算法的有效性。

日夜套跑运用模式下，高速夜行列车的开行势必要对运行图和现有高速动车组周转运用产生较大影响，本文未予考虑，未来面向日夜运行列车协同优化的动车组综合运用方案将是一个新的研究方向。此外，本文只研究了夜行列车交路计划编制方法，对于夜行列车检修计划和乘务计划也是需要进一步研究的问题。

[1] 聂磊，胡必松，付慧伶，等. 客运专线夜间行车与天窗的相互影响分析[J].交通运输系统工程与信息，2010，10(5)：66-72.

[2] 徐小勇.客运专线开行夕发朝至旅客列车的可行性研究[J].价值工程，2010(10)：141-142.

[3] 王相平，花伟，李博，等.基于矩型天窗下客运专线开行夕发朝至列车的可行性研究[J].铁道运输与经济，2014(11)：16-17，48．

[4] 彭其渊.客运专线运输组织[M].北京：科学出版社，2007.

[5] 朱文亭.高速铁路“夕发朝至”跨线列车运输组织研究[D].成都：西南交通大学，2011.

[6] 胡秀婷.京沪高速铁路综合维修天窗设置[J].交通运输工程与信息学报，2011，9(3)：103-110.

[7] 王超.京广高速铁路夜行列车开行方案研究[D].北京：北京交通大学，2014.

[8] 赵鹏，张迦南.铁路动车组的运用问题研究[J].北京交通大学学报，2009，33(3)：6-10，16.

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

[10]王忠凯.动车组运用检修计划优化方法的研究[D].北京：中国铁道科学研究院，2012．

[11]李华.高速铁路动车组运用计划编制理论与方法研究[D].北京：北京交通大学，2013．

[12]曲思源，徐行方.城际铁路动车组运用计划模型[J].同济大学学报：自然科学版，2010，38(9)：1298-1302．

[13]吴冰芝.客运专线动车组运用优化研究[D].成都：西南交通大学，2012.

Research on Circulation and Optimization of High-speed Night Train

HAN Bao-ming1， SUN Shi-zhao1， ZHENG Bin2， ZHANG Qi1

(1.School of Traffic and Transportation， Beijing Jiaotong University， Beijing 100044， China; 2.China Railway Engineering Consulting Group Co.， Ltd.， Beijing 100055， China)

The main differences between high speed night train and the existing high-speed EMU lie in the range and span of operation time， which may lead to the changes of operation conditions. On the basis of the summary of the characteristics of circulation plan for the night train， this paper proposes a strategy to solve the problem by dividing the solution process into two phases: fundamental circulation plan and full circle circulation plan. The former is the input of the latter’s model. Then a mathematical optimal model is established to minimize the inequality of operation and frequency of vehicle maintenance in other operation depots， which is fulfilled with improved depth-priority search algorithm and verified with data from Beijing-Guangzhou high-speed night train. The results show that the proposed method is effective to solve the problem of night train circulation and may provide technical support to the operation of night train.

Night train; Operation pattern; Circulation planning; depth-priority search algorithm

2014-11-17；

2014-11-26

国家科技支撑计划(2009BAG12A10)；国家自然科学基金联合基金项目(1434207)

韩宝明(1963—)，男，教授，博士生导师。

1004-2954(2015)07-0009-06

U292.3

A

10.13238/j.issn.1004-2954.2015.07.003