基于排序二叉树的列车分组钩计划自动编制方法

基于排序二叉树的列车分组钩计划自动编制方法

列车悬挂组合是一种复杂而重要的组合形式。因此，专家和科学家对悬挂列车的钩子计划进行了研究，并对基于经验的钩子计划进行了调整，如[1、2、3、4、5、6、7、8、9和10]。但是,传统的统筹对口调车法在下落列不为2的整次方时将产生大量方案需要筛选,而消逆法则是在箭翎线条件下逆序较多的情况时才体现出优势。因此,本文提出一种基于排序二叉树的摘挂列车编组钩计划自动编制方法。1摘挂列车在短期内的错误排列摘挂列车按站顺编组的目标是将无规律的车组按站顺排列,以便后续取送、装卸等调车作业的实现。假设调车机车在右端作业,各车组用阿拉伯数字代表,且规定列车编组后距调机最远的车组到站为1,从远到近依次为2,3,…。例1:1列待编车列为4,2,5,3,1,2,4,4,6,2,7,7,5,6,1,8,6根据摘挂列车站顺要求,编成后车组的排列顺序应为1,1,2,2,2,3,4,4,4,5,5,6,6,6,7,7,8编组摘挂列车常用的方法:先通过车组下落将待编车列进行分解,然后再通过连挂收编,形成符合站顺要求的车列。可见,下落方案的优劣决定了整个调车作业的效率,因此,摘挂列车编组钩计划问题的优化关键是对下落方案的优化。摘挂列车下落问题可以抽象为1个从1组大容量的无序数组中找出几组有序序列的排序问题。但是调车作业有其特殊性,调车作业是在平面上的作业,由调车机车带动车组在固定线路上进行编组,传统的排序算法如冒泡排序、希尔排序等方法大都不符合实际作业情况。因此,提出一种基于排序二叉树的最优下落方案确定方法。排序二叉树的1个重要特点是:1个无序序列可以通过构造1棵排序二叉树而变成1个有序序列,构造1棵排序二叉树的过程就是对无序序列进行排序的过程。基于排序二叉树的这个特点,将待编车列的排列序列建立排序二叉树,可对待编车列按编号大小进行初始排序。由于摘挂列车编组问题的关键是寻求1个固定排列中的几个有序序列,所以为了寻找到满足要求的几个相对较大有序序列(目的是使尽可能多的车组下落到同一轨道),首先必须知道所有的有序序列。排序二叉树中每1条从根节点到叶子节点的单侧通路都是1个有序序列,并且不同的路径表示不同的序列,因此,非常适用于确定摘挂列车编组中的有序序列。此外,在通过排序二叉树搜索有序序列的过程中,可运用堆栈结构存储下落方案备选序列;而调车过程中机车在轨道间推送、溜放车组的过程与堆栈的出栈、入栈过程类似;并且采用前序遍历方式搜索排序二叉树,相当于在车列中从左至右搜索,这与调车溜放过程从左至右溜放的作业要求是一致的。由此可见,采用排序二叉树搜索下落方案,在提高调车效率的同时也可满足调车作业特定的约束条件。2有序车组暂合列的确定基于排序二叉树确定下落方案的方法是:建立排序二叉树,搜索排序二叉树得到几组有序车组序列,再经过组合筛选出n-1组有序车组序列(n为可供调车的调车线数),将剩余车组组成暂合列,从而形成最终的下落方案。2.1可选组的二次号码建立排序二叉树之前,需要对原始待编车列进行重新编号,又称二次编号,使每个车组都有唯一的无重复的编号,以便后续搜索排序二叉树。车组重新编号的规则为:假定编组摘挂列车的牵出线在调车场的右侧,则从左侧开始,找到原始编号定为1的车组,将其二次编号定为1,再向右寻找原始编号为1的车组,并将其递增地二次编号定为2,继续上述步骤,直至所有原始编号为1的车组都已找到并对其递增地二次编号;再从车列最左侧开始找出原始编号为2的车组并对其递增地二次编号;依此类推,直到所有的车组二次编号完成。对于例1所示的1列待编车列,各车组对应的二次编号为7,3,10,6,1,4,8,9,12,5,15,16,11,13,2,17,14将此序列按从左至右的顺序插入排序二叉树中,生成具有如下性质的排序二叉树。①若排序二叉树的左子树不空,则左子树上所有节点的关键码值(即二次编号)均小于它的根节点的关键码值。②若排序二叉树的右子树不空,则右子树上所有节点的关键码值均大于它的根节点的关键码值。③排序二叉树的左、右子树也分别为排序二叉树。生成的排序二叉树节点按图1所示的数据结构存贮在计算机中,该节点中存贮包括二次编号后的编号、原始编号以及后续可选组等信息。图1中:Pi指向该节点的父节点,若当前节点为根节点则Pi为NULL;Lchild指向该节点的左节点;Data为数据域,存贮当前节点车组的二次编号;Rchild指向该节点的右孩子;Data1代表该节点对应车组的原始编号;LaterData为该节点对应车组的后续可选组。对于原始编号为m的车组,其后续可选组就是原始编号车列中编号同为m以及所有编号为m+1的车组。后续可选组是为便于二叉树搜索而定义的一个非常重要的概念,数据结构中以车组的二次编号存贮。对于例1的待编车列,其原始编号为2的后续可选组为2,2,3,则对应二次编号为3的后续可选组为4,5,6。2.2有序序列搜索调车溜放过程是按照从左至右的顺序将车组溜放,而排序二叉树每条从根节点到叶子节点的单侧通路都是1个有序序列,为此采用前序遍历方式搜索排序二叉树中所有根节点到叶子节点的通路,产生按从左至右有序排列的车组序列。为减少分解和收编过程中调动车组的次数,根据排序二叉树搜索出的有序序列,其对应的车组必须是原始编号相邻的车组。为得到满足条件的有序车组序列可选集,制定如下搜索步骤。Step1访问当前节点P。Step2若节点P对应的车组为已存在栈的栈内元素的后续可选组,则将节点P入该栈;否则,建立新栈,将节点P压入新栈作为栈底元素。Step3若入栈的节点为叶子节点,则将所有栈内元素大于1的栈记录到有序车组序列的可选集中,转Step4;否则按前序遍历规则将下一个节点作为当前节点P,返回Step1。Step4若所有节点已遍历,则遍历结束,输出搜索到的有序序列;否则,按前序遍历规则,搜索到下一个新节点,将新节点与其根节点之间搜索到的车组分别从其所在栈中出栈,销毁空栈,并返回Step2。搜索流程如图2所示。2.3可选采用分离组的方案由于可选集中可能包含相同编号的车组,而且可选集中有序车组序列并不满足尽量减少下落次数及收编过程调车次数的要求,因此,搜索得到的有序车组序列并不等同于下落方案,需按照一定规则从这个有序车组序列可选集中组合筛选出下落方案。定义下落完成后无需再分解的下落列为固定列。当可用调车线数为n时,可选出n-1个固定列,其余车组组成1个暂合列,收编时只需分解这列暂合列。因此,在下落方案生成时必须要求固定列中无交错的车组,则固定列的特征是除完整组(位置相邻且原始编号相同的所有车组组成的序列)外,不同原始编号的车组不得超过2种。对应于固定列,特定义不能下落到同一列的车组为分离组,用于将超过2种原始编号的车组分离。分离组应具有如下性质:①1列下落列中的分离组从左至右依次确定;②分离组内所有车组位置相邻;③分离组内除完整组(位置相邻且原始编号相邻的完整组可视为1组完整组)外,不同原始编号的车组不得超过2种。基于以上分析,确定可选下落方案的步骤如下。Step1删除交错车组。对于搜索排序二叉树得到的二次编号车组序列可选集,如果某车组编号比其后的车组编号大,则从序列中去除该车组。Step2选出元素最多的序列。假设:还有h个序列需要选择,元素最多且没有相同二次编号的序列有l组。当l≤h时,则将l个序列全部入选作为下落列,并再选出h-l个序列;当l>h时,则从l组序列中组合选出h组序列,作为并列方案,这将产生Chllh种组合,即有Chl组并列方案。如果元素最多的编后序列中有d个序列含有相同元素,则这d个序列作为并列备选方案。Step3删除相同二次编号的车组,即将Step2中选出的序列里所有元素在其他组序列中去除。Step4选出序列里有2组及其以上的分离组,则保留组内元素最多的分离组,其他车组去除。Step5重复Step2—Step4,根据可用调车线数n调整方案,选出n-1组序列,将剩余车组按原始排列顺序合并为1列暂合列。上述的下落方法,可根据编组场实际可用调车线数n灵活调整方案,不再像对口法一样受调车线数的限制,因此更能适应现场环境的变化,满足调车计划实时性的要求。2.4可选信号的生成以例1为例,已知可供调车线数为4,按照第2.1节的方法,建立如图3所示的排序二叉树,树内数字为车组二次编号后的号码。在图3的基础上,按照第2.2节的方法进行二叉树搜索,得到的有序序列可选集为1,23,6,4,57,10,8,97,10,12,117,10,12,15,16,177,10,12,15,13,14根据有序序列可选集,按照第2.3节的步骤生成可选下落方案,具体步骤如下。(1)如果某车组编号比其后的车组编号大,则去除,得1,23,4,57,8,97,10,117,10,12,15,16,177,10,12,13,14(2)选出元素最多的序列7,10,12,15,16,17;将选出序列中的车组在其他序列中去除;由于选出序列里有2组分离组,分别为7,10和12,15,16,17,删去7,10;则可得1,23,4,58,91112,15,16,1713,14(5)由此得到:第1次选出序列为12,15,16,17;第2次选出序列为3,4,5;第3次选出序列为1,2和8,9以及13,14中的任一个;剩余的所有车组组合成为暂合列。由于第3次选取时有3个序列可选,则最后可得到3组方案。将二次编号转为原始序列编号,则3组方案分别如下。第1组6,7,7,82,2,21,14,5,3,4,4,5,6,6第2组6,7,7,82,2,24,44,5,3,1,5,6,1,6第3组6,7,7,82,2,26,64,5,3,1,4,4,5,13调车时间调整溜放钩数和调动车辆数较少的钩计划,其所用的调车时间也较少,是较好的调车钩计划。基于文献的筛选标准,根据本文提出的下落方案生成方法的特点,考虑如下因素进行下落方案筛选。1l相邻组的组数如果待编车列中的相邻车组包含在同一下落列内,则分解待编车列时,相邻车组可一起同时溜放。因而,每利用1个邻组,就可节省1个溜放钩。2暂合列内收缩固定组的发育情况为了实现计算机自动收编,引入收编固定组概念,定义具有以下特性的固定组为收编固定组。①收编固定组在暂合列中从左至右依次确定;②收编固定组内所有车组必须在暂合列中位置相邻;③暂合列内所有收编固定组不得含有2种及其以上的相同原始编号;④每个收编固定组内,除完整组外,不得有2种以上不同原始编号的车组。暂合列内收编固定组的组数决定了溜放钩的数量,组数越多,分解暂合列的溜放钩数越多。如例1确定的下落方案1,其暂合列的收编固定组分组情况如图4所示,每个方格内为1组收编固定组。3连挂暂合列的处置车列最右端的车组为端组,分为待编车列端组和暂合列端组。在分解待编车列时,若待编车列端组下落在暂合列内,则可不溜出该车组,直接连挂暂合列,节省1个溜放钩;定义待编车列端组变量DC为0-1变量,若待编车列端组可不溜出,则DC=1,否则DC=0;在分解暂合列时,若暂合列端组向上线分解,则可不溜出,由调机带动连挂上线车组,节省1个溜放钩;定义暂合列端组变量DH也为0-1变量,若暂合列端组可不溜出,则DH=1,否则DH=0。4车列坐底可节省1个帮扶放钩坐底分为待编车列坐底和暂合列坐底。在分解待编车列时,其最左端车组可以停留在原线路不牵出,称为待编车列坐底。车列坐底可节省1个溜放钩;定义待编车列坐底变量ZC为0-1变量,若待编车列最左端车组可坐底,则ZC=1;否则ZC=0;在分解暂合列时,如果其前端车组对口线路空闲,该车组也可以停留在原线路不牵出,称为暂合列坐底,也可节省1个溜放钩;定义暂合列坐底变量ZH为0-1变量,若暂合列最左端车组可坐底,则ZH=1,否则ZH=0。5暂合列内进行机械密度的确定暂合列内可对口的组包括上线可对口组和暂合列可对口组。上线可对口组指暂合列里的组在上线有可对口列;暂合列可对口组指在上线没有可对口列,但是暂合列左端有可对口的组。若以上2种情况都没有,则称为暂合列内对口空闲组,当暂合列对口空闲组的组数大于1时,则意味着暂合列要重复分解,则溜放次数将增加。先确定上述5个参数的取值,然后按照公式N=L-G+DC+DH+ZC+ZH计算总组数N。根据总组数N选择下落方案:N值大的方案,所产生的调车钩数最少,说明方案相对较优;若有2组方案的N相同,则暂合列内对口空闲组的组数K较小的方案相对较优。例如,对于例1中产生的3组下落方案,按照上述筛选方法进行筛选,计算过程见表1。由表1可知:方案1的N最大,其完成列车编组需要的调车钩数最少,则方案1为最优方案。4系统程序的实现无序的车列下落完成以后,再通过收编将车组编成按顺序排列的车列。收编过程就是通过调车机车拉动车组进行溜放,从而实现对暂合列的分解。暂合列的分解相对复杂,包含大量重复的溜放过程,还需基于专家经验知识、利用端组和坐底实现减钩优化,很少有文献讨论如何通过计算机实现优化收编过程。考虑到本文所提的下落方法只产生1列暂合列,收编过程只需考虑该暂合列的分解,减少了分解的复杂性,从而使采用计算机实现收编过程成为可能。下落方案筛选时,已将暂合列内的车组按收编固定组分组;而分为同一组的车组,在收编过程中看作一个整体,不再分开溜放;每组的最左端车列作为该组的标识,代表了整组中所有车列。为此,在实现收编时只需寻找到每组的标识,根据其对应的对口列进行对口操作。摘挂列车收编过程的计算机自动编制算法流程如图5所示。图中:ZA为暂合列的总车数;ZD为暂合列坐底组的车数,若无坐底组,则ZD=0;DZ为暂合列可利用端组的车数,若端组不可利用,则DZ=0。该算法的优势是充分利用了暂合列内的端组和坐底,有效减少了溜放次数,达到了优化的目的,同时利用暂合列收编固定组的概念,简化了利用计算机实现列车收编的过程。5统筹能力分析对于例1,基于本文提出的排序二叉树方法,生成的最终钩计划如图6(