旅客列车始发方案研究综述

陈钉均，倪少权，吕红霞，吕苗苗

（西南交通大学 交通运输与物流学院，四川 成都 610031）

1 研究目的与意义

作为铁路旅客运输组织的基础，旅客列车运行图是对旅客列车运行时间、空间关系的图解表示，是旅客列车在区间运行及在车站到发或通过时刻的技术文本，是受多种因素制约、技术性强的综合运输计划。在铺画旅客列车运行图前，无论是手工铺画还是计算机铺画，首先需要确定各旅客列车运行线的始发点，即各次旅客列车的始发时刻。只要旅客列车在始发站或终到站的出发或到达时刻确定了，整个旅客列车运行图的骨架也就随之确定[1]。

旅客列车始发方案主要解决旅客列车运行线布局问题，是编制旅客列车运行图的重要前提，也是旅客列车运行图的骨架和核心，直接影响旅客列车运行图质量。同时，合理的旅客列车始发方案不仅能够满足旅客对出行时间和服务质量的要求，提升铁路旅客运输的市场竞争力，也能够充分利用现有客运站设备和客车整备所设施，提高客运站作业组织的质量和效率。提高旅客运输效率可以节约运营成本，增加运营收入。总之，合理的旅客列车始发方案能够同时兼顾铁路部门和旅客的利益，提高铁路旅客运输组织水平，具有重要的理论意义及现实意义。

2 国内外研究现状及存在问题

2.1 研究现状

对于旅客列车始发方案的研究，由于路情的不同，国外的研究主要集中在时刻表 ( 运行图 ) 的编制方面[2-5]，单独对旅客列车运行图编制的初始阶段——旅客列车始发方案的研究还比较少。目前，国内外对该领域的研究主要集中在以下方面。

（1）无约束条件的列车始发方案研究。符卓通过定量化方法将旅客列车运行方案图编制问题转化为一个多目标优化问题，运用分层序列法解决问题的思路，按照各目标的重要性程度进行求解，并且给出了第一层优化目标——方便旅客出行的启发式算法。其具体通过定义合理始发时间范围、合理终到时间范围、合理到发时间范围、合理始发区间等概念，将定量与定性相结合，运用匈牙利算法，提出方便旅客出行的列车出发点优化方法[1]。郭富娥通过讨论列车会让、枢纽站行车间隔、列车运行线调整等处理方法，提出人机相结合编制旅客列车运行方案图，并开发了计算机辅助编制旅客列车运行方案的软件，得到了相应的运用[6]。符卓针对只将 24 小时分为合理和不合理到发时间的范围过宽情况，结合每个时间段列车到发对旅客方便程度不同的特点，将 24 小时划分为多个方便程度不同的时间段，将方便旅客出行问题转化为指派问题，对列车的到发点进行整体优化[7]。

（2）经济合理使用车底的列车始发方案优化方法研究。经济合理使用客车车底是编制旅客列车运行方案图时需要考虑的主要目标之一。符卓通过对该问题的分析和归纳，提出基于启发式算法的合理使用车底的到发区间组合中的始发区间；基于指派问题的合理始发区间的全局优化，得到满意始发区间；基于指派问题的满意始发区间所对应的所有合理终到区间组合进行全局优化，得到所有的最优到发区间组合[8]。王慈光应用同余理论，分别对旅客列车无约束条件的合理发车范围、照顾途中大站的合理发车范围、考虑客车车底折返情况的合理发车范围、既考虑车底折返又考虑途中大站的合理发车范围 4 种情况，提出了运用代数方法计算旅客列车合理发车范围[9-10]。张玉召等通过概括旅客列车始发时间范围的影响因素，分析车底需要数量与列车始发时间范围之间的关系，提出以客运站始发旅客列车车底在配属站和折返站停留时间之和最少为目标的旅客列车始发时间域数学优化模型，并给出了传统方法与启发式方法相结合的算法求解模型[11]。潘锋讨论了影响客车运用效率的主要因素，分析了车底需要数量与车底在站停留时间之间的关系，提出了优化客车使用的多种措施，同时讨论了提高动车组运用效率问题[12]。

（3）方便换乘的列车始发方案优化研究。陈玲玲等针对旅客换乘的需要，为使各方向旅客列车的到达时刻相互衔接以减少旅客中转换乘时间，分析了两列不同方向的旅客列车到达途中换乘站时间的相互关系；以先到达途中换乘站的列车发车时刻为基点，应用同余理论，用代数方法计算出后到达列车的发车时刻，进而求得可行解[13]。徐瑞华等在讨论首末班列车协调必要性的基础上，以多线换乘接续的可达性和合理性，建立多向列车换乘衔接模型，并依据早晚间客流的特点，提出首末班列车发车时间域的计算方法；该模型和方法为旅客列车运营组织提供必要的决策依据[14]。

（4）客运站设备能力约束下的列车发车时间域研究。陈团生等在基于大量问卷调查的基础上，确定了旅客出行在各发车时间域的方便系数，并运用目标规划原理，以方便旅客出行程度最大为目标，并构造了三级控制策略；考虑客运站到发线发车能力和旅客列车必须在合理的时间范围发车等约束条件，建立了旅客列车发车时间域的目标规划模型[15]。倪少权等建立了以到发线、客车整备线能力为约束，车底使用数最少为目标的数学优化模型，讨论了运行区段内旅客列车的始发时间范围问题，并设计了启发式遗传算法对模型进行求解[16]。

（5）旅客对列车发车时间的偏好选择研究。马建军等以基于网状线路高中速列车行车组织模式为前提，利用计算机仿真技术研究了跨线中速列车在既有线始发、终到时间域的计算方法[17]。史峰等通过分析不同旅客对列车始发时间分布的需求，同时考虑列车能力对客流分布的作用及旅客群体选择行为，设计了基于旅客列车始发时间分布的旅客出行选择网络，提出以旅客出行总费用最少为优化目标，并建立了旅客列车始发时间分布的双层规划模型，同时给出了模拟退火启发式算法对模型进行求解[18]。

（6）天窗条件下列车始发方案研究。张玉召等通过分析既有线旅客列车合理发车范围确定方法，详细分析了客运专线开设垂直矩形天窗条件下跨线旅客列车的合理发车域的确定方法，应用同余理论，讨论了上线列车、下线列车、既上线又下线列车、多次上线和下线列车等情况下，列车的合理始发范围确定方法[19]。

2.2 有关研究存在的问题

从旅客列车始发方案编制问题的有关研究成果来看，国内外专家学者对旅客列车始发方案问题的模型及求解算法进行了有益的探索，但是仍存在以下主要问题。

（1）研究成果的适用性。国外铁路线路能力及车站能力均比较充裕，研究主要集中在方便旅客及方便换乘等方面，因此国外的研究成果不完全适用于我国国情。目前，旅客列车始发时间主要由编图人员凭经验采用试探的方法在较宽的时间窗里寻找，直到结果满意为止，没有考虑整体优化始发时间点以供编图人员选择，影响了编图质量；并且对列车运行图的编制与优化，大多只考虑区间运行情况，较少考虑客运站设备能力，特别是未考虑始发、终到站的客车整备线能力的影响。

（2）模型的可行性。目前，有关研究主要从旅客方便性 ( 合理始发、终到时间 ) 和企业经济性( 节约车底 ) 两方面确定旅客列车始发方案，没有考虑我国大型客运站因政治、经济原因需开行大量列车而造成客运站设备能力，尤其是到发线能力、客车整备线能力相对紧张的实际情况，易造成旅客列车始发方案难以实施。

（3）求解算法的有效性。实际规模的旅客列车始发方案问题是一个大型的组合优化问题，并且基于客运站到发线与客车整备线协调使用的旅客列车始发方案问题是一个复杂度很高的NP ( Nondeterministic Polynomial ) 问题。对于 NP 问题的求解，学术界至今还没有成熟的理论和方法。因此，有必要对旅客列车始发方案的求解算法进行深入研究。

3 研究展望

3.1 研究目标

旅客列车始发方案的编制需要综合考虑客流需求、车底运用、客运站到发线能力、客车整备线能力、路网天窗设置等因素，在旅客列车开行方案及各车站线路相关数据已确定的基础上，实现旅客列车始发时间与客运站设备能力协调的优化编制。依据不同情况，具体实现以下目标：旅客列车始发时间域的优化编制；既有线旅客列车始发方案的优化编制；高速铁路旅客列车始发方案的优化编制。

3.2 研究内容

针对已有研究存在的不足，在现有相关研究工作的基础上，综合考虑方案的方便性、经济性和可行性，对旅客列车始发方案编制问题作进一步的研究。

（1）考虑客运站设备能力条件下旅客列车始发方案的编制问题。为提高旅客列车服务质量和吸引客流，需要将列车始发、终到时间安排在“黄金时段”，这将形成旅客列车在某一时间段密集到发，造成客运站接发车能力与区间通过能力紧张。另外，旅客列车的始发终到时刻影响动车组及车底的接续关系，进而决定运载工具的运用效率。因此，合理编制旅客列车始发方案对于充分发挥我国铁路技术与经济效益有重要影响。

（2）考虑天窗开设条件下旅客列车始发方案的编制问题。除客运站设备能力影响旅客列车始发方案的可行性外，天窗的开设对旅客列车的运行及线路的通过能力都有一定的影响。因此，天窗开设与旅客列车始发方案编制的协同优化是值得研究的问题。

（3）高速铁路动车组列车始发方案的编制问题。高速铁路动车组列车与既有线旅客列车有很大的区别，高速铁路一般采用公交化的周期运行图，旅客对出行时间也有更高的要求，加之目前高速铁路的快速发展，动车组列车始发方案的编制问题也是值得研究的重要内容。

（4）从旅客列车始发方案到运行图优化的过渡问题。旅客列车始发方案编制的研究只解决了列车运行线的整体布局，未考虑旅客列车在区间运行时可能产生的冲突，并且未对旅客列车途经大站占用到发线等问题给予讨论，这在一定程度上将影响旅客列车始发方案的可行性。因此，有必要对旅客列车始发方案到运行图的过渡问题进行研究。

（5）基于稳定性的旅客列车始发方案编制问题。旅客列车始发方案的编制需要提高旅客列车运营组织的可靠性和保障列车的安全正点运行。目前，旅客列车开行数量众多，尤其是高峰时期，列车密度很大，容易形成前行列车晚点造成后行列车的连带晚点。因此，有必要讨论稳定性旅客列车始发方案编制问题。

3.3 研究方法

铁路旅客列车始发方案的优化编制问题是一个约束复杂的多目标决策问题，由于问题的组合优化特性，随着开行列车数量的增多，问题的求解难度也逐步增加。针对问题的特点，拟采用以下思路加以解决。

（1）简化思想。旅客列车始发方案的编制涉及列车运行计划和客运站技术作业两方面，而列车运行计划的编制本身就是一个影响因素众多的复杂问题，加上客运站能力、路网天窗设置等，问题规模更加庞大，很难找到问题的解。而该问题实质上是编制列车运行图的骨架，应尽可能提高其可行性。因此，考虑列车始发、终到站之间旅行时间确定的情况，而不考虑列车在各区间的运行情况，可简化问题的复杂性，使问题的求解变得可行。

（2）降维思想。针对铁路网客运站数量较多、开行的旅客列车数量庞大的特点，若对所有旅客列车始发方案同时优化编制，将是一个非常复杂的问题。因此，将客运节点站按照一定方法进行重要度排序，逐次优化各节点站旅客列车始发方案，将客运节点“多对多”列车始发方案问题转化为多个“一对多”问题。以 4 个客运节点为例，其转化思想如图 1 所示。

图1 客运节点分解图

其中，←→表示客运站之间有互发旅客列车，若客运节点站重要度排序为S1、S2、S3、S4，则首先编制S1与S3、S4之间互开旅客列车的始发方案，其次编制S2与S3之间互开旅客列车的始发方案，最后编制S3与S4之间互开旅客列车的始发方案。

（3）协同思想。旅客列车始发方案的编制受旅客列车开行方案、客运站设备能力和客车整备所整备能力三者的影响。因此，运用协同思想使旅客列车始发时间与客运站设备能力、客车整备所整备能力协调，得出可行的旅客列车始发方案。

（4）启发式智能算法。针对旅客列车始发方案模型的特点，综合运用模糊集理论、运筹学、组合数学、最优化理论和现代优化算法等相关理论，依照循序渐进的思路，设计高效的启发式算法，深入研究我国铁路旅客列车始发方案编制理论与方法。

4 结束语

旅客列车始发方案的编制是一个复杂的优化问题，针对有关研究存在的不足，需要综合考虑方案的方便性、经济性和可行性，为我国铁路旅客列车运行图的编制提供必要的理论支持，成为计算机编制旅客列车运行图的有效辅助手段。

[1] 符 卓. 旅客列车运行方案图优化编制方法的研究[J]. 铁道学报，1996，18(4)：10-17.

[2] Senzana M. Heuristic Approach to Train Rescheduling[J].Journal of Operation：Research，2007(7)：9-29.

[3] Vromans，M.J.C.M. Reliability of Railway Systems [D].Rotterdam：Erasmus University，2005.

[4] Alberto Caprara，Michele Monaci，Paolo Toth. A Lagrangian Heuristic Algorithm for A Realworld Train Timetabling Problem[J]. Discrete Applied Mathematics，2006，154(5)：738-753.

[5] Herrmann，T.M.Stability of Timetables and Train Routings through Station Regions[D]. Zurich： Swiss Federa Institute of Technologyzurich，2006.

[6] 郭富娥. 利用计算机编制旅客列车运行方案[J]. 铁道学报，1993，15(2)：71-75.

[7] 符 卓. 方便旅客旅行的列车到发点优化确定方法[J]. 长沙铁道学院学报，1998，16(3)：30-33.

[8] 符 卓. 优化车底使用数的客车运行方案图编制方法[J]. 铁道学报，1996，18(6)：6-13.

[9] 王慈光. 确定旅客列车合理开车范围的代数方法[J]. 西南交通大学学报，1998(2)：70-78.

[10] 王慈光. 运输模型及优化[M]. 北京：中国铁道出版社，2004.

[11] 张玉召，张红伟，文娟娟. 车底需要数最少的旅客列车始发范围优化模型[J]. 铁道工程学报，2011(4)：111-114.

[12] 潘 锋. 提高客车运用效率的研究[D]. 成都：西南交通大学，2005.

[13] 陈玲玲，王慈光. 基于旅客列车合理接续条件的发车时刻确定方法[J]. 西南交通大学学报，2007，42(2)：234-237.

[14] 徐瑞华，张 铭，江志彬. 基于线网运营协调的城市轨道交通首末班列车发车时间域研究[J]. 铁道学报，2008，30(2)：7-11.

[15] 陈团生，毛保华，何宇强. 旅客列车发车时间域优化研究[J]. 铁道学报，2006，28(4)：12-16.

[16] Ni Shaoquan，Chen Dingjun，Lv Miaomiao. Research on Optimization Model of Initial Schedule of Passenger Trains based on Improved Genetic Algorithm[C]. //IEEE Computer Society. 2009 International Coference on Intelligent Computing Technology and Automation. Los Alamitos：IEEE Computer Society Publications，2009：273-276.

[17] 马建军，胡思继，周 曦，等. 京沪高速铁路高中速列车到发时间域的计算方法[J]. 北方交通大学学报，2002，26(5)：28-31.

[18] 史 峰，黄铮诚，周文梁，等. 基于用户平衡分析的旅客列车始发时间分布优化[J]. 铁道科学与工程学报，2008，5(6)：69-75.

[19] 张玉召，严余松. 客运专线跨线列车合理始发范围的确定方法研究[J]. 兰州交通大学学报，2010(3)：79-82.