基于雙重啟發式動態規劃算法的列車運行調整研究

孟慧慧，王長林

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

基于雙重啟發式動態規劃算法的列車運行調整研究

孟慧慧，王長林

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

通過對列車行車組織特點及運行調整策略的研究，采用自適應動態規劃體系中的雙重啟發式動態規劃算法，建立了列車運行調整模型。雙重啟發式動態規劃算法適合處理具有實時性、約束性、非線性、隨機性等特點的列車運行調整復雜動態系統的優化控制問題，通過仿真驗證，該算法求解速度快、精度高，對列車晚點的調整起到了良好的控制作用。為列車運行調整的深入研究提供了一定的參考價值。

運行調整；雙重啟發式動態規劃算法；模型建立

城市軌道交通列車運行自動調整是列車自動監控系統（ATS，Automatic Train Supervision）的重要功能，通過列車運行自動調整模塊（ATR，Automatic Train Regulation）實現。當列車發生晚點時，ATR將列車實際時刻表時間與計劃時刻表時間進行比較，計算時刻表偏差，通過調整運行時間和停站時間，使列車能夠安全、及時、有效地恢復到按計劃時刻表時間運行。

列車運行調整的關鍵是運行時間和停站時間的調整。列車區間運行時間受列車速度條件和線路通過能力的影響，當列車以線路允許的最大速度運行時為區間最小運行時間，同時，為保證行車效率及節能、舒適度等，需要設定區間最大運行時間。

對列車運行時間的調整必須介于區間最小運行時間和最大運行時間之間。對列車停站時間的調整也要介于最小停站時間和最大停站時間之間。最小停站時間是列車停車后，司機開關門操作及乘客上下車的最小時間，同時，列車不能無限度的在站內停車，需要設定最大停車時間。

目前有許多方法用于對列車運行調整模型進行建立，包括人工智能方法[1～2]、運籌學的優化理論[3]等。但由于約束性、非線性、隨機性等因素的影響，使用上述兩類方法無法在短時間內求得令人滿意的可行解，本文采用雙重啟發式動態規劃算法進行求解，可以在短時間內求得優化解，同時滿足實時調度的需求。

1 雙重啟發式動態規劃算法描述

自適應動態規劃（ADP，Adaptive Dynamic Programming）采用動態規劃的基本思想，利用函數近似方法如神經網絡來近似取得代價函數，并使其最小，以避免動態規劃在計算最優代價函數時遇到的“維數災”問題，適用于復雜、非線性系統的決策優化或控制問題[4]。

ADP的實現一般需要評價（Critic）、模型（Model）和動作（Action）3個模塊。評價模塊對代價函數進行近似，模型模塊反映被控系統的特性，動作模塊產生控制信號。根據評價模塊輸出的函數不同，現有的自適應動態規劃方法主要有3種類型：輸出代價函數的近似值為啟發式動態規劃（HDP，Heuristic Dynamic Programming）；輸出代價函數對狀態量的偏導數為雙重啟發式動態規劃（DHP，Dual Heuristic Programming）；輸出代價函數和代價函數對狀態量的偏導數之和為全局雙啟發式動態規劃（GDHP，Global Dual Heuristic Dynamic Programming）。

本文是用BP神經網絡來近似取得代價函數，因此構造的自適應動態規劃結構圖如圖1所示。

圖1 自適應動態規劃結構圖

DHP算法中評價網絡輸出λ(j+1)，其中J(x^(j+1))為代價函數，評價網絡的訓練目標是最小化誤差性能指標E(j)=0.5Pλ*(j)–λ(j)P22，其中λ*(j)為評價網絡輸出期望值。

根據梯度下降法訓練評價網絡和動作網絡，更新評價網絡參數來最小化代價函數對狀態量的偏導數，更新動作網絡參數來最小化代價函數。

2 列車運行調整模型建立

列車運行過程中，對晚點列車的調整是按每個區間的運行時間和每個車站的停車時間進行調整的。對整條線路上的列車運行模型描述如圖2所示。

當列車運行模型用狀態空間表示時，列車時刻表偏差為x(j)=t(j)–T(j)，其中t(j)為實際運行時間，T(j)為計劃運行時間。

圖2 列車運行模型

根據列車運行特點，列車運行調整約束條件描述如下：

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

（2）列車運行時間約束：Tmin≤rkj≤ Tmax

Tmin為第k列車從第j站到第j+1站的最小運行時間，該值由列車牽引計算決定；

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

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

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

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

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

DHP方法設計的列車運行調整模型結構圖如圖3所示。

圖3 列車運行調整模型結構圖

根據動作網絡和評價網絡的更新規則使代價函數對狀態量的偏導數λ(j)最小，從而求得運行時間調整u(j)。

3 列車運行調整模型實現

列車運行調整初始效用函數設定為：

其中P、Q、R是正定的對角矩陣，P是時刻表偏差x(j+1)的權重矩陣，Q是追蹤間隔偏差(x(j+1)–x(j))的權重矩陣，R是運行時間調整u(j)的權重矩陣，P、Q、R的值由系統需求及性能決定。

動作網絡、評價網絡、預測評價網絡均采用3層BP神經網絡構造，隱含層傳遞函數為tansig()函數，輸出層傳遞函數為線性purelin()函數，初始權重為[0, 1]之間的隨機值[5]。

本文中BP神經網絡通過訓練誤差性能指標E(j)，使其達到目標值，通過求解貝爾曼方程可得到最優化調整u(j)。

4 仿真分析

本文采用某地鐵的數據和visual studio 2010軟件仿真平臺，對以上建立的列車運行調整模型進行仿真。共有20站，開行列車34列，上下行各17列，計劃運行周期為88 min。對10列列車進行仿真，首先輸入列車晚點信息，當仿真系統獲取到列車晚點信息后，采用雙重啟發式動態規劃算法進行列車調整，最后輸出調整后的列車時刻表。

（1）輕微晚點：單列車小范圍晚點

晚點信息輸入如圖4所示。

圖4 晚點信息輸入

從圖中可知，車次號為9529的列車在下行方向E站晚點80 s，采用雙重啟發式動態規劃算法進行列車調整后，調整前后的運行圖如圖5所示。

圖5 列車輕微晚點調整前后運行圖

從圖5可以看出，車次號為9529的列車經過5站4區間恢復到計劃時刻表。調整前后具體的時刻信息如表1所示。

表1 列車晚點調整前后時刻表

從表1的數據可以看出，車次號為9529的列車在E站晚點80 s，出發時間由計劃的7:15:30變成7:16:50，到達F站的時間為7:18:40，區間運行時間調整了10 s。由于列車是小范圍晚點，只需對運行時間進行調整就可使列車快速恢復到計劃時刻表，因此，在F站的停站時間仍然為30 s，出發時間為7:19:10。依次對G、H、I、J站區間運行時間進行調整，當到達J站時，列車恢復到計劃時刻表，至此完成了列車調整。

（2）重大延誤及晚點傳播：單列車晚點超過120 s，造成后續列車晚點

晚點信息輸入如圖6所示。

從圖中可知，車次號為9527的列車在下行方向F站晚點140 s，采用雙重啟發式動態規劃算法進行列車調整后，調整前后的運行圖如圖7所示。

從圖7可以看出，車次號為9527的列車經過7站6區間恢復到計劃時刻表。同時對后續車次號為9529的列車在E站造成50 s的晚點影響，經過4站3區間恢復到計劃時刻表。調整前后車次號為9527的列車時刻信息如表2所示，車次號為9529的列車時刻信息如表3所示。

圖6 晚點信息輸入

圖7 列車重大延誤調整前后運行圖

表2 車次號為9527的列車調整前后時刻表

表3 車次號為9529的列車調整前后時刻表

從表2和表3的數據可以看出，車次號為9527的列車在F站晚點140 s，出發時間由計劃的7:15:00變成7:17:20，到達G站的時間為7:19:50，區間運行時間調整了30 s。由于列車發生重大延誤，不對該列車的停站時間進行調整，通過調整運行時間使該列車在L站恢復到計劃時刻表。同時晚點傳播，使后續車次號為9529的列車在前一站E站發生50 s的晚點。對車次號為9529的列車同樣采用雙重啟發式動態規劃算法進行調整，使之在H站恢復到計劃時刻表。

根據上述仿真驗證，雙重啟發式動態規劃算法避免了求解過程中“維數災”問題，在短時間內求得最優解，對列車小范圍晚點及晚點傳播進行快速調整。

5 結束語

列車運行調整具有實時性、約束性、非線性、隨機性等特點，求解復雜。本文采用雙重啟發式動態規劃算法，通過使代價函數對狀態量的偏導數達到最小，提高求解精度，同時滿足列車運行調整動態系統的實時性要求，使晚點列車在短時間內恢復到計劃時刻表。為今后列車運行調整的研究提供一定的參考價值。

列車運行調整是一項非常復雜的工作，需要考慮各種因素的影響，本文建立的模型和算法還不能解決所有列車晚點情況的調整，還需繼續研究和改進，進一步提高列車運行調整的效率。

[1]賈傳峻，胡思繼，楊宇棟．列車運行調整微粒群算法研究[J]．鐵道學報，2006，12（3）：31-33．

[2]路 飛，宋沐民，田國會．基于多智能體的地鐵列車運行調整方法[J]．中國鐵道科學，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．

責任編輯 方 圓

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

孟慧慧，在讀碩士研究生；王長林，教授。