動車組高級修計劃優(yōu)化模型及算法研究

武建平， 何君禮, 林柏梁， 王 輝， 張旭輝， 王忠凱

(1. 北京交通大學 交通運輸學院，北京 100044； 2. 中國鐵路設計集團有限公司 交通運輸規(guī)劃研究院， 天津 300142；3. 中國鐵路沈陽局集團有限公司 客運部，遼寧 沈陽 110000; 4. 中國鐵道科學研究院集團有限公司 電子計算技術研究所，北京 100081； 5. 中國鐵路上海局集團有限公司 車輛部，上海 200071)

高級修計劃是動車組運用與檢修管理工作的重要組成部分，涵蓋三、四、五級檢修。由于復雜的檢修規(guī)程、全年不均衡的客流分布、檢修車間有限的檢修能力以及長達2～8周的檢修耗時(修時)等原因，動車組高級修計劃需要以自然年或更長的時間為規(guī)劃期提前進行編制。編制該計劃的主要目的是在合理利用有限檢修資源以及遵守既定檢修規(guī)程的條件下，為計劃期內(nèi)客流長高峰期時期(如春運、暑運等)提供足夠的技術狀態(tài)良好的動車組。該計劃是動車組運用計劃、動車組二級修計劃以及檢修基地工作組織的先決條件。

自2008年京津城際鐵路開通以來，我國高速鐵路取得迅猛發(fā)展。按照文獻[1]的要求，先期投入運營的動車組在未來幾年內(nèi)會集中進入高級修作業(yè)環(huán)節(jié)。由于高級修修時較長，當該作業(yè)發(fā)生在客流高峰時期，會因為上線動車組數(shù)量不足造成旅客的出行需求無法得到滿足，由此帶來的不僅是運營收入的損失，還有出行者對鐵路運輸?shù)臐M意度下降，而提前檢修又會造成檢修成本的增加。同時，在檢修能力給定條件下，集中送修還會造成修時延長，影響車輛的運用效率。因此，科學地制定出既滿足用車需求又盡可能降低檢修成本的高級修送修計劃是目前高速鐵路運輸領域亟待解決的一個科學技術難題。

國內(nèi)外不少專家學者針對相關問題進行了研究，并取得一定成果。Marti等[2-3]以荷蘭鐵路車輛的預防性檢修制度為背景，從整數(shù)規(guī)劃的角度出發(fā)，構建了鐵路車輛檢修計劃編制模型。Abbink等[4]以高峰時期能力短缺最小化為目標構建了動車組的運用優(yōu)化模型，并采用CPLEX進行求解。Alfieri等[5]和 Giacco等[6]針對動車組的定期預防維修問題建立多商品流模型，提前調(diào)整運用計劃使未來1～3 d內(nèi)需要檢修的動車組及時得到維修。王瑩等[7]以動車組可行運用計劃為決策變量，以待檢動車組檢修前的累計運行里程最大化為優(yōu)化目標，建立動車組檢修計劃優(yōu)化模型，并將列生成算法嵌入分枝定界算法進行求解。Li等[8]針對動車組的運用與二級檢修計劃建立了0-1整數(shù)規(guī)劃模型，考慮了動車組和運行徑路之間的匹配關系、動車組的檢修要求和動車所的檢修能力限制等約束條件。王忠凱[9]構建了動車組運用與檢修一體化編制的數(shù)學優(yōu)化模型，針對動車組運用檢修計劃優(yōu)化方法，提出帶有狀態(tài)約束的旅行商問題和帶拓撲約束的車間調(diào)度問題，給出了這兩類問題的數(shù)學描述，并設計了求解問題的構造圖和基于最大最小蟻群優(yōu)化算法的通用求解方法。以上文獻均是針對動車組的運用檢修計劃編制問題，而專門針對動車組高級修計劃問題的研究較少。李燕等[10]提出了一種預測動車組高級修檢修量的方法，為高級修計劃的編制提供了決策依據(jù)。Lin等[11]針對動車組高級修問題，通過設立狀態(tài)函數(shù)構建了0-1整數(shù)非線性規(guī)劃模型，并利用模擬退火算法進行求解。Wu等[12]通過構建時間-狀態(tài)網(wǎng)絡將動車組高級修送修問題轉化為網(wǎng)絡上的徑路選擇問題，并構建了相應的數(shù)學規(guī)劃模型與求解策略。在動車組高級修其他相關方面，陳彥[13]、王忠凱等[14]、賈志凱[15]等針對動車組高級修車間工藝流程進行了優(yōu)化研究。王東屏等[16]、王紅等[17]等從單一部件和多部件的維修策略進行了深化研究。到目前為止，針對動車組高級修計劃的優(yōu)化研究僅見于文獻[11-12]。

目前，在動車組高級修計劃編制的實際工作中仍是借助Excel表，以人工經(jīng)驗編制計劃。該方法不僅效率較低，而且易造成動車組過度檢修，增加檢修成本。在動車組高級修檢修量逐年上升的形勢下，該方法顯然已經(jīng)不能滿足實際的工作需求。在充分借鑒上述研究成果的基礎上，本文結合我國動車組高級修計劃編制過程中涉及的諸多因素，構建了0-1整數(shù)規(guī)劃模型，并設計了相應的粒子群求解策略，以實現(xiàn)動車組高級修計劃的優(yōu)化。

1 問題描述

動車組的日常檢修計劃與運用計劃存在著很強的耦合關系，所以日常檢修計劃通常與運用計劃協(xié)同優(yōu)化制定。但是動車組的高級修修時較長，在存在用車長高峰時期且檢修能力有限的條件下，高級修送修計劃需要提前制定。編制動車組高級修計劃是以動車組的歷史運用數(shù)據(jù)與檢修記錄為基礎，結合檢修規(guī)程、不同時期不同車型的用車需求以及有限的檢修能力等因素來確定具體的送修時間。由于高級修計劃是提前編制的，是動車組運用計劃以及日常檢修計劃的前提條件，所以該計劃在編制時無需考慮全年的動車組運用以及日常檢修計劃，只需將動車組的高級修率(處于高級檢修狀態(tài)的動車組列數(shù)占動車組保有量的比率)控制在給定的閾值之下，能為全年的各段時期(尤其是客流長高峰時期)提供預期數(shù)量的動車組即可。高級修計劃編制完成后，根據(jù)高級修計劃可以供應的車組數(shù)量以及實際的運輸需求再實時制定動車組運用計劃、日常檢修計劃以及檢修基地的檢修生產(chǎn)計劃。編制高級修計劃需重點考慮以下三方面。

1.1 高級修檢修周期與檢修等級

鐵路動車組運用維修規(guī)程中部分動車組高級修檢修周期見表1。

表1 CRH系列部分動車組高級修檢修周期

由表1可見，四、五級修的檢修周期長度分別為三級修檢修周期長度的2倍和4倍。此外，動車組相鄰兩次高級修之間的間隔不能超過一個三級修的檢修周期[1]。所以，動車組高級修的檢修周期等于該型號動車組的三級修檢修周期，只是相鄰兩次高級修的修程不同。根據(jù)這一規(guī)律可畫出動車組高級修檢修等級循環(huán)圖,見圖1。

1.2 用車需求

我國鐵路客流量主要集中在每年的春運、暑運、國慶節(jié)以及各小長假期間，其他時間較少。客流全年分布不均造成了不同時期動車組用車需求的不同。一個質(zhì)量良好的高級修送修計劃須滿足各時期的用車需求。結合實際用車需求，本文在不同時期設置不同的高級修率上限來確保各時期的用車需求，如在客流高峰時期設置較低的高級修率，在客流低谷則相反。同時，根據(jù)實際需求，各型號動車組的在修列數(shù)也不能超過相應的上限值。

1.3 檢修能力

本文是以“天”為最小單位時間進行計劃的優(yōu)化，且不涉及具體的檢修流程，所以只需考慮各等級高級修每天的在修列數(shù)即可。此外，由于檢修車間的能力限制，還應考慮一定的送車間隔。

2 優(yōu)化模型

本文以動車組在本次高級修周期內(nèi)的總損失里程最少為優(yōu)化目標，考慮了檢修規(guī)程、運車全年的用車需求以及檢修能力等實際約束條件，建立0-1整數(shù)規(guī)劃模型。由于動車組高級修送修計劃每年編制一次，而高級修檢修周期一般都大于1年，所以在目標計劃期內(nèi)同一列動車組至多檢修一次。基于此本文假設在計劃期內(nèi)動車組至多進行一次高級修作業(yè)。而該模型構建的首要基礎是生成動車組的備選送修時間集合，即送修時間窗。

2.1 備選送修時間集合生成策略

首先需要推算各動車組的高級修預計到修時間[10]。由于動車組高級修計劃的編制不考慮動車組運用以及二級修計劃，所以在推算預計到修時間時是以規(guī)劃期內(nèi)動車組的每天平均運行里程為依據(jù)進行的。推算出每列動車組的預計到修時間后，以其為中心生成動車組的送修時間窗。對于每列動車組來說，其時間窗在以“天”為最小時間單位時是連續(xù)的，所以可以用一個時間區(qū)間表示。推算動車組高級修預計到修時間需要準備的數(shù)據(jù)見表2。

此處以某一列動車組為例進行預計到修時間的推算，涉及符號定義見表2。

表2 符號定義

我們可以得到動車組距上次高級修的運行里程

( 1 )

動車組的高級修送修日期推算公式為

( 2 )

式( 2 )中，動車組的預計到修日期以里程周期和時間周期中的先到者為準。在推算出預計到修日期之后，以預計到修日期為中心，檢修周期的浮動區(qū)間為范圍生成動車組高級修備選送修時間集合。具體步驟為

Step1準備動車組集E和空集E′。

Step2從集E中任意取出一組動車e，并按照式( 1 )與式( 2 )推算動車組預計到修時間t。

Step6若E為空，轉Step7，否則轉Step2繼續(xù)執(zhí)行Step2到Step6。

Step7令E=E′，輸出所有動車組的送修時間集We(e∈E)，算法結束。

有時送修時間窗內(nèi)的備選時間無法滿足模型求解的需要，可適當擴大時間窗，但窗口的擴大會增加模型的求解難度。

2.2 數(shù)學優(yōu)化模型

確定每列動車組的送修時間窗后，定義以下三組0-1決策變量為

模型中使用的集、角標和參數(shù)定義見表3。

表3 模型中使用的集、下標和參數(shù)定義

模型的目標函數(shù)是以動車組的損失里程(檢修周期上限與該周期內(nèi)的實際運行里程之差)最小為優(yōu)化目標。最小化損失里程，可以增大相鄰兩次高級修之間的間隔，從而減少檢修次數(shù)。對于各次高級修的檢修成本，本文根據(jù)檢修等級將其視為定值，不予考慮。因此，最小化損失里程可以實現(xiàn)高級修成本的最小化。模型構造

( 3 )

( 4 )

( 5 )

( 6 )

( 7 )

( 8 )

k∈[WSe,WEe] ?e∈Em∈Mg∈G

( 9 )

?g∈Ge∈Em∈M

(10)

k∈[WSe,WEe] ?e∈Em∈Mg∈G

(11)

(12)

?e∈Em∈Mg∈Gt∈T

(13)

各約束條件所代表的實際意義如下：式( 4 )保證了每列動車組在時間窗中只能選一個時間送修；式( 5 )保證了在不同時間處于高級修狀態(tài)的動車組標準列數(shù)低于給定的高級修率上限值與保有量之積；式( 6 )保證了不同時間任意車型的在修車列數(shù)不超過在修列數(shù)的上限值；式( 7 )保證了在計劃期內(nèi)處于檢修狀態(tài)的動車組列數(shù)不超過對應等級的最大檢修能力；式( 8 )保證了在計劃期內(nèi)檢修車間可同時接收動車組的組數(shù)；式( 9 )保證了檢修的完整性，即一旦檢修工作開始就不能停下直到檢修結束；式(10)保證了動車組處于高級修狀態(tài)的范圍；式(11)保證了送修間隔連續(xù)性；式(12)保證了檢修車間處于送修間隔的范圍；式(13)是決策變量的取值。

3 求解算法設計

對于配屬動車組列數(shù)較多的鐵路局集團有限公司，數(shù)學模型求解的復雜度較高，若應用傳統(tǒng)的運籌學最優(yōu)化方法求解，很難在可接受的時間內(nèi)得到優(yōu)化解。對此，本文結合該模型特點，采用具有求解精度高且尋優(yōu)速度快的粒子群算法[16]進行優(yōu)化求解。

3.1 模型約束條件的處理

在應用粒子群算法求解之前，需要對模型的約束條件進行處理。式( 4 )、式( 9 )～式(12)是邏輯約束，可以通過設定解的編碼規(guī)則予以實現(xiàn)，另外4組約束可通過懲罰函數(shù)法進行無約束處理，從而可將模型轉化為無約束的最優(yōu)化問題。

對于懲罰系數(shù)的取值，一方面需要結合動車組的實際運用情況，另一方面則根據(jù)約束的強度不同進行確定。令λ1、λ2、λ3、λ4為式( 5 )～式( 8 )的懲罰系數(shù)，其中式( 6 )的約束最強，式( 7 )最弱，懲罰系數(shù)的大小關系為λ2>λ1>λ4>λ3。則模型的目標函數(shù)可轉化為

(14)

3.2 粒子群算法相關策略

(1) 粒子編碼方式及初始解生成

每個粒子表示各動車組送修時間的一個整體方案，根據(jù)式( 4 )，可將粒子的維度取為動車組的總列數(shù)，粒子中各維的取值依次等于對應動車組的送修時間，具體形式

Ti=(ti1,ti2,…,tie,…,ti|E|)

i=1,2,…,Ie∈E

(15)

式中：tie為第i個粒子中第e列動車組的送修時間；I為粒子群規(guī)模；|E|為動車組的總列數(shù)。

針對任意粒子中的每一維度(動車組e)的取值，通過在[WSe,WEe]內(nèi)隨機選取送修時間來確定，從而產(chǎn)生初始解。

(2) 慣性權重

為了使粒子群算法在進化早期具有較好的搜索能力而在進化后期具有較好的開發(fā)能力，本文采用線性時變慣性權重

ω(r)=ωmax-(ωmax-ωmin)r/Rmax

(16)

式中：ω(r)為第r次迭代時慣性權重的取值；ωmax、ωmin分別為慣性權重的最大值、最小值；Rmax為最大迭代次數(shù)。

(3) 學習因子

同樣，為了使粒子群在前期加強全局搜索，在后期收斂于全局最優(yōu)，本文通過不斷減小自我學習因子和增大社會學習因子來實現(xiàn)，其變化方程

(17)

(18)

(4) 粒子進化方程

粒子以一定的速度(Vi)進行搜索進化，速度變量表示粒子位置的改變方向與改變量的大小，與粒子具有相同維度，則粒子的位置與速度的改變方程為

Vi(r+1)=ω(r)Vi(r)+c1(r)ξ(r)[Pi(r)-

Ti(r)]+c2(r)η(r)[G(r)-Ti(r)]

(19)

Ti(r+1)=Ti(r)+Vi(r+1)

(20)

3.3 算法步驟

Step2計算各粒子的適應度值。

Step3對于每個粒子，比較其適應度值與其歷史最優(yōu)位置適應度值的大小，如果當前適應度更優(yōu)，則更新粒子的歷史最優(yōu)位置。

Step4對于每個粒子，比較當前迭代次數(shù)的歷史最優(yōu)位置適應度值與全局最優(yōu)位置適應度值的大小，如果某一粒子的歷史最優(yōu)位置的適應度值更優(yōu)，則更新全局最優(yōu)位置。

Step5根據(jù)式(12)～式(14)計算慣性權重、自我學習因子與社會學習因子。

Step6根據(jù)式(15)、式(16)更新粒子的位置與速度，更新過程中粒子的位置與速度均不允許超出給定的范圍，若超出則取為邊界值。

Step7r=r+1如果r>Rmax，轉Step8，否則，轉Step2。

Step8算法結束，輸出計算結果。

4 案例分析

由于動車組實際數(shù)據(jù)保密而且非常復雜，所以這里只能給出經(jīng)過加工的數(shù)據(jù)，即各動車組的送修時間窗。該集合是根據(jù)動車組運用與檢修歷史數(shù)據(jù)，調(diào)用3.1節(jié)所述方法所生成。為表示方便，可將備選日期用日期序數(shù)來表示(以數(shù)據(jù)統(tǒng)計日期為第1天)，如2017年1月1日用138表示。動車組的備選送修時間集合，見表4(只列出送修時間備選在計劃編制期內(nèi)的動車組，其中符號M1、M2、M3分別表示CRB1B、CRH1E、CRH380D車型)。

表4 動車組備選送修時間集合

由表4中可知，共有60列動車組在計劃編制期內(nèi)發(fā)生高級檢修作業(yè)，其中送修時間最多的有101個備選日期，最少的只有36個備選日期。

此時，模型的目標函數(shù)可下式代替

(21)

應用Visual Studio 2010開發(fā)平臺，基于VC++語言，本文實現(xiàn)模型與算法的程序設計，計算環(huán)境為Intel處理器，2.00 GHz主頻，4.00 GB內(nèi)存。經(jīng)試驗，計算耗時為10 min左右，達到應用需求。求解迭代過程中的目標函數(shù)下降曲線見圖2。

從圖2可以看出，在前300次的迭代過程中，算法的搜索能力較強，可有效避免早熟現(xiàn)象的產(chǎn)生；而從第300次到第600次的迭代過程中，算法的開發(fā)能力變強，有利于最優(yōu)解的尋找；最后400次迭代過程目標函數(shù)值沒有變化，說明無約束問題的近似最優(yōu)解已經(jīng)生成。將求解結果進一步調(diào)整即可得到原問題的優(yōu)化方案，調(diào)整策略如下：

Step1按照論文中式( 1 )與式( 2 )計算出參與高級修計劃編制的動車組預計到修時間。

Step2將得到的松弛問題(近似)最優(yōu)解中的相同型號動車組高級修送修時間按照Step1計算出的預計到修時間的順序進行重排序。

Step3在計劃期內(nèi)逆向找到重排序后的方案中不滿足原問題約束條件的最晚時間段(稱為目標時間段)的起始時間和終止時間，并計算出目標時間段的跨度。

Step4將在目標時間段起始時間送修的動車組的送修時間在送修時間備選集的范圍內(nèi)向后移動，移動的長度是目標時間段跨度、送修時間備選集中最大值與計劃送修時間之差兩者之中的最小值。

Step5若無法后移，則將在目標時間段內(nèi)在修的動車組的送修時間在送修時間備選集范圍內(nèi)向前移動。

Step6對調(diào)整后的方案按照原問題約束條件進行檢查，重復Step3～ Step5，直到調(diào)整結果完全滿足原問題的約束條件或者調(diào)整結果連續(xù)兩次無改變?yōu)橹埂?/p>

最終方案見表5。

表5 動車組高級修送修時間表

根據(jù)優(yōu)化方案和人工方案繪制高級修率折線圖，見圖3。

從圖3可以看出，優(yōu)化方案的高級修率在各時期都保持在上限值之下且變化平穩(wěn)，滿足用車需求，在計劃執(zhí)行時可輕微調(diào)整即可；而人工方案的高級修率偏離閾值較遠且變化幅度大，在計劃執(zhí)行時需要不斷的調(diào)整。將優(yōu)化方法與人工編制方案相比，各指標見表6。

表6 不同方案各項指標對比

由表6可見，與人工方案相比，優(yōu)化方案在里程損失、超過高級修率上限值天數(shù)和編制時間等方面都有優(yōu)化。其中，損失里程從397.2萬km減少到311.5萬km，減少了85.7萬km，減少百分比為21.58%；超過高級修率上限值天數(shù)從162 d降到0 d，可以更好地滿足各時期的用車需求；計劃編制時間從7 d左右減小到10 min，編制效率大大提升。

5 結束語

本文考慮了動車組高級修的檢修周期、不同時期不同車型的用車需求以及檢修能力限制等實際約束，以動車組損失里程最少為優(yōu)化目標建立了0-1整數(shù)規(guī)劃模型，并設計了相應的粒子群求解策略。最后通過案例分析說明了該方法的合理性與有效性。相對于人工編制計劃，本文所述方法將動車組的損失里程降低了21.58%，將超過高級修率上限的天數(shù)從162 d降為0 d，將計劃編制時間從7 d左右縮短到10 min，因此，本文所述方法提高了動車組高級修送修計劃編制的質(zhì)量和效率。但本文只是優(yōu)化編制了配屬于一個路局的動車組高級修送修計劃，下一步需要從全路角度出發(fā)，優(yōu)化全路的動車組高級修送修計劃。