有限状态机在列车解编顺序中的应用

李新琴，牛林杰

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

编组站的主要工作是解编作业，合理地组织列车解体作业和编组作业时编组站调度工作的核心问题，同时解编作业的优化是整个阶段计划优化体系的关键内容之一。编组站阶段计划的优化还涉及配流方案以及到发线、调机合理运用，其中解体顺序和编组顺序的协调优化是整个阶段计划优化的纽带。对于编组站列车解编顺序的协调问题，本文采用调机的有限状态机模型，有限状态机是一种面向对象的状态机思想，可以适合于编组站复杂的情况状态管理。在铁路现场变动比较大的情况下，调车机车的运行状态是一定的，确定机车状态，正确的开发出机车运行状态函数，使机车的运转合理并效率较高，能很好的应用在编组站阶段计划机车运用自动化中。

1 列车解编顺序考虑的因素

列车解体和编组任务安排就是对调车机车任务的安排，所以可以运用调机的运转模拟有线状态机简称调机状态机。另外，车流的推算是机车任务安排的前提。在这里假设车站内只有一台调车机车可以灵活使用，既可以解体、编组及取送。

1.1 机车运用计划

调车机车运用计划用于合理安排每台调车机车在本阶段必须完成的调车工作以及这些调车工作的时间，它是车站阶段计划的关键内容。只有合理运用调车机车，正确组织编解取送，才能加速调车场的车辆集结过程，实现列车出发计划，并完成装卸任务和缩短货车停留时间创造条件。通过调车机车的运用安排，将车站的调车工作全面部署。调机的运用主要是对一个作业区域内多台调机情况下的安排和分工，涉及到作业的流畅、平行作业干扰性尽可能小、工作量均衡；各区机车相互配合、相互创造条件、相互支援，形成一个解体、编组、取送车都高效率完成任务的系统；同时还要考虑机车整备和司机吃饭时间、机车走行距离短、燃料节省等因素。

1.2 配 流

车站内车流包括列车到发计划以及编组计划、确报信息、站存车信息、扣车信息和调车信息，以及装卸线上的货物装卸情况。其中解体顺序的确定主要依据列车到发计划、确报信息。

配流的约束条件：①列车方向限制，即编组去向约束，到达列车中只有与出发列车编组去向相符的车流才能成为出发列车的车流来源。②技术作业限制。到达列车首先要经过列车技术检查、货运检查、车号核对等作业后，才能进入解体作业程序。③牵出线能力的限制，在一个阶段内，解体、编组列车数量决定了牵出线解体、编组能力。④车流接续时间限制。用于运行图、编组计划和调度日班计划规定的编组始发列车车流，其接续时间必须满足列车到、解、集、编、发所需的作业时间要求。⑤始发列车编组辆数限制。满轴约束，即对必须满轴出发的列车，其需求的车数就等于满轴车数；对可欠轴的列车，其需求的车数可小于满轴车数。

2 有限状态机

有限状态机（FMS）或有限状态自动机或称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。系统的行为如果在不同的时间（环境）下，其工作不同，并且行为可以分成所谓的有限的状态以及不重叠的程序块时，系统显示了状态行为。这其实说明了两件事情，如果是状态机，肯定体现了离散的和有限的。

状态存储关于过去的信息，它反映了从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行活动的描述。

3 模型的建立

在模型中假设到达列车使用的到发线不发生冲突，到发线问题已解决。以调机运转为核心，在车站到达场中，某一时刻场内的到达列车是一定的，编组列车数量及出发时间也是一定的，所有调机的任务即状态机的转化状态也是有限的。

设此时刻时间为t，调车场集结的待编现车记作d0，到达列车按到达时间排序依次：d1，d2，d3，…，ds，到达车辆总数为s。离此时刻最近的未出发列车记为f，f所需的车流为fj，在到达的列车总数s中，包含fj车流的列车数为m，不包含列车fj车流的列车数为n，即m＋n＝s，di为m中的一辆列车（i＞＝1），即到达列车并包含出发列车车流的一辆列车。dj（j＞＝1）为n中的一辆列车，即到达列车中并不包含出发列车车流的一辆列车。

在实际应用过程中，在程序中加入时间控件，按实际时间的推移、实际到达时刻和出发列车的最晚出发时间做解体顺序。

在状态机模型中，最重要的就是建立一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）和当前状态到下一状态的转换函数（transition function）的计算模型。

3.1 状态集

在调机状态机中调机工作分为6个状态：

1、投喂时间。开春后，当水温上升到16℃以上，应开始投喂。虾一般夜间进食，每天投喂时间选择下午5-6点。

状态①：空闲；

状态②：解体m中的一辆；

状态③：解体n中一辆；

状态④：编组f列车；

状态⑤：取送；

状态⑥：其他（整备、吃饭等）。

3.2 起始状态

起始状态可以从任意状态开始，在这里假设起始状态为空闲。

3.3 输入符号集

3.4 转换函数

1）Bool QuestNotFull（int num）／／出发列车是否缺少车流；

2）Bool GetAndSend（）／／是否有取送作业；

3）Void TimeToMash（）／／列车最晚编组时间到开始编组；

4）Void TimeOn（）／／出发列车最晚出发时间到，列车出发；

5）Void FindNowCar（）／／寻找现车车数；

6）Void DisCar（int n）／／解体列车，n为解体此阶段的第几辆列车；

7）Int judgeDisCar（）／／判断应该解哪一列车，返回解体车辆的序号。

3.5 程序实现

在此算法中机车有任务集合work[]，每到达一列车任务集合就增加一个，要编组列车任务、取送任务、列车的其他任务都加入其中。通过决策函数judgeDisCar（）来判断应该解体哪一列车，在judge－DisCar（）函数中用有限状态机的算法实现函数，返回一个序列值，即该解第几列车。ResultList[]，列车每解体一列车就在增加列车序号，最终形成一个完整的列车解体顺序表。TimeToMash（）判断是编组列车的最晚编组时间是否到了，GetAndSend（）判断是否有取送任务，取送任务可直接寻找空闲时间安排取送任务。在事件触发中用Timer控件实现，通过引发Timer事件有规律的隔一段时间判断机车运行状态，并准确给予下一状态。

3.6 机车状态转换图

机车状态转换，见图1。

图1 机车状态转换

3.7 算 例

1）参数说明。列车解体由一台调机担当、列车到达技检作业时间为30min、出发技检的时间为30min，解体时间为20min、列车编成数为35辆，允许欠轴发车。

2）厂内现车为1／2、2／4、3／18、4／20、5／10。

3）到达列车车流数据，见表1。

4）出发列车编组数据，见表2。

表1 到达列车车流数据

表2 出发列车编组数据

5）结果。运用有限状态机推理的列车编组顺序为11302、22601、36208、36407、23802。

4 结束语

目前，我国铁路编组站自动化水平已经较高，但是自动化优化还是有待以提高，本文应用有限状态机实现了自动安排机车解体和编组任务，是实现编组站全面自动化的一部分，其产生的计划的可执行性较高，具有实际的应用价值，有限状态机执行效率高，开发可模块化，易于维护，在研究和开发阶段计划机车任务安排中有重要的意义。

[1] 谢晓阳.有限状态机在RTC设计中的分析与应用[J].计算机系统应用，2008（5）：77－78.

[2] 王明智，赵强.编组站智能调度系统阶段计划优化模型及算法研究[J].铁道学报，2005（6）：1－9.

[3] 王正彬.基于解编顺序的阶段计划车流推算模型及算法[J].西南交通大学学报，2008，43（1）：63－68.

[4] 王慈光.车站技术作业整体统筹模型[J].铁路运输与经济，1996，18（4）：71－74.

[5] 薛锋，王慈光.编组站列车编组顺序的调整方法[J].铁道学报，2007，29（4）：1－5.