文 / 馬佳驥

一、引言

近年來,中國經(jīng)過完善鐵道基礎設施和運用先進的技術裝備很大程度地增強了軌道交通實力,但總的來說，中國軌道交通運能仍然保持緊張的局面。在通過車站改造、增開線路等舉措解決緊張的物流能力狀況的同時,還必須進一步優(yōu)化摘掛列車編組方案以達到軌道運能的充分利用。

二、當前摘掛列車編組現(xiàn)狀

在國內,因為許多的中短途運輸方式也比較多使用于鐵道交通,所以摘掛列車的編組形式在所有列車編組中也是最復雜且相當關鍵的一個編組型式,也因此,我國相關科技人員對此研究比較多。在國外,由于中短途運輸主要采取高速公路的方式,而超長距離運輸主要采取航空方式,有一小部分的中長途運輸主要采取鐵路運輸,從而不出現(xiàn)摘掛列車這種列車貨運模式,因此國外對摘掛列車的研究相對較少。目前,盡管在對我國摘掛列車準備方法的基礎理論研究上已經(jīng)獲得了一定成績,但是在已有理論基礎上,還沒有有效的計算機算法,難以實現(xiàn)計算機進行編組作業(yè)計劃的自動準備。

由于摘掛列車編組調車計劃可抽象為平面內的排序問題，因此，作者通過對比車站調車作業(yè)實際操作情況與十大經(jīng)典排序算法，發(fā)現(xiàn)堆排序算法更貼近實際，屬于選擇排序的一種，優(yōu)于冒泡算法與希爾排序算法，而且可根據(jù)實際車站股道數(shù)量不同調整計劃方案。本文通過建立堆排序算法數(shù)學模型并求解來實現(xiàn)摘掛列車編組自動編制的過程。

三、相關研究理論和算法

1.堆排序介紹

堆排序的思想是將一列待排序的序列構造成一個大頂堆，它是使用堆的統(tǒng)計構造方式來設計的一類順序計算,相似于二叉樹的構建方式,需要符合堆的特性。各個父結點的值都大于等于其左小孩和右小孩結點的數(shù)值,則稱之為最大根堆;各個父結點的值都小于等于其左小孩和右小孩結點的數(shù)值,則稱之為最小根堆。當待排序的數(shù)值數(shù)目一定時，由于堆數(shù)越多，堆的層級越少，因此，我們可以根據(jù)車站實際可用調車股道數(shù)目來設計不同的堆數(shù),如二叉堆、三叉堆、多叉堆,本文將利用二叉堆進行堆排序舉例說明,多叉堆的排序算法依次類推。

2.堆排序的計算步驟

首先把所有待排列的數(shù)組都建立為一個大根堆,此時這個數(shù)組的最值就設在堆構成的最頂層。

設待排序整個數(shù)組個數(shù)為n，把最頂部的數(shù)值和末尾的數(shù)值進行調換,此時末尾的數(shù)就是最大值,而剩下待排列的數(shù)組個數(shù)就是n-1。

將剩下的n-1 個數(shù)組重新建立成大根堆,然后把頂端的數(shù)據(jù)和n-1 位置上的數(shù)據(jù)進行互換,這樣多次進行,便可獲得有序數(shù)組。

3.堆排序計算

（1）構造大跟堆

假設存在以下數(shù)組（如圖1），首次確保11 位置大根堆結構,第二次確保12 位置大根堆結構（如圖2）,第三次實現(xiàn)了13 位置的大根堆架構,直到實現(xiàn)了15 位大根堆架構。每個插入新的數(shù)字都和它的根節(jié)點作比較,如果超過根節(jié)點,則交換,然后依次類推,直至小于或等于它的根節(jié)點為止。如圖3 所示,此時成為大根堆結構。

圖1 無序數(shù)組示意圖

圖2 12位置大跟堆結構圖

圖3 初始大跟堆結構圖

（2）在固定最大值后再構建大根堆

我們可以將前一次構建出的初始大根堆進行重新排序,即將最頂層的元素與末尾元素進行轉換,之后再將剩下的數(shù)據(jù)重新建立為一個大根堆,如圖4 所示,其中黑色圓圈內為已經(jīng)固定的數(shù)值,不再進行重新排序。

圖4 固定最大值

此時整個數(shù)組中的最大數(shù)已排在末尾,將位置最頂層的最大數(shù)值“3”與其左右孩子數(shù)值加以對比,如果仍為最大,則不需要交換,但若小于左右孩子數(shù)值,則將其與子孩子中的最大值進行調換,直至最頂層位置上大于等于其左右孩子數(shù)值,構造大根堆。圖4 中，由于最頂層的最大數(shù)值3 小于其左右孩子數(shù)值，且其右孩子數(shù)值6 為左右孩子中的最大值，故將數(shù)值3與數(shù)值6 進行調換，此時檢驗其他根節(jié)點，發(fā)現(xiàn)父節(jié)點的數(shù)值均大于它的子節(jié)點，此時該結構滿足大跟堆結構。將最頂層數(shù)值6 與末尾數(shù)值2 進行調換，固定調換后末尾數(shù)值6，此時，位置4 和位置5 的數(shù)值（即數(shù)值6 和數(shù)值8）已經(jīng)固定，不再參與后續(xù)步驟的排序。調換后最頂層數(shù)值2 小于其左右孩子數(shù)值，因此，將其與左右孩子中的最大數(shù)值5 進行調換，此時該結構滿足大跟堆結構。

重復執(zhí)行以上操作,直到所有數(shù)字排序完成結束,得到一個有序數(shù)組,如圖5 所示。初始大根堆構造后采用固定最大值法重新構造大跟堆，此過程本文中的堆排序算法搜索流程圖如圖6 所示。

圖5 最終大跟堆結構圖

圖6 堆排序算法搜索流程圖

四、摘掛列車編組計劃模型構建及求解

1.研究對象概況

摘掛列車按站順編組的主要目標,是使原無規(guī)律的車組按站順排序,以利于后續(xù)的取送、搬運等調車作業(yè)的進行。實施調車作業(yè)的機車一般在右端進行作業(yè),將各節(jié)車廂用阿拉伯數(shù)字代表,并規(guī)定每列車組編組后距調車機車最遠的一節(jié)車廂編號為1,從遠至近的編號分別為1、2、3，假設某站點的一列待編車列3,4,1,7,2,6,1,2,5,3,7,根據(jù)摘掛列車站順編組要求,編成后的車列應為1,1,2,2,3,3,4,5,6,7,7，編組過程如圖7 所示。

圖7 編組過程圖

通常摘掛列車的編組使用下落法將其解體后,再連掛收編,以生成滿足站順需要的新車列?？梢?降落方法的好壞也決定了調車員作業(yè)的效果。本文將堆排序所構造的大根堆高度（層級）模擬車站的調車線路,即每一層級均為一個調車股道,由于本文中使用的方法為二叉堆排序,所以調車線數(shù)量設為4 條,調車機車在右端進行調車作業(yè)。

2.模型構建及求解

首先在創(chuàng)建初始大根堆以前,我們就必須先對待編車列進行重復編碼,即二次編碼（位置編碼）,使每節(jié)車廂中都有獨立的無重疊的編碼,以便后續(xù)的計算排序。二次排序的規(guī)則為:從距離調車機車最遠的一側開始,依次無重復的進行從小到大編號，此編號也可稱為位置編號。因此,本文中的研究對象車站待編車列二次編號為5,7,1,10,3,9,2,4,8,6,11。

將車列中的“5”和“7”依次下落，并根據(jù)堆排序的大跟堆排序規(guī)則，將數(shù)值5 和數(shù)值7 進行位置調換，形成的大根堆結構如圖8 所示。

圖8 12位置大跟堆結構

按照初始大根堆的建立規(guī)則依次下落11 個車組，形成的初始大根堆如圖9 所示。由于大跟堆的層級可模擬調車股道，因此，設本文中的四條調車線的編號由上到下依次為股道一、二、三、四，第一批車組下落后，股道一上的車組為11，股道二上的車組依次為10、9，股道三上的車組依次為7、8、1、2，股道四上的車組依次為4、5、3、6。

圖9 初始大根堆

將大根堆的尾端和頂端的數(shù)組借助調車機車摘掛作業(yè)進行調換，流程如圖10 所示，固定末尾數(shù)值，將其余數(shù)值按照大跟堆排序規(guī)則重新進行排序，直到滿足大跟堆結構。重復執(zhí)行以上操作，得到最終的車列排序數(shù)組如圖11 所示。

圖10 首尾調換

圖11 最終大跟堆結構

此時，股道一上的車組為1，股道二上的車組依次為2、3，股道三上的車組依次為4、5、6、7，股道四上的車組依次為8、9、10、11，調車機車在右端進行調車作業(yè)。最后，借助調車機車按照順序進行收編作業(yè)。

五、結語

本文通過將摘掛列車調車作業(yè)計劃的編制與計算機堆排序算法相結合，擬出針對摘掛列車解體到編組過程的堆排序模型，形成多個較優(yōu)的暫合列，利用堆排序便于檢索的特點，簡化了收編任務，進而實現(xiàn)了摘掛列車按照站順編制的調車作業(yè)計劃，為調車編組及調車作業(yè)自動計劃的編排提供了強大的技術保障。

本文所提供的摘掛列車調車作業(yè)編組計劃模型與傳統(tǒng)的調車計劃相比，優(yōu)點在于形成了多個較優(yōu)的暫合列，而傳統(tǒng)的下落方案生成的暫合列需經(jīng)過對口分解進行較多次的交錯組合，因此節(jié)省了暫合列內部調整的步驟。該方法不受實際使用的調車股道數(shù)目影響,可按照車站實際情況使用的調車工作線數(shù)靈活調整調車計劃，因此適用于復雜多變的鐵路系統(tǒng)。