摘掛列車編組計劃優化研究

文 / 馬佳驥

一、引言

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

二、當前摘掛列車編組現狀

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

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

三、相關研究理論和算法

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，調車機車在右端進行調車作業。最后，借助調車機車按照順序進行收編作業。

五、結語

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

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