基于強化學習的多時隙鐵路空車實時調配研究

譚 雪，張小強,2，石紅國,2，成嘉琪

基于強化學習的多時隙鐵路空車實時調配研究

譚 雪1，張小強1,2，石紅國1,2，成嘉琪3

（1. 西南交通大學，交通運輸與物流學院，成都 611756；2. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，成都 611756；3. 上海市政工程設計研究總院（集團）有限公司，上海 200000）

鐵路空車調配計劃是進行運輸組織的基礎和重要條件，空車供求關系的時空變化特性和運輸生產(chǎn)的動態(tài)性，使求解多時隙空車實時調配最優(yōu)策略變得困難。強化學習中的Q-learning時序差分算法能較好地解決不完全信息下的大規(guī)模序列決策問題，故本文將決策周期劃分為若干個時隙，提出多時隙空車實時調配模型：首先利用空車實際調配的局部馬爾科夫特性改進Q-learning算法，進行“單一空車調配策略評估”以量化單一空車在決策周期內所有時空狀態(tài)下采取不同行動的長期回報；然后提出空車實時優(yōu)先調配算法，求解決策周期全局最優(yōu)的調配策略。算例表明模型可以兼顧實時調配長期回報最大、空走距離小、即時需求響應程度高，求解出每時隙下最優(yōu)且決策周期全局最優(yōu)的實時調配策略，以使運輸部門快速適應變化的貨運市場需求、提供科學合理的空車實時調配策略是可行的。

鐵路運輸；空車實時調配；強化學習；空車；多時隙

0 引 言

空車調配計劃是鐵路技術計劃的重要組成部分，合理確定空車調配數(shù)量和調配方向，減少空車走行公里對鐵路降本增效至關重要。鐵路空車調配受運輸生產(chǎn)動態(tài)性、路網(wǎng)結構復雜性和空車供需不確定性等復雜因素的影響，屬于不完全信息下的時變決策問題，因此優(yōu)化決策周期內的空車實時調配策略較為困難。

空車調配算法分為靜態(tài)調配模型和動態(tài)調配模型，模型目標一般是決定調配起訖點、空車數(shù)量和輸送路徑。靜態(tài)調配模型是依據(jù)已知的空車供需確定性信息優(yōu)化當前調配策略[1-4]，直觀性強且容易實施，但不適合處理實際中空車供求狀況隨時空動態(tài)變化的實時調配過程。動態(tài)調配以基于時空網(wǎng)絡的實時調配模型為主，指在一個決策周期內，依據(jù)當前和未來時隙的空車供求信息來優(yōu)化調配策略。比如文獻[5]同時考慮了決策周期內的固定需求及各時隙新產(chǎn)生的空車需求，分兩階段求解實時調配策略；文獻[6]從動態(tài)優(yōu)化的角度構建多時點調配模型。上述兩種實時調配模型降低了空車調配時變系統(tǒng)研究復雜性，可為決策周期內每一時隙調整調配策略提供依據(jù)。但是由于鐵路空車供求關系的時空不匹配性和不確定性，按上述方法求解出的實時調配策略從調配決策周期全局看不一定是最優(yōu)解。

綜上所述，對鐵路空車調配決策周期內建立全局最優(yōu)的實時調配模型研究很少。Q-learning是強化學習[7-11]中應用最為廣泛的一種時序差分算法：智能體通過狀態(tài)觀測值、行動和即時回報序列與環(huán)境持續(xù)交互學習，構建對環(huán)境的認知，完成策略評估—策略改進—迭代收斂，進而求解馬爾科夫決策過程（Markov Decision Process, MDP）的最優(yōu)決策序列?？哲噷崟r調配本質屬于不完全信息下的MDP問題，所以Q-learning算法可以量化單一空車在決策周期內所有時空狀態(tài)下的調配動作價值函數(shù)，并用之優(yōu)化實時調配策略。因此，本文將鐵路空車實時調配轉化為多時隙大規(guī)模序列決策問題，應用強化學習構建多時隙空車實時調配模型，求解時空動態(tài)變化和不完全空車供需信息下，兼顧決策周期全局最優(yōu)和各時隙最優(yōu)的多時隙鐵路空車實時調配策略，最后通過仿真算例驗證模型的有效性。

1 多時隙空車實時調配模型

針對鐵路空車需求時空變化特征和實際調配過程的馬爾科夫特性，將決策周期拆解為多時隙，提出多時隙空車實時調配模型：（1）以實際空車調配的局部馬爾科夫特性，改進Q-learning算法，進行“單一空車調配策略評估”以量化單一空車在決策周期內所有時空狀態(tài)下采取不同行動（站內停留或站間調配）的長期回報；（2）在每個時隙下的實時調配階段，將所有空車視為多智能體系統(tǒng)，在綜合考慮貨主即時需求響應程度高、空車走行距離小、鐵路運輸企業(yè)長期回報最大的基礎上，使用優(yōu)先調配算法求解該時隙下最優(yōu)且決策周期同樣最優(yōu)的站間空車調配數(shù)量和調配方向。

1.1 基于局部MDP的單一空車調配模型

當智能體不能提前獲知狀態(tài)轉移概率時，該過程是不完全信息下的MDP（又稱局部MDP）。顯然，單一空車調配為局部MDP模型，針對空車需求時空變化特征和實際調配過程，合理構建該局部MDP是基于Q-learning的單一空車調配策略評估和求解實時調配策略的基礎。

② 當空車執(zhí)行一次完整調配時，獎勵計算方法如式（1）-（3）所示：

以下提供單一空車調配局部MDP模型構建的算例。

1.2 基于Q-learning的單一空車調配策略評估

表1 局部MDP下單一空車調配Q-learning策略評估偽代碼

Fig.1 Pseudocode for pail empty wagon distribution evaluation in local MDP

1.3 空車實時優(yōu)先調配算法

從強化學習的角度分析，每一輛空車是相互獨立的，每一時隙也是相互獨立的，分而治之，將決策周期內每一個時隙的所有空車（下稱空車）調配拆解為單一空車的實時調配合集，調配系統(tǒng)的目標函數(shù)是最大化多時隙初始狀態(tài)下所有單一空車調配動作價值：

為降低求解復雜度，確保空車調配系統(tǒng)全局最優(yōu)，對傳統(tǒng)運輸問題的目標函數(shù)加以改進。建立空車實時優(yōu)先調配算法，為防止對流，假定在每個時隙滿足本站空車需求基礎上，再確定剩余空車站間優(yōu)先調配量和調配方向，具體模型如下：

2 模擬計算分析

2.1 算例設計

站間運行時間、重走貨運收益以及折扣貨運收益見表2，站內等待和空車站間走行不產(chǎn)生貨運收益。在每個時隙，6個站點中既有已滿足本站裝車的可參與站間調配的剩余空車站點，又有空車不足需要其余站調撥的站點。各站點剩余空車數(shù)、空車需求數(shù)見表3。

表2 站間運行時間（天）/貨運（重走）收益（元·輛/天）/折扣貨運收益（元/輛）

表3 每個時隙下站點空車剩余數(shù)和空車需求數(shù)

2.2 實驗結果及對比試驗

采用空車實時優(yōu)先調配算法對模型求解，部分時刻的空車調配量、調配方向結果節(jié)選見表4。求解結果顯示所有時刻的站點空車需求均可滿足，站內空車利用總數(shù)分別為64/281/257/255/131輛，站間調配剩余空車總數(shù)分別為45/106/48/71/62輛，且均在2天內完成站間調配，空車需求響應效率高。

Tab.4 Excerpts from the results of empty wagons and distribution when//

上式中各變量含義同前。

三種模型在所有時隙下的指標結果如表5所示。

表5 指標對比表

由表5可知，在多時隙鐵路空車實時調配問題上，所提實時優(yōu)先調配算法（M）總體比空走距離最小化（M1）和調配結束狀態(tài)價值最大化（M2）模型性能要優(yōu)。

結果直接說明了實時優(yōu)先調配算法中優(yōu)先函數(shù)（式（8））的合理性。即實時調配時，剩余空車優(yōu)先從狀態(tài)價值低的起始站點向調配結束站狀態(tài)價值高且空走距離短的方向調配，以期獲得最大調配長期回報、低空走距離和高響應效率。

3 結 論

本文研究了不完全信息下的鐵路空車調配問題，建立了基于強化學習的多時隙空車實時調配全局最優(yōu)模型，首先，將決策周期劃分為若干時隙，再通過“基于Q-learning的單一空車調配策略評估”和“空車實時優(yōu)先調配”兩階段求解每一時隙的實時調配策略，最后通過算例與空走距離最小化和調配結束狀態(tài)價值最大化模型對比。實驗結果表明：所提模型可兼顧實時調配預期回報、調配后狀態(tài)價值和空走距離求解出每個時隙下最優(yōu)且決策周期全局最優(yōu)的調配策略，從而方便鐵路運輸部門快速適應變化的貨運市場需求、進行科學合理的運輸組織。后續(xù)研究中，可以進一步引入車種代用，分析其對空車調配的影響。

[1] HOLMBERG K, JOBORN M, LUNDGREN J T. Improved empty freight car distribution [J]. Transportation Science, 1998, 32 (2): 163-73.

[2] 程學慶. 鐵路空車調配綜合優(yōu)化模型及求解[J]. 中國鐵道科學, 2012, 33 (6): 115-119.

[3] 薛鋒, 孫宗勝. 鐵路空車調整模型的D-W分解算法[J]. 交通運輸工程與信息學報, 2019, 17 (4): 43-48.

[4] 朱健梅, 譚云江, 閆海峰. 鐵路空車調整優(yōu)化模型及其蟻群算法[J]. 交通運輸工程與信息學報, 2006 (3): 8-15.

[5] 陳勝波, 何世偉, 劉星材, 等. “實貨制”下鐵路空車動態(tài)調配兩階段優(yōu)化模型與算法研究 [J]. 鐵道學報, 2015, 37 (5): 1-8.

[6] 王波, 榮朝和, 黎浩東, 等. 鐵路空車調配的多時點優(yōu)化模型研究 [J]. 交通運輸系統(tǒng)工程與信息, 2015, 15 (5): 157-163, 171.

[7] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning [J]. Nature, 2015, 518 (7540): 529-533.

[8] ZHU M, WANG X, WANG Y. Human-like autonomous car-following model with deep reinforcement learning [J]. Transportation Research Part C: Emerging Technologies, 2018, 97: 348-368.

[9] MAO C, SHEN Z. A reinforcement learning framework for the adaptive routing problem in stochastic time- dependent network [J]. Transportation Research C: Emerging Technologies Partc: 2018, 93: 179-197.

[10] XU Z, LI Z, GUAN Q, et al. Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach [C]// 24th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) . London: Assoc Computing Machinery, 2018: 905-913.

[11] WANG Z, QIN Z, TANG X, et al. Deep Reinforcement Learning with Knowledge Transfer for Online Rides Order Dispatching [C]// 2018 Ieee International Conference on Data Mining. New York: IEEE Press, 2018: 617-626.

Reinforcement-learning-based Multi-slot Rail Empty Wagon Real-time Distribution

TAN Xue1, ZHANG Xiao-qiang1, 2, SHI Hong-guo1, 2, CHENG Jia-qi3

(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China；2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 611756, China；3. Shanghai Municipal Engineering Design Institute Co., Ltd., Shanghai 200000, China)

Rail empty wagon distribution is critical to a transportation enterprise. The spatio-temporal characteristics of the supply and demand of empty wagons and the dynamics of transportation generate difficulties in developing an optimal strategy for multi-slot empty wagon real-time distribution. A Q-reinforcement-learning algorithm can solve large-scale sequence decision problems using incomplete information. In this study, the decision period is divided into multi-slots, and a multi-slot empty wagon distribution model is proposed. First, based on local Markov characteristics of empty wagon distribution, an improved Q-learning algorithm is designed, and a single empty wagon strategy evaluation is performed to evaluate a single wagon’s long-term gains under all spatio-temporal states during the decision period. Second, an empty wagon real-time priority distribution algorithm is proposed to solve the strategy for each slot. A case study of multi-slot empty wagon real-time distribution shows that our proposed model can maximize long-term gains as well as minimize unloaded distances of a real-time distribution. Thus, providing rail transportation enterprises with scientific real-time empty wagon distribution strategies is feasible.

railway transportation; empty wagon real-time distribution; reinforcement learning; empty wagon; multi-slot

1672-4747（2020）04-0053-08

U292.8

A

10.3969/j.issn.1672-4747.2020.04.007

2020-06-07

國家鐵路局科技開發(fā)項目（KF2019-101-B）

譚 雪（1997—），女，漢族，安徽亳州人，碩士，研究方向：機器學習、數(shù)據(jù)挖掘，E-mail：779495316@qq.com

張小強（1975—），男，漢族，江西石城人，副教授，博士后，研究方向：鐵路運營管理，人工智能與智慧物流，E-mail：xqzhang@swjtu.edu.cn

譚雪，張小強，石紅國，等. 基于強化學習的多時隙鐵路空車實時調配研究[J]. 交通運輸工程與信息學報，2020, 18(4): 53-60

（責任編輯：劉娉婷）