分析基于列生成算法的動車組檢修計劃優(yōu)化

孟迎

【摘 要】隨著我國社會經(jīng)濟整體形式的良好發(fā)展，我國社會交通運輸行業(yè)也實現(xiàn)了快速發(fā)展，尤其是在火車客運方面實現(xiàn)了動車發(fā)展。動車組在客運方面的應用給我國人民的生活帶來了很大的方面，甚至提高了我國經(jīng)濟發(fā)展的速度。那么，在這種情況下，如何保證動車組的良好運行與發(fā)展就成為了有關(guān)部門關(guān)心的重點，即要盡量優(yōu)化動車組的檢修方案，這也是本文所要探討的主要內(nèi)容。

【關(guān)鍵詞】列生成算法；動車組；檢修計劃

【中圖分類號】 F287.3【文獻標識碼】 A【文章編號】1672-5158（2013）07-0054-02

動車組已經(jīng)成為了我國人民出行良好的選擇，而動車組檢修計劃的好壞對于動車組運行效率的高低、動車組維修費用的高低等都有著重要的意義，最總要的是良好的動車組檢修計劃能夠在很大程度上提高我國動車組車輛的優(yōu)化配置。但是從研究角度來講，對動車組檢修計劃的維修還相對較少，研究力度和深度都嚴重不足，直接限制了我國動車組的整體發(fā)展。正因如此，本文要總結(jié)國內(nèi)外先進的維修經(jīng)驗，結(jié)合自身的實際情況，建立具有特色的動車組檢修計劃，實現(xiàn)檢修計劃的優(yōu)化。

一、問題概述

對于動車組檢修而言其需要一個完善的檢修計劃，這樣的計劃就是我們保證動車組檢修質(zhì)量的關(guān)鍵，而其中檢修計劃的編制是進行檢修的主要依據(jù)，而檢修計劃的編制主要是指“考慮作業(yè)時間在一天以上的動車組檢修約束，根據(jù)動車組當前的工作狀態(tài)，提前一天到三天安排需要進行二級以上檢修的動車進入到待檢狀態(tài)，并生成動車組的運用計劃”。

具體而言動車組檢修計劃的基本特征分為以下幾點，第一點，已知的信息條件。其一，交路段狀況，主要是指該交路段的起始點，動車在該交路段的起始時間以及運行的總時間、總里程等等。其二，檢修基地狀況，是指動車組維修所在的車站或者整個線路所連接的線路，檢修的能力以及所需要的檢修時間，所需要的備用車數(shù)量等等。其三，動車組狀況，這種狀況主要是動車組總運行里程以及所歷史所行使的時間等等，同時通過檢測，也能夠了解到該動車組是否需要維修，也就是說能夠判斷出該動車組是否為待檢車輛。第二點，需要進行約束的信息條件。要優(yōu)化動車組檢修計劃就要從條件約束開始，只有這樣才能夠保證檢修的實際效果。要限制動車組相鄰的兩個路段之間的時間；相鄰路段中的交叉點同時為兩個交路段的起點和終點；動車上次檢修到這次檢修之間的時間一定要控制在安全運行時間之內(nèi)，路程也需要控制在一定的范圍之內(nèi)；使用中的動車組數(shù)量也要保證守恒，這樣才能夠真正保證車輛的正常運行。

二、建構(gòu)檢修網(wǎng)絡

檢修網(wǎng)絡的建構(gòu)需要借助于很多參數(shù)，不同參數(shù)存在著不同的意義，其中H表示的是檢修計劃的整個周期，K則表示在檢修期間動車組現(xiàn)在的檢修級別，而M表示的是檢修基地的集合，初次之外還存在很多小的參數(shù)。而檢修網(wǎng)絡的建構(gòu)需要從以下幾個步驟進行。

第一步，建結(jié)點。結(jié)點的建立需要從不同的方便進行，首先，要建立檢修基地的結(jié)點，在整個網(wǎng)絡中這個結(jié)點可以用ovm表示，以同樣的方式要將該結(jié)點進行H次的復制，這樣所獲得的檢修結(jié)點就記做mhv，各個不同檢修結(jié)點放到一起的整體就記為集合MV。其次，夜間結(jié)點的建立，夜間結(jié)點主要建立在那些不是檢修地點，但是卻是交路段中的起始點的位置，該位置的結(jié)點都記做sov，同樣也要進行N此的復制，這樣所生成的結(jié)點標記以及夜間結(jié)點的整體集合分別為shv、Vs。而在這一步驟中所有建立的結(jié)點都可以用集合V來表示。

第二步，建接續(xù)弧。在接續(xù)弧中主要包括交路段弧、檢修弧以及等待弧等內(nèi)容，不同類型的弧所表示的內(nèi)容是不同的，其標記方式也是不同的，但是，從總體而言，所有弧都可以用集合A表示。

第三部，建網(wǎng)絡。檢修網(wǎng)絡圖是進行動車組安全檢修的關(guān)鍵內(nèi)容，是一種計劃上的保障，這種網(wǎng)絡圖建立起來之后可以用N（V，A）表示，而建立起來的網(wǎng)絡圖大致如圖1所示：圖1 動車組檢修連續(xù)網(wǎng)絡圖

三、列生成算法在動車組檢修中的應用

在動車組檢修中存在著很多充滿了變動性質(zhì)的條件，這樣就為動車組檢修計劃的優(yōu)化造成了很大的障礙，所以，面對如此多的變量，我們需要運用一種行之有效的運算方法，而其中列生成算法就是一種有效的模型求解方式。

列生成算法能夠很直接的找到問題的下界，“其常常被嵌入分枝定界算法中進行求解”，這種方法就比較適合與動車組檢修計劃中各種計算模型的求解。從總體而言，列生成算法的基本思路為，對于變量的考慮，每次只限于其中的一小部分，并不是對計算中的所有變量都考慮入內(nèi)，而所求得的內(nèi)容也是其中的一個限制問題，這樣就能夠較輕松的收獲單純乘子，同時要善于利用價格中的問題以及其子問題來實現(xiàn)對限制主問題的解決。

首先，生成可行解。可行解的生成也是需要通過幾個步驟實現(xiàn)的，第一步是要復制所構(gòu)件的網(wǎng)絡，這樣就形成了總網(wǎng)絡N。第二步，主要是對需要進行檢測的動車組進行排列，排列的順序主要是以動車組的剩余運行里程進行排序，方向是從少到多，同時，要制定一個可行的運行計劃。同時要根據(jù)“深度優(yōu)先”的原則，從待檢動車組初始結(jié)點開始進行搜索，一直要搜索到在檢修周期內(nèi)到達可行的動車組檢修基地，同時還要根據(jù)該動車組的實際情況確定所需要的檢修時間來選擇等待弧。而在檢修工作完成之后，還需要選擇一個擔當交路，從而形成一個新的行駛路徑，同時刪除除了等待弧以外的所有弧。第三步，復制接續(xù)網(wǎng)絡，形成完整的網(wǎng)絡N，第四步，對于那些非檢測動成要保證其能夠在原有的交路段進行基本擔當工作，同時也要適當刪除無用的弧，對于剩余弧以及剩余非待檢動車重新進行線路的生成。

其次，確定分枝策略。對于動車組檢修計劃的優(yōu)化而言，是一個對線性問題的規(guī)劃，這種類型常用的分枝策略主要是把求解結(jié)果中的分數(shù)解變量強行的設置為1與零，最后劃分解空間，對分數(shù)解進行刪除處理。但是從實際工作角度來講，采用這種列生成法對整個模型進行求解，0分枝方法對問題的解決來說并沒有很大的實際意義，問題的收斂率也會受到限制，所以，最好只選擇1分枝進行求解。

最后，算法的流程。對于動車組這樣一個高科技含量的現(xiàn)代化交通工具，其檢修計劃必然也需要以現(xiàn)代化的運算方式計算機進行，所以，進行動車組檢修計劃的求解過程中，也應該利用計算機來實現(xiàn)，經(jīng)常采用的軟件以及程序都會隨著計算機技術(shù)的發(fā)展而不斷更新，而大致的算法流程如圖2所示：

素有很多種，我們需要不斷的進行總結(jié)與綜合運用，更重要的是對于動車組的檢修工作而言，我們還需要在不斷的實踐工作中進行研究，以提高檢修計劃的實用性。

結(jié)束語：

本文主要對動車組計算過程中所需要解決的問題，以及網(wǎng)絡的構(gòu)件等內(nèi)容進行了簡單的論述，主要目的就是提高我國動車組檢修工作的共組效率以及工作質(zhì)量，盡量減少動車組檢修次數(shù)，提高動車組的經(jīng)濟價值與社會價值。同時通過以上分析還簡單認識到了列生成算法在我國動車組檢修計劃優(yōu)化中的應用方式，這種方式的應用有其非常適合的一面，也存在不適應的一面，所以需要我們再日后的實際工作中進一步總結(jié)動車組檢修計劃的優(yōu)化方式。

參考文獻

[1] 張才春，陳建華，花偉.基于不同檢修能力的動車組運用計劃研究[J].中國鐵道科學，2010（05）

[2] 苗建瑞，王瑩，楊肇夏.基于最優(yōu)接續(xù)網(wǎng)絡的動車組交路計劃優(yōu)化模型與算法研究[J].鐵道學報，2010（02）

[3] 花偉，張才春，范振平，徐利民.動車組動態(tài)備用方式研究[J].鐵道運輸與經(jīng)濟，2011（01）

[4] 苗建瑞，王瑩，楊肇夏.基于最優(yōu)接續(xù)網(wǎng)絡的動車組交路計劃優(yōu)化模型與算法研究[J].鐵道學報，2010（02）

[5] 周愛生，高文佳，閆文立.提高CRH2型動車組三級修檢修效率的幾點建議[J].鐵道機車車輛，2011（03）