摘掛列車編組計(jì)劃優(yōu)化研究

文 / 馬佳驥

一、引言

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

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

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

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

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

1.堆排序介紹

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

2.堆排序的計(jì)算步驟

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

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

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

3.堆排序計(jì)算

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

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

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

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

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

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

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

圖4 固定最大值

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

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

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

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

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

1.研究對象概況

摘掛列車按站順編組的主要目標(biāo),是使原無規(guī)律的車組按站順排序,以利于后續(xù)的取送、搬運(yùn)等調(diào)車作業(yè)的進(jìn)行。實(shí)施調(diào)車作業(yè)的機(jī)車一般在右端進(jìn)行作業(yè),將各節(jié)車廂用阿拉伯?dāng)?shù)字代表,并規(guī)定每列車組編組后距調(diào)車機(jī)車最遠(yuǎn)的一節(jié)車廂編號為1,從遠(yuǎn)至近的編號分別為1、2、3，假設(shè)某站點(diǎn)的一列待編車列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)車線路,即每一層級均為一個(gè)調(diào)車股道,由于本文中使用的方法為二叉堆排序,所以調(diào)車線數(shù)量設(shè)為4 條,調(diào)車機(jī)車在右端進(jìn)行調(diào)車作業(yè)。

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

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

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

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

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

圖9 初始大根堆

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

圖10 首尾調(diào)換

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

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

五、結(jié)語

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

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