文 / 馬佳驥

一、引言

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

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

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

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

三、相關(guān)研究理論和算法

1.堆排序介紹

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

2.堆排序的計算步驟

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

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

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

3.堆排序計算

（1）構(gòu)造大跟堆

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

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

圖2 12位置大跟堆結(jié)構(gòu)圖

圖3 初始大跟堆結(jié)構(gòu)圖

（2）在固定最大值后再構(gòu)建大根堆

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

圖4 固定最大值

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

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

圖5 最終大跟堆結(jié)構(gòu)圖

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

四、摘掛列車編組計劃模型構(gòu)建及求解

1.研究對象概況

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

圖7 編組過程圖

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

2.模型構(gòu)建及求解

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

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

圖8 12位置大跟堆結(jié)構(gòu)

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

圖9 初始大根堆

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

圖10 首尾調(diào)換

圖11 最終大跟堆結(jié)構(gòu)

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

五、結(jié)語

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

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