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

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

0 引言

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

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

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

1 車輛段線區(qū)布局

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

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

2 貨車車輛段調(diào)車模型及求解

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

2.1 貨車車輛段調(diào)車模型

2.1.1 模型建立

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

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

2.1.2 初始條件

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

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

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

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

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

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

2.2 模型求解

2.2.1 遺傳算法

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

（1）編碼設計。將貨車需要進行的若干項檢修項目視為具有遺傳性質(zhì)的染色體，并且將其分配到不同股道，研究采用自然數(shù)向量表示的編碼方式，將貨車需要進行的檢修項目進行自然數(shù)排列，向量τ= {r1，r2，…，rn}代表一個完整檢修作業(yè)，從r1到r2，…，rn-1到rn，再從rn返回到r1。例 如，向 量τ為{1，2，3，4，5，6，7，8，9，10}的排列，表示一個完整的檢修作業(yè)集合有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）適應度函數(shù)。在遺傳算法中，依靠適應度函數(shù)值來衡量群體中個體適應環(huán)境的能力，適應度函數(shù)通常是由目標函數(shù)轉換而成，函數(shù)值越大的個體將有機會獲得更大的機會繁衍下一代。根據(jù)調(diào)車作業(yè)優(yōu)化模型，貨車占線及轉線的時間越大，則表明所產(chǎn)生的方案越不理想，也就意味著被淘汰的可能性越大。由目標函數(shù)變換得到的適應度函數(shù)計算公式為

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

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

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

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

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

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

2.2.2 算法求解

求解步驟如下。

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

步驟2：算法相關參數(shù)設置。

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

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

步驟5：求最優(yōu)解至符合遺傳終止條件。

步驟6：輸出最優(yōu)結果并進行分析。

3 實例分析

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

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

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

續(xù)表

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

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

（3）遺傳參數(shù)設置如表3所示。

表3 遺傳參數(shù)設置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”表示該敞車執(zhí)行第5道檢修工序時在第3股道；“3”則表示該敞車執(zhí)行第3道檢修工序時在第4股道。相應地，第2、第3、第4條染色體依次表示平車、棚車、罐車，其字符串含義同上。取m1為0.4，m2為0.6，經(jīng)編程實現(xiàn)選擇、交叉、變異和篩選，算法求解完成，目標函數(shù)收斂圖如圖4所示。由圖4可以看出，當?shù)螖?shù)達到 48次時得到最優(yōu)解（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”表示該類車型不進行此項檢修作業(yè)。對應的得到目標函數(shù)值為27.64 h， 占用總時間為65.5 h，調(diào)車時間為2.4 h，小于車輛段規(guī)定維修時間72 h。每道工序在相應股道進行檢修作業(yè)甘特圖如圖5所示。同樣，在迭代至48次時，適應度函數(shù)呈收斂狀態(tài)，適應度收斂圖如圖6所示。由此可以看出遺傳算法實現(xiàn)了檢修時間及轉線時間的縮減，在一定意義上實現(xiàn)了優(yōu)化的目的，為貨車調(diào)車作業(yè)實現(xiàn)自動化提供了理論幫助。

4 結論

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

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

（2）合理地考慮車輛段車輛檢修作業(yè)順序，可以提高調(diào)車作業(yè)計劃的編制質(zhì)量。

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