地鐵車輛段/停車場列車運營日計劃優化模型與算法研究

牟宗元，馬 亮

（1.西南交通大學 信息科學與技術學院，成都 611756；2.電子科技大學 光電信息學院， 成都 610054）

地鐵車輛段/停車場列車運營日計劃優化模型與算法研究

牟宗元1，馬 亮2

（1.西南交通大學 信息科學與技術學院，成都 611756；2.電子科技大學 光電信息學院， 成都 610054）

綜合考慮列車正線運營、車輛檢修、車輛調車等需求，將列車運營日計劃優化問題歸結為指派問題，并建立0-1整數規劃模型。針對優化模型的目標函數不確定性及為了提高求解效率，根據實際經驗和計劃編制優先原則，設計一種基于規則的啟發式算法，并利用計算機輔助決策實現運營日計劃的自動編制。通過實例驗證了模型和算法的有效性。

地鐵車輛段；停車場；列車運營日計劃；0-1規劃；啟發式算法

地鐵車輛段是實現車輛檢修、行車管理的基本生產單位，停車場除不能完成車輛定修等較大修程的檢修任務外，其它功能同車輛段一致[1]。車輛段運營組織以車輛檢修為中心，段內行車按計劃執行。目前，車輛段沒有相應的計劃自動編制輔助系統，全靠車場調度員（場調）依據運行圖、檢修需求、調車需求等信息手動編制計劃。計劃的下達依靠紙質文件當面交接或傳真下發至執行崗位，并通過在紙面上變更和電話通知執行崗位修正的方式調整計劃。因此，車輛段內行車組織存在計劃編制效率不高、計劃下達及變更手續復雜、人為因素影響大等問題，需要研究計劃自動編制的輔助系統，實現列車計劃的自動化管理。

1 列車行車計劃優化問題

地鐵車輛段/停車場的列車作業計劃分為運營日計劃和收車計劃。運營日計劃為每日去正線運營的列車規定了時間、經由轉換軌等信息，收車計劃規定了列車回庫的時間、股道等信息。列車作業計劃一般由場調負責編制，并下達給值班員、信號員等執行。

運營日計劃通常由夜班場調在編制完當日收車計劃后，依據列車運行圖、次日的檢修計劃、回庫車實際停放股道等信息進行編制，編制時需充分考慮第2天的檢修需求。同時，還應保證按運行圖順序發車，不堵車，減少調車或轉線作業等。收車計劃由場調在實際運行圖的基礎上，結合次日檢修需求安排回庫車停放股道，編制時要考慮接車效率、作業難度等因素，盡量保證不間斷接車，減少調車作業。

列車運營日計劃是為運行圖中規定的車次安排電客車承擔運營任務，即將車次指派給擔當的電客車。收車計劃為回段的電客車安排接車股道，即將電客車指派到指定的接車股道。列車運營日計劃和收車計劃的優化問題可看成一類指派問題[2]。下面重點論述列車運營日計劃優化的模型及算法設計過程。

2 運營日計劃優化模型

變量xij表示車次與電客車的關系：

設cij表示車次Pi指派給電客車Hj的費用，該費用包括指派的可行性和優化指標，在本文中可以歸納為滿足檢修需求、滿足調車需求、減少干擾等指標。若指派方案可行且達到優化指標，則費用低，否則費用相應增加。運營日計劃優化的目標是使得總指派費用最低，即目標函數為：

運營任務的指派要使得運行圖每個車次任務都有一輛電客車執行。因此，約束有：

表示每一個運營任務都需要由一輛電客車來承擔；

表示每一輛電客車最多承擔一個運營任務。

綜合公式（1）、（2）、（3），將運營日計劃指派問題歸納為如下數學模型：

3 優化模型的求解分析

運營日計劃指派模型屬于典型的0-1整數規劃問題。當運營任務數與電客車數相等時，即m=n，該問題變為平衡指派問題。當m＜n時，為非平衡指派問題，可構造n–m項虛擬任務，使問題轉化為平衡指派問題。匈牙利算法[3]是求解平衡指派問題的經典方法，但是匈牙利算法適用于模型規模較小且費用矩陣確定的指派問題。因此，很多學者開始研究針對大規模指派問題的啟發式算法[4～6]。

啟發式算法是一種基于直觀或經驗構造的算法，在可接受的花費下求得問題的一個可行解。在沒有約束或約束條件不足的情況下，可能得到很差的解。但是實際問題往往有很多約束及規則可循，在此限制下，從初始解（可以為空）出發，利用啟發式算法可以得到一個較好的解，該解可能不是最優解，但在實際工程中往往是滿足需求的一個較優解。

針對運營日計劃指派問題，由于該問題的費用系數較難確定，目標函數難以精確地定義，問題求解算法的選取存在困難。罰函數[7]可以給出目標函數，但是由于指派規模較大，求解上會消耗過多的時間，降低了編制的效率。因此，本文設計了一種基于規則的啟發式算法，根據現場大量經驗和固有的約束條件，制定優先規則，逐步搜索得到一個較優解。算法的優點是簡單，執行效率高，可以在合理時間內得到較好的答案。

4 基于規則的啟發式算法

分析運營日計劃編制固有的約束條件。結合實際經驗，制定計劃自動編制的優化規則。采用計算機自動決策方式生成運營日計劃。

4.1 約束條件

（1）運用車數應大于等于運行圖要求的車數；（2）一個車次任務只能派給一輛電客車；

（3）一輛電客車在同一時段，最多安排一個車次任務；

（4）列車能按計劃正常發車。

4.2 優化規則

場調在編制日運營計劃時，正線運營車對應的股道是指收車計劃中指定的股道，庫內車則是當前的實際股道，如果有調車計劃則是調車計劃的最終股道。需要說明的是，車輛段運用庫為減小占地規模，一般將長股道分為AG和BG兩部分，AG靠近咽喉端，BG在AG后遠離咽喉端，如圖1所示。若AG、BG都有發車，則必須AG車先發，然后BG車經過調車進入AG再發車，即AG計劃時間早于BG計劃時間。因此，在制定運營日計劃時要考慮AG、BG車輛的關系。

圖1 運用庫股道示意圖

自動決策的優化規則如下：

（1）無條件為指定車次安排車輛、股道，沒有指定則不安排；

（2）為庫備計劃安排指定庫備的車輛，沒有則不安排；

（3）根據高峰情況為高峰車安排高峰車次，沒有指定則不安排；

（4）為BG上有車的AG車輛安排車次，以空閑AG為BG的調車、出車準備條件；

（5）為其它的AG車輛安排車次；

（6）為BG車輛安排車次；

（7）安排中保證AG的計劃時間在BG的計劃時間之前。

4.3 啟發式算法

根據約束條件和優化規則，設計基于規則的啟發式算法求解運營日計劃優化模型，算法步驟如下：

（1）初始化，獲取運營日計劃編制的基礎數據，主要有運行圖、檢修計劃以及回庫車停放股道；

（2）判斷運用車數是否滿足運行圖要求的車數，若滿足，進入下一步，若不滿足則顯示提示信息，并結束；

（3）數據處理，提取運行圖車次任務，按發車路徑將發車股道分為兩組，建立車與股道及檢修需求的對應關系；

（4）為指定車次的情況安排車輛，沒有則不安排；

（5）為庫備計劃安排庫備車輛，沒有則不安排；

（6）對有高峰需求的車，安排高峰車次；

（7）按發車股道分組交替為AG的運用車安排車次，優先為BG有車的AG車安排車次，直到AG上的車全部安排完；

（8）按發車股道分組交替為BG的運用車安排車次，以空閑AG為BG的調車、出車準備條件，確保BG的計劃時間晚于AG的計劃時間，直到車次全部安排完畢。

算法流程如圖2所示。

圖2 基于規則的啟發式算法流程圖

5 實驗結果

在地鐵車輛段/停車場綜合自動化平臺下，利用C#語言編程實現了營運日計劃編制模塊。數據來源于成都地鐵3號線，主要包括列車運營任務及車輛信息，如表1和表2所示。

表1 列車運營任務

表2 車輛信息

使用地鐵車輛段/停車場綜合自動化系統中的運營日計劃自動決策模塊自動求解，得到優化的運營日計劃，界面如圖3所示。

由結果可知，系統先安排停在17股道的324車作為庫備車，次日有檢修的325、326、327和328車不再安排上線運營，對于有高峰需求的301和309車，系統自動為其分配119和120的高峰車次。其它車次按照“先AG后BG，交替安排”的規則，自動分配到對應的電客車。系統根據運行圖、檢修需求、運用車及股道信息，采用基于規則的啟發式算法自動決策出運營日計劃，經過人工修改確認后即可作為正式的計劃。

圖3 運營日計劃自動編制界面

6 結束語

列車計劃自動編制是地鐵車輛段/停車場綜合自動化的重要組成部分。本文在分析現有人工編制方法存在效率低下和易錯等問題的基礎上，以運營日計劃編制為例，建立了運營日計劃優化的指派模型，在綜合考慮實用性和效率的情況下，設計了一種基于規則的啟發式算法，實現計劃的自動快速編制，得到滿意的結果。同時，利用該方法也可自動編制收車計劃，從而實現列車計劃的自動編制。

[1]中華人民共和國建設部.GB 50157-2013地鐵設計規范中國標準書號[S].北京：中國計劃出版社，2013.

[2]姚恩瑜，何 勇，陳仕平.數學規劃與組合優化[M].杭州：浙江大學出版社，2001：142-144.

[3]KUHN H W.The Hungarian Method for the Assignment Problem[J].Naval Research Logistics,2005,52(1):7-21.

[4]李 言，陳祖安，徐躍飛，等.指派問題的遺傳算法研究與實現[J].西安理工大學學報，1996（4）：271-276.

[5]殷人昆，吳 陽，張晶煒.蟻群算法解決指派問題的研究和應用[J].計算機工程與科學，2008（4）：43-45.

[6]孫曉雅，林 焰.一種新的離散粒子群算法在指派問題中的應用[J].計算機應用研究，2009（11）：4091-4093.

[7]陶世群，蒲保興.基于遺傳算法的多級目標非平衡指派問題求解[J].系統工程理論與實踐，2004（8）：80-85.

責任編輯 陳 蓉

Optimization model and algorithm of train operation daily plan for metro depot/parking lot

MOU Zongyuan1,MA Liang2
( 1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China;2.School of Optoelectronic Information,University of Electronic Science and Technology,Chengdu 610054,China)

Considering the requirements of train operation in the main line,maintenance and shunting,the optimization problem for train operation daily plan could be boiled down to an assignment problem,and then the 0-1 integer programming model was established.Because the objective function of the optimization model is uncertain,and in order to improve the solution effciency,a heuristic algorithm based on the priority principles was designed according to the practical experience and the priority principles of planning.Because of the objective function is uncertain and in order to improve the solution effciency,a heuristic algorithm based on the priority principles was designed according to the practical experience and the priority principles of planning.Meanwhile the train operation daily plans were drawn up automatically by using computer aided decision-making.The effectiveness of the model and algorithm was verifed by an example.

metro depot;parking lot;train operation daily plan;0-1 programming;Heuristic Algorithm

U231.92：TP39

A

1005-8451（2016）08-0001-04

2016-02-18

四川省科技支撐計劃項目（2015GZ0234）。

牟宗元，在讀碩士研究生；馬 亮，在站博士后。