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

基于強化學(xué)習(xí)的多時隙鐵路空車實時調(diào)配研究

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

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

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

鐵路運輸；空車實時調(diào)配；強化學(xué)習(xí)；空車；多時隙

0 引 言

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

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

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

1 多時隙空車實時調(diào)配模型

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

1.1 基于局部MDP的單一空車調(diào)配模型

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

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

以下提供單一空車調(diào)配局部MDP模型構(gòu)建的算例。

1.2 基于Q-learning的單一空車調(diào)配策略評估

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

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

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

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

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

2 模擬計算分析

2.1 算例設(shè)計

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

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

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

2.2 實驗結(jié)果及對比試驗

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

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

上式中各變量含義同前。

三種模型在所有時隙下的指標(biāo)結(jié)果如表5所示。

表5 指標(biāo)對比表

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

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

3 結(jié) 論

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

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

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

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

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

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

[6] 王波, 榮朝和, 黎浩東, 等. 鐵路空車調(diào)配的多時點優(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—），女，漢族，安徽亳州人，碩士，研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘，E-mail：779495316@qq.com

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

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

（責(zé)任編輯：劉娉婷）