韩忻辰 ,俞胜平 ,袁志明 ,程丽娟
(1.东北大学流程工业综合自动化国家重点实验室,辽宁沈阳 110819;2.中国铁道科学研究院集团有限公司通信信号研究所,北京 100081)
随着我国高速铁路列车事业的飞速发展,现我国高铁运行里程数已达三万余公里,居世界第一.也正是随着高铁速度的不断提升与列车数量的不断增多,使得高铁路网规模扩大化,路网结构复杂化,其强耦合、快演变、多约束等特点也越来越明显.加之,恶劣天气、设备故障等突发事件的不可预知性,可能会导致单列车或多列车出现延误晚点现象.随着路网不断传播扩散,将造成大面积的列车无法按照计划运行.因此,当原调度计划受到扰动影响无法继续运行时,如何进行重调度或动态调度[1],如何能更好地协调各列车尽快恢复有序运行、减小延误时间、缩小影响范围,从而实现高速铁路列车运行快速、运营安全、到站准时、旅客舒适,已成为目前迫切需要解决的问题[2].
目前,列车调度方法研究主要集中在静态调度即运行图编制上,而针对高速铁路列车动态调度问题的研究,其方法大致可分为仿真方法、运筹学方法和智能算法3类.利用仿真方法有文献[3]针对随机扰动交通条件下最优调度方案的稳定性,提出了一种将基于替代图的铁路优化系统(railway optimization by means of alternative graphs,ROMA)与路网设计微观仿真环境(environment for the design and simulation of railway network,EGTRAIN)相结合的框架.文献[4]提出了一种基于仿真方法的列车时刻表优化模型,并在该模型的基础上又开发了一种集成路径再规划算法的框架.文献[5]则基于全路路网,利用MapInfo技术整合铁路车站及区间基础地理信息数据,构建了一个列车运行仿真系统.文献[6]基于部件组合思想和考虑线路双向运行以及列车运行过程中随机扰动建立的列车运行仿真模型,可根据需要模拟的列车运行计划及关联路网的数据,快速生成与列车运行环境和列车运行规则对应的仿真框架,并且在最终的仿真验证中也证实了该模型的有效性.而基于运筹学方法的如文献[7–9]结合累积流变量模型的特点,构建基于累积流变量的列车运行图整数规划模型,将原问题按列车划分为子问题并通过拉格朗日松弛算法优化列车运行图.文献[10–11]都是针对不同扰动进行的研究,文献[10]主要是针对若干典型场景建立了不同模型并采用改进粒子群算法对模型求解,而文献[11]则是通过建立不同策略匹配表,并基于极大加代数的时刻表递推思路进行求解.文献[12]提出了针对新增运行线(包括将需调整的运行线)视为一类特殊的新增列车的整数规划问题,并建立了基于拉格朗日松弛法的局部调整模型.运用智能算法的如文献[13]针对突发事件的影响,提出了调整策略控制参数的粒子群优化算法,并同常规的遗传算法(genetic algorithm,GA)与粒子群优化(particle swarm optimization,PSO)算法进行了比较.文献[14]采用了蚁群优化算法与遗传算法,其最终结果显示该两种算法的延迟成本比先进先出(first input first output,FIFO)的方法降低了30%和28%.文献[15]采用双适应值法,通过改变3个不同的参数分析粒子群算法所得结果,可以有效处理大规模列车约束问题.文献[16]将人工免疫算法引入到遗传算法中,指导个体向最优方向发展,能够避免一般进化算法可能遇到的退化现象,提高全局搜索能力.文献[17]通过改进萤火虫算法(improved firefly algorithm,IFA)优化调整列车调度,在保证列车安全运行的情况下,可以将列车晚点产生的不利影响控制在很小的区间范围内.
仿真方法所构建的模型较为直观,但是其基于一定的假设条件之上,真正遇到大规模问题就会显得乏力,模型的结果与现实情况会有很大的差距.运筹学方法缺乏实时性和适应性,不能很好地满足实际列车动态调整的需要[13].智能算法容易陷入局部最优,且在多约束条件下,为求得更好更优的解需要大量增加迭代次数,导致计算时间过长.而强化学习是以目标为导向,通过智能体与环境不断交互学习进而求得最优策略的算法,采用强化学习求解组合优化问题,通过奖励函数的合理引导可以取得比人类设计更好的解决方法,且模型的泛化能力强.并且目前采用该算法应用于高速铁路列车动态调度问题的研究还是相对较少.
因此,本文针对突发事件对高速铁路列车造成的延误影响,结合强化学习中智能体与环境不断交互、不断试错的特点,选定具体的单线单向多车站且列车可在多股道车站内进行越行的场景,采用经典的Qlearning方法进行调度策略的优化.首先建立高速铁路列车动态调度的数学模型,然后根据模型搭建起用于与智能体交互的环境,运用Q-learning方法使智能体在不同状态下或探索未知的策略,或利用当前的最优策略,循环往复不断优化,最终得到调整后的调度计划,将延误影响降至最小.将所建立的模型与算法在多种扰动场景下进行仿真研究,仿真结果表明应用强化学习中的Q-learning方法能够学习到满意的高铁调度策略,为高铁优化调度提供良好的决策依据.
在高铁列车实际运行过程中,当遇到大风、暴雪等突发事件影响导致列车到发时间晚点时,需要根据初始调度计划信息、区间运行时间和车站停站等信息,在初始调度计划的基础上,对列车在所停车站的到发时间、列车顺序、股道占用等进行快速调整,使受影响列车尽可能地恢复至原计划运行状态,避免因一车延误造成全网延误的现象.因此高速铁路列车动态调度问题是在初始调度计划安排的基础上,根据扰动的影响程度,对其进行再次的决策与优化.而再次的决策与优化是在某一评价函数最优(如总晚点时间最小或总晚点列车数量最少)的情况下,对突发扰动影响的列车及其相关联的列车确定闭塞区间的占用时间、到发时间及列车顺序等一系列事件的动态调度.
现有的依靠调度员经验按列车逐站调整或者整体平移的人工调整方式,难以在突发事件下对列车运行图进行快速准确地调整,往往只是将延误列车及其后续列车进行顺延处理,并不能将延误所带来的影响降至最小.所以本文采用Q-learning的方法,将延误影响到的列车群当作一个整体,进行包括数学模型、交互环境、状态动作、奖励函数等关键因素的设计,从而对其进行优化调度.
高速铁路列车动态调度数学模型中所用模型参数定义如表1所示.
表1 模型参数定义Table 1 Model parameter meaning table
根据第2节高速铁路列车动态调度问题描述,建立如下数学模型.
目标函数为最小化各列车在各车站的实际到站、离站时间与计划到站、离站时间的偏差和.
目标函数:
约束条件:
1) 列车i实际离开车站j的时间不得早于图定离站时间.而对于在j*站受扰动影响发生晚点的i*车而言,其离站时间为图定计划时间与扰动时间之和,故离站时间约束如下所示:
2) 列车i在车站j的停站时间不得小于j站规定的最小停站时间约束.即i车在j站的离站时间Dij距离其到站时间Aij的间隔应大于等于该站最小的停站时间.
4) 相邻列车i,i+1在车站j的最小进站时间间隔约束.当zi,i+1,j-1=1时,即i车在i+1车之前到达j站,所以Ai+1,j -Aij应大于等于j站的最小到站间隔,反之亦然.
其中j≥2.
5) 相邻列车i,i+1在车站j的最小离站时间间隔约束.当zi,i+1,j=1时,即i车在i+1车之前离开j站,所以Di+1,j -Dij应大于等于j站的最小离站间隔,反之亦然.
其中j <M.
6) 列车i在车站j,j+1之间的最小区间运行时分约束.受地形制约等因素的影响,列车i在车站j,j+1之间的区段内运行速度须保证列车安全,即列车在j+1站的到站时间Ai,j+1与在j站的离站时间Dij之差应大于等于该区间内的最小运行时分
8)j与j+1站之间的闭塞区间资源占用唯一性约束.在kj,j+1闭塞区间内,列车数量只有两种状态,即无列车状态0或只有一辆列车状态1.
9)j站内股道资源占用唯一性约束.同约束(8),在lj股道内,列车数量也只有两种状态,即无列车状态0或只有一辆列车状态1.另外,因受车站内股道总数量限制,停在该站列车应小于等于该站内的总股道数Lj.
上述建立的数学模型为混合整数非线性规划模型(mix-integer non-linear programming,MINLP),其包含着大量的约束方程、离散变量和连续变量,采用运筹学方法和智能优化方法均难以在有效时间内进行快速求解,无法满足现场对实时性的要求[18].而强化学习是以目标为导向的机器学习方法,设计合理的交互环境,其可以在模型未知(model-free)的情况下,进行学习求解,故采用强化学习中的Q-learning算法对其进行动态调度.
机器学习可根据反馈的不同,将其分为监督学习(supervised learning)、无监督学习(unsupervised learning)和强化学习(reinforcement learning)3大类.其中强化学习是一种以环境反馈作为输入的、特殊的、适应环境的机器学习方法,它的主要思想是与环境交互和试错,利用评价性的反馈信号实现决策的优化[19],其基本框架如图1所示.
图1 强化学习框架Fig.1 Framework of RL
在强化学习中,Q-learning是目前应用最为广泛的算法之一,其被公认为是强化学习发展过程中的一个里程碑[20],该算法的思想是直接优化一个可迭代计算的Q函数.其中Q函数定义为在某一状态s ∈S时,执行动作a ∈A,此后按最优动作序列执行所获得的回报的期望.Q函数更新公式为
其中:α为算法收敛的学习率,γ为折扣因子,rt+1为智能体在状态st采取行动at后所获得的即时奖励[21].
Q-learning算法的运用,还需定义其6个基本的组成要素,分别为智能体(agent)及其可以采取的动作(action)、智能体进行交互的环境(environment)、智能体与环境交互后确定当前所处的状态(state)、采取不同的策略所能获得的奖励(reward)以及保存Q函数值的Q-table.
根据第3.2节所设计的数学模型,建立智能体与之交互的环境.建立交互环境的目的是让智能体不断试错寻优,用以学习到最优策略.所以环境设立的好坏也影响了最终决策的优劣.在建立环境之前,首先提出4个为方便处理问题的假设条件.
假设1假设在环境中运行的列车为一个质点,即忽略列车的长度.这样处理的好处是会忽略列车在跨越两个闭塞区间资源或驶入、驶离车站时因车身长度所耗费的时间.
假设2假设时间是离散的,并且确定时间刻度的分辨率为1 min,即智能体从环境获得观测值(observation)并采取动作是每分钟进行一次.该假设是与人工调度以分钟为最小调度单位相符合的.
假设3假设车站内股道的设置是相对简单的,仅仅是用一系列平行的直线来代替,而不去考虑现实场景股道之间的复杂性.
假设4假设每辆列车只有两个动作前进(go)或者停止(stop),如果列车选择前进动作,那么列车将以规定速度前进,忽略列车提速的过程.同样,也忽略列车减速过程.
由上述提出的4个假设,结合数学模型中的约束条件,建立起实验所需的环境.首先对列车可占用的资源进行编号,其中可占用的资源包括:车站内的股道以及车站间的闭塞区间.编号顺序以简单的两站一区间为例进行说明,如下图2所示.
图2 两站一区间资源编号Fig.2 Resource number of two stations and one section
上图所示为车站1内有3个股道,编号为0,1,2.车站1,2之间的整个区间被分为3个闭塞区间,编号为3,4,5.车站2内有两个股道,编号为6,7.
下面考虑数学模型中所需要满足的约束条件.
针对约束(1)–(7),本文建立了一个列车状态矩阵S,其具体的表现形式如式(12).其中:S中的第i行表示第i辆列车,第t列表示时刻t,列的增加表示时刻t的增加.S中的每个元素si,t表示在第t时刻,第i辆车所占据的资源编号.N表示需要进行动态调度的列车总数,T表示经动态调度后所有列车到达终点站的时间总跨度.
例如式(13),S中第2列,表示在第1分钟(时刻t从0时刻开始),G1车在0号资源,G2车在1号资源,G3车在2号资源.假设图3情景发生在第2分钟,此时G1车选择前进,对应S中第3列各车所对应的资源占用.由此可见,S中保留了各列车占用资源的历史信息,所以时间约束(1)–(7)可以从状态矩阵S中进行判断.
图3 状态切换Fig.3 State switching
约束(8)–(9)都可以归为资源占用的唯一性约束,即每个资源在当前时刻只可为空闲或最多被一辆列车所占据,不可出现多列车占用资源冲突的情况,如图4所示.如果在某一时刻出现列车争夺资源的现象,就把该资源随机分配给其中一辆车.
图4 资源唯一性约束Fig.4 Uniqueness of resources
综上所述,模型中的约束条件均在建立的环境中一一体现,并限制了智能体的动作选择.
前面提到了目前高速铁路列车动态调度的缺点,本文所采取的方法是将整个因突发事件影响受到牵连的所有列车当作列车群,作为一个智能体去进行调度策略的优化.
而对于智能体所处的状态定义,则是根据第4.1节所建立的仿真环境,将智能体的状态定义为每辆列车目前所处的资源编号.如state=[i,j,k]表示智能体包含3辆列车,其目前所占用的资源分别为i,j,k号资源.
对于每辆列车而言,在当前时刻t可选择的动作分为两种,即前进(go)或停止(stop).而对于第4.2节所定义的智能体,其全部可以采取的动作组合数最多为2N种,其中N表示智能体所包含的列车数量.
当列车处于闭塞区间资源并满足第3.2节数学模型中的所有约束时,其可以采取的动作集合为{go,stop},为加快算法的收敛,本文将对该列车强制采取动作前进(go).又为了使算法可以探索到更多的可能性,也为了发现可能存在的更优策略,对处在车站资源的列车且满足模型中所有约束时,将从动作集合{go,stop}中依策略进行动作选择,而并非是直接采取动作前进(go).以图5来说明上述提到的两种情况.
图5 采取动作时的两种情况Fig.5 Two situations while taking an action
目前,G1车正处于4号资源,在该资源中必须连续前进,选择动作前进.若满足所有约束,则前进到5号资源.G2车目前正处于资源1,当其满足所有约束时,其可选的动作为{go,stop},而并非强制采取前进.这样处理的原因是本文所建立的模型仅允许列车在多股道车站内进行越行,所以可能G2车停在该站让G3车先去占用3号资源会得到一个更好的解.
其次,本文利用ϵ-greedy策略去进行动作的选择.采用这种策略的好处是在保证智能体往更优方向前进的同时又可以保留一定的探索性.其中
ϵ-greedy策略如下:
式(15)中:a*表示在st状态下Q值最大的动作,A(st)表示在st状态下所有可选的动作集合,rand为一个服从标准正态分布的抽样值.根据式(14)绘制出ϵ与1-ϵ的图像如图6所示.
图6 ϵ与1-ϵ的图像Fig.6 ϵ and 1-ϵ
可发现随着迭代次数的增长,ϵ逐渐减小趋近于0,而1-ϵ则逐渐增大趋近于1.表示在训练的开始,智能体大概有50%的概率去探索新的动作.但是随着训练次数的增加,智能体更偏向于利用已经学习到的知识,从而会更多地采用已经学习到的最优动作序列.
因为在第3.2节中数学模型的优化目标为
即最小化所有列车在各站的到发晚点时间和.所以本文所采取的奖励函数为目标函数值的倒数,即
根据上式发现,当总延迟时间越小,即目标函数越优,给予智能体的奖励也就越大.但是注意奖励机制的设置是只有当智能体到达最终状态时才会给予奖励,即所有列车都到达终点站时才会有奖励,其余时刻智能体所获得奖励为0.在这种奖励机制与奖励函数的设置下,只有在完整的一轮训练结束后,才会反向传播更新Q-table的值.这样设置的原因是根据本文数学模型中所设定的目标函数及奖励函数,只有当所有列车均到站后才可以确定,类似问题的处理方法在文献[22]也有所涉及.
在实验中发现当训练次数增多,该奖励反向传播至前几轮经过的状态时,其对应Q-table中的值非常小,故在式(16)基础上,对其做了放大10000倍的处理.
另外,本文在奖励函数的设置中还采用了一种加速算法收敛的技巧,即如果智能体表现的不好,并非置之不顾,给予奖励0,而是会给予其一惩罚.当扰动发生造成的延误时间已知时,对于整个智能体而言其完成一轮训练的时间阈值可人为确定.当目标函数值超过该阈值时,即该解已经不满足调度要求的下限,认为智能体在该轮训练中表现较差,给予的奖励为一个负值.综上所述,奖励r的表达式为
首先,本文是利用t与action去获得Q(st,at),而不是常规地利用state与action去获得Q(st,at).具体原因是Q-table的设置并没有采用常规state×action的结构,因为在此算法中state的数量太多.例如智能体包含列车数量为N,线路资源数量为M,时间跨度为T分钟,那么该环境所对应state数量为MN ·T,其对应的Q-table元素个数为MN ·T ×2N,当列车数量或资源数量增加时,该数值将呈现指数型的爆炸式增长.
故本文所建立的Q-table为time×action的结构,如表2.对于上述情况,Q-table中的元素个数仅为T ×2N.随着列车数量增加与时间跨度增大,这样构造的Q-table也会扩张,但是其扩张幅度远小于state×action类型的Q-table.当然这样处理是通过牺牲一部分算法的计算时间来实现的,即需要更多次的训练才可以得到理想的结果.之后为方便理解与统一表达,依旧采用Q(st,at)这种表达方式.
表2 Q-table结构Table 2 The structure of Q-table
根据上述Q-learning算法所需的几大要素的设置,给出Q-learning算法在求解高速铁路列车调度时的算法流程:
步骤1定义超参数学习率α、折扣因子γ,导入列车时刻表T-Table,同时确定扰动作用点delay-point,造成的延误时间delay-time等.初始化环境、智能体及其状态,初始化Q-table,列车状态矩阵S matrix,总训练回合数max-episodes.
步骤2开始智能体的策略更新循环,在每次训练之前初始化当前时刻t,初始化智能体的起始状态state.
步骤3根据当前时刻t、状态state,判断智能体当前时刻可采取的满足约束的动作集合actions,以及下一时刻智能体中各列车可能到达的资源集合res.
步骤4根据t,actions与当前进行训练的回合数episode以及Q-table运用ϵ-greedy策略选择动作action.
步骤5根据t,state以及action得到下一时刻的状态state-,奖励r以及是否可以停止本轮训练的标志done.
步骤6根据t+1,state-获得智能体下一时刻满足约束的动作集合actions-.
步骤7根据t以及action 从Q-table中获得式(11)中Q函数更新公式中的Q预测值
步骤8根据Q-table与求得的actions-去计算,可以计算Q目标值
步骤9至此式(11)中所有变量都已得到,可进行Q函数的更新,即对Q-table进行更新.
步骤10当前时刻t ←t+1更新,状态state更新.由done判断本轮循环是否可以结束,若未结束则返回步骤3;若本轮循环结束并且结果未收敛,则返回步骤2,并且episode←episode+1;否则进行步骤11.
步骤11如果智能体最后结果已经收敛或者已经达到最大训练回合数,则退出训练并输出训练优化过后的调度计划opt-plan.
Q-learning算法求解高铁动态调度问题的伪代码如表3所示.
表3 Q-learning求解高铁动态调度Table 3 Q-learning solves the problem of high-speed railway dynamic scheduling
为验证所搭建仿真环境的合理性以及Q-learning算法解决高铁动态调度问题的有效性,利用仿真实例进行验证.该实例采用Python3.6编写,运行环境为Windows10 64位操作系统,处理器为Intel i7-8系列,16 GB内存.
进行验证的例子采用三车四站三区间的情形,其中21个资源构造如图7所示.
图7 仿真环境设置Fig.7 Simulation environment
规定列车速度为300 km/h,车站1到车站2距离50 km,分为5个闭塞区间,即通过每个闭塞区间需2 min;车站2到车站3距离30 km,分为3个闭塞区间,即通过每个闭塞区间需2 min;车站3到车站4距离10 km,分为2 个闭塞区间,即通过每个闭塞区间需1 min.规定第3.2节数学模型中的到发时间间隔约束=1 min,各区间最小运行时间为=2 min,并规定经停站最小作业时间
列车图定计划时刻表如表4所示.
表4 计划时刻表Table 4 Table of scheduled times
突发情况设定为=6 min.此时,时间跨度Tspan=11:34-11:03=31min.阈值可设定为Tthreshold=Tspan++10=47 min,即如果智能体不能在47 min内到达终点状态,就给予其一惩罚.
在第5.1节所示的仿真环境情形下,对智能体进行大量训练,最终经实验确定超参数α=0.1,γ=0.9,max_episodes=2300,训练结果如图8所示.
图8 训练结果Fig.8 The results of training
在=6 min的情况下,求得目标函数的最优解为42 min,即当G1列车在始发站晚点6 min的情况下,对3辆列车在4个站造成的总晚点时间为42 min,调整后的调度计划如图9所示.
图9 调整后的运行图Fig.9 The adjusted schedule
检查校验后,该调度计划满足数学模型中的所有约束,发现G2车在各站均按计划到站、离站;G1车因为扰动延误在G2发车后发车,在各站的到站、离站均晚点6 min,所以G1车的总晚点时间为36 min;G3车因避让晚点的G1 车,在各站的到站、离站均晚点1 min,所以G3车的总晚点时间为6 min,最终目标函数的解为42 min.从图9中也可以发现G2,G3列车在站内调整计划占用的股道资源以满足资源占用唯一性约束.
图9对应调整后的时刻表如表5所示.
训练结束后,Q-table中各值(取整之后)如图10所示.
图10 Q-table结果Fig.10 The Q-table
改变扰动延误时间及扰动作用点进行多种仿真.
1) 当=2 min,Tthreshold=31+2+10=43 min时,最终目标函数解为12 min,训练结果与动态调度计划如图11所示.
图11 =2min仿真结果Fig.11 The simulation resultsof=2 min
2) 当=3 min,Tthreshold=31+3+10=44 min时,最终目标函数解为24 min,训练结果与动态调度计划如图12所示.
图12 =3 min仿真结果Fig.12 The simulation results of =3 min
为更好地验证Q-learning算法在求解较大规模场景时的有效性,给出以下的验证场景如图13所示.同样,规定列车速度为300 km/h,根据图中数据计算得车站1,2之间每个闭塞区间的运行时间为2 min,车站2,3之间每个闭塞区间的运行时间为2 min,车站3,4之间每个闭塞区间的运行时间为1 min,车站4,5之间每个闭塞区间的运行时间为2 min,车站5,6之间每个闭塞区间的运行时间为2 min,并且规定==1 min,=3 min.
图13 复杂场景实例Fig.13 The complex scenario
各列车计划时刻表如表6所示.在该仿真场景下,对不同的晚点时间、晚点车站及晚点列车做了多种仿真,最终的调度结果如图14所示.
表6 计划时刻表Table 6 Table of scheduled times
图14 复杂场景仿真Fig.14 The complex scenario simulation
对于上述6种仿真情况,分别将Q-learning方法与人工方法(Manual)的调度结果进行对比,如表7所示.其中,人工方法采取的是晚点列车整体平移,不产生越行的方式进行调整.
表7 对比结果Table 7 The comparison result
其中,改进率ψ的计算公式如式(20).当ψ >0时,说明调度结果通过Q-learning方法得到了改进;反之,ψ <0时,说明Q-learning方法调度效果不如人工方法.
经过多种仿真实例,可发现本文建立的数学模型及通过该模型所搭建的环境是满足约束、符合算法运行条件的.在此基础上,运用Q-learning算法对该模型进行了求解并同基本的人工调度方法进行了对比.结果显示:在合适的超参数、训练次数的条件下,经过可接受的计算时间,可以找到模型的满意解,实现延误影响的最小化,并对人工调度解有很大的提高.
本文以高速铁路调度问题为研究对象,建立了相应的数学模型,在模型基础上又设计了合适的与智能体交互的仿真环境,并利用强化学习中的经典Q-learning算法对不同情境下的实例进行了求解.其最终结果表明,Q-learning算法要求的交互环境的设计是合理的,Q-learning算法也适合求解高铁调度决策类型的问题.当然,作为初步工作,本文只是对单线单向线路进行了仿真,还有许多其他复杂的因素需要考虑,如线路成网、移动闭塞区间等较为复杂、细化的因素,将在之后的工作中继续改进.