基于雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法的列車運(yùn)行調(diào)整研究

孟慧慧，王長(zhǎng)林

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 610031)

基于雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法的列車運(yùn)行調(diào)整研究

孟慧慧，王長(zhǎng)林

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 610031)

通過對(duì)列車行車組織特點(diǎn)及運(yùn)行調(diào)整策略的研究，采用自適應(yīng)動(dòng)態(tài)規(guī)劃體系中的雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法，建立了列車運(yùn)行調(diào)整模型。雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法適合處理具有實(shí)時(shí)性、約束性、非線性、隨機(jī)性等特點(diǎn)的列車運(yùn)行調(diào)整復(fù)雜動(dòng)態(tài)系統(tǒng)的優(yōu)化控制問題，通過仿真驗(yàn)證，該算法求解速度快、精度高，對(duì)列車晚點(diǎn)的調(diào)整起到了良好的控制作用。為列車運(yùn)行調(diào)整的深入研究提供了一定的參考價(jià)值。

運(yùn)行調(diào)整；雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法；模型建立

城市軌道交通列車運(yùn)行自動(dòng)調(diào)整是列車自動(dòng)監(jiān)控系統(tǒng)（ATS，Automatic Train Supervision）的重要功能，通過列車運(yùn)行自動(dòng)調(diào)整模塊（ATR，Automatic Train Regulation）實(shí)現(xiàn)。當(dāng)列車發(fā)生晚點(diǎn)時(shí)，ATR將列車實(shí)際時(shí)刻表時(shí)間與計(jì)劃時(shí)刻表時(shí)間進(jìn)行比較，計(jì)算時(shí)刻表偏差，通過調(diào)整運(yùn)行時(shí)間和停站時(shí)間，使列車能夠安全、及時(shí)、有效地恢復(fù)到按計(jì)劃時(shí)刻表時(shí)間運(yùn)行。

列車運(yùn)行調(diào)整的關(guān)鍵是運(yùn)行時(shí)間和停站時(shí)間的調(diào)整。列車區(qū)間運(yùn)行時(shí)間受列車速度條件和線路通過能力的影響，當(dāng)列車以線路允許的最大速度運(yùn)行時(shí)為區(qū)間最小運(yùn)行時(shí)間，同時(shí)，為保證行車效率及節(jié)能、舒適度等，需要設(shè)定區(qū)間最大運(yùn)行時(shí)間。

對(duì)列車運(yùn)行時(shí)間的調(diào)整必須介于區(qū)間最小運(yùn)行時(shí)間和最大運(yùn)行時(shí)間之間。對(duì)列車停站時(shí)間的調(diào)整也要介于最小停站時(shí)間和最大停站時(shí)間之間。最小停站時(shí)間是列車停車后，司機(jī)開關(guān)門操作及乘客上下車的最小時(shí)間，同時(shí)，列車不能無限度的在站內(nèi)停車，需要設(shè)定最大停車時(shí)間。

目前有許多方法用于對(duì)列車運(yùn)行調(diào)整模型進(jìn)行建立，包括人工智能方法[1～2]、運(yùn)籌學(xué)的優(yōu)化理論[3]等。但由于約束性、非線性、隨機(jī)性等因素的影響，使用上述兩類方法無法在短時(shí)間內(nèi)求得令人滿意的可行解，本文采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行求解，可以在短時(shí)間內(nèi)求得優(yōu)化解，同時(shí)滿足實(shí)時(shí)調(diào)度的需求。

1 雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法描述

自適應(yīng)動(dòng)態(tài)規(guī)劃（ADP，Adaptive Dynamic Programming）采用動(dòng)態(tài)規(guī)劃的基本思想，利用函數(shù)近似方法如神經(jīng)網(wǎng)絡(luò)來近似取得代價(jià)函數(shù)，并使其最小，以避免動(dòng)態(tài)規(guī)劃在計(jì)算最優(yōu)代價(jià)函數(shù)時(shí)遇到的“維數(shù)災(zāi)”問題，適用于復(fù)雜、非線性系統(tǒng)的決策優(yōu)化或控制問題[4]。

ADP的實(shí)現(xiàn)一般需要評(píng)價(jià)（Critic）、模型（Model）和動(dòng)作（Action）3個(gè)模塊。評(píng)價(jià)模塊對(duì)代價(jià)函數(shù)進(jìn)行近似，模型模塊反映被控系統(tǒng)的特性，動(dòng)作模塊產(chǎn)生控制信號(hào)。根據(jù)評(píng)價(jià)模塊輸出的函數(shù)不同，現(xiàn)有的自適應(yīng)動(dòng)態(tài)規(guī)劃方法主要有3種類型：輸出代價(jià)函數(shù)的近似值為啟發(fā)式動(dòng)態(tài)規(guī)劃（HDP，Heuristic Dynamic Programming）；輸出代價(jià)函數(shù)對(duì)狀態(tài)量的偏導(dǎo)數(shù)為雙重啟發(fā)式動(dòng)態(tài)規(guī)劃（DHP，Dual Heuristic Programming）；輸出代價(jià)函數(shù)和代價(jià)函數(shù)對(duì)狀態(tài)量的偏導(dǎo)數(shù)之和為全局雙啟發(fā)式動(dòng)態(tài)規(guī)劃（GDHP，Global Dual Heuristic Dynamic Programming）。

本文是用BP神經(jīng)網(wǎng)絡(luò)來近似取得代價(jià)函數(shù)，因此構(gòu)造的自適應(yīng)動(dòng)態(tài)規(guī)劃結(jié)構(gòu)圖如圖1所示。

圖1 自適應(yīng)動(dòng)態(tài)規(guī)劃結(jié)構(gòu)圖

DHP算法中評(píng)價(jià)網(wǎng)絡(luò)輸出λ(j+1)，其中J(x^(j+1))為代價(jià)函數(shù)，評(píng)價(jià)網(wǎng)絡(luò)的訓(xùn)練目標(biāo)是最小化誤差性能指標(biāo)E(j)=0.5Pλ*(j)–λ(j)P22，其中λ*(j)為評(píng)價(jià)網(wǎng)絡(luò)輸出期望值。

根據(jù)梯度下降法訓(xùn)練評(píng)價(jià)網(wǎng)絡(luò)和動(dòng)作網(wǎng)絡(luò)，更新評(píng)價(jià)網(wǎng)絡(luò)參數(shù)來最小化代價(jià)函數(shù)對(duì)狀態(tài)量的偏導(dǎo)數(shù)，更新動(dòng)作網(wǎng)絡(luò)參數(shù)來最小化代價(jià)函數(shù)。

2 列車運(yùn)行調(diào)整模型建立

列車運(yùn)行過程中，對(duì)晚點(diǎn)列車的調(diào)整是按每個(gè)區(qū)間的運(yùn)行時(shí)間和每個(gè)車站的停車時(shí)間進(jìn)行調(diào)整的。對(duì)整條線路上的列車運(yùn)行模型描述如圖2所示。

當(dāng)列車運(yùn)行模型用狀態(tài)空間表示時(shí)，列車時(shí)刻表偏差為x(j)=t(j)–T(j)，其中t(j)為實(shí)際運(yùn)行時(shí)間，T(j)為計(jì)劃運(yùn)行時(shí)間。

圖2 列車運(yùn)行模型

根據(jù)列車運(yùn)行特點(diǎn)，列車運(yùn)行調(diào)整約束條件描述如下：

（1）列車實(shí)際出發(fā)時(shí)間約束：t(j)≥T(j)

（2）列車運(yùn)行時(shí)間約束：Tmin≤rkj≤ Tmax

Tmin為第k列車從第j站到第j+1站的最小運(yùn)行時(shí)間，該值由列車牽引計(jì)算決定；

Tmax為第k列車從第j站到第j+1站的最大運(yùn)行時(shí)間，該值由最小運(yùn)行時(shí)間加上預(yù)留時(shí)間決定。

（3）列車停站時(shí)間約束：Smin≤Skj+1≤ Smax

Smin為第k列車在第j+1站的最小停站時(shí)間，該值由列車開關(guān)門時(shí)間、旅客上下車時(shí)間等決定；

Smax為第k列車在第j+1站的最大停站時(shí)間。

（4）列車追蹤間隔約束：t(j+1)–t(j)≥H

DHP方法設(shè)計(jì)的列車運(yùn)行調(diào)整模型結(jié)構(gòu)圖如圖3所示。

圖3 列車運(yùn)行調(diào)整模型結(jié)構(gòu)圖

根據(jù)動(dòng)作網(wǎng)絡(luò)和評(píng)價(jià)網(wǎng)絡(luò)的更新規(guī)則使代價(jià)函數(shù)對(duì)狀態(tài)量的偏導(dǎo)數(shù)λ(j)最小，從而求得運(yùn)行時(shí)間調(diào)整u(j)。

3 列車運(yùn)行調(diào)整模型實(shí)現(xiàn)

列車運(yùn)行調(diào)整初始效用函數(shù)設(shè)定為：

其中P、Q、R是正定的對(duì)角矩陣，P是時(shí)刻表偏差x(j+1)的權(quán)重矩陣，Q是追蹤間隔偏差(x(j+1)–x(j))的權(quán)重矩陣，R是運(yùn)行時(shí)間調(diào)整u(j)的權(quán)重矩陣，P、Q、R的值由系統(tǒng)需求及性能決定。

動(dòng)作網(wǎng)絡(luò)、評(píng)價(jià)網(wǎng)絡(luò)、預(yù)測(cè)評(píng)價(jià)網(wǎng)絡(luò)均采用3層BP神經(jīng)網(wǎng)絡(luò)構(gòu)造，隱含層傳遞函數(shù)為tansig()函數(shù)，輸出層傳遞函數(shù)為線性purelin()函數(shù)，初始權(quán)重為[0, 1]之間的隨機(jī)值[5]。

本文中BP神經(jīng)網(wǎng)絡(luò)通過訓(xùn)練誤差性能指標(biāo)E(j)，使其達(dá)到目標(biāo)值，通過求解貝爾曼方程可得到最優(yōu)化調(diào)整u(j)。

4 仿真分析

本文采用某地鐵的數(shù)據(jù)和visual studio 2010軟件仿真平臺(tái)，對(duì)以上建立的列車運(yùn)行調(diào)整模型進(jìn)行仿真。共有20站，開行列車34列，上下行各17列，計(jì)劃運(yùn)行周期為88 min。對(duì)10列列車進(jìn)行仿真，首先輸入列車晚點(diǎn)信息，當(dāng)仿真系統(tǒng)獲取到列車晚點(diǎn)信息后，采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行列車調(diào)整，最后輸出調(diào)整后的列車時(shí)刻表。

（1）輕微晚點(diǎn)：?jiǎn)瘟熊囆》秶睃c(diǎn)

晚點(diǎn)信息輸入如圖4所示。

圖4 晚點(diǎn)信息輸入

從圖中可知，車次號(hào)為9529的列車在下行方向E站晚點(diǎn)80 s，采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行列車調(diào)整后，調(diào)整前后的運(yùn)行圖如圖5所示。

圖5 列車輕微晚點(diǎn)調(diào)整前后運(yùn)行圖

從圖5可以看出，車次號(hào)為9529的列車經(jīng)過5站4區(qū)間恢復(fù)到計(jì)劃時(shí)刻表。調(diào)整前后具體的時(shí)刻信息如表1所示。

表1 列車晚點(diǎn)調(diào)整前后時(shí)刻表

從表1的數(shù)據(jù)可以看出，車次號(hào)為9529的列車在E站晚點(diǎn)80 s，出發(fā)時(shí)間由計(jì)劃的7:15:30變成7:16:50，到達(dá)F站的時(shí)間為7:18:40，區(qū)間運(yùn)行時(shí)間調(diào)整了10 s。由于列車是小范圍晚點(diǎn)，只需對(duì)運(yùn)行時(shí)間進(jìn)行調(diào)整就可使列車快速恢復(fù)到計(jì)劃時(shí)刻表，因此，在F站的停站時(shí)間仍然為30 s，出發(fā)時(shí)間為7:19:10。依次對(duì)G、H、I、J站區(qū)間運(yùn)行時(shí)間進(jìn)行調(diào)整，當(dāng)?shù)竭_(dá)J站時(shí)，列車恢復(fù)到計(jì)劃時(shí)刻表，至此完成了列車調(diào)整。

（2）重大延誤及晚點(diǎn)傳播：?jiǎn)瘟熊囃睃c(diǎn)超過120 s，造成后續(xù)列車晚點(diǎn)

晚點(diǎn)信息輸入如圖6所示。

從圖中可知，車次號(hào)為9527的列車在下行方向F站晚點(diǎn)140 s，采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行列車調(diào)整后，調(diào)整前后的運(yùn)行圖如圖7所示。

從圖7可以看出，車次號(hào)為9527的列車經(jīng)過7站6區(qū)間恢復(fù)到計(jì)劃時(shí)刻表。同時(shí)對(duì)后續(xù)車次號(hào)為9529的列車在E站造成50 s的晚點(diǎn)影響，經(jīng)過4站3區(qū)間恢復(fù)到計(jì)劃時(shí)刻表。調(diào)整前后車次號(hào)為9527的列車時(shí)刻信息如表2所示，車次號(hào)為9529的列車時(shí)刻信息如表3所示。

圖6 晚點(diǎn)信息輸入

圖7 列車重大延誤調(diào)整前后運(yùn)行圖

表2 車次號(hào)為9527的列車調(diào)整前后時(shí)刻表

表3 車次號(hào)為9529的列車調(diào)整前后時(shí)刻表

從表2和表3的數(shù)據(jù)可以看出，車次號(hào)為9527的列車在F站晚點(diǎn)140 s，出發(fā)時(shí)間由計(jì)劃的7:15:00變成7:17:20，到達(dá)G站的時(shí)間為7:19:50，區(qū)間運(yùn)行時(shí)間調(diào)整了30 s。由于列車發(fā)生重大延誤，不對(duì)該列車的停站時(shí)間進(jìn)行調(diào)整，通過調(diào)整運(yùn)行時(shí)間使該列車在L站恢復(fù)到計(jì)劃時(shí)刻表。同時(shí)晚點(diǎn)傳播，使后續(xù)車次號(hào)為9529的列車在前一站E站發(fā)生50 s的晚點(diǎn)。對(duì)車次號(hào)為9529的列車同樣采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行調(diào)整，使之在H站恢復(fù)到計(jì)劃時(shí)刻表。

根據(jù)上述仿真驗(yàn)證，雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法避免了求解過程中“維數(shù)災(zāi)”問題，在短時(shí)間內(nèi)求得最優(yōu)解，對(duì)列車小范圍晚點(diǎn)及晚點(diǎn)傳播進(jìn)行快速調(diào)整。

5 結(jié)束語

列車運(yùn)行調(diào)整具有實(shí)時(shí)性、約束性、非線性、隨機(jī)性等特點(diǎn)，求解復(fù)雜。本文采用雙重啟發(fā)式動(dòng)態(tài)規(guī)劃算法，通過使代價(jià)函數(shù)對(duì)狀態(tài)量的偏導(dǎo)數(shù)達(dá)到最小，提高求解精度，同時(shí)滿足列車運(yùn)行調(diào)整動(dòng)態(tài)系統(tǒng)的實(shí)時(shí)性要求，使晚點(diǎn)列車在短時(shí)間內(nèi)恢復(fù)到計(jì)劃時(shí)刻表。為今后列車運(yùn)行調(diào)整的研究提供一定的參考價(jià)值。

列車運(yùn)行調(diào)整是一項(xiàng)非常復(fù)雜的工作，需要考慮各種因素的影響，本文建立的模型和算法還不能解決所有列車晚點(diǎn)情況的調(diào)整，還需繼續(xù)研究和改進(jìn)，進(jìn)一步提高列車運(yùn)行調(diào)整的效率。

[1]賈傳峻，胡思繼，楊宇棟．列車運(yùn)行調(diào)整微粒群算法研究[J]．鐵道學(xué)報(bào)，2006，12（3）：31-33．

[2]路 飛，宋沐民，田國(guó)會(huì)．基于多智能體的地鐵列車運(yùn)行調(diào)整方法[J]．中國(guó)鐵道科學(xué)，2007（1）：123-126．

[3] E.Petenson. An Introduction to Computer-aided Train Dispatch[J].Advanced Transportation，1999，20(1): 63-72．

[4] J. Si，A. G Barto, W. B. Powell, D. Wunsch. Handbook of Leaming and Approximate Dynamic Programming[M]. New York: Wiley-IEEE Press, 2004．

[5] George Ct Lendaris, Thaddeus T. Shannon, Andres Rustan. A Comparison of Training Algorithms for DHP Adaptive Critic Neuro-Control[C]. IEEE 1999: 2265-2270．

責(zé)任編輯 方 圓

Train operation regulation based on Dual Heuristic Programming Algorithm

MENG Huihui, WANG Changlin
( School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China )

This article researched on the characteristics of train traff i c organization and operation adjustment strategy, used Dual Heuristic Dynamic Programming Algorithm of adaptive dynamic programming system, established the model of train operation regulation. Dual Heuristic Dynamic Programming Algorithm was suitable for processing optimal control problem of train operation regulation complex dynamic system, which was with many characteristics, such as real-time, binding, nonlinearity, randomness. Through the simulation, the Algorithm was high speed and precision in solving the problem, and had good control effect on the regulation of train delays. At the same time, the Algorithm provided a certain reference value for further study of the train operation regulation.

operation regulation; Dual Heuristic Programming Algorithm; modelling

U292∶TP39

A

1005-8451（2014）08-0001-04

2014-01-20

孟慧慧，在讀碩士研究生；王長(zhǎng)林，教授。