臧 瑤 徐 剛 黃 瑛 邢宗義

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

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

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

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

1 問題描述

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

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

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

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

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

2.1 解構(gòu)建圖的表示及解的構(gòu)建

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

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

圖1 路徑構(gòu)建示意圖

所有螞蟻均從起始點出發(fā)，依據(jù)狀態(tài)轉(zhuǎn)移策略在第一列的可選節(jié)點中選擇轉(zhuǎn)移節(jié)點，選擇完畢后對信息素進行更新，重復(fù)直至到達最后一列完成解的構(gòu)建。在解構(gòu)建過程中，若出現(xiàn)某一列可使用車組集為空的情況，即對當(dāng)前解舍棄，返回第一列重新解的構(gòu)建。解構(gòu)建完畢后為所有經(jīng)過節(jié)點的集合vij，解析后得到車組號與列車車次的對應(yīng)關(guān)系。

2.2 目標函數(shù)與約束

2.2.1 約束條件

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

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

(1)

式中:

Xij——決策變量;

n——除晚高峰外所有車次的總數(shù);

k——有早高峰或指定車次任務(wù)的車組數(shù)。

同時，一列車唯一對應(yīng)一個車次，因此有：

(2)

式中：

m——所有狀態(tài)良好車組的總數(shù)。

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

Pm=Mf/Mtotal=1

(3)

式中：

Mf——完成的早高峰指定車次任務(wù)數(shù)；

Mtotal——早高峰指定車次任務(wù)總數(shù)。

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

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

(4)

式中：

Tl——當(dāng)次列車與上次列車的時間間隔；

l——需要進行道岔轉(zhuǎn)換的車次序號。

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

(5)

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

因此，列車運營計劃編配的數(shù)學(xué)模型為：

j=1,2,…,n-k

(6)

式中：

Cij——狀態(tài)良好的車組與待配車次的匹配程度。

2.2.2 目標函數(shù)的選擇

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

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

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

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

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

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

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

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

Cij=|Rj-Rbest|

(7)

式中：

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

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

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

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

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

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

(8)

式中：

ρ——信息揮發(fā)系數(shù)，0<ρ<1。

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

當(dāng)所有螞蟻完成一次循環(huán)后，為使搜索過程更具指導(dǎo)性，讓螞蟻的領(lǐng)域集中在當(dāng)前循環(huán)為止的最好路徑領(lǐng)域內(nèi)，需對全局最優(yōu)及全局最差路徑的信息素軌跡量進行更新。

首先找到當(dāng)前循環(huán)為止的全局最優(yōu)路徑，應(yīng)用式(9)的全局更新規(guī)則對所有節(jié)點上的信息素進行更新。

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

(9)

式中：

γ——參數(shù)；

Lbest——當(dāng)前循環(huán)找出的全局最優(yōu)路徑長度。

然后找到當(dāng)前循環(huán)最差螞蟻所經(jīng)過的路徑，應(yīng)用式(10)的全局更新規(guī)則對屬于最差路徑但不屬于全局最優(yōu)路徑中的節(jié)點的信息素進行更新。

(10)

式中：

ε——參數(shù)；

Lworst——當(dāng)前循環(huán)最差路徑長度。

2.4 狀態(tài)轉(zhuǎn)移策略的選擇

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

(1) 根據(jù)當(dāng)前車次的股道約束確定可選車組停放位置，并結(jié)合車組停放位置表確定第k個可選車組中當(dāng)前狀態(tài)為1的車組集合Tallowedk1。

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

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

(11)

式中：

t——時間;

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

q——在區(qū)間[0,1]均勻分布的隨機數(shù)；

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

ηsj——節(jié)點vsj的能見度；

(4) 在后續(xù)的循環(huán)中，選擇合適車組擔(dān)任下一車次，轉(zhuǎn)移概率如下：

(12)

式中：

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

τsj——節(jié)點vsj上的信息素；

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

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

3 仿真分析

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

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

圖2 車次信息統(tǒng)計表截圖

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

圖3 股道信息統(tǒng)計表截圖

最后，統(tǒng)計車組信息。車組信息包括車號、狀態(tài)、擔(dān)任車次、當(dāng)前總走行里程、距離測量基準時間的天數(shù)及測量基準時間對應(yīng)的車組總走行里程等，如圖4所示。

其中，只能為狀態(tài)良好的車組編配車次。指定任務(wù)包括早高峰與指定車次兩類，若B股道車組有早高峰任務(wù)，也應(yīng)為A股道狀態(tài)良好的車組編配車次。

圖4 車輛信息統(tǒng)計表截圖

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

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

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

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

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

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

4 結(jié) 語

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