一种列车运行图编制与优化方法、装置、设备及存储介质

1.本技术实施例涉及高速铁路调度技术领域，具体而言，涉及一种列车运行图编制与优化方法、装置、设备及存储介质。


背景技术：

2.近年来，为了满足社会经济发展的需要和缓解旅客出行需求的压力，铁路运输业的发展越来越迅速。列车运行图将铁路系统的各种运输组织活动连接在一起，在行车组织过程中，发挥基础的领导作用。高速铁路作为铁路运输的重要组成部分，同样需要严格按图行车，合理的编织并进一步优化高速铁路列车运行图，对于保证高铁动车组的安全运营，满足旅客的出行需求，提高铁路运输和营收能力有着重要作用，因此高铁列车运行图的编制与优化问题是许多专家学者重点关注的问题。现有的列车运行图相关技术中，第一种方法是使用整数规划或其他非线性规划方法进行精确求解，如：李皓基于时空网络构建列车运行图的整数规划模型，将大规模组合优化问题转化为最短路径问题，并设计了拉格朗日松弛算法求解原问题；第二种方法是使用启发式算法获得近似最优解，如：任向达建立高铁列车运行图编制混合整数规划模型，并设计遗传算法对模型进行求解。
3.现有的列车运行图编制与优化方法中，精确求解方法的计算量巨大，难以在实际线路上应用；启发式方法容易陷入局部最优解，求解时间较长，当列车运行时间或车站客流量出现波动时需要重新编图，同时，对专家知识和既有经验的需求程度较高，编制出的运行图质量很大程度上取决于专家经验与所建立的数学模型的准确性。强化学习给出了一种解决精确求解方法和启发式算法局限性的新思路，但还没有广泛应用于铁路调度领域，相关研究均集中在重调度和列车运行图动态调整领域，在高铁列车运行图编制与优化问题上应用强化学习方法的研究较少，且不能适用于我国高速铁路实际情况，无法快速准确编制并优化列车运行图。


技术实现要素：

4.本技术实施例提供一种列车运行图编制与优化方法、装置、设备及存储介质，旨在快速准确的编制并优化列车运行图。
5.本技术实施例第一方面提供一种列车运行图编制与优化方法，所述方法包括：
6.将列车的运行环境信息输入待训练的列车运行图编制模型中，所述运行环境信息包括列车信息以及车站信息；
7.根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型；
8.通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图。
9.本技术实施例第二方面提供一种列车运行图编制与优化装置，所述装置包括：
10.运行环境信息接收模块，用于将列车的运行环境信息输入待训练的列车运行图编
制模型中，所述运行环境信息包括列车信息以及车站信息；
11.模型训练模块，用于根据所述运行环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型；
12.列车运行图编制优化模块，用于通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图。
13.本技术实施例第三方面提供一种可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时，实现如本技术第一方面所述的方法中的步骤。
14.本技术实施例第四方面提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时，实现本技术第一方面所述的方法的步骤。
15.使用本技术提出的列车运行图编制优化方法，建立了一个基于离散事件动态系统的列车运行环境，使用基于马尔可夫决策过程模型的q学习算法在该列车运行环境中进行多轮训练，在每轮训练中，获得列车运行环境的参数并选择执行的动作，执行该动作后，更新该状态-动作对的q值，考虑到了在列车运行中，两个相邻的决策时刻之间的关联性很小，引入了列车相邻状态以及车站相邻状态，对传统的q学习方法进行了改进，符合列车运行的实际情况，更好的对列车运行图编制优化模型进行了训练。并且根据改进的贪婪搜索策略进行状态选择，提高了算法的搜索效率和搜索深度。
附图说明
16.为了更清楚地说明本技术实施例的技术方案，下面将对本技术实施例的描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
17.图1是本技术一实施例提出的状态转移过程示意图；
18.图2是本技术一实施例提出的列车运行图编制与优化方法的流程图；
19.图3是本技术一实施例提出的场景一列车运行图编制优化的仿真结果图；
20.图4是本技术一实施例提出的场景一应用q学习算法编制得到的列车运行图；
21.图5是本技术一实施例提出的场景二中列车车站总等待时间的变化趋势图；
22.图6是本技术一实施例提出的场景二中应用q学习算法编制得到的列车运行图；
23.图7是本技术一实施例提出的场景三中列车车站总等待时间的变化趋势图；
24.图8是本技术一实施例提出的场景三中应用q学习算法编制得到的列车运行图；
25.图9是本技术一实施例提出的列车运行图编制与优化装置的示意图。
具体实施方式
26.下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本技术一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本技术保护的范围。
27.本技术实施例中，在进行列车运行图编制之前，需要建立一个列车运行环境，以该
环境为基础设计列车运行图编制的马尔可夫决策过程模型，进而使用q学习算法，得到最优的列车运行图编制优化策略，进而编制出符合实际运行情况的列车运行图。
28.在接收列车运行环境参数之前，执行的步骤为：
29.s11：构建基于离散事件动态系统的列车运行环境，所述列车运行环境用于限制列车运行时需要满足的约束条件与状态。
30.本实施例中，列车运行环境就是列车运行时的约束条件与列车状态的集合，列车在符合列车运行环境的条件下进行运行，才可以实现正常的运行，本技术构建了基于离散事件动态系统的列车运行环境，将多辆列车在各个车站的停车以及发车视为离散事件，对这些离散事件进行动态的处理，为列车运行图的编制与优化提供环境条件。
31.本实施例中，对构建的列车运行环境做出如下假设：区间为双向线路，下行列车和上行列车分别在各自方向的路线上运行；线路上行驶的列车为两种不同速度等级的列车；高等级列车的时速大于低等级列车的时速；同等级列车在各个行车区间的纯运行时间相同；且列车在区间按照最高时速运行，速度均匀；允许不同速度等级的列车发生越行，高速度等级的列车可以在站内越行低速度等级的列车；允许列车延长在各站的停车时间；保证列车运行安全的各类时间间隔一直，包括上下行列车数量、速度等级、始发站的列车发车顺序等。基于以上假设，设置列车运行环境的约束条件以及列车的状态转换过程。
32.构建基于离散事件动态系统的列车运行环境的具体步骤为：
33.s11-1：设置列车运行环境的约束条件。
34.本实施例中，设置列车运行环境的约束条件的具体步骤为：
35.s11-1-1：设置列车在行车区间的运行时间约束，所述运行时间约束为列车的实际运行时间等于行车区间的纯运行时间。
36.本实施例中，列车在行车区间运行的时间需要满足列车在行车区间的运行时间约束，列车在区间运行速度均匀，且不考虑启动、加速、减速、停车等影响因素，此时列车的实际运行时间等于区间纯运行时间，表达式如下：
37.a
i,k+1-d
i,k
＝r
i,(k,k+1)
38.其中，a
i,k
表示列车i到达车站k的时间，d
i,k
表示列车i离开车站k的时间，r
i,(k,k+1)
表示列车i在区间(k,k+1)的纯运行时间。
39.s11-1-2：设置列车在车站的停留时间约束，所述停留时间约束为列车在车站的停留时间等于列车到达车站与离开车站的时间间隔，且列车在车站的停留时间不小于列车在车站的停留时间和等待发车时间之和。
40.本实施例中，列车在车站内的停留时间需要满足停留时间约束，列车在车站的停留时间是指列车到达该车站与离开该车站之间的时间间隔，由停站时间和等待发车时间两部分构成，停站时间为列车上下旅客作业，停在车站内的时间，等待发车时间为列车作业完成，等待允许发车的时间，表达式如下：
41.d
i,k-a
i,k
＝p
i,k
+w
i,k
≥p
i,k
42.其中，w
i,k
表示列车i在车站k的等待发车时间，p
i,k
表示列车i在车站k的停站时间。
43.s11-1-3：设置同向列车车站到达间隔时间约束，所述同向列车车站到达间隔时间约束为同向列车到达车站的时间间隔不小于预设同向列车最小到达间隔时间。
44.本实施例中，设同向列车到达车站k时，前行列车i和后行列车j之间，应该满足到
达时间间隔约束，以保证同向列车的安全运行，表达式如下：
[0045][0046]
其中，表示车站k同向到达的两列列车之间的最小间隔时间，即到达间隔时间。
[0047]
s11-1-4：设置同向列车车站发车间隔时间约束，所述同向列车车站发车间隔时间约束为同向出发的两列列车的发车时间间隔不小于预设同向列车最小出发间隔时间。
[0048]
本实施例中，设同向列车离开车站k，前行列车i和后行列车j之间应满足同向列车车站发车间隔时间约束，以保证同向列车之间的安全运行，表达式如下：
[0049][0050]
其中，表示车站k同向出发的两列列车之间的最小间隔时间，即发车间隔时间。
[0051]
s11-1-5：设置同向列车区间追踪间隔时间约束，所述同向列车区间追踪间隔时间约束为前行列车和后行列车离开当前车站的时间间隔和到达下一车站的时间间隔均不小于预设列车区间追踪间隔时间。
[0052]
本实施例中，设在区间(k,k+1)同向运行的两列列车，由于运行速度均匀且固定，因此只需要保证前行列车i和后行列车j离开车站k的时间间隔和到达车站k+1的时间间隔不小于列车区间追踪间隔时间即可，表达式如下：
[0053][0054][0055]
其中，表示区间(k,k+1)上追踪运行的两列列车之间的最小间隔时间，即列车区间追踪间隔时间。
[0056]
s11-1-6：设置车站能力约束，所述车站能力约束为车站在同一时刻内容纳列车的实际数量不大于该车站内的股道数量。
[0057]
本实施例中，为了保证车站内的列车数量不超过车站的最大容量，车站k在时刻t容纳列车的实际数量不应该大于车站内股道数量。表达式如下：
[0058][0059]
其中，表示在时刻t在车站k的列车数量，表示车站k的股道数量。
[0060]
s11-2：设置列车状态和车站状态。
[0061]
本实施例中，在列车状态转换的离散事件动态系统中，系统的状态由所有列车和车站的状态进行表征，在构建列车运行环境时，需要设置列车状态和车站状态，具体步骤包括：
[0062]
s11-2-1：将列车在运行中的不同状态分别设置为等待发车状态、区间运行状态和停车状态。
[0063]
s11-2-2：将车站的状态分别设置为允许发车状态和不允许发车状态。
[0064]
本实施例中，列车的状态包括：等待发车状态(列车在车站等待发车)、区间运行状态(列车在两个车站之间运行)、停车状态(列车在车站内停车)。
[0065]
车站的状态包括：允许发车(车站内的列车可以从该车站出发)、不允许发车(未满足发车间隔时间)。列车和车站的状态是动态转换的，车站的状态改变可以在列车状态转换
中得到体现。
[0066]
示例地，使用来表示列车i在t时刻的状态，分别表示上述三个列车状态。具体转换过程为：当列车的当前状态为3时，其下一个状态将变为1，这表示该列车在该车站已完成停站作业并准备离开车站。当该车站状态为允许发车时，允许该列车将其状态从1转换为2，当列车状态转换为2时，该列车必须立即离开当前车站；当该车站状态为不允许发车时，该列车的状态仍然保持为1，继续在车站等待发车，此时列车的等待时间会增加。
[0067]
参考图1，图1是本技术一实施例提出的状态转移过程示意图，如图1所示，节点si表示列车i到达车站k，节点si'表示列车i上下旅客作业结束，节点s
i”表示列车i与车站k发出的上一列车之间的区间追踪间隔时间约束和到达下一车站k+1时的到达间隔时间约束均满足，节点s
i”'表示车站k发车间隔时间约束满足，允许列车发车。通常，节点si和节点si'之间的操作是强制性的，而在节点s
i”和节点s
i”'之间发生的操作则密切依赖于当前系统的情况。
[0068]
λ
it
表示在当前时刻t，列车i在当前状态的剩余时间。若列车状态为在车站k等待向区间(k,k+1)发车，则表达式如下：
[0069][0070][0071]
t
max
＝max{t1,t2,0}
[0072][0073]
其中，m表示该车站向区间(k,k+1)发出的上一列列车编号，t1计算得到列车i在满足发车间隔时间约束条件下需要在车站k等待的总时间，t2计算得到列车i在与列车m满足追踪间隔时间和到达间隔时间约束条件下需要在车站k等待的总时间。
[0074]
若列车状态为在区间(k,k+1)匀速运行，则表达式如下：
[0075][0076]
若列车状态为在车站k停车，则表达式如下：
[0077][0078]
具体来说，在状态2
→
3和状态3
→
1的转换过程中，由于列车的区间运行时间以及停站时间已经给定，所以状态转换是必须的、不需要判断的。然而，在状态1
→
2的转换中，由于两列列车可能在车站发生越行操作，尽管前一列车已经满足发车条件，但仍保持状态1，等待后一列车发车离站后再改变状态，因此该状态转换过程是列车运行图编制模型中的关键所在，是应用强化学习得到优化后的调度策略的体现。
[0079]
s12：构建所述待训练的列车运行图编制优化模型，所述列车运行图编制优化模型在满足所述列车运行环境的条件下进行列车运行图编制与优化。
[0080]
本实施例中，基于构建好的列车运行环境，建立了待训练的列车运行图编制优化模型，该模型实质上是一种马尔可夫决策过程模型，用于编制与优化列车运行图。该马尔可夫决策过程模型包括四个组成部分：状态变量、动作变量、状态转移概率、奖励值函数。
[0081]
构建所述待训练的列车运行图编制优化模型：
[0082]
s12-1：设置所述列车运行图编制优化模型的状态变量，所述状态变量包括当前列车以及相邻列车的速度等级、当前列车所处车站和相邻区间的占用情况、不同速度等级列车区间运行时间差值、当前时刻距离当前车站发出同方向下一列车的时间差值。
[0083]
本实施例中，假设当前决策时刻t允许在车站k的列车i发车，且列车i的运行方向为下行方向。列车具有两种速度等级，当前列车所处车站同向发出的上一列车与当前列车的速度等级是否相同，会影响到列车运行图编制的合理性；而当前列车与车站将要同向发出的下一列车之间的速度等级关系，将影响到后续列车在该车站的等待时间。当前列车i的速度等级level(i)，车站k发出的上一列下行方向列车m的速度等级level(m)，车站k将要发出的下一列下行方向列车j的速度等级level(j)。level(
·
)的取值与线路上开行列车的速度等级有关。
[0084]
本实施例中，车站站内股道被列车占用的程度以及相邻两个区间开向该车站的两条线路上列车的拥堵的程度，对该车站一段时间后是否会发生容量超限的情况有较大的影响。车站k站内股道被列车占用的程度degree(k)，区间(k-1,k)开向车站k的下行线路上列车“拥堵”的程度degree(k-1,k)，区间(k,k+1)开向车站k的上行线路上列车“拥堵”的程度degree(k+1,k)。degree(
·
)的取值有{0,1,2,
…
,d-1}，表达式如下：
[0085][0086][0087]
其中，表示该线路最多可以容纳的列车数目，表示该线路当前时刻的列车数目。
[0088]
本实施例中，不同速度等级列车区间运行时间差值为：区间(k,k+1)中两种速度等级列车的运行时间差值，将该差值设为d-time(k,i)。
[0089]
本实施例中，距离该车站发出同方向下一列车的时间差值的设置，确保了高等级列车的越行机会不会被错过，该差值在调度策略中是一个重点考虑的因素。当前时刻t距离车站k发出列车j的时间差值remain(j)，根据列车j当前所处状态，给出表达式如下：
[0090][0091][0092]
因此，本实施例中，当前决策时刻t的状态变量s
t
为：
[0093]st
＝[level(i),level(m),level(j),degree(k),degree(k-1,k),degree(k,k+1),d-time(k,i),remain(j)]
[0094]
s12-2：设置所述列车运行图编制优化模型的动作变量，所述动作变量包括发车与不发车。
[0095]
本实施例中，动作变量指列车在列车运行环境中执行的动作，列车可选择的动作为发车状态与不发车状态。
[0096]
设发车状态为a0，表示当前时刻列车发车，从车站等待发车状态转换为区间运行状态。
[0097]
设不发车状态为a1，表示当前时刻列车不发车，仍然保持车站等待发车状态。
[0098]
s12-5：确定所述q学习算法为训练所述列车运行图编制优化模型的训练算法。
[0099]
本实施例中，在进行列车运行图编制优化时，状态转移概率是未知的，此时综合考虑求解问题的规模和状态变量的构成，选择q学习算法，对列车运行图编制优化模型进行训练，进而实现对列车运行图的编制与优化。
[0100]
s12-3：设置所述列车运行图编制优化模型的奖励值函数。
[0101]
本实施例中，q学习算法的核心原则是：在一次训练中，通过状态-动作对的生成顺序对奖励值进行反向传播(通常在训练结束时)。在列车运行图编制与优化的问题中，一次训练可能非常长，同时生成多个列车的状态-动作，只是在训练结束时生成奖励值会导致出现的问题有：优化目标是所有列车等待时间的总和，某一列车在某一车站的等待时间不同会给其他列车的等待时间造成影响，不能明确每次动作决策的奖励分配；当列停站时间或者区间运行时间产生波动时，列车在同样的动作选择序列下得到的列车总等待时间是不同的；当训练过程过长时，奖励值的反向传播效果很差。
[0102]
为了解决上述三个问题，针对每次决策动作后会出现的三种情况，对即时奖励值进行了如下定义：
[0103]
若当前时刻的动作选择导致在该车站可以进行下一次决策前车站容量超限，则返回一个负奖励值，该负奖励值远远小于正常的奖励值。示例地，可将该负奖励值设置为-500。
[0104]
若当前时刻的动作选择并不会导致车站容量超限，且该决策不是该车站的最后一次动作决策，则返回的即时奖励值表达如下：
[0105]
r(π(a
t
|s
t
)＝-(w
i,k
+w
j,k
)
[0106]
其中，r(π(a
t
|s
t
)表示奖励值，w
i,k
表示当前列车i在车站k的等待发车时间，w
j,k
表示车站k发出的下一列车j(运行方向与列车i相同)的等待发车时间。
[0107]
若当前时刻的动作选择并不会导致车站容量超限，且该决策是该车站的最后一次动作决策(发出最后一列列车)，则返回的即时奖励值表达式如下：
[0108][0109]wi,k
＝t-(a
i,k
+p
i,k
)
[0110]
其中，表示车站k的最早被占用时间；β是一个很小的常数，表示在调度策略的训练过程中考虑车站被占用的时间，从而在确保实现最小化列车总等待时间的优化目标的前提下，尽可能地减少列车运行线占用运行图的时间。
[0111]
s12-4：确定所述列车运行图编制优化模型的优化目标以及目标函数，所述优化目标为列车的总旅行时间最短。
[0112]
本实施例中，列车运行图编制马尔可夫决策过程模型的优化目标为：列车总旅行时间最短。单列车i的旅行时间由列车的区间运行时间、车站停站时间和车站等待发车时间三部分组成。由于列车区间运行时间和车站停车时间是给定的，因此最小化列车总旅行时间的优化目标可以等效转化为最小化列车车站总等待时间，表达式如下：
[0113][0114]
其中，c表示模型中所有车站编号的集合，c＝{1,2,
…
,k,k+1,
…
,m}，m为车站总数；t表示模型中所有列车编号的集合，t＝{1,
…
,i,
…
,j,
…
,n}，n为列车总数。
[0115]
在对高铁运行图的列车车站总等待时间进行优化的同时，也需要关注如何提高运行图的运输能力。在确保实现优化目标的前提下，考虑尽可能减少列车运行线占用运行图时间，即各车站被占用的时间之和，表达式如下：
[0116][0117][0118][0119]
其中，分别表示车站k的最早和最晚接车时间，分别表示车站k的最早和最晚发车时间，分别表示车站k的最早和最晚被占用时间。
[0120]
本实施例中，构建了基于马尔可夫决策过程的列车运行图编制模型，明确了优化目标为最小化列车车站总等待时间，同时在实现该优化目标的前提下，考虑尽可能减少列车运行线占用运行图时间，将连续的列车运行过程描述为离散的列车状态转移，提出了基于离散事件动态系统的列车运行环境模型。
[0121]
s12-5：确定q学习算法为训练所述列车运行图编制优化模型的训练算法。
[0122]
本实施例中，在进行列车运行图编制优化时，状态转移概率是未知的，此时综合考虑求解问题的规模和状态变量的构成，选择q学习算法，对列车运行图编制优化模型进行训练，进而实现对列车运行图的编制与优化。
[0123]
参考图2，图2是本技术一实施例提出的列车运行图编制与优化方法的流程图。如图2所示，该方法包括以下步骤：
[0124]
s301：将列车的运行环境信息输入待训练的列车运行图编制模型中，所述运行环境信息包括列车信息以及车站信息。
[0125]
本实施例中，列车运行的环境信息包括了列车信息以及车站信息，列车信息包括了列车编号，列车速度等级，列车运行方向，列车在各个车站的停车时间等，车站信息包括了车站位置，站内股道数，区间运行时间等。
[0126]
s302:根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型。
[0127]
本实施例中，根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型的具体步骤为：
[0128]
s302-1：当训练开始时，根据所述运行环境信息，初始化列车的运行环境，同时随机改变列车的区间运行时间和车站停站时间，得到列车运行环境的初始参数。
[0129]
本实施例中，需要对整个列车运行图编制优化模型进行多轮训练，在每一轮训练开始时，首先需要初始化列车的运行环境。
[0130]
本实施例中，初始化运行环境时，对于列车信息，需要重置列车位置、状态、在当前状态剩余时间等信息，除了第一轮训练之外，还需要重置最后观察到的状态-动作对。对于
车站信息，需要重置车站内列车数量、已发出列车数量、是否满足发车时间间隔约束等信息，除了第一轮训练之外，还需要重置最后观察到的状态-动作对。
[0131]
本实施例中，使用q学习算法对模型进行训练，需要设置训练的相关初始参数。
[0132]
示例地，q表的初始值设置为0，学习效率α＝0.05，折扣因子γ＝0.9，车站被占用的时间考虑权重β＝0.02，列车相邻状态权重τ＝0.5，同时还要预设训练次数。
[0133]
本实施例中，在每一轮次训练开始时，随机改变列车的区间运行时间和停站时间，这样可以增加整个模型的泛化性，使模型在接收到不同数据时，依然可以很好的编制和优化高铁运行图。
[0134]
示例地，第一轮训练中，1号列车的(1,2)区间运行时间为20分钟，在车站1的停站时间为5分钟，在第二轮训练中，将1号列车的(1,2)区间运行时间调整为21分钟，在车站1的停站时间修改为6分钟。
[0135]
s302-2：根据所述初始参数，获得列车运行的初始状态。
[0136]
本实施例中，列车运行环境的初始参数就是列车运行的状态变量的初始值，列车运行的状态变量就是在训练中，每次决策时，列车所处的状态。
[0137]
本实施例中，列车运行的初始状态包括了当前列车及相邻列车的速度等级，所述车站和相邻区间的占用情况，不同速度等级列车区间运行时间差值，当前时刻距离该车站发出同方向下一列车的时间差值。
[0138]
示例地，将当前时刻列车运行的初始状态记为s
t
，设当前时刻t＝0，当前时刻的动作反转标志位置0。
[0139]
s302-3：根据所述初始状态，通过贪婪搜索策略，选择当前决策时刻采取的动作，得到当前决策时刻对应的状态-动作对。
[0140]
本实施例中，贪婪搜索策略即ε-贪婪搜索策略，该搜索策略是设定一个贪婪值ε，在每次决策时抽取一个0-1之间的随机数，当随机数小于贪婪值时，则选择当前状态s
t
对应的q值最大的动作，当随机数小于贪婪值时，就随机选择动作，状态-动作对由当前决策时刻的状态和选择的动作组成。
[0141]
示例地，在决策时刻t＝0时的状态动作对记为(s
t
,a
t
)，则表示列车在当前t时刻的状态s
t
下采取动作a
t
。
[0142]
通常情况下，贪婪值ε的取值是一个(0,1)区间中的固定值，但是该取值方法会降低算法的收敛速度，导致模型的训练速度降低。本实施例中根据当前时刻状态s
t
下对动作a0和a1的选择次数，改进了ε的取值，使用了实时更新的ε(s
t
)代替固定不变的ε，表示在状态s
t
下选择最优动作的概率，表达式如下：
[0143][0144]
其中，n(ai|s
t
)表示在状态s
t
下选择动作ai的次数，max{n(a0|s
t
),n(a1|s
t
)}表示在状态s
t
下对所有动作选择次数的最大值。
[0145]
本实施例中，随着训练次数的增加，各种动作选择策略得到了充分学习，最优策略得以凸显，状态s
t
下ε(s
t
)的值不断减小，智能体趋向选择最优动作。这样既能保证搜索深度，又能提高搜索效率。
[0146]
s302-4：执行所述动作，得到所述动作对应的奖励值以及后续状态，并使所述q学
习算法，根据q值更新公式更新所述当前列车对应的状态-动作对的q值。
[0147]
本实施例中，执行上一步骤中选择的动作，系统会返回一个奖励值，后续状态指执行完列车的动作之后，在下一决策时刻之前的列车运行环境的状态，后续状态记为s
t+1
。
[0148]
本实施例中，使用q学习算法，在每执行一个动作之后，都会使用q值更新公式，计算该状态-动作对的q值，状态-动作对所对应的q值越大，说明该动作对优化目标起到的有益效果越大。在一轮训练中会进行多次决策，每次决策并执行动作之后，系统会根据q值更新公式计算并更新状态-动作对的q值。此时系统会将该状态-动作对的q值在q值表中进行更新。
[0149]
本实施例中，在列车运行图的编制与优化问题中，假设当前时刻对车站k的列车i是否发车做决策，下一时刻可能是对车站p的列车q是否发车做决策，两个相邻的决策时刻之间关联性很小，因此对传统的q值更新方法进行改进，将maxq(s
t+1
,a)替换成q
next
(s
t
,a
t
)，表达式如下：
[0150]
q(s
t
,a
t
)
←
q(s
t
,a
t
)+α[r(π(a
t
|s
t
))+γq
next
(s
t
,a
t
)-q(s
t
,a
t
)]
[0151]
其中，每一列车存储最近一次决策的状态-动作对(s,a)，由同一列车观察到的下一个状态定义为列车相邻状态s'；每一个车站存储最近一次决策的状态-动作对(s,a)，由同一车站观察到的下一个状态定义为车站的相邻状态s”。每一个状态-动作对(s,a)在整个q学习训练过程中都可以有很多个“列车相邻状态”和“车站相邻状态”，假设在当前q值更新时刻t，(s,a)有n
t
个s'和m
t
个s”，则q
next
(s
t
,a
t
)的表达式如下：
[0152][0153]
其中，τ表示“列车相邻状态”在(s,a)的两种相邻状态中所占权重，1-τ表示“车站相邻状态”所占的比重。
[0154]
s302-5：根据所述奖励值以及后续状态，确定当前车站是否满足预设的车站容量约束，当所述当前车站不满足所述预设的车站容量约束时，在当前状态下再次对还未选择过的动作进行选择，并执行选择的动作。
[0155]
本实施例中，当执行动作后，返回的奖励值是一个非常小的负值时，说明该动作执行之后，车站内的列车数量超过了站内股道数量，不满足预设的车站容量约束。当返回的奖励值为正常奖励值时，说明执行该动作后，车站内的列车数量没有超过站内股道数量，满足预设的车站容量约束。
[0156]
本实施例中，当返回的奖励值时一个非常小的负值时，则对后续状态s
t+1
进行标识，标识为“reverse_action”，根据该后续状态标识，可以得到该后续状态中，车站内的列车数量超过车站内的股道数量。
[0157]
示例地，可以设置一个动作反转标志位，用于标记该状态下选择动作的次数。当前状态动作反转标志位初始值为0，当模型在当前决策时刻做出的动作选择导致在该车站的下一决策时刻前车站内的列车数量超过站内股道数量，则动作反转标志位置1，返回当前决策时刻，直接选择另一个动作。若重新选择的动作同样会导致车站容量超限，则说明本次训练失败，列车并未到达终点，动作反转标志位置2。
[0158]
s302-6：当所述当前车站满足所述车站容量约束或所述动作为当前决策时刻选择
的最后一个动作时，将所述当前列车的状态作为所述当前列车在上一决策时刻得到的状态-动作对的列车相邻状态和所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态。
[0159]
本实施例中，当前车站满足车站容量约束时，当前的动作为可行动作。当该动作为当前决策时刻选择的最后一个动作时，说明当前决策时刻可以选择的所有动作都已经被选择过，并没有更多的动作可供选择。
[0160]
本实施例中，在每一轮次决策完毕后，都会存储该轮次决策最后观察到的列车状态-动作对和车站状态-动作对，在每一轮次进行动作决策以及执行之后，若当前车站满足车站容量约束或者该动作为当前决策时选择的最后一个动作时，得到当前列车在上一次决策时刻得到的状态-动作对(s',a)，当前车站在上一次决策时刻得到的状态-动作对为(s”,a)。
[0161]
同时，将当前决策时刻的列车状态作为上一决策时刻得到的状态-动作对的列车相邻状态，将当前决策时刻的车站状态作为上一决策时刻得到的状态-动作对的车站相邻状态。
[0162]
示例地，当前决策时刻可以选择的所有动作都已经被选择过，即为当前状态s
t
对应的所有动作选择得到的后续状态均为“reverse_action”，此时动作反转标志位置2。
[0163]
s302-7：更新对应于所述当前列车在上一决策时刻得到的状态-动作对的列车相邻状态数量和平均最大q值，以及对应于所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态数量和平均最大q值，所述相邻状态数量和平均最大q值用于后续轮次决策中的q值更新。
[0164]
本实施例中，在当前状态下，可以在两个动作中进行选择，即发车或者不发车，每个动作对应一个q值，所有动作对应的q值均记录在q值表中，选取最大的q值并在q值表中分别与当前车站的状态-动作对和当前列车的状态-动作对所对应的最大平均q值进行平均。
[0165]
本实施例中，当前列车的相邻状态即该列车在下一次决策时的状态，当前车站的相邻状态即该车站在下一次决策时的状态。
[0166]
本实施例中，在列车相邻状态数量和平均最大q值以及车站相邻状态数量和平均最大q值更新完成后，更新所述当前列车的状态-动作对和所述当前车站的状态-动作对为当前所述状态-动作对。
[0167]
示例地，当前决策时刻的状态为s4，是当前列车在上一决策时刻得到的状态-动作对(s3,a3)的相邻状态，表示当前列车的上一决策是在状态s3下采取了动作a3，同时也是当前车站在上一决策时刻得到的状态-动作对(s2,a2)的相邻状态，表示当前车站的上一决策是在状态s2下采取了动作a2。当前列车在上一决策时刻得到的状态-动作对为(s3,a3)时，更新后的平均最大q值为当前状态s4下得到的最大q值与该状态-动作对所记录的最大q值的平均值；同样，当前车站在上一决策时刻得到的状态-动作对(s2,a2)时，更新后的平均最大q值为当前状态s4下得到的最大q值与该状态-动作对所记录的最大q值的平均值。
[0168]
s302-8：将所述当前列车对应的状态-动作对作为当前决策时刻得到的列车状态-动作对和车站状态-动作对进行存储。
[0169]
本实施例中，在更新完当前列车在上一决策时刻得到的状态-动作对的相邻状态数量和平均最大q值以及当前车站在上一决策时刻得到的状态-动作对的相邻状态数量和
平均最大q值之后，将当前列车对应的状态-动作对，即当前列车在当前决策时刻得到状态-动作对作为当前决策时刻得到的列车状态-动作对和车站状态-动作对。
[0170]
示例地，当前决策时刻得到的状态-动作对为(s4,a4)在最大平均q值更新完成后，更新当前列车的状态-动作对和当前车站的状态-动作对为(s4,a4)，将该状态-动作对作为当前决策时刻得到的列车状态-动作对和车站状态-动作对进行存储。
[0171]
s302-9：重复执行上述动作决策、动作执行、获得状态-动作对、更新相邻状态数量和平均最大q值、更新当前状态-动作对步骤，当全部列车到达终点站或当前决策时刻可选择的所有动作都已经执完毕时，结束本轮训练。
[0172]
本实施例中，在一轮训练中，在当前决策时刻t下完成列车状态-动作对和车站状态-动作对更新之后，更新当前状态，令s
t
＝s
t+1
，开始进行下一次决策，执行选择的动作并同时更新状态-动作对的q值，以及更新相邻状态数量和平均最大q值。若全部列车到达终点站或当前决策时刻可选择的所有动作都已经执行完毕时，结束本次训练。
[0173]
本实施例中，通过查看动作反转标志位，可以知道所有动作是否都已经执行过，若动作反转标志位为2时，代表所有动作都已经执行完毕。
[0174]
s302-10：重复进行多轮训练，当训练次数达到预设训练次数时，结束训练，得到列车运行图编制优化模型。
[0175]
本实施例中，会进行多轮训练，在每轮训练开始时，随机修改列车的区间运行时间与停站时间，使用修改后的参数对整个模型进行训练，达到预设的训练次数后，结束训练，训练好的模型即列车运行图编制优化模型，训练的目标是最小化列车车站总等待时间。训练次数可以根据实际情况自行设置。
[0176]
在本技术另一个实施例中，通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图，包括：
[0177]
s41：将所述列车运行环境信息输入所述列车运行图编制优化模型中；
[0178]
s42：根据所述列车运行环境信息，通过所述列车运行图编制优化模型定制对应的列车运行图编制优化策略；
[0179]
s43：根据所述列车运行图编制优化策略，输出所述列车运行图。
[0180]
本实施例中，在得到训练好的列车运行图编制优化模型之后，训练好的列车运行图编制优化模型会根据输入的列车运行环境参数，通过训练出的智能体制定对应的列车运行图编制优化策略，以最小化每辆列车的停站时间为目标，编制列车运行图，得到列车运行图。
[0181]
示例地，以京沪高铁线路作为例，选取京沪高铁线路从北京南至泰安站一共7个车站，车站的基本参数包括：站名、站内股道数量和区间运行时间(高等级车速：350km/h，低车速等级：250km/h)，各个车站的发车间隔时间均设置为5min，到达间隔时间均设置为4min，各区间追踪时间均设置为4min。如表1所示，表1是京沪高铁车站基本参数。
[0182][0183]
表1
[0184]
选取上行和下行方向各8列列车，总计16列列车，列车基本参数包括：列车速度等级和运行方向，如表2所示，表2是本技术一实施例提出的列车基本参数表，其中，速度等级1表示高等级列车，0表示低等级列车；运行方向1表示下行方向，0表示上行方向。
[0185][0186]
表2
[0187]
除了上述车站和列车的基本参数，16列列车在中间5个车站的停车时间基本设定如
[0188]
表3所示。表3是本技术一实施例提出的列车停站时间(min)基本设定
[0189][0190]
表3
[0191]
本实施例中，共设计了3种测试场景，每次训练结束后，学习到相应的调度策略，对每种场景分别进行测试，得到基于当前训练情况下编制出列车运行图。同时，对每种场景下每次测试得到的列车总等待时间进行记录，等待50000次训练结束后，画出其变化趋势图，以便判断在该场景下算法的性能以及优化效果。
[0192]
(1)场景一：列车车站停车时间及区间运行时间均为基本值
[0193]
在该场景下，列车车站停车时间参考表3中的数据，列车区间运行时间参考表1中的数据。
[0194]
参考图3，图3是本技术一实施例提出的场景一列车运行图编制优化的仿真结果图。如图3所示，该图表示了在场景一中列车车站总等待时间的变化趋势，从图中可以看出，场景一测试环境下列车总等待时间的变化曲线随着测试次数(即训练次数)的增加而逐渐收敛，训练到第38000次时就基本可以达到一个稳定的值(151min)。
[0195]
参考图4，图4是本技术一实施例提出的场景一应用q学习算法编制得到的列车运行图，如图4所示，图中每条代表一辆列车，在场景一中应用q学习算法完成训练后得到的调度策略，编制出的列车运行图的总旅行时间为1880min，列车车站总等待时间为151min，列车运行线占用运行图时间为977min。
[0196]
(2)场景二：列车车站停车时间部分值改变
[0197]
在该场景下，列车车站停车时间参考表4中的数据，表4是本技术一实施例提出的场景二列车停站时间表。
[0198][0199]
表4
[0200]
其中，加粗下划线的值表示该列车在该车站的停车时间的改变值。
[0201]
参考图5，图5是本技术一实施例提出的场景二中列车车站总等待时间的变化趋势图，如图5所示，场景二测试环境下列车总等待时间的变化曲线随着测试次数(训练次数)的增加而逐渐收敛，训练到第39000次时就基本可以达到一个稳定的值(153min)。
[0202]
参考图6，图6是本技术一实施例提出的场景二中应用q学习算法编制得到的列车运行图，如图6所示，图中每条线代表一辆列车，在场景二中应用q学习算法完成训练后得到的调度策略，编制出的列车运行图列车总旅行时间为1882min，列车车站总等待时间为153min，列车运行线占用运行图时间为969min。
[0203]
(3)场景三：列车区间运行时间部分值改变
[0204]
在该场景下，列车车站停车时间参考表2中的数据，列车区间运行时间参考表5中的数据，表5是本技术一实施例提出的场景三列车区间运行时间图。
[0205][0206]
表5
[0207]
参考图7，图7是本技术一实施例提出的场景三中列车车站总等待时间的变化趋势图，如图7所示，场景三测试环境下列车总等待时间的变化曲线随着测试次数(训练次数)的增加而逐渐收敛，训练到第40500次时基本就可以达到一个稳定的值(157min)。
[0208]
参考图8，图8是本技术一实施例提出的场景三中应用q学习算法编制得到的列车运行图，如图8所示，图中每条线代表一辆列车，在场景三中应用q学习算法完成训练后的到调度策略，编制出的列车运行图列车总旅行时间为1908min，列车车站总等待时间为157min，列车运行线占用运行图时间为980min。
[0209]
从上述实例中可知，本实施例中的三种场景下，列车运行图的编制与优化问题上均取得了收敛结果，并且在q学习算法训练过程中引入随机性，将列车运行时间波动、车站停车时间(客流量)变化等随机情况加入测试中，有效的提高了训练得到的列车运行图编制优化模型的鲁棒性和泛化能力，在三种场景下均可以快速准确的得到较优的列车运行图，证明了本技术的方法在列车运行图编制优化方面的适用性和有效性。
[0210]
本技术实施例中，构建了基于马尔可夫决策过程的列车运行图编制模型，明确了优化目标为最小化列车车站总等待时间，同时在实现该优化目标的前提下，考虑尽可能减
少列车运行线占中运行图时间，将连续的列车运行环境过程描述为离散的列车状态转移，提出了基于离散事件动态系统的列车运行环境模型，有利于简化列车运行图编制优化的计算过程。另外，本技术实施例中考虑到列车运行实际过程中存在客流量波动性大、列车运行时间不确定等因素，在q学习训练过程中引入区间运行时间和车站停车时间波动，训练出的模型鲁棒性高、泛化能力强，能够实现对列车运行图的及时优化。本技术实施例中还可以通过重新设定状态变量和奖励函数，调整q值的更新方法，解决列车运行重调度等其他问题。为了提高方法迭代过程的收敛性，本技术实施例中对q学习算法进行了改进，考虑到算法的搜索效率和搜索深度，设计了基于动作选择次数的改进ε-贪婪搜索策略，考虑到该问题两个相邻的决策时刻之间的关联性较小，引入“列车相邻状态”和“车站相邻状态”对q值的更新方法进行了改进，得到的列车运行图编制优化模型可以更加准确的编制并优化列车运行图。
[0211]
基于同一发明构思，本技术一实施例提供一种列车运行图编制与优化装置。参考图9，图9是本技术一实施例提出的列车运行图编制与优化装置900的示意图。如图9所示，该装置包括：
[0212]
运行环境信息接收模块901，用于将列车的运行环境信息输入待训练的列车运行图编制模型中，所述运行环境信息包括列车信息以及车站信息；
[0213]
模型训练模块902，用于根据所述运行环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型；
[0214]
列车运行图编制优化模块903，用于通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图。
[0215]
可选地，所述模型训练模块901包括：
[0216]
信息接收子模块，用于接收列车的运行环境信息，所述运行环境信息包括列车信息以及车站信息；
[0217]
初始参数获得子模块，用于当训练开始时，根据所述运行环境信息，初始化列车的运行环境，同时随机改变列车的区间运行时间和车站停站时间，得到列车运行环境的初始参数；
[0218]
初始状态获得子模块，用于根据所述初始参数，获得列车运行的初始状态；
[0219]
动作选择子模块，用于根据所述初始状态，通过贪婪搜索策略，选择当前决策时刻采取的动作，得到当前列车对应的状态-动作对；
[0220]
动作执行子模块，用于执行所述动作，得到所述动作对应的奖励值以及后续状态，并使用q学习算法，根据q值更新公式更新所述当前列车对应的状态-动作对的q值；
[0221]
约束条件判断子模块，用于根据所述奖励值以及后续状态，确定当前车站是否满足预设的车站容量约束，当所述当前车站不满足所述预设的车站容量约束时，在当前状态下再次对还未选择过的动作进行选择，并执行选择的动作；
[0222]
当前状态-动作对确定子模块，用于当所述当前车站满足所述车站容量约束或所述动作为当前决策时刻选择的最后一个动作时，将所述当前列车的状态作为所述当前列车在上一决策时刻得到的状态-动作对的列车相邻状态和所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态；
[0223]
平均最大q值更新子模块，用于更新对应于所述当前列车在上一决策时刻得到的
状态-动作对的列车相邻状态数量和平均最大q值，以及对应于所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态数量和平均最大q值，所述相邻状态数量和平均最大q值用于后续轮次决策中的q值更新；
[0224]
状态-动作对更新子模块，用于将所述当前列车对应的状态-动作对作为当前决策时刻得到的列车状态-动作对和车站状态-动作对进行存储；
[0225]
迭代训练子模块，用于重复执行上述动作决策、动作执行、获得状态-动作对、更新相邻状态数量和平均最大q值、更新当前状态-动作对步骤，当全部列车到达终点站或所有动作都已经执完毕时，结束本轮训练；
[0226]
模型获得子模块，用于重复进行多轮训练，当训练次数达到预设训练次数时，结束训练，得到所述列车运行图编制优化模型；
[0227]
可选地，所述装置还包括：
[0228]
列车运行环境构建模块，用于构建基于离散事件动态系统的列车运行环境，所述列车运行环境用于限制列车运行时需要满足的约束条件与状态；
[0229]
模型构建模块，构建所述待训练的列车运行图编制优化模型，所述列车运行图编制优化模型在满足所述列车运行环境的条件下进行列车运行图编制与优化。
[0230]
可选地，所述列车运行环境构建模块包括：
[0231]
约束条件设置子模块，用于设置列车运行环境的约束条件；
[0232]
状态设置子模块，用于设置列车状态和车站状态。
[0233]
可选地，所述约束条件设置子模块包括：
[0234]
运行时间约束设置子模块，用于设置列车在行车区间的运行时间约束，所述运行时间约束为列车的实际运行时间等于行车区间的纯运行时间；
[0235]
停留时间约束设置子模块，用于设置列车在车站的停留时间约束，所述停留时间约束为列车在车站的停留时间等于列车到达车站与离开车站的时间间隔，且列车在车站的停留时间不小于列车在车站的停留时间和等待发车时间之和；
[0236]
到达约束设置子模块，用于设置同向列车车站到达间隔时间约束，所述同向列车车站到达间隔时间约束为同向列车到达车站的时间间隔不小于预设同向列车最小到达间隔时间；
[0237]
发车约束设置子模块，用于设置同向列车车站发车间隔时间约束，所述同向列车车站发车间隔时间约束为同向出发的两列列车的发车时间间隔不小于预设同向列车最小出发间隔时间；
[0238]
追踪间隔时间约束设置子模块，用于设置同向列车区间追踪间隔时间约束，所述同向列车区间追踪间隔时间约束为前行列车和后行列车离开当前车站的时间间隔和到达下一车站的时间间隔不小于预设列车区间追踪间隔时间；
[0239]
车站能力约束设置子模块，用于设置车站能力约束，所述车站能力约束为车站在同一时刻内容纳列车的实际数量不大于该车站内的股道数量。
[0240]
可选地，所述状态设置子模块包括：
[0241]
列车状态设置子模块，用于将列车在运行中的不同状态分别设置为等待发车状态、区间运行状态和停车状态；
[0242]
车站状态设置子模块，用于将车站的状态分别设置为允许发车状态和不允许发车
状态。
[0243]
可选地，所述模型构建模块包括：
[0244]
状态变量设置子模块，用于设置所述列车运行图编制优化模型的状态变量，所述状态变量包括当前列车以及相邻列车的速度等级、当前列车所处车站和相邻区间的占用情况、不同速度等级列车区间运行时间差值、距离当前车站发出同方向下一列车的时间差值；
[0245]
动作变量设置子模块，用于设置所述列车运行图编制优化模型的动作变量，所述动作变量包括发车与不发车；
[0246]
学习方法确定子模块，用于确定通过q学习算法进行所述列车运行图编制优化模型的训练；
[0247]
奖励值函数设置子模块，用于设置所述列车运行图编制优化模型的奖励值函数；
[0248]
优化目标确定子模块，用于确定所述列车运行图编制优化模型的优化目标以及目标函数，所述优化目标为列车的总旅行时间最短；
[0249]
学习方法确定子模块，用于确定所述q学习算法为训练所述列车运行图编制优化模型的训练算法。
[0250]
可选地，所述列车运行图编制优化模块903包括：
[0251]
数据输入子模块，用于将所述列车运行环境信息输入所述列车运行图编制优化模型中；
[0252]
策略定制子模块，用于根据所述列车运行环境信息，通过所述列车运行图编制优化模型定制对应的列车运行图编制优化策略；
[0253]
列车运行图编制优化子模块，用于根据所述列车运行图编制优化策略，输出所述列车运行图。
[0254]
基于同一发明构思，本技术另一实施例提供一种可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如本技术上述任一实施例所述的列车运行图编制与优化方法中的步骤。
[0255]
基于同一发明构思，本技术另一实施例提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行时实现本技术上述任一实施例所述的列车运行图编制与优化方法中的步骤。
[0256]
对于装置实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。
[0257]
本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。
[0258]
本领域内的技术人员应明白，本技术实施例可提供为方法、装置、或计算机程序产品。因此，本技术实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
[0259]
本技术实施例是参照根据本技术实施例的方法、终端设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些
计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理终端设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理终端设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0260]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理终端设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0261]
这些计算机程序指令也可装载到计算机或其他可编程数据处理终端设备上，使得在计算机或其他可编程终端设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程终端设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0262]
尽管已描述了本技术实施例的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本技术实施例范围的所有变更和修改。
[0263]
最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。
[0264]
以上对本技术所提供的列车运行图编制与优化方法、装置、设备及存储介质，进行了详细介绍，本文中应用了具体个例对本技术的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本技术的方法及其核心思想；同时，对于本领域的一般技术人员，依据本技术的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本技术的限制。

技术特征：
1.一种列车运行图编制与优化方法，其特征在于，所述方法包括：将列车的运行环境信息输入待训练的列车运行图编制模型中，所述运行环境信息包括列车信息以及车站信息；根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型；通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图。2.根据权利要求1所述的方法，其特征在于，根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型，包括：当训练开始时，根据所述运行环境信息，初始化列车的运行环境，同时随机改变列车的区间运行时间和车站停站时间，得到列车运行环境的初始参数；根据所述初始参数，获得列车运行的初始状态；根据所述初始状态，通过贪婪搜索策略，选择当前决策时刻采取的动作，得到当前列车对应的状态-动作对；执行所述动作，得到所述动作对应的奖励值以及后续状态，并使用所述q学习算法，根据q值更新公式更新所述当前列车对应的状态-动作对的q值；根据所述奖励值以及后续状态，确定当前车站是否满足预设的车站容量约束，当所述当前车站不满足所述预设的车站容量约束时，在当前状态下再次对还未选择过的动作进行选择，并执行选择的动作；当所述当前车站满足所述车站容量约束或所述动作为当前决策时刻选择的最后一个动作时，将所述当前列车的状态作为所述当前列车在上一决策时刻得到的状态-动作对的列车相邻状态和所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态；更新对应于所述当前列车在上一决策时刻得到的状态-动作对的列车相邻状态数量和平均最大q值，以及对应于所述当前车站在上一决策时刻得到的状态-动作对的车站相邻状态数量和平均最大q值，所述相邻状态数量和平均最大q值用于后续轮次决策中的q值更新；将所述当前列车对应的状态-动作对作为当前决策时刻得到的列车状态-动作对和车站状态-动作对进行存储；重复执行上述动作决策、动作执行、获得状态-动作对、更新相邻状态数量和平均最大q值、更新当前状态-动作对步骤，当全部列车到达终点站或当前决策时刻可选择的所有动作都已经执完毕时，结束本轮训练；重复进行多轮训练，当训练次数达到预设训练次数时，结束训练，得到所述列车运行图编制优化模型。3.根据权利要求1所述的方法，其特征在于，在接收所述环境信息之前，所述方法还包括：构建基于离散事件动态系统的列车运行环境，所述列车运行环境用于限制列车运行时需要满足的约束条件与状态；构建所述待训练的列车运行图编制优化模型，所述列车运行图编制优化模型在满足所述列车运行环境的条件下进行列车运行图编制与优化。
4.根据权利要求3所述的方法，其特征在于，构建基于离散事件动态系统的列车运行环境，包括：设置列车运行环境的约束条件；设置列车状态和车站状态。5.根据权利要求4所述的方法，其特征在于，所述设置列车运行环境的约束条件，包括：设置列车在行车区间的运行时间约束，其中所述运行时间约束为列车的实际运行时间等于行车区间的纯运行时间；设置列车在车站的停留时间约束，其中所述停留时间约束为列车在车站的停留时间等于列车到达车站与离开车站的时间间隔，且列车在车站的停留时间不小于列车在车站的停留时间和等待发车时间之和；设置同向列车车站到达间隔时间约束，其中所述同向列车车站到达间隔时间约束为同向列车到达车站的时间间隔不小于预设同向列车最小到达间隔时间；设置同向列车车站发车间隔时间约束，其中所述同向列车车站发车间隔时间约束为同向出发的两列列车的发车时间间隔不小于预设同向列车最小出发间隔时间；设置同向列车区间追踪间隔时间约束，其中所述同向列车区间追踪间隔时间约束为前行列车和后行列车离开当前车站的时间间隔和到达下一车站的时间间隔均不小于预设列车区间追踪间隔时间；设置车站能力约束，其中所述车站能力约束为车站在同一时刻内容纳列车的实际数量不大于该车站内的股道数量。6.根据权利要求4所述的方法，其特征在于，所述设置列车状态和车站状态，包括：将列车在运行中的不同状态分别设置为等待发车状态、区间运行状态和停车状态；将车站的状态分别设置为允许发车状态和不允许发车状态。7.根据权利要求3所述的方法，其特征在于，所述构建所述待训练的列车运行图编制优化模型，包括：设置所述列车运行图编制优化模型的状态变量，其中所述状态变量包括当前列车以及相邻列车的速度等级、当前列车所处车站和相邻区间的占用情况、不同速度等级列车区间运行时间差值、当前时刻距离当前车站发出同方向下一列车的时间差值；设置所述列车运行图编制优化模型的动作变量，其中所述动作变量包括发车与不发车；设置所述列车运行图编制优化模型的奖励值函数；确定所述列车运行图编制优化模型的优化目标以及目标函数，其中所述优化目标为列车的总旅行时间最短；确定所述q学习算法为训练所述列车运行图编制优化模型的训练算法。8.根据权利要求1所述的方法，其特征在于，通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图，包括：将所述列车运行环境信息输入所述列车运行图编制优化模型中；根据所述列车运行环境信息，通过所述列车运行图编制优化模型定制对应的列车运行图编制优化策略；根据所述列车运行图编制优化策略，输出所述列车运行图。
9.一种列车运行图编制与优化装置，其特征在于，所述装置包括：运行环境信息接收模块，用于将列车的运行环境信息输入待训练的列车运行图编制模型中，所述运行环境信息包括列车信息以及车站信息；模型训练模块，用于根据所述环境信息，通过q学习算法，对所述待训练的列车运行图编制优化模型进行训练，得到训练好的列车运行图编制优化模型；列车运行图编制优化模块，用于通过所述训练好的列车运行图编制优化模型进行列车运行图的编制与优化，得到列车运行图。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该计算机程序被处理器执行时，实现如权利要求1至8任一所述的方法中的步骤。11.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时，实现如权利要求1至8任一所述的方法的步骤。

技术总结
本申请实施例涉及铁路调度技术领域，具体涉及一种列车运行图编制与优化方法、装置、设备及存储介质，旨在快速准确的编制并优化列车运行图。所述方法首先构建了基于离散事件动态系统的列车运行环境，以该列车运行环境为基础设计了用于列车运行图编制的马尔可夫决策过程模型，之后通过改进的搜索策略和Q值更新方法，对该模型进行多轮训练，得到列车运行图编制优化策略，通过该策略进行列车运行图的编制与优化。与优化。与优化。


技术研发人员：宋士吉 杨琬露 江鹏
受保护的技术使用者：清华大学
技术研发日：2022.07.15
技术公布日：2022/11/1