基于離散動態(tài)規(guī)劃的列車節(jié)能速度曲線優(yōu)化

孔繁鑫，陳陽舟，詹璟原，尚 飛

（1.北京工業(yè)大學 北京交通工程重點實驗室，北京 100124；2.北京工業(yè)大學 人工智能與自動化學院，北京 100124)

0 引言

軌道交通以其速度快、運量大、準時安全等特點，成為支撐城市公共交通的重要方式之一[1]。與此同時，城市軌道交通系統(tǒng)的能耗不斷增加。據(jù)統(tǒng)計，2018年北京市軌道交通系統(tǒng)總電能耗達19億kW·h，牽引能耗達11億kW·h，牽引能耗約占系統(tǒng)總電能耗的57.9%[2]。通過優(yōu)化列車站間速度曲線，可以降低列車的牽引能耗，從而降低軌道交通系統(tǒng)的總能耗。

針對列車站間速度曲線優(yōu)化問題，國內(nèi)外學者已經(jīng)做了大量研究，方法主要分為2類：解析算法和數(shù)值算法[3]。最常見的解析算法基于極大值原理，可以找到全局最優(yōu)解、求解速度快，但不能處理非線性運行阻力和軌道速度限制等復(fù)雜的列車實際運行條件[4]。例如，Howlett等[5]利用極大值原理證明了列車最優(yōu)運行曲線由“最大牽引—巡航—惰行—最大制動”4個階段組成；Liu等[6]基于極大值原理將最優(yōu)控制過程分為最大牽引、部分牽引、惰行、部分制動、最大制動5種工況，并找到了各工況的切換點；朱金陵等[7]充分利用線路坡道，用極大值原理求解得到列車優(yōu)化控制策略。數(shù)值算法包括遺傳算法、動態(tài)規(guī)劃等。遺傳算法存在明顯的不足，如迭代參數(shù)的確定主要依靠經(jīng)驗、對初始種群依賴性強、搜索速度慢等；動態(tài)規(guī)劃是求解多級決策過程最優(yōu)化的一種數(shù)學方法，常用來處理帶約束的優(yōu)化問題，但其存在“維數(shù)災(zāi)難”問題。例如，陳榮武等[8]提出基于遺傳算法的能耗優(yōu)化算法，計算了不同運行時分的節(jié)能速度曲線；劉煒等[9]提出變長實矩陣編碼的多種群遺傳算法搜索列車節(jié)能運行曲線，增強了尋優(yōu)過程的穩(wěn)定性；Ko等[10]利用一階泰勒公式和梯形規(guī)則將最優(yōu)控制問題轉(zhuǎn)化為多階段決策過程，動態(tài)規(guī)劃求解得到列車節(jié)能速度曲線；Lu等[11]以速度變化量為控制變量，分別用蟻群算法、遺傳算法、動態(tài)規(guī)劃3種方法求解速度曲線優(yōu)化問題，動態(tài)規(guī)劃在離線求解中表現(xiàn)最佳。

既有研究多將整個狀態(tài)空間作為節(jié)能速度曲線優(yōu)化問題的搜索空間，導致求解的計算量和存儲量大，求解時間長。為此，構(gòu)建以位置為自變量、牽引力/制動力的系數(shù)為控制變量的列車節(jié)能速度曲線優(yōu)化模型，根據(jù)線路條件將位置離散化，將速度曲線優(yōu)化問題轉(zhuǎn)換為多階段決策過程，將狀態(tài)空間劃分成網(wǎng)格狀并利用狀態(tài)空間縮減策略對其縮減，利用離散動態(tài)規(guī)劃求解得到列車站間最優(yōu)速度曲線和最優(yōu)控制輸入，為列車運行提供參考速度曲線，進而降低列車站間運行的牽引能耗。

1 列車節(jié)能速度曲線優(yōu)化模型構(gòu)建

在時刻表已知的前提下，列車從某站到下一站存在多條速度曲線滿足預(yù)定的時間約束。不同的列車速度曲線如圖1所示。

圖1 不同的列車運行速度曲線Fig.1 Different speed running profiles of train

列車速度曲線優(yōu)化就是在固定的站間距離、規(guī)定的運行時間下，考慮列車牽引特性、基本阻力、速度限制和坡道阻力等因素的影響，確定一條速度曲線使列車運行過程的牽引能耗最小。將列車視為單質(zhì)點，以列車位置s為自變量、牽引力/制動力的系數(shù)u(u∈[-1，1])為控制變量、速度v和時間t為狀態(tài)變量，列車節(jié)能速度曲線優(yōu)化模型表示為

式中：J為列車運行過程中的牽引能耗；S為站間距離；f(u，v)為列車牽引力/制動力；f+(u，v)為f(u，v)的正部分；Tra(v)，Bra(v)分別為列車最大牽引力和最大制動力，可以從列車的技術(shù)手冊中獲得，也可以通過實驗數(shù)據(jù)擬合得到；M為列車質(zhì)量；Rb(v)為列車基本阻力，Rb(v) =Av2+Bv+C，參數(shù)A，B，C由列車型號、質(zhì)量等確定[12]；Rg(s)為列車坡道阻力，是列車重力在坡道方向的分量，由軌道傾斜程度決定，與列車位置s有關(guān)，Rg(s) =Mgsinθ(s) =其中g(shù)為重力加速度，g = 9.8 m/s2，θ(s)為軌道傾角，i(s)為軌道每1 000 m的高度差；Vlim為軌道速度限制。

2 離散動態(tài)規(guī)劃算法設(shè)計

將位置離散化，使得列車速度曲線優(yōu)化問題轉(zhuǎn)化為多階段決策過程，把列車的狀態(tài)空間離散化為網(wǎng)格狀并對其進行縮減，利用離散動態(tài)規(guī)劃對節(jié)能速度曲線優(yōu)化模型進行求解。

2.1 離散化處理

根據(jù)線路情況將位置離散化，位置集合由4部分組成：①將站間距離等間隔劃分的位置；②限速變化的位置；③軌道坡度變化的位置；④最大速度曲線達到或偏離限速的位置。為了減少不必要的階段，若等間隔劃分的位置離限速變化、坡度變化或最大速度曲線達到或偏離限速的位置小于等間隔位置間距的一半，則刪除該等間隔位置，將站間距離S劃分為K階段，產(chǎn)生K+ 1個位置為{s0，s1，…，sk，…，sK}。列車站間運行的有效速度集示意圖如圖2所示，其中黑色、紅色、藍色、棕色位置分別為等間隔劃分、最大速度曲線達到或偏離限速、限速變化和坡度變化的位置。

將控制系數(shù)等間隔離散化，可行的控制系數(shù)u∈ [-1，-0.75，-0.5，-0.25，0，0.25，0.5，0.75，1]，其中負數(shù)表示制動，-1為最大制動，0表示惰行，正數(shù)表示牽引，1為最大牽引。將列車速度v與運行時間t劃分成網(wǎng)格狀，每個格子的大小為Δv×Δt。速度和時間的離散間隔會影響最優(yōu)目標速度曲線的求解精度，理論上，Δv，Δt的取值越小越好。

2.2 狀態(tài)空間縮減

圖2 列車運行有效速度集示意圖Fig.2 Schematic diagram of train running effective speed set

為縮小搜索空間，用最大速度曲線與最小速度曲線對速度集合進行縮減。最大速度曲線：在滿足軌道限速與終點停車的條件下，列車按照最大牽引力運行。牽引階段最大牽引力加速至軌道限速，制動階段從終點倒推，巡航階段速度與軌道限速相等，沒有惰行階段。最小速度曲線：為按時到達終點，列車在站間有最小速度限制，該限制存在于列車最大速度曲線到達并基本保持在軌道限速的區(qū)間，而在該區(qū)間外，列車做勻加/減速運動。最大速度曲線與最小速度曲線之間的速度構(gòu)成了有效的速度集合，即

式中：Vmax,k與Vmin,k分別為最大速度與最小速度曲線sk位置的速度值。

2.3 動態(tài)規(guī)劃正向搜索

列車狀態(tài)包括列車位置、速度和運行時間，用φ= [s，v，t]表示，初始狀態(tài)為：φ0= [s0，v0，t0]= [0，0，0]。正向搜索是從初始狀態(tài)起，由不同的控制輸入u搜索滿足公式 ⑺ 限制的狀態(tài)，直到到達終點位置sK。離散動態(tài)規(guī)劃搜索過程如圖3所示。圖3中的陰影部分對應(yīng)圖2中的有效速度集合，速度落在陰影部分外的為無效控制。

令i，j，p分別為速度、時間、控制的索引，則列車在sk位置的狀態(tài)表示為在狀態(tài)的控制表示為

列車第k+ 1階段的能耗為

列車從s0到sK的總能耗表示為

圖3 離散動態(tài)規(guī)劃搜索過程Fig.3 Discrete dynamic programming search process

由貝爾曼最優(yōu)性原理，公式 ⑴ 的速度曲線優(yōu)化問題可以轉(zhuǎn)化為多階段決策問題，具體如下。

動態(tài)規(guī)劃的遞推方程表示為

由于位置s是離散的，可選控制輸入u也是離散的，正向搜索過程中列車的狀態(tài)[sk，vk，tk]一般不會落到網(wǎng)格點，將其近似到最近的網(wǎng)格點。需要注意的是，每個狀態(tài)對應(yīng)著自初始狀態(tài)φ0以來的最小能耗。當有多條搜索路徑到達同一狀態(tài)[sk，vk，tk]時，利用公式 ⑾ 選擇使得能耗最小的控制作為最優(yōu)解。

為保存正向搜索結(jié)果，構(gòu)建3個數(shù)組：能耗數(shù)組、索引數(shù)組和控制數(shù)組。能耗數(shù)組存儲列車從初始狀態(tài)到當前狀態(tài)總牽引能耗的最小值，索引數(shù)組和控制數(shù)組存儲列車從初始狀態(tài)到當前狀態(tài)最優(yōu)速度曲線對應(yīng)的上一個狀態(tài)的索引和控制。

2.4 動態(tài)規(guī)劃反向搜索

反向搜索是根據(jù)能耗數(shù)組、索引數(shù)組和控制數(shù)組，利用公式 ⑾ 遞推得到列車的最優(yōu)速度曲線和最優(yōu)控制輸入。反向搜索步驟如下。

步驟1：從終端狀態(tài)[sK，vK，tK]開始搜索。

步驟2：取當前狀態(tài)對應(yīng)的能耗數(shù)組、控制數(shù)組的值并保存。

步驟3：由索引數(shù)組得到當前狀態(tài)對應(yīng)的前一狀態(tài)的索引值并將其作為當前狀態(tài)。

步驟4：對當前狀態(tài)進行判斷。若當前狀態(tài)為初始狀態(tài)，則搜索結(jié)束，得到最優(yōu)速度曲線；否則，轉(zhuǎn)步驟2。

3 仿真驗證

為驗證算法的有效性，選擇北京地鐵亦莊線同濟南—經(jīng)海路站間線路，分別對動態(tài)規(guī)劃且狀態(tài)空間縮減(方案1)、動態(tài)規(guī)劃且狀態(tài)空間未縮減(方案2)和枚舉法(方案3) (與動態(tài)規(guī)劃對狀態(tài)空間離散化不同，枚舉法的速度、時間未離散化處理)進行仿真實驗。其站間距離為2 265 m，時刻表規(guī)定的站間運行時間為150 s。同濟南—經(jīng)海路軌道坡度和速度限制如表1所示。北京地鐵亦莊線列車的牽引特性、制動特性和運行阻力如圖4所示。

表1 同濟南—經(jīng)海路軌道坡度和速度限制Tab.1 Track slope and speed limit of Tongjinan-Jinghailu

圖4 北京地鐵亦莊線列車的牽引特性、制動特性和運行阻力Fig.4 The traction characteristic, braking characteristic and running resistance of trains on Beijing Subway Yizhuang line

將站間位置離散化，方案1和方案2均分為31個階段，取Δv= 0.1 m/s，Δt= 0.1 s。方案3的計算時間隨著階段數(shù)的增加而指數(shù)增加，以劃分17個階段為例，搜索對應(yīng)的站間節(jié)能速度曲線。用1.6 GHz處理器、8 GB RAM的個人電腦通過Python編程實現(xiàn)。方案1對應(yīng)的最優(yōu)速度曲線和最優(yōu)控制輸入如圖5所示。方案3對應(yīng)的最優(yōu)速度曲線和最優(yōu)控制輸入如圖6所示。方案2求解的節(jié)能速度曲線與方案1相同。

北京地鐵亦莊線同濟南—經(jīng)海路的節(jié)能速度曲線優(yōu)化3種方案的性能如表2所示。

圖5 方案1對應(yīng)的最優(yōu)速度曲線和最優(yōu)控制輸入fig.5 The optimal velocity curve and optimal control input corresponding to scheme 1

圖6 方案3對應(yīng)的最優(yōu)速度曲線和最優(yōu)控制輸入fig.6 The optimal velocity curve and optimal control input corresponding to scheme 3

由表2可知，方案1與方案2都采用動態(tài)規(guī)劃方法求解，得到的節(jié)能速度曲線相同，終端速度和終端時間的偏差、能耗相同，唯一區(qū)別是方案1進行了狀態(tài)空間縮減，其求解時間僅為方案2的2.5%，狀態(tài)縮減策略使得搜索效率明顯提高。動態(tài)規(guī)劃算法的離散化數(shù)據(jù)近似處理導致列車終端狀態(tài)與目標狀態(tài)產(chǎn)生較大的偏差。方案3采用枚舉法求解，速度和時間未進行離散化處理，避免了動態(tài)規(guī)劃狀態(tài)近似帶來的誤差，終端狀態(tài)的偏差較小。但是，方案3計算得到的能耗較大，主要是由于階段劃分較少導致的。然而由于枚舉法的計算量、存儲量隨著階段數(shù)的增加而呈指數(shù)趨勢增加，如果繼續(xù)增加階段數(shù)會導致計算機溢出，計算停止。離散動態(tài)規(guī)劃算法解決了枚舉法計算量和存儲量大的問題，比枚舉法減少能耗5.6%，且隨著階段數(shù)的增加，得到的節(jié)能速度曲線會逐漸逼近全局最優(yōu)解?？梢姡瑒討B(tài)規(guī)劃且狀態(tài)縮減方案可以在較短時間內(nèi)找到最優(yōu)的列車站間節(jié)能速度曲線。

4 結(jié)束語

列車牽引能耗是城市軌道交通系統(tǒng)總能耗的主要部分，優(yōu)化列車站間速度曲線對降低運營成本、促進低碳經(jīng)濟具有重要的意義?；陔x散動態(tài)規(guī)劃求解列車站間速度曲線的優(yōu)化問題，并利用最大速度曲線、最小速度曲線對狀態(tài)空間進行縮減，可以提高動態(tài)規(guī)劃算法的搜索效率，降低列車的牽引能耗。仿真實驗表明，利用動態(tài)規(guī)劃且狀態(tài)縮減方案可以在較短時間內(nèi)找到最優(yōu)的列車節(jié)能速度曲線。為進一步降低城市軌道交通的總電能耗，應(yīng)考慮多車協(xié)作的速度曲線優(yōu)化問題，利用列車的再生制動能量，減少整個線路列車的牽引能耗。

表2 3種方案的性能Tab.2 Performance of the three scenarios