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

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

（蘭州交通大學(xué) 機(jī)電工程學(xué)院，甘肅 蘭州 730070）

0 引言

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

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

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

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

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

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

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

貨車車輛段的調(diào)車作業(yè)基本包括所有貨車在段內(nèi)有向移動(dòng)的全部?jī)?nèi)容，是將貨車檢修任務(wù)和車輛段檢修資源調(diào)動(dòng)起來(lái)的關(guān)鍵所在。

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

2.1.1 模型建立

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

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

2.1.2 初始條件

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

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

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

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

（4）股道相容性約束：當(dāng)某一股道上有貨車進(jìn)行檢修作業(yè)或占用時(shí)，該股道不可停靠2輛及以上貨車。

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

2.2 模型求解

2.2.1 遺傳算法

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

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

（2）適應(yīng)度函數(shù)。在遺傳算法中，依靠適應(yīng)度函數(shù)值來(lái)衡量群體中個(gè)體適應(yīng)環(huán)境的能力，適應(yīng)度函數(shù)通常是由目標(biāo)函數(shù)轉(zhuǎn)換而成，函數(shù)值越大的個(gè)體將有機(jī)會(huì)獲得更大的機(jī)會(huì)繁衍下一代。根據(jù)調(diào)車作業(yè)優(yōu)化模型，貨車占線及轉(zhuǎn)線的時(shí)間越大，則表明所產(chǎn)生的方案越不理想，也就意味著被淘汰的可能性越大。由目標(biāo)函數(shù)變換得到的適應(yīng)度函數(shù)計(jì)算公式為

式中：Ti表示進(jìn)行第i道檢修工序的最小檢修時(shí)間，h；Fi表示轉(zhuǎn)線至第i道檢修工序所在股道的最小時(shí)間，h。

（3）選擇。研究采用隨機(jī)競(jìng)爭(zhēng)選擇方式，假設(shè)群體大小為Ni，首先采用輪盤(pán)賭的形式選擇1對(duì)個(gè)體i，j，則任意個(gè)體i的適應(yīng)度為fi，j的適應(yīng)度為fj，然后2個(gè)個(gè)體間進(jìn)行競(jìng)爭(zhēng)，適應(yīng)度值高的被選中，如此反復(fù)操作直到選滿，個(gè)體被首先選中的概率為

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

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

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

（5）算法終止。設(shè)置迭代次數(shù)，達(dá)到最大次數(shù)時(shí)運(yùn)算結(jié)束并輸出結(jié)果。

2.2.2 算法求解

求解步驟如下。

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

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

步驟3：利用合理的編碼形式將實(shí)際問(wèn)題轉(zhuǎn)換，并且生成初始種群。

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

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

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

3 實(shí)例分析

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

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

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

續(xù)表

（2）貨車檢修轉(zhuǎn)線時(shí)間如表2所示。

表2 檢修轉(zhuǎn)線時(shí)間表 hTab.2 Maintenance transfer schedule

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

表3 遺傳參數(shù)設(shè)置Tab.3 Genetic parameter setting

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

4 結(jié)論

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

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

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

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