譚 雪，張小強(qiáng),2，石紅國,2，成嘉琪

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

譚 雪1，張小強(qiáng)1,2，石紅國1,2，成嘉琪3

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

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

鐵路運(yùn)輸；空車實(shí)時(shí)調(diào)配；強(qiáng)化學(xué)習(xí)；空車；多時(shí)隙

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 模擬計(jì)算分析

2.1 算例設(shè)計(jì)

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

表2 站間運(yùn)行時(shí)間（天）/貨運(yùn)（重走）收益（元·輛/天）/折扣貨運(yùn)收益（元/輛）

表3 每個(gè)時(shí)隙下站點(diǎn)空車剩余數(shù)和空車需求數(shù)

2.2 實(shí)驗(yàn)結(jié)果及對(duì)比試驗(yàn)

采用空車實(shí)時(shí)優(yōu)先調(diào)配算法對(duì)模型求解，部分時(shí)刻的空車調(diào)配量、調(diào)配方向結(jié)果節(jié)選見表4。求解結(jié)果顯示所有時(shí)刻的站點(diǎn)空車需求均可滿足，站內(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//

上式中各變量含義同前。

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

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

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

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

3 結(jié) 論

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

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

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

[6] 王波, 榮朝和, 黎浩東, 等. 鐵路空車調(diào)配的多時(shí)點(diǎn)優(yōu)化模型研究 [J]. 交通運(yùn)輸系統(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ā)項(xiàng)目（KF2019-101-B）

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

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

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

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