貨車車輛段調車模型與求解

邱建東，任 偉，祁育棟，張 飛

（蘭州交通大學 機電工程學院，甘肅 蘭州 730070）

0 引言

貨車車輛段主要承擔鐵路貨車的段修任務，在整個段修過程中，調車作業是車輛段組織貨車檢修工作的關鍵步驟，也是比較復雜的作業內容。目前在實際的調車作業中，依舊采用人工或半人工作業方式，在車輛段檢修能力及場地規模有限的前提下，隨著貨車檢修數量增加，調車作業亦越來越復雜。因此，利用計算機編制和優化調車作業計劃是一個亟需解決的理論和技術難題[1-2]。

許多學者將研究的重點投入到高速鐵路動車所客車調車作業中，而鐵路貨車在進行檢修作業時同樣需要大量甚至更多的調車。動車所的調車作業跟貨車車輛段的調車作業有相似之處。王忠凱等[3]將調車作業視作是有時空約束條件的車間調度問題，并以減少動車無效占用時間和調車路徑費用為目標，利用改進的MAX-MIN蟻群系統求解；張惟皎等[4]考慮列位條件，目的在于提高存車線利用率和減少調車走行距離，并基于極大存車線方案，設計模擬退火算法并取得良好效果；王家喜[5]則以調車鉤數最小為目標，優化調車鉤數以提高調車效率，并設計粒子群算法對構建的整數模型求解；童佳楠等[6]在考慮列位約束條件的基礎上，將調車作業視作是具有約束性質工藝的混合flow-shop調度問題，提出利用遺傳算法解決該問題；殷迪等[7]則將調車作業視為帶有不定加工時長的job-shop調度問題，以實現存車線上的總預留時間最大化，構建調車作業計劃優化模型，利用啟發式算法求解 模型。

在鐵路車輛檢修調車作業的研究中，無論是從問題自身出發，還是將問題轉化為其他形式的問題，對于車輛在檢修工序的順序要求上都沒有進行考慮，對于鐵路貨車而言，由于必要的檢修步驟具有嚴格的順序要求，這個問題也更加突出。因此，從這個角度出發，以貨車線路占用時間及車輛轉線時間和最小為目標構建模型，并運用改進的遺傳算法求解。

1 車輛段線區布局

車輛段貨車檢修作業可視作一個整體，包括出入段作業和檢修計劃規定的若干項檢修作業。各部分檢修作業均需一定的時間完成，檢修作業在具備條件的檢修區內進行，貨車在車輛段轉線和停留，須滿足股道與股道之間的連通和空間占用條件。

以蘭州西車輛段段內線路布置為例，說明貨車車輛段的功能分區，大部分車輛段只進行段修，少數車輛段在設備及場地條件允許的情況下會分擔一部分站修任務。蘭州西車輛段段內布局如圖1所示，該車輛段內布置多個功能線區，其中D1—D4為段 修作業區，主要完成貨車段修作業任務；Z1—Z3為 站修作業區，主要完成貨車站修任務；T為調梁區，主要功能是為貨車調梁；X為罐車清洗作業區，主要是在罐車檢修前對其進行清洗作業，避免有毒、易燃、易爆氣體或液體殘留；P為拋丸、噴漆作業區，主要是進行貨車車廂的拋丸、噴漆作業；R為預修作業區，主要對進入車輛段的所有貨車進行預修作業；S1—S7為存車區，主要進行貨車在段內的 中轉、停留和整備等作業；E為車輛段進出線。

2 貨車車輛段調車模型及求解

貨車車輛段的調車作業基本包括所有貨車在段內有向移動的全部內容，是將貨車檢修任務和車輛段檢修資源調動起來的關鍵所在。

2.1 貨車車輛段調車模型

2.1.1 模型建立

根據我國貨車車輛段實際情況，貨車的檢修調車作業均依靠調車機車牽引完成，大多數車輛段僅配置2臺牽引機車，日常調車作業中只運用1臺機車，另1臺為備用機車，因而調車機車的數量對模型的建立與求解不會造成沖突，調車方案的建立均以1臺牽引機車為準。車輛段為實現檢修效率的提高，根據檢修計劃及車輛段各個檢修作業區檢修臺位的數量要求，同一類型檢修項目的貨車被推送至檢修作業區進行同一作業，如蘭州西車輛段段修作業區設有4條檢修股道，每條檢修股道可容納7輛貨車同時進行同一作業。建立模型時，由于同一類型檢修項目的貨車由調車機車一次性推入，檢修完畢之后，由調車機車一次性牽出，可將這類貨車視作一個整體。檢修結束之后，貨車將被牽引至存車線，次日成批交付。考慮到以上因素，在車輛段檢修作業符合《鐵路技術管理規程》及各檢修規程的前提下，以貨車檢修時占線時間及車輛轉線時間和Z最小為目標，建立以下調車作業模型。

式中：T為貨車檢修作業時間，h；F為調車作業中貨車轉線時間，h；e為車輛段內任意檢修車輛；d為檢修線區編號；l為檢修線區內股道編號；D為車輛段線區集合；E為貨車集合；W為轉線路徑集合；Ld為股道集合；m1，m2為分別表示T和F的權重系數，根據車輛段調車作業設備的配置情況，m1，m2的取值也不同，但都滿足兩者之和為1；xedl為 0-1變量，貨車e在任意線區d的股道l上停留并進行檢修作業為1，否則為0；為0-1變量，表示貨車轉線路徑選擇，當任意貨車e按照其轉線順序，從線區d的股道l上轉至另一檢修線區d′的股道h上，選擇W中的第k條調車路徑時，為1，否則為0；為任意貨車e進入線區d的股道l的時刻；為任意貨車e離開線區d的l股道的時刻。

2.1.2 初始條件

（1）檢修作業約束：如果貨車需要在某線區進行檢修作業，指定車輛須在指定線區選擇一條股道進行停留，完成計劃作業。

（2）路徑約束：貨車在兩線區之間轉線時只能選一條通路。

（3）檢修作業時間約束：貨車在指定股道檢修作業時，必須在規定的時間內完成，否則視為不可檢修，須離開檢修股道。

式中：Te為貨車檢修最小用時，h。

（4）股道相容性約束：當某一股道上有貨車進行檢修作業或占用時，該股道不可停靠2輛及以上貨車。

式中：zdlec為0-1變量，表示貨車在股道的占用次序，當任意貨車e優先貨車c至股道l時，zdlec為1，否則為0；xcdl為0-1變量，表示任意貨車c在任意線區d的股道l上停留并進行檢修作業為1，否則為0。

2.2 模型求解

2.2.1 遺傳算法

貨車車輛段檢修調車作業是一個NP-hard問題，這類問題隨著車輛段檢修貨車、檢修股道數量及檢修作業工序的增加，其組合量會以指數級增加，很難用傳統的數學規劃方法從其中找到最優解。遺傳算法在解決調度問題時，其優勢在于一方面可以隨機從一個目標轉向下一個目標，不易陷入局部搜索的困境之中，另一方面搜索時具有較高效率，通過以下設置以實現對模型的求解[8]。

（1）編碼設計。將貨車需要進行的若干項檢修項目視為具有遺傳性質的染色體，并且將其分配到不同股道，研究采用自然數向量表示的編碼方式，將貨車需要進行的檢修項目進行自然數排列，向量τ= {r1，r2，…，rn}代表一個完整檢修作業，從r1到r2，…，rn-1到rn，再從rn返回到r1。例 如，向 量τ為{1，2，3，4，5，6，7，8，9，10}的排列，表示一個完整的檢修作業集合有10個工序，則對于集合R= {1，2，3，4，5，6，7，8，9，10}，如果有一個體的向量為{5，4，9，10，8，1，2，7，6，3}，則表示的檢修順序為5→4→9→10→8→1→2→7→6→3→5。

（2）適應度函數。在遺傳算法中，依靠適應度函數值來衡量群體中個體適應環境的能力，適應度函數通常是由目標函數轉換而成，函數值越大的個體將有機會獲得更大的機會繁衍下一代。根據調車作業優化模型，貨車占線及轉線的時間越大，則表明所產生的方案越不理想，也就意味著被淘汰的可能性越大。由目標函數變換得到的適應度函數計算公式為

式中：Ti表示進行第i道檢修工序的最小檢修時間，h；Fi表示轉線至第i道檢修工序所在股道的最小時間，h。

（3）選擇。研究采用隨機競爭選擇方式，假設群體大小為Ni，首先采用輪盤賭的形式選擇1對個體i，j，則任意個體i的適應度為fi，j的適應度為fj，然后2個個體間進行競爭，適應度值高的被選中，如此反復操作直到選滿，個體被首先選中的概率為

（4）遺傳操作。在整個遺傳算法的運算過程中，遺傳操作是其中重要的步驟之一，交叉運算將遺傳算法跟其他的元啟發式算法區別開來，是遺傳算法中關鍵之處，是產生新個體的主要方法。研究中采用比較廣泛的兩點交叉，兩點交叉運算示意圖如圖2所示。

①將生成的新個體融入下一代形成新的種群，并判斷新種群的規模，如果達不到初始種群的規模，則重復交叉操作直至達到要求，然后終止交叉操作。交叉概率Pc擬給定為0.9。

②變異采用啟發式變異方法。隨機產生2個變異位置i和j，交換位置i和j上的基因。變異概率Pm擬給定為0.08。啟發式變異示意圖如圖3所示。

（5）算法終止。設置迭代次數，達到最大次數時運算結束并輸出結果。

2.2.2 算法求解

求解步驟如下。

步驟1：依據貨車參數信息，分析貨車故障類型并制定合理檢修計劃。

步驟2：算法相關參數設置。

步驟3：利用合理的編碼形式將實際問題轉換，并且生成初始種群。

步驟4：設計適應度函數，利用遺傳操作過程選取適應度比較高的個體，并且遺傳給下一代。

步驟5：求最優解至符合遺傳終止條件。

步驟6：輸出最優結果并進行分析。

3 實例分析

為了驗證研究提出的考慮貨車檢修順序的情況及模型的有效性，以蘭州西車輛段實際檢修作業為例，對其調車作業進行分析，以該車輛段日常檢修的敞車、平車、棚車、罐車4種車型作為檢修實例，并根據實際作業數據對模型進行解算。

（1）各車型檢修作業占線時間如表1所示。

表1 檢修作業占線時間 hTab.1 Busy time of maintenance operation

續表

（2）貨車檢修轉線時間如表2所示。

表2 檢修轉線時間表 hTab.2 Maintenance transfer schedule

（3）遺傳參數設置如表3所示。

表3 遺傳參數設置Tab.3 Genetic parameter setting

設計編碼形式為4×6 = 24 bit，隨機選取4輛車的父代染色體 （1 1 5 3 4，2 2 6 5 1，2 1 3 3 6 4 ，1 3 4 5 2 1），每條染色體上的編碼字符順序從左至右依次表示貨車檢修項目所在股道號排列，字符本身表示各檢修項目下工序序號。例如，第一染色體（1 1 5 3 4）中“5”表示該敞車執行第5道檢修工序時在第3股道；“3”則表示該敞車執行第3道檢修工序時在第4股道。相應地，第2、第3、第4條染色體依次表示平車、棚車、罐車，其字符串含義同上。取m1為0.4，m2為0.6，經編程實現選擇、交叉、變異和篩選，算法求解完成，目標函數收斂圖如圖4所示。由圖4可以看出，當迭代次數達到 48次時得到最優解（3 3 2 3 3 1，4 3 1 0 2 6，2 2 2 3 4 1，4 4 1 0 2 4），其中“0”表示該類車型不進行此項檢修作業。對應的得到目標函數值為27.64 h， 占用總時間為65.5 h，調車時間為2.4 h，小于車輛段規定維修時間72 h。每道工序在相應股道進行檢修作業甘特圖如圖5所示。同樣，在迭代至48次時，適應度函數呈收斂狀態，適應度收斂圖如圖6所示。由此可以看出遺傳算法實現了檢修時間及轉線時間的縮減，在一定意義上實現了優化的目的，為貨車調車作業實現自動化提供了理論幫助。

4 結論

根據現行車輛段貨車檢修制度及車輛段調車作業的特點，在貨車檢修數量逐年增長、車輛段調車作業日益復雜、調車作業計劃編制水平低下的背景下，提高貨車車輛段調車作業質量及實際檢修能力具有重要意義。考慮到車輛段貨車檢修臺位及股道利用，建立貨車車輛段調車作業優化模型，并設計基于貨車檢修作業順序的改進遺傳算法進行求解，結合蘭州西車輛段實例對其進行驗證，得到以下結論。

（1）通過遺傳算法的反復迭代，進而逐步獲得問題的優化解，與目前車輛段采取的人工調度方式相比，可以充分地考慮到貨車檢修臺位及調車股道的適用性，進而提高車輛段檢修效率。

（2）合理地考慮車輛段車輛檢修作業順序，可以提高調車作業計劃的編制質量。

針對不同類型的貨車車輛段，調車計劃是保證調車作業的具體行動計劃，不僅僅要保證其質量，計劃編制的效率也是關鍵，調車計劃編制方法將是下一步研究的方向。