考慮列位合理占用的動車所調車作業計劃編制優化

戶佐安 ，鄭 磊 ，周 姝

（1.西南交通大學交通運輸與物流學院, 四川 成都 611756；2.西南交通大學綜合交通大數據應用技術國家工程實驗室, 四川 成都 611756；3.西南交通大學綜合交通運輸智能化國家地方聯合工程實驗室, 四川 成都 611756；4.中鐵二院工程集團有限責任公司, 四川 成都 610031）

動車所調車作業計劃是根據動車所檢修能力、場庫布局形式、出入所時刻、作業項目等編制的動車所運用組織指導性文件.它保證了動車組按時入所和上線運行，并在規定時間內利用各功能股道，實現檢修、整備、調移等作業的高效協同進行.隨著我國高速鐵路規模增大，上線運用動車組數量增加，傳統人工編制的動車所調車作業計劃存在很大的局限性，難以滿足現實需求，如何自動化編制高質量的動車所調車作業計劃成為動車組運用管理中亟須解決的問題.

國內外學者對動車所調車作業優化問題進行了大量研究，取得了較好成果.王忠凱等[1]以減少關鍵檢修線區的無效占用時間和降低調車路徑費用為目標，基于動車組轉線作業拓撲圖，建立調車作業計劃編制優化模型，采用改進蟻群算法進行求解；張惟皎等[2]考慮了存車線的列位占用，以提高存車線運用效率和減少調車走行距離為目標建立存車線運用優化模型，采用模擬退火法進行求解；王家喜等[3]考慮動車所的股道占用和進路占用沖突問題，以調車鉤數最小為目標建模，并采用粒子群算法進行求解；郭小樂等[4]把動車組總延誤時間最小作為優化目標，設計微進化算法進行模型的求解；Broek[5]提出了一種可自動構建分流計劃的綜合局部搜索方法，整合了動車組出入進路、作業任務、股道停放、列車路線，在交通規劃軟件和真實場景中的應用證明了該方法優于當時最先進的混合整數規劃算法；Haahr等[6]首次將動車組調車優化問題和列車單元重組優化問題相結合，通過基于分枝切割的方法求解這一綜合優化問題，并且對比了股道分配領域不同求解算法的性能，通過反例說明了傳統最優化方法的啟發式性質.陳韜等[7]提出了將高速鐵路樞紐站技術作業與動車所調車作業計劃協同編制的思想，以作業效率最大化為優化目標構建模型，設計了一種基于并行禁忌搜索策略的混合算法進行求解.韓寶明等[8]以最小化最晚完工時間為目標，建立動車所一級修靈活作業順序的數學模型，考慮動車組作業先后順序、單個動車組作業流程等條件，設計改進遺傳算法進行求解.

綜上，動車所調車作業計劃編制可歸結為一類多目標、多約束的大規模復雜優化問題，既有文獻多是基于旅行商、多商品流等問題的思想，建立混合整數規劃模型，采用啟發式算法進行求解，有較好的效果，但針對某些具體場景的研究尚有不足.一是部分研究忽略了調車作業進路安排，在較大規模案例中進路沖突問題將會凸顯，可能降低解的質量；另一方面，既有研究較少考慮動車組的長短編之分和股道雙列位占用對調車作業計劃編制的影響.本文基于我國動車所設施設備布局及動車組調車作業特點，考慮動車所股道兩個列位的合理占用，建立調車作業計劃編制優化模型，基于動車組可行路徑生成和作業優先次序交換設計模擬退火算法，并采用某動車所實際運營數據對模型和算法進行驗證.

1 問題分析

1.1 動車所內動車組作業項目及特征

為提高動車所內動車組的檢修整備效率，我國采用動車組一體化檢修制度，作業項目包括：出所和入所、一級修和二級修、聯合檢查、鏇輪和臨修、吸污和洗車、存車和熱備、解體和編組、轉線等.其中，一些作業具有前后銜接關系，例如一級修完成后需進行聯合檢查.動車所進行作業有白班和夜班之分：夜班多為一級修，作業時間較短但作業動車組數量多；白班多為是二級修或臨修與一級修結合，作業時間較長，但作業動車組數量少.

《鐵路動車組運用維修規則》[9]規定動車組的檢修作業原則上在其配屬的動車所內進行.因此，根據配屬關系和作業項目可將入所作業的動車組分為三類：本所配屬的需入庫作業動車組、本所配屬的不需入庫作業動車組和非本所配屬的動車組.由于動車所庫內檢修線相對庫外存車線數量較少，通常情況下需入庫作業動車組在所有入所動車組中占比最大，對該類動車組進行合理作業安排，提高檢修線的利用率，是動車所調車作業計劃編制中的重點.非本所配屬的動車組作業較簡單，通常只在存車線上過夜或進行吸污、上水作業.

1.2 動車所場庫布局對調車作業的影響

動車所調車作業計劃編制的影響因素較多，從動車所場庫布局角度來看，動車所平面功能區域的布置會直接影響動車組的作業流程，進而影響調車作業計劃的編制.例如，場庫布局為“檢查庫 + 庫前場 + 存車場”的動車所，如圖1（a）所示，動車組的檢修整備流程一般為“入所→（存車）→洗車→吸污→檢修→存車→出所”；場庫布局為“檢查庫 +存車場”的動車所，如圖1（b）所示，動車組的檢修整備流程一般為“入所→（存車）→檢修（可含洗車、吸污）→存車→出所”.動車所的股道類型和功能區域布置的多樣性使動車組的作業次序較為靈活，如洗車和檢修作業的先后次序可互換.此外，對于兼具存車線功能的洗車線和鏇修線，在股道后續占用不沖突的前提下，可安排已完成作業的動車組停放在該股道上以提高股道的利用率.

圖1 動車所場庫布置示意Fig.1 Layout schematic diagram of EMU depots

1.3 動車組編組狀態和列位占用的影響

我國鐵路動車組按編成輛數有短編動車組和長編動車組之分，按編組狀態可分為短編動車組單編、短編動車組重聯和長編動車組.短編動車組在編組上具有靈活性，根據出入所呈現的不同編組狀態，可劃分為不同情形，如表1所示.

表1 短編動車組編組狀態Tab.1 Marshalling state of short-form EMUs

為滿足長編和重聯動車組的檢修、整備、存車等作業需求，我國動車所股道的有效長均按照可以停放一列長編或重聯動車組的標準而設計的.事實上，動車所的每條股道均有兩個列位，若設有分割信號，則可停放兩列未重聯的短編動車組；若無分割信號，則可以選擇任一列位停放一列短編動車組.重聯動車組待解體、短編動車組待重聯、空閑存車線數量較少時，均會出現兩列短編動車組占用同一股道相鄰兩列位的情況.由于該兩列動車組的存放時間和作業項目可能存在差異，其調車作業次序及下階段的股道占用情況會受到較大影響.因此，編制動車所調車作業計劃應考慮股道列位的合理占用，盡力避免進路沖突、存車線占用沖突等問題.

一方面，由于未重聯短編動車組的出入所時刻、各作業完成時刻可能存在差異，若盲目地將兩列未重聯短編動車組停放在同一條股道，可能產生額外的轉線，降低調車作業效率.另一方面，動車所各功能區的股道數量固定，在動車組檢修任務日益繁重的情況下，若實現短編動車組對股道兩個列位的合理占用，且避免產生多余的轉線和進路沖突，則能夠提高股道的利用率，從而提高動車所的檢修能力和調車作業效率.

1.4 關鍵技術問題描述

目前，我國動車組運用組織有以下特點：動車組通常在白天上線運行，日常的一級檢修、洗車等一系列所內作業大多在夜間進行.在白班計劃中動車組的調車作業時間相對寬松，而對于作業較繁忙的夜班計劃，動車組出入所時刻、空閑股道狀態等對調車作業計劃編制的限制更顯著.基于此，本文研究的動車所調車作業計劃編制優化有以下兩個關鍵技術問題：一是如何在動車組出入所時刻及作業項目不同的情況下，合理確定動車組調車作業的先后次序及股道占用的具體情況，保證動車組按時出入所并能完成所有作業；二是如何在編制調車作業計劃時考慮實時的動車組編組狀態和股道及其列位占用情況，從而合理利用股道及其列位以提高調車作業效率.

2 模型建立

2.1 建模說明與假設

基于我國動車所的設施設備布局形式、動車所現行調車作業的特點及其計劃編制實際情況，對本文模型建立做以下說明：

1）針對單一類型動車所的調車作業計劃編制問題進行建模，編制周期為一個班計劃，即白班計劃或夜班計劃；

2）在動車所內進行檢修整備作業的動車組，從編組形式上包括短編動車組單編、短編動車組重聯和長編動車組，從動車組配屬上分為本所動車組和外所動車組；

3）動車所內的進路包括入所進路、調車進路和出所進路；

4）各動車組到達和出發時刻已知，即動車組在動車所內的停留總時間確定，必須在該時間內完成檢修整備作業；

5）本班計劃開始時，可能存在上一班計劃中入所但未出所的動車組；

6）滿足動車組轉線所需的實際最大時間，所有動車組均采用相同的最小轉線時間標準.

考慮到動車所調車作業的復雜性，為突出重點，降低模型復雜度及求解難度，做以下假設：

1）動車所的檢修班組的數量充足，每條檢修線可同時進行檢修作業；

2）動車所的股道均帶分割信號，即各股道都可停放兩列短編動車組.

2.2 模型參數

模型主要參數定義和說明如下：

E為動車組集合，E=EL∪ES=EW∪EO，其中：EL為短編動車組集合；ES為長編動車組集合；EW為本所動車組集合；EO為外所動車組集合.e為動車組索引，對于同一股道上先后緊鄰作業的動車組，定義后行車組e的前行車組為e′， ?e,e′∈E.

D為動車所股道集合, 由檢修線和其他股道兩大部分組成，D=DM∪DN=DM∪DS∪DW1∪DW2∪DX∪DI，其中：DM為檢修線集合；DN為除檢測線外的其他股道集合；DS為普通存車線集合；DW1和DW2分別為機洗線和人工洗車線集合；DX和DI分別為鏇修線和臨修線集合.d為股道索引, ?d∈D，特別地，用d1和d2表示股道的兩個列位，d1,d2∈d.

R為動車所內的進路集合，R=RA∪RD∪RS，其中：RA為白日交路集合；RD為夜晚交路集合；RS為調車作業進路集合.r為進路索引， ?r∈R.

Nr為不同咽喉區域的平行進路數量.

Ts為轉線作業的時間標準.

τ為同一進路上避免沖突的列車間隔時間.

ter,s、ter,f分別為動車組e執行進路r的開始時刻、結束時刻.

Pe為動車組e的作業項目集合，p為作業項目索引， ?p∈Pe，對于動車組e后緊鄰兩項作業，定義后項作業p的前項作業為p‘， ?p′∈Pe′.

Ne為常量，其值等于動車組e的作業項目數量.p=Ne時表示最后的作業項目，p=1 時表示最開始的作業項目.

Pd為動車所股道d可進行的作業項目集合.

Tep為動車組e執行作業項目p的時間標準.

tedp,s、tedp,f分別為動車組e在股道d上執行作業項目p的開始時刻、結束時刻.

te,a、te,d分別為動車組e的入所時刻、出所時刻.

ts、tf分別為本班調車計劃的開始時刻、結束時刻.

Ted為輔助變量，表示前行車組e‘離開股道d后，該股道可供后行車組e作業的時間.

θpp′為0-1輔助變量，動車組e作業p和p‘需要轉線取1，否則取0.

yedr為0-1輔助變量，股道d滿足動車組e承擔進路r的任務功能時時取1，否則取0.

sedp為0-1輔助變量，股道d滿足動車組e執行作業p功能時取1，否則取0.

cedp為0-1決策變量，考慮約束動車組e能在股道d進行作業p時取1，否則取0.

xedp為0-1決策變量，動車組e執行在股道d進行作業p時取1，否則取0.

2.3 優化模型

已知動車所班計劃中需進行各項作業的動車組數量，通過減少動車組不必要的轉線作業，降低調車進路發生時間沖突的幾率，有利于提高動車所的調車作業效率.采用本班計劃內的動車所股道占用次數來衡量動車所的調車作業效率，以減少動車所股道占用次數作為優化目標，如式（1）所示.

約束條件包括：

式（2）、（3）表示動車組任一作業項目均應在本班時間內完成；式（4）表示動車組某項作業在股道上的停留時間不小于該作業的時間標準；式（5）、（6）為考慮動車組進行后項作業是否需要轉線的前、后項作業的時間接續約束；式（7）、（8）表示動車組不同類型的作業必須在具備相應作業功能的股道上進行；式（9）為動車所某股道及其列位不發生占用時間沖突的約束；式（10）、（11）為考慮列車間隔時間的咽喉進路不發生占用時間沖突的約束；式（12）、（13）為動車組是否在某股道進行作業的決策約束；式（14）為動車組是否進行轉線調車的決策約束；式（15）為平行進路數量約束；式（16）表示動車組某項作業時只占用一條股道；式（17）表示某股道在同一時刻最多停留兩列動車組.

3 算法設計

上述模型屬于大規模的混合整數規劃模型，約束條件較多且復雜.在運輸組織優化建模中，此類模型比較普遍，一般結合模型特點，采用啟發式算法進行求解[10-11].模擬退火算法是一種經典的啟發式算法，具有易于實現、魯棒性高、計算過程簡單等特點，被廣泛用于求解復雜的非線性優化問題.在結構設計上，根據實際情況和輸入數據特點設置合適的狀態函數和退火策略，符合本文模型的特點和求解需求.

本文模型中，當動車所的股道數目、動車組的數量、作業任務量增大，模型的求解難度會急劇上升.求解得到的調車作業計劃需確定每列動車組進行各項作業的起止時間和占用的股道，即反映各動車組在所內完成調車作業走行的全過程.模型的求解過程分為以下3個階段：

1）生成單列動車組的檢修整備可行路徑.

2）生成包含全部動車組可行路徑的調車作業計劃可行解.

3）采用模擬退火算法在可行解中尋優.

3.1 模型的編碼和可行解

動車所調車作業計劃包含的信息涉及各動車組入所、檢修整備、出所等作業過程和動車所各股道的占用情況，因此，本文分別對上述兩種信息進行實數編碼.由于動車組調車作業時間標準通常為5 min的整數倍，按5 min的整數倍為單位時間，劃分本班計劃得到編碼長度.例如以15 min為一段進行編碼，動車組編碼片段如圖2所示，0表示未進行檢修整備作業，正整數表示作業項目類型（2、9分別為檢修整備作業、轉線），-1表示存車.股道編碼片段如圖3所示，0表示股道空閑狀態，3表示占用該股道的動車組序號為e3，-1表示某動車組轉線時占用該股道.模型求解完成后，解碼兩套編碼得到完整的動車所調車作業計劃方案.

圖2 動車組的個體編碼片段Fig.2 Individual code fragments of the EMU

圖3 股道的個體編碼片段Fig.3 Individual code fragments of the tract

根據某動車組入所時各股道的占用和剩余可作業時間狀態對其各項作業的順序、時間、股道占用作出合理安排，即得到該動車組的檢修整備可行路徑.對于全部動車組，由于出入所時間不一，在動車所的實際停留時間也不同，為盡量避免無法生成調車作業計劃可行解，應制訂合理的動車組間進行檢修整備作業的優先級順序.同時考慮將動車組按照作業項目先分類再生成可行解，在求解過程中不同分類的動車組僅與具有相應功能的股道集合雙向匹配，有利于降低方案組合數量，提高求解速率.

本文中模型的可行解生成算法如下：

步驟1輸入各動車組入所、出所時刻、作業項目和編組狀態，本班計劃開始、結束時刻，各股道的功能和初始占用狀態，各類型作業時間標準等；

步驟2根據各動車組具體作業項目生成其合理作業順序，并將全部動車組分為上文所述三類，根據各動車組在所實際停留時間從小到大排列生成檢修作業初始優先級順序；

步驟3按照動車組檢修作業優先級順序選取一列動車組，根據股道當前列位占用狀態和剩余可用作業時間等信息及各約束條件，對該動車組按照其作業項目順序隨機選取具有相應功能且空閑的股道進行檢修整備作業，每項作業結束后更新該動車組和占用股道的時空狀態；

步驟4重復步驟3，遍歷該動車組的作業項目，若能在其停留時間內完成全部的檢修整備作業，則得到該動車組完整的個體編碼，即生成該動車組的檢修整備可行路徑，否則該路徑不可行；

步驟5重復步驟4，遍歷該班計劃內的所有動車組，得到各動車組個體編碼和各股道個體編碼，若能在班計劃時間內生成全部動車組的檢修整備可行路徑，則該解可行，若無法生成則表明產生了作業的時空沖突，應舍棄該不可行解；

步驟6對于可行解，根據各動車組個體編碼和各股道個體編碼的信息，得到完整的動車所調車作業計劃，計算該可行解的目標值；

步驟7采用模擬退火算法產生隨機擾動，得到新的動車組檢修作業優先級順序，重復步驟3 ～ 6，生成新的動車所調車作業計劃可行解.

3.2 模擬退火算法尋優

在可行解中進行尋優的關鍵是鄰域解的生成，對于動車所調車作業計劃，一種鄰域構造方法是隨機交換可行解中兩列動車組對股道的占用，但這種方法在作業動車組數量較多、問題求解規模較大時具有一定的盲目性，求解效率不高.

動車組檢修優先級順序對調車作業計劃編制結果有影響，在實踐中，當作業動車組數量較多時，按照動車組在所實際停留時間從小到大排列的動車組檢修優先級順序可能無法得到可行的調車作業計劃.例如圖4（a）所示，圖中：t1～t3為動車所入所時間，t4～t6為完成調車作業后的出所時間；S1、S2 和M1分別表示機洗線、人工洗車線和運用檢修線.按該排序方式的動車組檢修優先級順序為e2，e1，e3，而e3無法按圖中時間出所，原因是M1在e2檢修前的可用檢修時間被浪費.將優先級順序調整為e1，e2，e3時，e3可順利完成檢修整備，如圖4（b）所示.

圖4 調車作業安排Fig.4 Arrangement of shunting operation

鑒于此，本文的鄰域結構設計為：對初始可行解的動車組檢修作業優先級排序，在非重聯的短編動車組中隨機選擇兩列，交換其在檢修作業優先級順序中的位置.這種鄰域結構有較好的隨機擾動性能，有利于可行解的優化，同時能保證重聯的短編動車組同步作業，有利于提高調車作業的效率.本文的模擬退火算法采用線性降溫方式，依據Metropolis接受準則接受新解，其他規則不再贅述.完整的動車所調車作業計劃編制優化模型的算法流程如圖5所示.

圖5 動車所調車作業計劃編制優化算法流程Fig.5 Flow chart of optimization algorithm for shunting operation plan of EMU depot

4 實例分析

4.1 數據準備

國內某盡端式動車所，采用“存車場 + 檢查庫”的場庫布局，如圖6所示，檢查庫設有4條檢修線JC1～JC4，存車場設有12條股道，均可用于動車組存放，其中S1道為機洗線，S2道為人工洗車線，S11道為鏇輪線，S12道為臨修線，動車所內所有股道均帶有分割信號，調車作業的平行進路為2條.

圖6 動車所平面示意Fig.6 Schematic plan view of EMU depot

該動車所承擔本所配屬動車組的檢修整備及部分外所動車組的過夜任務，進行各項作業的時間標準如表2所示.

表2 動車組作業時間標準Tab.2 EMU operating time standards

某個夜班（20：00—08：00）中需要進行檢修整備作業的動車組的各項信息如表3所示，其中e1 ～e12為本所配屬動車組，e13 ～ e15為外所過夜動車組.“線存”“庫存”表示本班開始時或結束時動車組在存車線或檢修線上，本班開始時e1在S5道，e2、e3分別在S9道兩列位.作業項目中“檢修”表示在檢查庫進行一級修及其他作業，“機洗”“人工洗車”“吸污”表示對應作業不在檢查庫進行.

表3 作業動車組基本信息Tab.3 Basic information of operating EMU

4.2 求解與結果分析

采用Python語言在Spyder開發環境上實現優化模型的求解.取初始溫度100，降溫速率0.98，終止溫度為1，最大迭代次數500，同溫迭代次數1，經多次測試，均能在4 s內求得該算例的最優解.取其中一次求解結果，迭代收斂曲線如圖7所示.將求解結果進行整理，得到該算例的最優調車作業計劃如表4所示.

表4 最優調車作業計劃Tab.4 Optimal shunting operation plan

圖7 迭代收斂曲線Fig.7 Iterative convergence curve

在本例中，一級修作業時間15 min及轉線時間15 min，動車組入庫一級修用時約 3 h，本班計劃為12 h，檢修線為4條，則不考慮檢修線雙列位占用時理論最大檢修能力為16列.本班計劃實際入庫檢修的動車組為10列，且檢修線JC4利用了雙列位，從編制結果來看檢修線的能力也有較多富余.該動車所存車線為12條，占用存車線的動車組為15列，本算例中存車線恰好滿足一股道一列車的停放需求，但當動車組數量增加或停留時間延長時，充分利用股道列位具有求解優勢.

在迭代過程中，股道占用次數最多為41次，其產生原因是為避免股道時空占用沖突，部分動車組進行了不必要的轉線，最低為34次，對應的方案中沒有動車組不必要的轉線.在需要入庫作業的10列動車組中，有8列實現了入所后快速入庫作業，對于檢修線作業效率和利用率的提高有較好的效果.可以看出，本文的模型和算法在求解動車所調車作業計劃的有效性和實用性得到了一定提高.

5 結 論

本文根據我國現行動車組運用管理和動車所調車作業的特點，在上線運用動車組數量增加的背景下，著眼于動車所調車作業效率和實際檢修能力的提高，考慮動車所股道雙列位的合理利用，建立調車作業計劃編制優化模型，設計基于動車組作業優先次序的模擬退火算法進行求解，結合算例對其進行驗證，得到如下結論：

1）合理利用動車所股道雙列位有利于提高股道利用率和動車所調車作業效率.

2）合理的動車組作業優先次序能夠提高調車作業計劃的編制速率和質量.

針對不同類型的動車所，考慮調車作業白班計劃和夜班計劃的聯合協調編制，是需要進一步研究的方向.