客运站到发线运用优化研究综述

江 秀，倪少权，陈钉均

（1. 西南交通大学 交通运输与物流学院，四川 成都 610031；2. 西南交通大学 全国铁路列车运行图编制研发培训中心，四川 成都 610031；3. 西南交通大学 综合交通运输智能化国家地方联合工程实验室，四川 成都 610031）

车站到发线运用计划是规定车站某一阶段内所有到发列车占用到发场具体线路和时间的计划，是车站行车技术作业的关键性工作之一[1]。车站到发线运用计划的科学与合理，直接关系到车站的能力。客运站到发线运用优化，不仅能提高车站的行车技术管理水平和运输生产效率，而且有助于提高客运站行车技术作业自动化水平。客运站到发线运用优化研究综述主要从模型种类、模型算法、目标函数与约束条件 3 个方面分析已有研究成果。

1 研究现状

1.1 模型种类

1.1.1 0-1规划模型

目前，到发线运用优化模型中，0-1 规划模型应用最为广泛。0-1 规划模型还包括一次 0-1 规划模型[2-3]、二次 0-1 规划模型[4-8]及混合 0-1 规划模型[9-14]。

（1）一次 0-1 规划模型方面，何林等[2]以方便旅客上下车为目标，建立高速铁路车站到发线运用的一次 0-1 规划模型，并利用遗传算法进行求解。陈建鑫等[3]所建模型也为一次 0-1 规划模型，所不同是其将到发线的运用当作指派问题进行研究，采用指派问题常用的匈牙利算法进行求解。

（2）二次 0-1 规划模型方面，吕红霞等[4]采用“时间片”法，以可行性与交叉干扰最小为目标函数，以 1 列列车只能占用 1 条到发线，同一时间片内的列车不能安排至同一到发线为约束条件，建立了二次 0-1 规划模型，并通过分解，将其化为 2 个简单的 0-1 规划模型进行求解。有关研究是通过构建二次 0-1 规划模型研究到发线的运用优化，只是目标函数、约束条件与求解算法有所不同[5-8]。

（3）混合 0-1 规划模型方面，高建等[9]以出发列车正点、保持到发线固定使用方案与保证高等级列车优先接发为优化目标；以 2 列车占用到发线的起始时差的关系不等式来表示时间相冲突的 2 列相邻列车占用同一到发线的约束条件 ( 非“时间片”法 )，建立了到发线运用的混合 0-1 整数规划模型，并采用模拟退火算法进行求解。构建混合 0-1规划模型研究到发线运用优化[10-14]的研究中，林志安等[10-11]对约束条件的考虑比较全面，如需要进行上水作业的列车、行邮作业量大的列车对到发线的要求；同一站台两侧的到发线最好不要同时安排2 列出发时刻相近的列车或 1 列出发和 1 列到达列车等约束。

综上所述，一次 0-1 规划模型的目标函数单一，约束条件较少，适用于简略分析；当需要考虑多项目标，约束条件较全面时需要建立二次 0-1 规划模型或混合 0-1 规划模型才能更贴切地反应实际情况。

1.1.2 排序模型

以张贵英、Kroon 为代表的国内外学者，利用排队理论构建排序模型研究到发线运用优化问题。张贵英等[15-16]以列车接入的可行性与到发线运用的均衡性为目标，将到达的列车作为排队论中的服务对象，将到发线作为排队论中的服务机构，以列车在车站的作业时间作为排队论中的服务时间，以“先到先服务”原则、“权重大小”原则与“有限度大小”原则作为排队论中的服务原则 ( 选用原则视具体情况而定，可以单原则，也可以多原则组合 ) 建立第 3 类多目标排序模型，并利用启发式算法进行求解，得到车站到发线运用的初始方案。Kroon 等[17]在从安全角度出发，在研究特定列车的作业进路时，只考虑该进路是否可行，以及进路只由 1 个路段组成，将车站到发线运用问题看成具有固定时间窗口的排序问题，从而建立到发线运用优化的排序模型。

1.1.3 其他模型

其他模型主要是指动态规划模型[18]、图着色模型[19]、可交替图模型[20]与随机机会约束规划模型[21]，而到发线运用优化采用这些类模型的研究较少。

朱亮等[18]考虑到同一车场内t2时刻到发线状态由t1时刻起始状态和t1至t2时段内接入及发出的列车决定，提出到发线运用优化问题是一个多层约束条件动态规划问题，以时刻表的刻度作为基本步长λ，建立到发线运用状态转移方程，以到发线剩余价值 ( 剩余到发线结构重要度指数之和，结构重要度由结构重要度分析法确定相应权重值 ) 最大为目标函数，建立动态规划模型。由于该模型中的动态转移方程的决策变量仅涉及到发线数量，因此利用该模型所求得的解仅是符合功能要求的解，后续还需要进行到发线占用冲突检验，以及考虑到发线均衡运用等。

Cardillo 等[19]将列车表示为无向图的顶点，不能安排至同一到发线的 2 顶点相连表示为无向图的边，采用颜色集合表示到发线的集合，然后使用颜色集合给无向图中所有顶点逐一着色，并使任何相邻顶点所着颜色互不相同，用颜色dj给顶点vi着色表示将列车vi安排到发线dj，构建图着色模型。所建模型以到发线使用条数最少为目标函数，利用启发式算法进行求解。

夏明等[21]考虑到到发线运用过程中的不确定因素，如旅客上下车延误、车站作业等，研究了旅客列车停站时间和接续时间随机变动情况下的到发线运用优化问题，以提高车站作业效率和方便旅客乘降为目标，建立了到发线运用随机机会约束规划模型。

1.2 目标函数与约束条件

到发线合理运用的优化目标如表 1 所示。

表1 到发线合理运用的优化目标

在现有研究成果中，大部分所建模型为表中各单目标组合的多目标模型，少部分为单目标模型。这些研究主要包括：以到发线均衡使用、方便旅客乘降与有利于车站行车技术作业的组合为优化目标[8，22]，以有利于车站行车技术作业与行车作业交叉干扰最小的组合为优化目标[4]，以到发线均衡使用与列车站内走行时间最短的组合为优化目标[13]，以有利于行车技术作业与列车正点发车率最大的组合为优化目标[9]，以到发线均衡使用与总误工数最小的组合为优化目标[15]，以到发线均衡使用与列车在到发线上停留时间最短的组合为优化目标[23]，以到发线均衡使用构建单目标优化模型[24]，以方便旅客乘降构建单目标优化模型[2-3]等。

到发线运用优化模型所涉及的约束条件主要有以下方面。

（1）1 条到发线同一时间内只能接发 1 列列车。

（2）1 列列车在同一时间只能占用 1 条到发线。

（3）到发线作业的间隔时间约束。

（4）时间上存在重叠的 2 列车不能接入同一到发线。

（5）所有可能出现交叉干扰的列车均按平行进路接发列车。

（6）通过列车安排于正线。

（7）有上水要求的列车必须安排到有上水设备的到发线。

（8）有行包、邮政作业的列车必须安排接入靠近行包、邮政通道口站台的到发线。

（9）要求接入基本站台的列车必须安排靠近基本站台的到发线。

（10）存在换乘关系的 2 列车应安排在临靠相同站台的到发线上。

（11）终到站由同一车底担当的 2 列折返列车要安排在同一到发线上。

1.3 模型算法

到发线运用优化模型求解目前主要包括分层求解思想和直接求解思想。

分层求解是将目标问题分解成几个子问题，依次优化，分解后的子目标多是线性的，可以直接采用一些常用软件 ( 如 LINGO )，也可以考虑用运筹学中比较成熟的算法求解，如单纯形法[4]、分枝定界法[8]、匈牙利解法[3]等。吕红霞等[4]将 1 个二次0-1 规划模型，分解成 2 个子模型，分别采用分枝定界算法与单纯形法求解；雷定猷等[8]将 1 个多目标模型分解为 2 个模型，其中一个为一次 0-1 规划模型，采用分枝定界算法求出可行解，在此可行解的基础上再采用人机交互考虑另一模型。

直接求解即是寻找有效的搜索寻优算法直接对所建模型进行求解。客运站到发线运用优化研究所涉及的搜索寻优算法主要有：遗传算法( Genetic Algorithm，GA )、蚁群算法 ( Ant Colony Optimization，ACO )、模拟退火算法 ( Simulation Annealing，SA )、模因演算法 ( Memetic Algorithm，MA )、基于捕食策略的禁忌搜索算法 ( Tabu Search，TS )、克隆算法 ( Immune Clonal Selection Algorithm，ICSA )。基于 CNKI 相关文献，统计得出到发线运用优化模型常用算法情况如图 1 所示，遗传算法与分枝定界算法在到发线运用模型中使用频率较高，而禁忌搜索算法与蚁群算法使用较少，后续研究者可以尝试这 2 类算法的探索研究。

图1 到发线运用优化模型常用算法统计

2 研究评述

2.1 参数 Cij 的确定

在以有利于车站行车技术作业为目标的模型中，有些研究使用参数Cij，这一参数表示第i列列车由第j条到发线接发的权值。Cij取值描述如表 2 所示。其中，类别 1 中Cij是由历史数据和工作人员的经验得出，但是否符合到发线固定使用方案，如何得出，凭借什么经验，涉及哪些因素没有做出明确阐述；类别 2 中Cij的设定方法是否符合车站实际工作仍有待探讨。

2.2 到发线运用与相关作业的综合考虑

到发线运用与进路选择、机车作业的综合研究较少，而国外研究主要将到发线安排与列车作业进路、运行图等进行综合考虑。始发终到客运站，以及机车换挂站均存在着机车作业，机车作业对到发线的运用具有较大影响，而相关研究较少，其中提及到发线相关作业包括机车作业，但是实际所建模型均未考虑机车作业影响因素[7，22]。铁路实际生产作业中，在始发站，机车需要出段至到发线或机待线；在终到站，机车需要从到发线或机待线入段；机车出入库和机车换挂的作业进路将占用车站咽喉区，对车站接发列车或者其他技术作业将产生进路冲突。因此，如果到发线安排不合理，会导致机车走行时间、占用咽喉时间、列车占用到发线时间过长，严重影响车站接发列车能力。因此，客运站到发线运用优化模型的后续研究应将机车作业这一约束加入考虑，使得到发线的运用方案更好地满足生产实际要求。

表2 取值描述

2.3 到发线运用优化的研究方向

（1）到发线权值的确定。对到发线权值设定的影响因素与取值方法还需要进一步明确研究，只有到发线的权值赋值恰当，求得的方案才能客观合理。

（2）到发线运用与相关作业的协调优化研究。只有综合考虑进路、机车等到发线相关作业，才能建立更加符合实际的到发线运用优化模型，进而提高到发线运用方案的可行性。

（3）求解算法研究。研究更好的模型求解算法，从而保证能更快更准确地得到满意的解，提高解决实际问题的能力。

3 结束语

制定科学合理的到发线运用计划，优化安排列车的接发顺序和位置是应对目前客运专线车站接发旅客列车数量成倍增长、到发线能力日趋紧张的状况，保障行车安全，提高行车效率的关键[22]。以上从模型种类、求解算法、目标函数与约束条件 3 个方面，对客运站到发线运用模型的现有研究成果进行的综合分析，为到发线运用优化的进一步研究提供参考。

[1] 李宇航. 大型客运站高峰期到发线运用优化方案研究[D].北京：北京交通大学，2010.

[2] 何 林，吕红霞. 高速铁路车站到发线运用优化研究[J]. 铁道运输与经济，2012，34(18)：47-50，66.

[3] 陈建鑫. 高速客运站到发线运用优化安排[J]. 科技论坛，2008(1)：26，73.

[4] 吕红霞，倪少权，纪洪业. 技术站调度决策支持系统的研究——到发线的合理使用[J]. 西南交通大学学报，2000，35 (3)：255-258.

[5] 吕红霞，何大可，陈 韬. 基于蚁群算法的客运站到发线运用计划编制方法[J]. 西南交通大学学报，2008，43(2)：153-158.

[6] 郭 莉，吕红霞，陈焕云. 基于遗传算法的铁路本站到发线运用优化研究[J]. 西南交通大学学报，2005，31(1)：28-31.

[7] 郭吉安，石红国. 客运专线与既有线衔接车站到发线运用优化研究[J]. 交通运输工程与信息学报，2012，10(2)：132-136.

[8] 雷定猷，王 栋，刘明翔. 客运站股道运用优化模型及算法[J]. 交通运输工程学报，2007，7(5)：84-87.

[9] 高 建. 基于模拟退火算法的客运站到发线运用优化研究[J]. 交通科技与经济，2011(4)：73-75.

[10] 林志安，潘玲巧. 基于 Memetic 算法的客运站到发线分配问题研究[J]. 兰州交通大学学报，2008，27(6)：80-82.

[11] 林志安，潘玲巧. 铁路客运站到发线分配问题研究[J]. 铁道运输与经济，2010，32(10)：58-61.

[12] 乔瑞军，朱晓宁，张天伟. 客运专线车站到发线运用多目标优化模型[J]. 北京交通大学学报，2012，36(3)：57-64.

[13] 乔瑞军. 客运专线车站接发车进路选择与调整问题研究[D]. 北京：北京交通大学，2012.

[14] Biilionnet A. Using Integer Programming to Solve the Train-Piatforming Problem[J]. Transportation Science，2003，37(2)：213-222.

[15] 张英贵，雷定猷，刘明翔. 铁路车站股道运用排序模型与算法[J]. 中国铁道科学，2010，31(2)：96-99.

[16] 张英贵. 铁路客运站股道运用优化方法与应用研究[D]. 长沙：中南大学，2012.

[17] Kroon L J，Romeijn H E，Zwaneveld P J. Routing Trains Through Railway Stations：Complexity Issues[J]. European Journal of Operational Research，1997，98(1)：458-498.

[18] 朱 亮，周浪雅，诸葛恒英. 大型客运站到发线运用及进路决策模型研究[J]. 铁道运输与经济，2013，35(6)：46-51.

[19] Cardillo D D L，Mione N. k L-list Colouring of Graphs[J].European Journal of Operational Research，1998，106(1)：160-164.

[20] D’Ariano A. Improving Real-Time Train Dispatching Models，Algorithms and Applications[D]. The Netherlands：Delft University of technology，2008.

[21] 夏 明，周磊山，乐逸祥. 客专大站到发线运用随机机会约束模型与算法研究[J]. 物流技术，2010 (4)：54-58.

[22] 李 琦. 高速铁路大型客运站到发线运用优化研究[D]. 成都：西南交通大学，2012.