基于均衡運用原則的列車運營日計劃編配研究*

臧 瑤 徐 剛 黃 瑛 邢宗義

(1. 南京理工大學自動化學院， 210094， 南京；2. 中車青島四方機車車輛股份有限公司專項辦， 266111， 青島//第一作者，碩士研究生)

在確定了第二日列車運營日計劃模板后，為模板中相應的列車車次編配狀態良好的車組，稱為列車運營日計劃編配。目前傳統的人工編配方式存在生產效率低下、安全隱患大等問題，因此，科學地進行列車運營日計劃編配具有重要現實意義。

目前，針對城市軌道交通列車運營日計劃編配的研究甚少。由于動車組運用計劃編制和城市軌道交通列車運營日計劃編制的目的都是為運輸生產提供狀態良好的車輛，因此，對動車組運用計劃編制問題的研究對于城市軌道交通列車運營日計劃編制具有一定的借鑒意義[1]。文獻[2]在已知列車運行圖的基礎上，建立求解動車組運用問題的整數規劃模型，將動車組的接續運行與檢修計劃制定過程轉化為動車組運用網絡上的TSP(旅行商問題)問題，借鑒蟻群算法求解。文獻[3]建立了動車組運用計劃編制數學模型，采用遺傳算法使生成的交路段數最少，利用交路段互換的方法實現各基地動車組使用的均衡性。文獻[4]對韓國KTX動車組的運用計劃優化問題進行了研究，以列車運用時間最低為優化目標，基于交換生成滿足檢修約束的最優動車組交路。文獻[5]以運用列車數最少、總運行里程最低為優化目標，在動車組運用順序和列車定員等約束下建立動車組運用優化模型。

本文以車組號與車次匹配度最高為目標函數建立列車運營日計劃編配模型，實現列車檢修與運用的解耦和，使列車在規定時限內得到檢修，在提高列車運營可靠性的同時保障行車安全。

1 問題描述

表1為某城市軌道交通列車運營日計劃表。早高峰車次為0202、0402、0702、1002，晚高峰車次為1702、1802、1902、2002；每個車次都有其發車方向， 0102、0302、0402、0602、0902、1102為上行方向，其余車次為下行方向。

表1 某城市軌道交通列車運營日計劃表

回庫車次與出車車次數相差越多，代表車次對應的列車的日運行里程數越大。以編號為1的計劃為例，出庫車次為0102，回庫車次為0135，即需要跑34個單趟。晚班調度只對除晚高峰之外的車次進行安排，晚高峰車次由早班調度在出車前根據車組實際狀況進行安排。

列車運營日計劃編配問題可表述為：在時刻表/車次信息、股道信息、車組信息已知情況下，對列車運營日計劃表進行編配。列車運營日計劃要滿足道岔轉換最小時間約束、早高峰指定車次約束、出庫便捷性約束和唯一性約束，選用合適的良好車組去擔當特定的列車車次。

2 基于改進BWAS(最優-最差蟻群算法)的列車運營日計劃編配算法設計

2.1 解構建圖的表示及解的構建

解構建圖的實質是對解空間的一種描述，通常為點-邊結構的拓撲結構。螞蟻可在該拓撲結構中根據路徑的信息素與局部啟發式信息以不同概率對下一節點進行選擇，重復直至完成路徑構建。任何優化問題的解均可經處理后分解為構造塊并映射為解構建圖中的節點;該節點與連接的有限集合通過網絡拓撲結構組合出問題的解空間[6]。

在傳統的TSP問題中，解構建圖為所有城市節點的連接網，邊的權值為兩城市節點間的距離。在本文中，首先需確定所有待編配車組與除晚高峰外的待編配車次的成本矩陣Cij，其中行代表車組號，列代表列車車次；車次按時間從早到晚依次排列，成本矩陣中的每一個值都作為一個節點vij(第i個車組擔任第j個車次)。在進行計劃編制時需按照車次時間順序依次進行編配，故將所有節點按從左到右的方向依次連接，當前節點僅可與右側相鄰列的所有節點連接，如圖1所示。

圖1 路徑構建示意圖

所有螞蟻均從起始點出發，依據狀態轉移策略在第一列的可選節點中選擇轉移節點，選擇完畢后對信息素進行更新，重復直至到達最后一列完成解的構建。在解構建過程中，若出現某一列可使用車組集為空的情況，即對當前解舍棄，返回第一列重新解的構建。解構建完畢后為所有經過節點的集合vij，解析后得到車組號與列車車次的對應關系。

2.2 目標函數與約束

2.2.1 約束條件

對列車運營計劃表編配問題的約束進行分析。

(1) 唯一性約束：由于一個車次唯一對應一列列車，故需滿足唯一性的原則：

(1)

式中:

Xij——決策變量;

n——除晚高峰外所有車次的總數;

k——有早高峰或指定車次任務的車組數。

同時，一列車唯一對應一個車次，因此有：

(2)

式中：

m——所有狀態良好車組的總數。

(2)早高峰指定車次約束：早高峰與指定車次的任務完成率Pm有如下約束：

Pm=Mf/Mtotal=1

(3)

式中：

Mf——完成的早高峰指定車次任務數；

Mtotal——早高峰指定車次任務總數。

(3) 道岔轉換最小時間約束：當前車次的道岔狀態要求與當下的道岔狀態不一致時需要進行道岔轉換，因此需考慮道岔轉換的最小時間間隔約束。

Tl>60,l∈[2,3,…,n]

(4)

式中：

Tl——當次列車與上次列車的時間間隔；

l——需要進行道岔轉換的車次序號。

(4) 出庫便捷性約束：當同一停車庫A、B股道均停放車組時，分別記停放在A、B股道上的車組為Ti1和Ti2，按車次順序進行編配時滿足如下約束：

(5)

其中，Ai表示車組Ti是否可以安排車次，當Ai=0時，代表該車組Ti暫時不能安排車次；當Ai=1時，代表該車組Ti可以安排車次。

因此，列車運營計劃編配的數學模型為：

j=1,2,…,n-k

(6)

式中：

Cij——狀態良好的車組與待配車次的匹配程度。

2.2.2 目標函數的選擇

可以將列車運營日計劃編配看成一個指派問題，其中：擔任車次任務的車組集合為{Ti，i=1,2,…,m}；待分配車次集合為{Fj，j=1,2,…,n}。Cij代表車組Ti與車次Fj的匹配程度，Cij值越小代表匹配程度越高；決策變量Xij∈[0,1]，當Xij=0時，代表車組Ti未擔當車次Fj，當Xij=1時，代表車組Ti擔當車次Fj。

在進行列車運營日計劃編配時，需使全部車次的總成本最低，即全部車次與車組的總匹配度最高，目標函數見式(6)。

其中，Cij的計算步驟如下：

(1) 將有早高峰或指定車次任務的車組號填入運營計劃對應車次。

(2) 對所有未安排車次(除晚高峰車次)所對應的里程由小到大進行排序，記為rj=a，a=1,2,…,n-k,rj表示車次Fj在排序后位于第a個位置，其中里程數相同的車次排名也相同。

(3) 對未安排車次的車組按規則進行排序。若某項檢修作業的檢修周期固定且為t,在一般情況下，所有車組兩次檢修作業之間的時間間隔也隨之確定。 由于檢修周期的確定與車組走行里程有關，因此要求兩次檢修時間間隔內所車組的走行里程接近。

將車組與車次按順序進行匹配。首先根據步驟(2)與步驟(3)對車組號及車次進行排序，然后按照排名先后進行匹配。盡量安排日均走行里程小的車組去擔任里程數大的車次，但由于股道約束、車組停放位置等因素的影響，車組與車次往往無法實現最佳匹配。

由于車次數一般少于車組數，因此，首先需將車組號對應的最佳匹配車次進行補全，依次加1，作為車組號最佳匹配車次參考。車組Ti與車次Fj的匹配度Cij的計算公式如下：

Cij=|Rj-Rbest|

(7)

式中：

Rj——車次Fj在所有車次中的排名；

Rbest——車組Ti的最佳匹配車次在所有車次中的排名。

2.3 信息素的表示、初始化及更新

由于本問題的解構建圖基于成本矩陣構建，每個元素均為一個節點，故將信息素τij置于每個節點上，代表第i個車組擔任第j個車次的期望程度。在初始時刻設τij(0)=K(K為常數)。

在建立一個解決方案過程中，螞蟻每選中一個節點vij，即應用式(8)的局部更新規則對所選擇的節點進行信息素更新。

τij=(1-ρ)τij+ρτij(0)

(8)

式中：

ρ——信息揮發系數，0<ρ<1。

螞蟻從上一個節點向vij移動時，局部更新規則使得vij的信息素含量減少，從而有效避免螞蟻收斂到同一路徑。

當所有螞蟻完成一次循環后，為使搜索過程更具指導性，讓螞蟻的領域集中在當前循環為止的最好路徑領域內，需對全局最優及全局最差路徑的信息素軌跡量進行更新。

首先找到當前循環為止的全局最優路徑，應用式(9)的全局更新規則對所有節點上的信息素進行更新。

τij=(1-ρ)τij+γΔτij

(9)

式中：

γ——參數；

Lbest——當前循環找出的全局最優路徑長度。

然后找到當前循環最差螞蟻所經過的路徑，應用式(10)的全局更新規則對屬于最差路徑但不屬于全局最優路徑中的節點的信息素進行更新。

(10)

式中：

ε——參數；

Lworst——當前循環最差路徑長度。

2.4 狀態轉移策略的選擇

與經典TSP問題中螞蟻狀態轉移策略不同，本文路徑上的能見度由當前車組與車次的匹配度確定。此外，螞蟻下一步可選擇的節點集合也不同，需考慮已選擇的車站、股道約束及未選車站狀態，具體狀態轉移策略如下：

(1) 根據當前車次的股道約束確定可選車組停放位置，并結合車組停放位置表確定第k個可選車組中當前狀態為1的車組集合Tallowedk1。

(2) 查看當前車輛禁忌表，篩選出第k個可選車組中當前狀態為2的車組集合Tallowedk2。

(3) 為使初始解集中在最優解附近，假設:若路徑上的信息量刺激未達到螞蟻的感覺閾限時，螞蟻忽視該刺激的存在，僅依賴節點間的能見度進行路徑選擇，即在初始若干代N中，車組Ti與以概率S擔當車次Fj。在初始N代中，不需對信息素進行局部更新，只需進行全局更新。

(11)

式中：

t——時間;

Tallowedk——螞蟻下一步可選車組的集合,Tallowedk=Tallowedk1∪Tallowedk2；

q——在區間[0,1]均勻分布的隨機數；

q0——參數(0≤q0≤1)，其大小決定利用已知條件確定節點與探索新路徑之間的重要程度；

ηsj——節點vsj的能見度；

(4) 在后續的循環中，選擇合適車組擔任下一車次，轉移概率如下：

(12)

式中：

pij,k——在第k個可選車組中，車組Ti擔任車次Fj的概率；

τsj——節點vsj上的信息素；

β——能見度的相對重要性(β≥0);

α——軌跡上殘留信息素的相對重要性(α≥0)。

3 仿真分析

采用Java開發語言、Myeclipse開發工具建立城市軌道交通列車運營日計劃編配仿真平臺。

首先，統計車次信息。車次信息包含車次、出車方向、時間、股道約束、里程、是否為早/晚高峰等，如圖2所示。

圖2 車次信息統計表截圖

其次，統計股道信息。股道信息包括股道號、是否占用、車號等，如圖3所示。

圖3 股道信息統計表截圖

最后，統計車組信息。車組信息包括車號、狀態、擔任車次、當前總走行里程、距離測量基準時間的天數及測量基準時間對應的車組總走行里程等，如圖4所示。

其中，只能為狀態良好的車組編配車次。指定任務包括早高峰與指定車次兩類，若B股道車組有早高峰任務，也應為A股道狀態良好的車組編配車次。

圖4 車輛信息統計表截圖

利用改進的最優-最差蟻群算法求解。設初始螞蟻種群數為50，信息素因子為1，期望啟發因子為5，信息素揮發系數為0.2，τij(0)=0.5，q0=0.2，以及最大循環代數為80。該算法每次循環執行80代，從多次執行情況可知，其平均在30代至40代之間收斂。算法收斂情況如圖5所示。

圖5 列車運營日計劃編配算法收斂情況

列車走行里程變化情況趨勢如圖6所示。由圖6可見，列車運用的均衡性有了小幅度的提升。為更好地說明執行列車日走行里程的變化趨勢，本文假設在車組信息、股道信息、車次信息等條件不變的情況下，重復執行該方案19次。列車日走行里程的變化情況如圖7所示。

在應用此方案約19 d后，所有運用列車的日走行里程基本趨于一致。該算法可在短時間內收斂并使車組運用的均衡性得到顯著提升。

圖6 執行方案一次后的列車日走行里程變化趨勢圖

圖7 運用方案19 d后的列車日走行里程變化趨勢圖

4 結 語

本文針對列車運營日計劃編配問題，提出一種基于改進的最優-最差蟻群算法的車次與車組號匹配算法，實現車組均衡運用，為后續的列車運營日計劃安排提供依據。