车站调车钩计划算法模型及自动编制系统优化

张颖波 上海铁路局浙江铁道集团

1 调车钩计划编制的现状与问题

统计资料显示，铁路货车在一次周转中，要经过多次调车作业，并要占用大量的人员、设备，消耗大量的燃材料，其费用约占铁路运营开支的1/4。货车由第一次装车至第二次装车的周转时间中，在装卸站和技术站的停留时间约占70%，其中花在编组站、区段站的停时约占40%。一次货车作业平均停时17 h 左右，有调中转7 h。若一次货车作业平均停时压缩1 h，有调中转压缩0.5 h，可压缩货车周转时间0.16天，可节省运用车1.3 万多辆，直接经济效益达15 亿元。由此可见，高质量的调车作业、对加速机车车辆周转、提高运输效率、增强运输能力、降低运输成本、保证运输安全具有十分重要的作用。

车站作业计划的优化编制一直是铁路运输组织工作的重要组成部分。调车作业计划的编制水平在很大程度上决定了运输效率的好坏。我国拥有80%的中间站，调车钩计划还靠人工编制来实现，车站在获取列车确报后，由人工编制调车钩计划，再输入到TMIS 系统中，并在执行过程中，由人工动态输入和修改相关调车信息，并依赖"毛玻璃"手工更新车站现车的位置及状态的变化。

造成这种现象的主要原因是中间站的站场结构类型多，调车方式灵活，影响编制调车计划的限制因素复杂，人工编制调车钩计划，单凭个人经验，编制方法、质量因人而异。而且大部分中间站的调车任务是由本务机完成，对调车计划的编制质量要求高，编制速度要求快，使得计算机自动编制中间站调车钩计划问题一直难以得到解决。

2 调车方法的优选及算法模型

所谓编制车站调车钩计划，是指当车站一批作业任务已确定的条件下，编制人员根据车站的线路结构、车辆位置、各种作业时间要求等因素，编制调车作业计划并在保证各车辆最终移动至指定位置条件下，使整个调车过程的作业效率最高。由于不同的编制方法、不同的调车方式、不同的站场股道运用，可以编出很多的调车作业方案，当车站调车任务多，运用车集中时，编制调车计划的难度很大。

2.1 调车方法的优选

按调车方法分类有统筹调车法、消逆法、分析计算法、基数排序调车法等都是基于统筹对口调车法。选编调车作业的实质就是消除逆，最快的消逆过程，就是最优的调车作业过程。在保证连挂钩最少，对溜放钩进行优化，并寻找各车组的有利下落位置。

调车作业计划的编制要求尽可能提高调车作业效率，减少作业时间。而调车作业效率主要是由：作业过程中发生的连挂钩数、溜放钩数以及作业过程中的带动车辆数等因素决定。

在以往编制调车作业计划时，首先要进行的就是"车组下落"，即为了调整顺序，把待编车列中的反顺序车组分解到不同线路上，而后根据车组下落的情况进行"合并下落列"等步骤来得到调车方案。不同的车组下落方案对应着不同的调车方案。因此，车组下落情况，对调车方案的优劣有重要的影响。采用分析计算法依据合列有利性原理，对各种下落列数的全部调车方案按对口子系统进行优化组合，产生各方案组的待选方案集，删除其中的必然不利方案，由各方案组的最优变异方案组成经过优化的比选方案集，然后综合考虑调车钩数和带动辆数对调车作业时间的影响，计算出各比选方案的换算溜放钩数，从而获得最佳方案。

2.2 最优车组排序的图论模型

求一个有向图的最小Hamiltom 路是一个NP 困难问题，当车组数较大时，一般很难求最大优解。但是，待编车列生成的有向图具有一定的特殊性，由于编组有站顺要求，因此所求的Hamiltom 路具有如下特征：只有当同一个到达站的车组节点全部经过后，才能进入下一个到达站的车组节点；而当同一个到达站的车组节点的进入节点和离开节点确定后，根据生成图的弧长取值可知，通过所有该到达站节点的最小Hamiltom 路的次序必定是第一个点为进入节点，最后一个节点为离开节点。而其它节点的次序与在原车列中的排列次序相同。按照此 方法即可将问题转化为最短路问题，而最短路问题则很容易求解。

例如：原车组排列为3 .4 .1.2 .1.2 .3.4, 即第一站的次序为3，5；第二站的次序为4，6；第三站的次序为1，7；第四站的位置为2，8。构造最短路图见图1。从节点0 到节点9 的最短路为5, 3, 4, 6, 7, 1, 2, 8。总路长为（3,4），即为3 挂钩4 摘钩。

图1 构造最短路图

2.3 最优解的判定

为解决动态规划中每一阶段各种状态的最优指标函数值必须通过递归计算得到，并且需要有足够的空间存储这些值的困难，以及克服位势法容易陷入局部最优解和没有考虑阶段转移费用等问题。将位势法与动态规划法相结合，设计一种求最优调车钩计划的隐枚举搜索算法。由于在求调车钩计划隐枚举搜索算法中，每次循环都是找当前状态集中综合指标最小的车组布局进行下一步的移动，而且状态集和比选方案集的规模都不会超过枚举规则M，因此算法的复杂度是Mn2，其中n 是本批调车任务需移动车组数。该方法是一个高效的算法，不仅速度快，而且当M 足够大时，能保证求得在综合意义上的最优解。

3 调车钩计划编制优化功能

调车钩计划优化编制系统主要完成对车站调车作业的管理（包括车站图形显示、接发列车、编制调车计划、执行和回放调车作业、数据统计分析），各种相关信息的录入和查询。

3.1 系统设计思路

系统启动后，自动连接远程TMIS 系统数据库，并实时读取数据用于初始化本地数据库，使本地与远程数据库信息同步。初始化完成后，在系统主界面显示车站的当前车辆分布情况，列车的编组信息在到达本站前已发送到本站，本系统根据到确报信息安排接车作业，出发列车要安排发车作业，车列在本站逗留期间可能要进行多项作业，根据列车的不同去向，将车列按照一定要求分组，再编组调车钩计划，打印下达调车作业任务，现场依据调车计划通知单，按顺序将车辆送到指定股道，并且在系统中完成对调车作业过程模拟和执行过程的回放，同时对于系统中的数据提供查询和管理功能。

3.2 系统功能模块

中间站调车钩计划自动优化编制系统主要涵盖七大功能。

3.2.1 现车信息动态查询和统计功能

本系统能够实现与TMIS 系统的连接，自动实时读取数据库数据，并可以根据需要显示不同的详细信息。如现在车状态的信息查询与屏幕显示、超时停留车、关门车信息查询与显示等，可显示现场的防溜措施，股道现车查询完全替代"毛玻璃"功能，还可以按要求显示各车辆的重量、车种、品名、吨位、收货人等详细信息，并有现在车进行车辆数和停留时间统计。

3.2.2 钩计划自动编制功能

系统内置钩计划编制的优化模型与算法，可自动读取TMIS 系统的相关数据，根据设定的优化限制条件自动编制调车钩计划，并可根据实际需要对钩计划施行人工调整，并智能添加备注栏信息。

3.2.3 图形编制钩计划（人机对话式编制）功能

操作人员可以通过系统所显示的股道现车图形，通过鼠标拖动车组位置来编制钩计划，使编制调车计划过程直观化。

3.2.4 调车作业动态模拟功能

系统可模拟站内发生的调车和接发列车作业情况并可观察各时段、各操作所引起的站场内现车情况的变化，在作业之前对作业有直观的了解。

3.2.5 大屏显示功能

系统可以实现全屏显示。并能用鼠标拖拉来实现画面的放大缩小，解决"毛玻璃"不能实现的效果，同时也可以根据需要对颜色设置。

3.2.6 作业回顾和历史操作回放功能

系统能对本班操作已执行的钩计划进行回推操作。同时对已完成钩计划进行回放显示每钩操作前后站场的现车情况，对历史操作进行跟踪。

3.2.7 作业计划单打印输出功能

智能打印钩计划作业通知单，可根据打印纸张大小自动排版，并自动插入调车作业期间通过本站的旅客列车信息。