文 / 马佳骥
近年来,中国经过完善铁道基础设施和运用先进的技术装备很大程度地增强了轨道交通实力,但总的来说，中国轨道交通运能仍然保持紧张的局面。在通过车站改造、增开线路等举措解决紧张的物流能力状况的同时,还必须进一步优化摘挂列车编组方案以达到轨道运能的充分利用。
在国内,因为许多的中短途运输方式也比较多使用于铁道交通,所以摘挂列车的编组形式在所有列车编组中也是最复杂且相当关键的一个编组型式,也因此,我国相关科技人员对此研究比较多。在国外,由于中短途运输主要采取高速公路的方式,而超长距离运输主要采取航空方式,有一小部分的中长途运输主要采取铁路运输,从而不出现摘挂列车这种列车货运模式,因此国外对摘挂列车的研究相对较少。目前,尽管在对我国摘挂列车准备方法的基础理论研究上已经获得了一定成绩,但是在已有理论基础上,还没有有效的计算机算法,难以实现计算机进行编组作业计划的自动准备。
由于摘挂列车编组调车计划可抽象为平面内的排序问题，因此，作者通过对比车站调车作业实际操作情况与十大经典排序算法，发现堆排序算法更贴近实际，属于选择排序的一种，优于冒泡算法与希尔排序算法，而且可根据实际车站股道数量不同调整计划方案。本文通过建立堆排序算法数学模型并求解来实现摘挂列车编组自动编制的过程。
1.堆排序介绍
堆排序的思想是将一列待排序的序列构造成一个大顶堆，它是使用堆的统计构造方式来设计的一类顺序计算,相似于二叉树的构建方式,需要符合堆的特性。各个父结点的值都大于等于其左小孩和右小孩结点的数值,则称之为最大根堆;各个父结点的值都小于等于其左小孩和右小孩结点的数值,则称之为最小根堆。当待排序的数值数目一定时，由于堆数越多，堆的层级越少，因此，我们可以根据车站实际可用调车股道数目来设计不同的堆数,如二叉堆、三叉堆、多叉堆,本文将利用二叉堆进行堆排序举例说明,多叉堆的排序算法依次类推。
2.堆排序的计算步骤
首先把所有待排列的数组都建立为一个大根堆,此时这个数组的最值就设在堆构成的最顶层。
设待排序整个数组个数为n，把最顶部的数值和末尾的数值进行调换,此时末尾的数就是最大值,而剩下待排列的数组个数就是n-1。
将剩下的n-1 个数组重新建立成大根堆,然后把顶端的数据和n-1 位置上的数据进行互换,这样多次进行,便可获得有序数组。
3.堆排序计算
（1）构造大跟堆
假设存在以下数组（如图1），首次确保11 位置大根堆结构,第二次确保12 位置大根堆结构（如图2）,第三次实现了13 位置的大根堆架构,直到实现了15 位大根堆架构。每个插入新的数字都和它的根节点作比较,如果超过根节点,则交换,然后依次类推,直至小于或等于它的根节点为止。如图3 所示,此时成为大根堆结构。
图1 无序数组示意图
图2 12位置大跟堆结构图
图3 初始大跟堆结构图
（2）在固定最大值后再构建大根堆
我们可以将前一次构建出的初始大根堆进行重新排序,即将最顶层的元素与末尾元素进行转换,之后再将剩下的数据重新建立为一个大根堆,如图4 所示,其中黑色圆圈内为已经固定的数值,不再进行重新排序。
图4 固定最大值
此时整个数组中的最大数已排在末尾,将位置最顶层的最大数值“3”与其左右孩子数值加以对比,如果仍为最大,则不需要交换,但若小于左右孩子数值,则将其与子孩子中的最大值进行调换,直至最顶层位置上大于等于其左右孩子数值,构造大根堆。图4 中，由于最顶层的最大数值3 小于其左右孩子数值，且其右孩子数值6 为左右孩子中的最大值，故将数值3与数值6 进行调换，此时检验其他根节点，发现父节点的数值均大于它的子节点，此时该结构满足大跟堆结构。将最顶层数值6 与末尾数值2 进行调换，固定调换后末尾数值6，此时，位置4 和位置5 的数值（即数值6 和数值8）已经固定，不再参与后续步骤的排序。调换后最顶层数值2 小于其左右孩子数值，因此，将其与左右孩子中的最大数值5 进行调换，此时该结构满足大跟堆结构。
重复执行以上操作,直到所有数字排序完成结束,得到一个有序数组,如图5 所示。初始大根堆构造后采用固定最大值法重新构造大跟堆，此过程本文中的堆排序算法搜索流程图如图6 所示。
图5 最终大跟堆结构图
图6 堆排序算法搜索流程图
1.研究对象概况
摘挂列车按站顺编组的主要目标,是使原无规律的车组按站顺排序,以利于后续的取送、搬运等调车作业的进行。实施调车作业的机车一般在右端进行作业,将各节车厢用阿拉伯数字代表,并规定每列车组编组后距调车机车最远的一节车厢编号为1,从远至近的编号分别为1、2、3，假设某站点的一列待编车列3,4,1,7,2,6,1,2,5,3,7,根据摘挂列车站顺编组要求,编成后的车列应为1,1,2,2,3,3,4,5,6,7,7，编组过程如图7 所示。
图7 编组过程图
通常摘挂列车的编组使用下落法将其解体后,再连挂收编,以生成满足站顺需要的新车列。可见,降落方法的好坏也决定了调车员作业的效果。本文将堆排序所构造的大根堆高度（层级）模拟车站的调车线路,即每一层级均为一个调车股道,由于本文中使用的方法为二叉堆排序,所以调车线数量设为4 条,调车机车在右端进行调车作业。
2.模型构建及求解
首先在创建初始大根堆以前,我们就必须先对待编车列进行重复编码,即二次编码（位置编码）,使每节车厢中都有独立的无重叠的编码,以便后续的计算排序。二次排序的规则为:从距离调车机车最远的一侧开始,依次无重复的进行从小到大编号，此编号也可称为位置编号。因此,本文中的研究对象车站待编车列二次编号为5,7,1,10,3,9,2,4,8,6,11。
将车列中的“5”和“7”依次下落，并根据堆排序的大跟堆排序规则，将数值5 和数值7 进行位置调换，形成的大根堆结构如图8 所示。
图8 12位置大跟堆结构
按照初始大根堆的建立规则依次下落11 个车组，形成的初始大根堆如图9 所示。由于大跟堆的层级可模拟调车股道，因此，设本文中的四条调车线的编号由上到下依次为股道一、二、三、四，第一批车组下落后，股道一上的车组为11，股道二上的车组依次为10、9，股道三上的车组依次为7、8、1、2，股道四上的车组依次为4、5、3、6。
图9 初始大根堆
将大根堆的尾端和顶端的数组借助调车机车摘挂作业进行调换，流程如图10 所示，固定末尾数值，将其余数值按照大跟堆排序规则重新进行排序，直到满足大跟堆结构。重复执行以上操作，得到最终的车列排序数组如图11 所示。
图10 首尾调换
图11 最终大跟堆结构
此时，股道一上的车组为1，股道二上的车组依次为2、3，股道三上的车组依次为4、5、6、7，股道四上的车组依次为8、9、10、11，调车机车在右端进行调车作业。最后，借助调车机车按照顺序进行收编作业。
本文通过将摘挂列车调车作业计划的编制与计算机堆排序算法相结合，拟出针对摘挂列车解体到编组过程的堆排序模型，形成多个较优的暂合列，利用堆排序便于检索的特点，简化了收编任务，进而实现了摘挂列车按照站顺编制的调车作业计划，为调车编组及调车作业自动计划的编排提供了强大的技术保障。
本文所提供的摘挂列车调车作业编组计划模型与传统的调车计划相比，优点在于形成了多个较优的暂合列，而传统的下落方案生成的暂合列需经过对口分解进行较多次的交错组合，因此节省了暂合列内部调整的步骤。该方法不受实际使用的调车股道数目影响,可按照车站实际情况使用的调车工作线数灵活调整调车计划，因此适用于复杂多变的铁路系统。
猜你喜欢 调车编组车组 加强中间站调车安全管理的分析与对策中国电气工程学报(2020年6期)2020-12-29一种自动生成某型部队编组ID的方法科技风(2019年27期)2019-10-20群文阅读有效性的思考黑河教育(2019年6期)2019-06-21争分夺秒的防控导弹车组小哥白尼·军事科学画报(2019年12期)2019-03-02宝珀GT亚洲系列赛汽车博览(2018年11期)2018-11-17SEC6小时首战结束汽车之友(2018年12期)2018-06-27选准议题巧编组 鉴赏阅读提素养试题与研究·教学论坛(2017年34期)2018-04-02迈向新高度汽车之友(2017年12期)2017-08-03小学数学合作学习之我见课程教育研究·学法教法研究(2016年33期)2017-03-30浅谈如何保证调车作业安全中小企业管理与科技·上旬刊(2017年2期)2017-02-17