构建列车运行图的方法、装置、设备以及存储介质与流程

1.本公开涉及计算机技术领域，尤其涉及智能交通、云计算技术领域。


背景技术：

2.列车运行图是用以表示列车在铁路区间运行及在车站到达、出发或通过时刻的视图，是列车运行的基础。根据列车运行图能够获知列车在每个车站的到达和出发(或通过)时刻，列车在铁路区间的运行时间，列车在车站的停站时间等信息。列车运行图是列车运行的时间与空间关系的图解，它表示列车在各区间运行及在各车站停车或通过状态的二维线条图。


技术实现要素：

3.本公开提供了一种构建列车运行图的方法、装置、设备以及存储介质。
4.根据本公开的一方面，提供了一种构建列车运行图的方法，包括：
5.确定m个车次中第k车次对应的n个车站；其中，m、k、n均大于1；
6.确定n个车站中第i车站对应的第k
′
车次；其中，k
′
和i均大于等于1，第k
′
车次为先于第k车次途径第i车站的相邻车次；
7.根据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间；其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔；以及
8.根据m个车次中的每个车次的优选出发时间，构建列车运行图。
9.根据本公开的另一方面，提供了一种构建列车运行图的装置，包括：
10.第一确定模块，用于确定m个车次中第k车次对应的n个车站；其中，m、k、n均大于1；
11.第二确定模块，用于确定n个车站中第i车站对应的第k
′
车次；其中，k
′
和i均大于等于1，第k
′
车次为先于第k车次途径第i车站的相邻车次；
12.第三确定模块，用于根据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间；其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔；以及
13.运行图模块，用于根据m个车次中的每个车次的优选出发时间，构建列车运行图。
14.根据本公开的另一方面，提供了一种电子设备，包括：
15.至少一个处理器；以及
16.与该至少一个处理器通信连接的存储器；其中，
17.该存储器存储有可被该至少一个处理器执行的指令，该指令被该至少一个处理器执行，以使该至少一个处理器能够执行本公开中任一实施例的方法。
18.根据本公开的另一方面，提供了一种存储有计算机指令的非瞬时计算机可读存储
介质，其中，该计算机指令用于使该计算机执行根据本公开中任一实施例的方法。
19.根据本公开的另一方面，提供了一种计算机程序产品，包括计算机程序，该计算机程序在被处理器执行时实现根据本公开中任一实施例的方法。
20.根据本公开方案，仅利用基于出发时间的约束确定每个车次的各车站优选出发时间，可以显著提升构建列车运行图的效率。
21.应当理解，本部分所描述的内容并非旨在标识本公开的实施例的关键或重要特征，也不用于限制本公开的范围。本公开的其它特征将通过以下的说明书而变得容易理解。
附图说明
22.附图用于更好地理解本方案，不构成对本公开的限定。其中：
23.图1是根据本公开实施例的构建列车运行图的方法的流程示意图；
24.图2是根据本公开实施例的构建列车运行图的方法的车次行驶示意图；
25.图3是根据本公开实施例的构建列车运行图的方法构建的列车运行图的示意图；
26.图4是可以实现本公开实施例的构建列车运行图的方法的场景图；
27.图5是根据本公开实施例的构建列车运行图的方法的流程示意图；
28.图6是根据本公开实施例的构建列车运行图的装置的结构示意图；
29.图7是用来实现本公开实施例的构建列车运行图的方法的电子设备的框图。
具体实施方式
30.以下结合附图对本公开的示范性实施例做出说明，其中包括本公开实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本公开的范围。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。
31.如图1所示，本公开实施例提供了一种构建列车运行图的方法，包括：
32.步骤s101：确定m个车次中第k车次对应的n个车站。其中，m、k、n均大于1。
33.步骤s102：确定n个车站中第i车站对应的第k
′
车次。其中，k
′
和i均大于等于1，第k
′
车次为先于第k车次途径第i车站的相邻车次。
34.步骤s103：根据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔。以及
35.步骤s104：根据m个车次中的每个车次的优选出发时间，构建列车运行图。
36.根据本公开实施例，需要说明的是：
37.m个车次，可以理解为目标列车的行驶路线一天内的上行路线和下行路线所需要运行的列车的数量。可以理解为目标列车行驶路线一天内的上行路线所需要运行的列车的数量。也可以理解为目标列车行驶路线一天内的下行路线所需要运行的列车的数量。其中，每个列车在一个行驶方向上配置一个车次。在列车为接续车时，其上行和下行配置为两个车次。列车可以理解为是动车、高铁、普通载客火车、载货火车、地铁等，在此不做具体限定。
38.第k车次，可以理解为m个车次中除首个运行车次之外的任一个车次。也即是说，m
个车次中除首个运行车次之外的任一个车次均可通过本公开实施例的步骤确定其所对应的多个n个车站的优选出发时间。
39.第k车次对应的n个车站，可以包括第k车次的始发站、终点站、停靠站和非停靠站。始发站、终点站、停靠站和非停靠站均可以是目标列车行驶路线上对应的任一个车站。每个第k车次对应的n个车站的n的数量可以不同。每个第k车次对应的n个车站中的始发站、终点站、停靠站和非停靠站可以不同。
40.第i车站，可以理解为第k车次对应的n个车站中的任一个车站。例如，第i车站可以是始发站、终点站、停靠站或非停靠站。
41.第i车站对应的第k
′
车次，如图2所示，可以理解为先于第k车次经过第i站的列车，且是与第k车次为相邻的两个经过第i车站的列车。在k
′
＝1时，第k
′
车次可以理解为目标列车行驶路线上第一个通过第i车站的车次，此时，第k车次为第二个通过第i车站的车次。需要说明的是，在i取值不同时，每个第i车站对应的第k
′
车次可能不同。因为m个车次中不同车次对应的n个车站不同，例如，第k车次会依次经过a、b、c、d、e、f车站，第q车次会依次经过a、b、c、d车站，且第q车次在a车站先于第k车次发车，但第q车次到达d车站后不会继续向前行驶至e车站，因此第k车次在e车站对应的第k
′
车次必然不会是第q车次。
42.第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，可以理解为第k车次对应的n个车站中，每相邻的两个车站的出发时间间隔都需要满足该约束条件。例如，如图2所示，第k车次在第i车站的出发时间与在第i-1车站的出发时间要满足第一出发时间条件的约束，以及，第k车次在第i车站的出发时间与在第i+1车站的出发时间要满足第一出发时间条件的约束。还需说明的是，根据相邻两车站的后一车站相对第k车次的车站类型不同，第一出发时间条件也不同。例如，后一车站是第k车次的停靠站和是第k车次的非停靠站时，第一出发时间条件不相同。
43.第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔，如图2所示，相邻车次中第k车次在第i车站的出发时间与第k
′
车次在第i车站的出发时间需要满足该约束条件。根据第i车站相对第k车次和第k
′
车次的车站类型不同，第二出发时间条件也不同。例如，第i车站可以是第k车次的发车站以及是第k
′
车次的发车站、第i车站可以是第k车次的通过车站(非停靠站)以及是第k
′
车次的发车站、第i车站可以是第k车次的发车站以及是第k
′
车次的通过车站(非停靠站)、第i车站可以是第k车次的通过车站以及是第k
′
车次的通过车站、第i车站可以是第k车次的到达车站(停靠站)以及是第k
′
车次的通过车站、第i车站可以是第k车次的通过车站以及是第k
′
车次的到达车站(停靠站)、第i车站可以是第k车次的到达车站以及是第k
′
车次的到达车站。
44.第k
′
车次在第i车站的优选出发时间，可以理解为是预先计算好的第k
′
车次在第i车站的出发时间。例如，在第k
′
车次相对作为第k车次时，根据第一出发时间条件、第二出发时间条件和第k
″
车次(先于第k
′
车次途径第i车站的相邻车次)在第i车站的优选出发时间，计算出的第k
′
车次在第i车站的优选出发时间。
45.确定第k车次分别在n个车站的优选出发时间，可以理解为利用约束传播算法，计算出第k车次的每个车站能够满足第一出发时间条件、第二出发时间条件的优选出发时间。
46.根据所述m个车次中的每个车次的优选出发时间，构建列车运行图，可以理解为根据每个车次对应的n个车站的优选出发时间，构建列车运行图。列车运行图的具体可视化结
构形式，可以根据需要进行选择和调整，在此不做具体限定，如图3所示，列车运行图可以示出每个车站所经过的列车，以及列车经过车站的具体时间。图3中纵坐标为目标列车路线的各车站，横坐标为24小时制的时间。其中，图3中的a点表示列车1到达车站2的时间，b点表示列车1从车站2出发的时间。
47.根据本公开实施例，仅利用基于出发时间的约束，即第一出发时间条件和第二出发时间条件，即可确定每个车次的各车站的优选出发时间，无需夹杂其他约束条件，因此可以显著提升每个车次的各车站的优选出发时间的计算效率，进而提高构建列车运行图的效率。可以实现根据市场需求灵活、高效且合理地利用计算机自动化的生成高质量列车运行图。本公开实施例的方法构建的列车运行图，可以避免列车在非停站停车或者被越行，同时保证了旅客的方便换乘以及站内的安全时间间隔，合理地安排了列车的到达和出发时刻。本公开实施例的方法，利用约束传播算法可以实现目标列车路线上m个车次的全局整体优化，相对于传统方案，应用本公开实施例的方法可以将宏观的列车运行图的时刻表编制问题的求解时间缩短50％。以一条上下行共计600车次的路线为例，传统方法求解时间在5小时以上，应用本公开实施例的方法求解时间仅需要2小时左右。
48.在一种实施方式中，本公开实施例的实施方式提供的构建列车运行图的方法，可以应用于如图4所示的场景框架下。在图4中，10表示能够可视化输出结果的终端设备，20表示服务器，30表示分布式计算机系统。本公开实施例的构建列车运行图的方法可以由服务器20或分布式计算机系统30执行，终端设备10用于将构建列车运行图所需的数据上报/发送至服务器20或分布式计算机系统30。服务器20或分布式计算机系统30完成本公开实施例的构建列车运行图的方法后，可以将构建的列车运行图可视化地输出到终端设备10。
49.在一个示例中，定义第k车次的始发时间(起车时间)、行驶速度和停车时间为预设定数值，在此基础上，根据相邻两车站间的距离，即可确定出第k车次在全程各站的到达时间和出发时间。
50.在一个示例中，第k车次的始发时间可以基于始发时间窗口确定。始发时间窗口可以理解为列车在始发站出发的时间区间。例如，出发时间在给定始发时间窗口内：
[0051][0052]
其中，ts[k]为第k车次的计划出发时间，tol[k]为可变动偏差，d[k，start[k]]为第k车次的始发站的始发时间，m为行驶路线上的总车次数量。
[0053]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s103：据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0054]
步骤s1031：根据第二出发时间条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在第i车站的第一候选出发时间。
[0055]
步骤s1032：根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间。
[0056]
步骤s1033：根据第一候选出发时间和第二候选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0057]
根据本公开实施例，需要说明的是：
[0058]
步骤s1031可以理解为，通过已经确定的第k
′
车次在第i车站的优选出发时间，基于第二出发时间条件限定的第k车次在第i车站的出发时间与第k
′
车次在第i车站的出发时间的约束条件，可以确定出满足第二出发时间条件限定的第一候选出发时间。
[0059]
步骤s1032可以理解为，通过预设的第k车次的始发时间、预设的第k车次的行驶速度、预设的车站停靠时间和第k车次对应的n个车站中每两个相邻车站之间的已知距离，可以计算出第k车次在第i车站的初始出发时间。在此基础上，基于第一出发时间条件限定的第k车次的每两个相邻车站的出发时间间隔，可以确定出满足第一出发时间条件限定的第二候选出发时间。
[0060]
步骤s1033可以理解为，基于第k车次在第i车站满足第二出发时间条件限定的第一候选出发时间、满足第一出发时间条件限定的第二候选出发时间，可以确定出第k车次在第i车站的优选出发时间。同时，第k车次对应n个车站，因此利用约束传播算法、第一候选出发时间和第二候选出发时间，确定出第k车次的n个车站中每个车站的优选出发时间，且保证每个车站的优选出发时间都可以满足第一出发时间条件和第二出发时间条件。
[0061]
根据本公开实施例，通过并行计算基于第一出发时间条件确定的k车次在第i车站的第二候选出发时间、和基于第二出发时间条件确定的第k车次在第i车站的第一候选出发时间，可以提高运算效率，能够更高效的利用约束传播算法、第一候选出发时间和第二候选出发时间，确定出第k车次的n个车站中每个车站的优选出发时间。同时，仅利用基于出发时间的约束，即第一出发时间条件和第二出发时间条件，即可确定每个车次的各车站的优选出发时间，无需夹杂其他约束条件，因此可以显著提升每个车次的各车站的优选出发时间的计算效率，进而提高构建列车运行图的效率。
[0062]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s103：据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0063]
步骤s1031：根据第二出发时间条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在第i车站的第一候选出发时间。
[0064]
步骤s1034：根据第一出发时间条件、第一候选出发时间、第k车次的始发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0065]
根据本公开实施例，需要说明的是：
[0066]
步骤s1031可以理解为，通过已经确定的第k
′
车次在第i车站的优选出发时间，基于第二出发时间条件限定的第k车次在第i车站的出发时间与第k
′
车次在第i车站的出发时间的约束条件，可以确定出满足第二出发时间条件限定的第一候选出发时间。
[0067]
步骤s1034可以理解为，通过第一候选出发时间、预设的第k车次的行驶速度、预设的车站停靠时间和第k车次对应的n个车站中每两个相邻车站之间的已知距离，可以计算出第k车次在第i车站的初始出发时间。在此基础上，基于第一出发时间条件限定的第k车次的每两个相邻车站的出发时间间隔，可以确定出满足第一出发时间条件限定的第k车次在第i车站的优选出发时间。由于第i车站的优选出发时间可以认为是n个车站中除始发站之外的任一个车站，因此可以基于此，确定出第k车次的n个车站中除始发站之外的所有车站的优选出发时间，再与预设的第k车次的始发站的始发时间组合，即可确定出第k车次分别在n个
车站的优选出发时间。
[0068]
根据本公开实施例，通过迭代计算方式，针对基于第二出发时间条件确定的第k车次在第i车站的第一候选出发时间，进一步利用第一出发时间条件进行计算，可以提高计算的精度，能够利用约束传播算法、更精准的确定出第k车次的n个车站中每个车站的优选出发时间。同时，仅利用基于出发时间的约束，即第一出发时间条件和第二出发时间条件，即可确定每个车次的各车站的优选出发时间，无需夹杂其他约束条件，因此可以显著提升每个车次的各车站的优选出发时间的计算效率，进而提高构建列车运行图的效率。
[0069]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s1031：根据第二出发时间条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在i车站的第一候选出发时间，包括：
[0070]
步骤s10311：确定第i车站相对第k车次的第一过站类型。
[0071]
步骤s10312：确定第i车站相对第k
′
车次的第二过站类型。
[0072]
步骤s10313：根据第一过站类型和第二过站类型，确定第二出发时间条件中的过站时间间隔条件。
[0073]
步骤s10314：根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在i车站的第一候选出发时间。
[0074]
根据本公开实施例，需要说明的是：
[0075]
第一过站类型，可以包括出发车站(始发站或停靠车站)、到达车站、通过车站(非停靠车站)。具体的，在第k车次途径第i车站时，若需要停靠一段时间再发车，则第i车站相对第k车次的第一过站类型为出发车站。在第k车次上行途径第i车站时，若停靠一段时间后需要作为接续车下行返回，则第i车站相对第k车次的第一过站类型为到达车站，同时相对更改车次后的接续车，第i车站的第一过站类型为出发车站。在第k车次途径第i车站时，不停靠直接通过，则第i车站相对第k车次的第一过站类型为通过车站。
[0076]
第二过站类型，可以包括出发车站(始发站或停靠车站)、到达车站、通过车站(非停靠车站)。具体的，在第k
′
车次途径第i车站时，若需要停靠一段时间再发车，则第i车站相对第k
′
车次的第一过站类型为出发车站。在第k
′
车次上行途径第i车站时，若停靠一段时间后需要作为接续车下行返回，则第i车站相对第k
′
车次的第一过站类型为到达车站，同时相对更改车次后的接续车，第i车站的第一过站类型为出发车站。在第k
′
车次途径第i车站时，不停靠直接通过，则第i车站相对第k
′
车次的第一过站类型为通过车站。
[0077]
过站时间间隔条件，用于确定途径同一车站的相邻两车次的出发时间的安全时间间隔。
[0078]
根据第一过站类型和第二过站类型的不同组合，确定的第二出发时间条件中的过站时间间隔条件有所不同，也即是说，第k车次在第i车站的出发时间和第k
′
车次在第i车站的出发时间的安全时间间隔会有所不同。
[0079]
例如，第i车站相对第k车次的第一过站类型为出发车站，第i车站相对第k
′
车次的第一过站类型亦为出发车站时，确定的过站时间间隔条件的两列车间的出发时间的安全时间间隔约束为：
[0080][0081]
其中，d[k,i]为第k车次在第i车站的出发时间，d[k
′
,i]为第k
′
车次在第i车站的
出发时间，h
dd
[k,i]和h
dd
[k
′
,i]为第k车次在第i车站的出发时间和第k
′
车次在第i车站的出发时间的安全时间间隔，d[i]为从第i车站出发的车次的集合。
[0082]
需要说明的是，在第k车次后于第k
′
车次从第i车站出发时，选用d[k,i]-d[k
′
,i]≥h
dd
[k,i]作为两列车间的出发时间的安全时间间隔约束。在第k
′
车次后于第k车次从第i车站出发时，选用d[k
′
,i]-d[k,i]≥h
dd
[k
′
,i]作为两列车间的出发时间的安全时间间隔约束。
[0083]
根据本公开实施例，通过第一过站类型和第二过站类型选择不同的第二出发时间条件，可以准确的确定第k车次在i车站的第一候选出发时间。
[0084]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s10314：根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在i车站的第一候选出发时间，包括：
[0085]
根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定初始候选出发时间。
[0086]
根据第k车次在第i车站至第i+1车站间的运行时间、附加时间、初始候选出发时间、第k
′
车次在第i车站至第i+1车站间的运行时间、第二附加时间和第k
′
车次在第i车站的优选出发时间，确定第k车次与第k
′
车次之间的越行时间间隔。
[0087]
根据第二出发时间条件中的越行时间间隔条件、越行时间间隔和初始候选出发时间，确定第k车次在i车站的第一候选出发时间。
[0088]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0089]
根据本公开实施例，需要说明的是：
[0090]
根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定初始候选出发时间，可以理解为：基于第k
′
车次在第i车站的优选出发时间，确定出能够满足过站时间间隔条件的出发时间作为第k车次在i车站的初始候选出发时间。
[0091]
运行时间，可以理解为基于第k车次的预设车速，根据第i车站至第i+1车站间的距离，所计算出的第k车次从第i车站行驶至第i+1车站所需的时间。
[0092]
附加时间中的起车加速时间，可以理解为第k车次在达到预设车速之前，从启动到达到预设车速的过程中所消耗的时间。
[0093]
附加时间中的停车减速时间，可以理解为第k车次在从预设车速开始减速到停车的过程中所消耗的时间。
[0094]
确定第k车次与第k
′
车次之间的越行时间间隔，包括：
[0095]
在第k车次晚于第k
′
车次到达第i车站的情况下，定义scd[k,k',i]为第k车次晚于第k
′
车次到达第i车站的越行安全间隔，越行安全间隔的关系式为：
[0096]
d[k,i]+scd[k,k
′
,i]+rt[k,i,i+1]+et[k,i,i+1]＝d[k
′
,i]+rt[k
′
,i,i+1]+et[k
′
,i,i+1]
[0097]
其中，rt[k,i,i+1]为第k车次在第i车站到第i+1车站的运行时间，et[k,i,i+1]为第k车次在第i车站到第i+1车站的附加时间(包括起车加速时间和停车减速时间)，rt[k',i,i+1]为第k'车次在第i车站到第i+1车站的运行时间，et[k',i,i+1]为第k'车次在第i车站到第i+1车站的附加时间(包括起车加速时间和停车减速时间)，d[k,i]为第k车次在第i车站的出发时间，d[k',i]为第k'车次在第i车站的出发时间。
[0098]
越行时间间隔条件，用于确定站间轨道为单轨，不允许越行的情况下，第k车次在第i车站的出发时间与第k'车次在第i车站的出发时间应满足的关系，保证第k车次与第k'车次在行驶过程中不会发生碰撞。
[0099]
根据本公开实施例，根据第k车次在第i车站至第i+1车站间的运行时间、附加时间、初始候选出发时间、第k
′
车次在第i车站至第i+1车站间的运行时间、第二附加时间和第k
′
车次在第i车站的优选出发时间，可以准确的计算出列车k和k'在车站i的越行安全间隔，通过越行安全间隔条件作为第k车次在第i车站的出发时间与第k'车次在第i车站的出发时间的约束，可以提高所配置的第k车次在第i车站的出发时间的安全性。
[0100]
在一个示例中，越行时间间隔条件的无越行的约束为：
[0101]
d[k,i]-d[k
′
,i]≥scd[k
′
,k,i]or d[k
′
,i]-d[k,i]≥scd[k,k
′
,i]
[0102]
其中，d[k,i]为第k车次在第i车站的出发时间，d[k
′
,i]为第k
′
车次在第i车站的出发时间，scd[k,k',i]为第k车次晚于第k
′
车次到达第i车站的越行安全间隔，scd[k
′
,k,i]为第k车次早于第k
′
车次到达第i车站的越行安全间隔。
[0103]
根据第k车次与第k
′
车次在第i车站的到达先后顺序不同，可以从无越行的约束中确定越行安全间隔所满足的约束。
[0104]
在一个示例中，第一候选出发时间可以基于过站时间间隔条件和越行时间间隔条件确定，具体的，可以将过站时间间隔条件和越行时间间隔条件写作一个第二出发时间条件的约束。
[0105]
例如，当第k车次晚于第k
′
车次过第i车站(或第k
′
车次晚于第k车次过第i车站)，且第i车站相对两列车为发发(出发车站-出发车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0106][0107]
其中，h
dd
[k',i]和h
dd
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，d[i]为从第i车站出发的车次的集合。n为车站总数。
[0108]
例如，当第k车次晚于第k
′
车次过第i车站(或第k
′
车次晚于第k车次过第i车站)，且第i车站相对两列车为通通(通过车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0109][0110]
其中，h
pp
[k',i]和h
pp
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合。n为车站总数。
[0111]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为发通(出发车站-通过车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为通发(通过车站-出发车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0112][0113]
其中，h
pd
[k',i]和h
dp
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合，d[i]为从第i车站出发的车次的集合。n为车站总数。
[0114]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为通发(通过车站-出发车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为发通(出发车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0115][0116]
其中，h
dp
[k',i]和h
pd
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合，d[i]为从第i车站出发的车次的集合。n为车站总数。
[0117]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为到到(到达车站-到达车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为到到(到达车站-到达车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0118][0119][0120]
其中，d[k,i-1]为第k车次在第i-1车站的出发时间，rt[k,i-1,i]为第k车次在第i-1车站到第i车站的运行时间，et[k,i-1,i]为第k车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，d[k',i-1]为第k'车次在第i-1车站的出发时间，rt[k',i-1,i]为第k'车次在第i-1车站到第i车站的运行时间，et[k',i-1,i]为第k'车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，h
aa
[k',i]和h
aa
[k,i]为第k车次和第k
′
车次的过站时间间隔。n为车站总数。
[0121]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为过到(通过车站-到达车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为到过(到达车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0122][0123]
其中，d[k,i-1]为第k车次在第i-1车站的出发时间，rt[k,i-1,i]为第k车次在第i-1车站到第i车站的运行时间，et[k,i-1,i]为第k车次在第i-1车站到第i车站的附加时间
(包括起车加速时间和停车减速时间)，d[k',i]为第k'车次在第i车站的出发时间，h
ap
[k',i]和h
pa
[k,i]为第k车次和第k
′
车次的过站时间间隔。n为车站总数。
[0124]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为到过(到达车站-通过车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为过到(通过车站-到达车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0125][0126]
其中，d[k',i-1]为第k'车次在第i-1车站的出发时间，rt[k',i-1,i]为第k'车次在第i-1车站到第i车站的运行时间，et[k',i-1,i]为第k'车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，d[k,i]为第k车次在第i车站的出发时间，h
pa
[k',i]和h
ap
[k,i]为第k车次和第k
′
车次的过站时间间隔。n为车站总数。
[0127]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s1032：根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间，包括：
[0128]
步骤s10321：根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站。
[0129]
步骤s10322：根据第k车次的始发时间、第一出发时间条件、第k车次的预设行驶速度、第k车次的预设停车时间，确定第k车次在第i车站的第二候选出发时间。
[0130]
根据本公开实施例，需要说明的是：
[0131]
第三过站类型，可以包括停靠车站、通过车站(非停靠车站)。具体的，在第k车次途径第i+1车站时，若需要停靠一段时间再发车，则第i+1车站相对第k车次的第三过站类型为停靠车站。在第k车次途径第i+1车站时，不停靠直接通过，则第i+1车站相对第k车次的第三过站类型为通过车站。
[0132]
根据本公开实施例，通过第一出发时间条件作为第k车次在第i车站的出发时间与在第i+1车站的出发时间的约束，可以提高所配置的第k车次在第i车站的出发时间的安全性。
[0133]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s1032：根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间，包括：
[0134]
在确定第k车次为接续车次的情况下，根据阈值时间间隔和第k车次接续前的历史车次的终点站到达时间，确定第k车次的始发时间。
[0135]
根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间。
[0136]
根据本公开实施例，需要说明的是：
[0137]
接续车次，可以理解为同一列车作为第q车次在上行行驶至终点站后，变更为第k车次并下行返回。上行行驶到达的终点站为下行行驶的始发站。
[0138]
阈值时间间隔，可以根据需要进行选择和调整，在此不做具体限定，保证列车在上
行行驶至终点站后停靠一段时间后，再下行出发。当列车为动车、高铁或地铁时，通过阈值时间间隔保证在上行行驶至终点站时，乘客有充足的时间在终点站下车，以及保证在下行行驶时，乘客有充足的时间在始发站上车。
[0139]
第k车次接续前的历史车次的终点站到达时间，可以理解为第q车次(历史车次)到达终点站的时间。
[0140]
根据本公开实施例，通过为接续车次设置阈值时间间隔，可以更加合理的得到作为接续车的第k车次的始发时间，以及进一步更合理的确定第k车次在第i车站的第二候选出发时间。
[0141]
在一个示例中，交路接续前后车(车次不同，但是同一列车)到发时间间隔大于20分钟，约束为：
[0142][0143]
其中，d[k,start[k]]为作为接续车的第k车次的始发站的始发时间，d[k
′
,end[k
′
]]为作为接续车之前的历史车的第k
′
车次的终点站到达时间，20为20分钟，60为60秒。表示第k车次和第k
′
车次对应的列车属于接续车集合。
[0144]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s1034：根据第一出发时间条件、第一候选出发时间、第k车次的始发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0145]
步骤s10341：根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站。
[0146]
步骤s10342：根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0147]
根据本公开实施例，需要说明的是：
[0148]
第三过站类型，可以包括停靠车站、通过车站(非停靠车站)。具体的，在第k车次途径第i+1车站时，若需要停靠一段时间再发车，则第i+1车站相对第k车次的第三过站类型为停靠车站。在第k车次途径第i+1车站时，不停靠直接通过，则第i+1车站相对第k车次的第三过站类型为通过车站。
[0149]
根据本公开实施例，通过第一出发时间条件作为第k车次在第i车站的出发时间与在第i+1车站的出发时间的约束，可以提高所配置的第k车次在第i车站的出发时间的安全性。
[0150]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s10342：根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0151]
在确定第k车次为接续车次的情况下，根据阈值时间间隔和第k车次接续前的历史车次的终点站到达时间，确定第k车次的始发时间。
[0152]
根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优
选出发时间。
[0153]
根据本公开实施例，需要说明的是：
[0154]
接续车次，可以理解为同一列车作为第q车次在上行行驶至终点站后，变更为第k车次并下行返回。上行行驶到达的终点站为下行行驶的始发站。
[0155]
阈值时间间隔，可以根据需要进行选择和调整，在此不做具体限定，保证列车在上行行驶至终点站后停靠一段时间后，再下行出发。当列车为动车、高铁或地铁时，通过阈值时间间隔保证在上行行驶至终点站时，乘客有充足的时间在终点站下车，以及保证在下行行驶时，乘客有充足的时间在始发站上车。
[0156]
第k车次接续前的历史车次的终点站到达时间，可以理解为第q车次(历史车次)到达终点站的时间。
[0157]
根据本公开实施例，通过为接续车次设置阈值时间间隔，可以更加合理的得到作为接续车的第k车次的始发时间，以及进一步更合理的确定第k车次在第i车站的第二候选出发时间。
[0158]
在一个示例中，交路接续前后车(车次不同，但是同一列车)到发时间间隔大于20分钟，约束为：
[0159][0160]
其中，d[k,start[k]]为作为接续车的第k车次的始发站的始发时间，d[k
′
,end[k
′
]]为作为接续车之前的历史车的第k
′
车次的终点站到达时间，20为20分钟，60为60秒。表示第k车次和第k
′
车次对应的列车属于接续车集合。
[0161]
在一个示例中，在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s10342：根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0162]
在确定第k车次为接续车次的情况下，根据阈值时间间隔和第q车次的终点站到达时间，确定第k车次的始发时间。
[0163]
根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0164]
根据本公开实施例，需要说明的是：
[0165]
第q车次的终点站与第k车次的始发站为同一车站。第q车次到达该车站的时间晚于第k车次。
[0166]
根据本公开实施例，通过为接续车次设置阈值时间间隔，可以更加合理的得到作为接续车的第k车次的始发时间，以及进一步更合理的确定第k车次在第i车站的第二候选出发时间。
[0167]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s10321和/或步骤s10341：根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站，包括：
[0168]
确定n个车站中第i+1车站对应第k车次的第三过站类型。
[0169]
在第三过站类型为非停靠车站的情况下，根据第i+1车站的出发时间、第i车站的出发时间、第k车次在第i车站至第i+1车站间的运行时间和附加时间，确定相邻的第i车站和第i+1车站的第一出发时间条件。
[0170]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0171]
根据本公开实施例，根据n个车站中第i+1车站对应第k车次的第三过站类型，可以确定出相邻的第i车站和第i+1车站的第一出发时间条件。
[0172]
在一个示例中，两站间出发时间间隔满足列车运行时间以及附加时间约束：
[0173]
如果第i+1车站不是停靠站，则第一出发时间条件的约束为：
[0174][0175]
其中，m为车次总数，pass[k]通过第i+1车站的车次的集合。
[0176]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s10321和/或步骤s10341：根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站，包括：
[0177]
确定n个车站中第i+1车站对应第k车次的第三过站类型。
[0178]
在第三过站类型为停靠车站的情况下，根据第i+1车站的出发时间、第i车站的出发时间、第k车次在第i车站至第i+1车站间的运行时间、附加时间和停车时间阈值，确定相邻的第i车站和第i+1车站的第一出发时间条件。
[0179]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0180]
根据本公开实施例，根据n个车站中第i+1车站对应第k车次的第三过站类型，可以确定出相邻的第i车站和第i+1车站的第一出发时间条件。
[0181]
在一个示例中，两站间出发时间间隔满足列车运行时间以及附加时间约束：
[0182]
如果第i+1车站是停靠站，则第一出发时间条件的约束为：
[0183][0184][0185]
其中，m为车次总数，w
min
为最小停站时间，w
max
为最大停站时间，stop[k]为停靠第i+1车站的车次的集合。
[0186]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s102：确定n个车站中第i车站对应的第k
′
车次，之后，还包括：
[0187]
在k
′
大于1的情况下，根据第一出发时间条件、第二出发时间条件和第k
″
车次在第i车站的优选出发时间，利用约束传播算法，确定第k
′
车次在第i车站的优选出发时间。其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔，第k
″
车次为先于第k
′
车次途径第i车站的相邻车次。
[0188]
根据本公开实施例，可以确定第k
′
车次在第i车站的优选出发时间。
[0189]
在一种实施方式中，本公开实施例提供了一种构建列车运行图的方法，包括步骤s101至步骤s104，其中，步骤s102：确定n个车站中第i车站对应的第k
′
车次，之后，还包括：
[0190]
在k
′
等于1的情况下，根据第一出发时间条件和第k
′
车次的始发时间，利用约束传播算法，确定第k
′
车次在第i车站的优选出发时间。
[0191]
根据本公开实施例，可以确定第k
′
车次在第i车站的优选出发时间。
[0192]
在一种实施方式中，若根据本公开上述任一实施例，无法得到第k车次对应的n个车站中的每一个车站的出发时间，则可以调整第k车次的停站计划和始发时间窗口，或调整与第k车次的无法求解的车站对应的关联车次的停站计划和始发时间窗口。
[0193]
根据本公开实施例，需要说明的是：
[0194]
停站计划，可以理解为列车预设的始发站、通过站、停靠站、终点站。
[0195]
始发时间窗口，可以理解为列车在始发站出发的时间区间。例如，出发时间在给定始发时间窗口内：
[0196][0197]
其中，ts[k]为第k车次的计划出发时间，tol[k]为可变动偏差，d[k，start[k]]为第k车次的始发站。
[0198]
如图5所示，在一个应用示例中，对于一条高铁线路，在输入给定数量的车次、各车次的停站计划、始发时间窗口后，经由构建的数学模型以及给定的停站计划以及始发时间窗口，可以求解出每个列车的各个对应车站的出发时间以及生成时刻表结果(列车运行图)。若数学模型求解过程中表明问题无解，则表示输入的各车次的停站计划、始发时间窗口会导致部分约束(第一出发时间条件和第二出发时间条件)无法被满足，需要修改车次停站计划或者始发时间窗口重新求解。
[0199]
其中，目标函数为找可行解问题，目标函数为0。
[0200]
数学模型为：
[0201]
定义决策变量为：
[0202]
d[k,i]∈z∩[0,24
×
60
×
60]
[0203]
其中，z为取整数的系数，d[k,i]为车次k在车站i的出发时间。24
×
60
×
60表示24小时乘以60分钟乘以60秒钟。
[0204]
数学模型定义约束包括：
[0205]
定义start[k],end[k],pass[k],stop[k]分别为第k车次的出发站，终点站，通过站，停靠站，ts[k]为第k车次的计划出发时间，tol[k]为可变动偏差。
[0206]
出发时间在给定窗口内：
[0207][0208]
其中，ts[k],tol[k]为第k车次的计划出发时间以及可变动偏差，d[k，start[k]]为第k车次的始发站，m为总车次数量。
[0209]
定义rt[k,i,i+1],et[k,i,i+1]为第k车次在第i车站到第i+1车站的运行时间以及附加时间(包括起车加速时间、停车减速时间)。
[0210]
两站间出发时间间隔满足列车运行时间以及附加时间约束：
[0211]
如果第i+1车站不是停靠站，则第一出发时间条件的约束为：
[0212][0213]
其中，m为车次总数，pass[k]通过第i+1车站的车次的集合。
[0214]
如果第i+1车站是停靠站，则第一出发时间条件的约束为：
[0215][0216][0217]
其中，m为车次总数，w
min
为最小停站时间，w
max
为最大停站时间，stop[k]为停靠第i+1车站的车次的集合。
[0218]
各车次终点站的到达时间设置为：
[0219]
d[k,end[k]]＝d[k,end[k]-1]+rt[k,end[k]-1,end[k]]+et[k,end[k]-1,end[k]
[0220]
其中，d[k,end[k]]为终点站的到达时间，d[k,end[k]-1]为终点站的前一站的出发时间。
[0221]
定义当第k车次晚于第k
′
车次过第i车站(或第k
′
车次晚于第k车次过第i车站)，且第i车站相对两列车为发发(出发车站-出发车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0222][0223]
其中，h
dd
[k',i]和h
dd
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，d[i]为从第i车站出发的车次的集合。
[0224]
定义当第k车次晚于第k
′
车次过第i车站(或第k
′
车次晚于第k车次过第i车站)，且第i车站相对两列车为通通(通过车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0225][0226]
其中，h
pp
[k',i]和h
pp
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合。
[0227]
定义当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为发通(出发车站-通过车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为通发(通过车站-出发车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔条件的组合约束为：
[0228][0229]
其中，h
pd
[k',i]和h
dp
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合，d[i]为从第i车站出发的车次的集合。
[0230]
例如，当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为发通(通过车站-出发车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为通发(出发车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件和越行时间间隔
条件的组合约束为：
[0231][0232][0233]
其中，h
dp
[k',i]和h
pd
[k,i]为第k车次和第k
′
车次的过站时间间隔，scd[k,k',i]和scd[k',k,i]为第k车次和第k
′
车次的越行时间间隔，p[i]为从第i车站通过的车次的集合，d[i]为从第i车站出发的车次的集合。
[0234]
定义当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为到到(到达车站-到达车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为到到(到达车站-到达车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0235][0236]
其中，d[k,i-1]为第k车次在第i-1车站的出发时间，rt[k,i-1,i]为第k车次在第i-1车站到第i车站的运行时间，et[k,i-1,i]为第k车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，d[k',i-1]为第k'车次在第i-1车站的出发时间，rt[k',i-1,i]为第k'车次在第i-1车站到第i车站的运行时间，et[k',i-1,i]为第k'车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，h
aa
[k',i]和h
aa
[k,i]为第k车次和第k
′
车次的过站时间间隔。
[0237]
定义当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为过到(通过车站-到达车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为到过(到达车站-通过车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0238][0239]
其中，d[k,i-1]为第k车次在第i-1车站的出发时间，rt[k,i-1,i]为第k车次在第i-1车站到第i车站的运行时间，et[k,i-1,i]为第k车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，h
ap
[k',i]和h
pa
[k,i]为第k车次和第k
′
车次的过站时间间隔。
[0240]
定义当第k车次晚于第k
′
车次过第i车站，且第i车站相对两列车为到过(到达车站-通过车站)过站类型时，或第k
′
车次晚于第k车次过第i车站，且第i车站相对两列车为过到(通过车站-到达车站)过站类型时，定义两列车间的过站时间间隔条件的约束为：
[0241]
[0242]
其中，d[k',i-1]为第k'车次在第i-1车站的出发时间，rt[k',i-1,i]为第k'车次在第i-1车站到第i车站的运行时间，et[k',i-1,i]为第k'车次在第i-1车站到第i车站的附加时间(包括起车加速时间和停车减速时间)，h
pa
[k',i]和h
ap
[k,i]为第k车次和第k
′
车次的过站时间间隔。
[0243]
定义交路接续前后车(车次不同，但是同一列车)到发时间间隔大于20分钟的约束为：
[0244][0245]
其中，d[k,start[k]]为作为接续车的第k车次的始发站的始发时间，d[k
′
,end[k
′
]]为作为接续车之前的历史车的第k
′
车次的终点站到达时间，20为20分钟，60为60秒。表示第k车次和第k
′
车次对应的列车属于接续车集合。
[0246]
定义接续后车与其他车次存在发到时间间隔约束为：
[0247][0248]
其中，d[k,start[k]]为作为接续车的第k车次的始发站的始发时间，d[k
′
,end[k
′
]]为其他车次(第k
′
车次)终点站的到达时间，h
da
[k,start[k]]第k车次的发到时间间隔。
[0249]
在一个示例中，根据第一过站类型和第二过站类型的不同组合，确定的第二出发时间条件中的过站时间间隔条件有所不同，也即是说，第k车次在第i车站的出发时间和第k
′
车次在第i车站的出发时间的安全时间间隔会有所不同。例如，第i车站相对第k车次的第一过站类型为出发车站，第i车站相对第k
′
车次的第一过站类型亦为出发车站时，确定的过站时间间隔条件的两列车间的出发时间的安全时间间隔约束为：
[0250][0251]
其中，d[k,i]为第k车次在第i车站的出发时间，d[k
′
,i]为第k
′
车次在第i车站的出发时间，h
dd
[k,i]和h
dd
[k
′
,i]为第k车次在第i车站的出发时间和第k
′
车次在第i车站的出发时间的安全时间间隔，d[i]为从第i车站出发的车次的集合。
[0252]
需要说明的是，在第k车次晚于第k
′
车次到达第i车站时，选用d[k,i]-d[k
′
,i]≥h
dd
[k,i]作为两列车间的出发时间的安全时间间隔约束。在第k
′
车次晚于第k车次到达第i车站时，选用d[k
′
,i]-d[k,i]≥h
dd
[k
′
,i]作为两列车间的出发时间的安全时间间隔约束。可以通过引入变量z[count]和z[count+1]确定第k车次晚于第k
′
车次到达第i车站，还是第k
′
车次晚于第k车次到达第i车站。
[0253]
z[count],z[count+1]∈{0,1}
[0254]
d[k,i]-d[k
′
,i]≥h
dd
[k,i]-m(1-z[count])
[0255]
d[k
′
,i]-d[k,i]≥h
dd
[k
′
,i]-m(1-z[count+1])
[0256]
z[count]+z[count+1]≥1
[0257]
其中，m为系数，d[k,i]为第k车次在第i车站的出发时间，d[k
′
，i]为第k
′
车次在第i车站的出发时间，h
dd
[k,i]和h
dd
[k
′
,i]为第k车次在第i车站的出发时间和第k
′
车次在第i车站的出发时间的安全时间间隔。
[0258]
在根据上述公式，计算出z[count]为1时，表示第k车次后到晚于第k
′
车次到达第i
车站，选用d[k,i]-d[k
′
,i]≥h
dd
[k,i]作为两列车间的出发时间的安全时间间隔约束。计算出z[count+1]为1时，表示第k
′
车次晚于第k车次到达第i车站，选用d[k
′
,i]-d[k,i]≥h
dd
[k
′
,i]作为两列车间的出发时间的安全时间间隔约束。
[0259]
如图6所示，本公开实施例提供了一种构建列车运行图的装置，包括：
[0260]
第一确定模块610，用于确定m个车次中第k车次对应的n个车站。其中，m、k、n均大于1。
[0261]
第二确定模块620，用于确定n个车站中第i车站对应的第k
′
车次。其中，k
′
和i均大于等于1，第k
′
车次为先于第k车次途径第i车站的相邻车次。
[0262]
第三确定模块630，用于根据第一出发时间条件、第二出发时间条件和第k
′
车次在第i车站的优选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔。以及
[0263]
运行图模块640，用于根据m个车次中的每个车次的优选出发时间，构建列车运行图。
[0264]
在一种实施方式中，第三确定模块630包括：
[0265]
第一确定子模块，用于根据第二出发时间条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在第i车站的第一候选出发时间。
[0266]
第二确定子模块，用于根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间。
[0267]
第三确定子模块，用于根据第一候选出发时间和第二候选出发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0268]
在一种实施方式中，第三确定模块630包括：
[0269]
第一确定子模块，用于根据第二出发时间条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在第i车站的第一候选出发时间。
[0270]
第四确定子模块，用于根据第一出发时间条件、第一候选出发时间、第k车次的始发时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0271]
在一种实施方式中，其中，第一确定子模块用于：
[0272]
确定第i车站相对第k车次的第一过站类型。
[0273]
确定第i车站相对第k
′
车次的第二过站类型。
[0274]
根据第一过站类型和第二过站类型，确定第二出发时间条件中的过站时间间隔条件。
[0275]
根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在i车站的第一候选出发时间。
[0276]
在一种实施方式中，其中，根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定第k车次在i车站的第一候选出发时间，包括：
[0277]
根据过站时间间隔条件和第k
′
车次在第i车站的优选出发时间，确定初始候选出发时间。
[0278]
根据第k车次在第i车站至第i+1车站间的运行时间、附加时间、初始候选出发时间、第k
′
车次在第i车站至第i+1车站间的运行时间、第二附加时间和第k
′
车次在第i车站的
优选出发时间，确定第k车次与第k
′
车次之间的越行时间间隔。
[0279]
根据第二出发时间条件中的越行时间间隔条件、越行时间间隔和初始候选出发时间，确定第k车次在i车站的第一候选出发时间。
[0280]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0281]
在一种实施方式中，其中，第二确定子模块用于：
[0282]
根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站。
[0283]
根据第k车次的始发时间、第一出发时间条件、第k车次的预设行驶速度、第k车次的预设停车时间，确定第k车次在第i车站的第二候选出发时间。
[0284]
在一种实施方式中，其中，第二确定子模块用于：
[0285]
在确定第k车次为接续车次的情况下，根据阈值时间间隔和第k车次接续前的历史车次的终点站到达时间，确定第k车次的始发时间。
[0286]
根据第一出发时间条件和第k车次的始发时间，确定第k车次在第i车站的第二候选出发时间。
[0287]
在一种实施方式中，其中，第四确定子模块用于：
[0288]
根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件。其中，第i+1车站为第i车站之后的相邻车站。
[0289]
根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0290]
在一种实施方式中，其中，根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间，包括：
[0291]
在确定第k车次为接续车次的情况下，根据阈值时间间隔和第k车次接续前的历史车次的终点站到达时间，确定第k车次的始发时间。
[0292]
根据第一出发时间条件、第一候选出发时间、第k车次的始发时间、第k车次的预设行驶速度、第k车次的预设停车时间，利用约束传播算法，确定第k车次分别在n个车站的优选出发时间。
[0293]
在一种实施方式中，其中，根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件，包括：
[0294]
确定n个车站中第i+1车站对应第k车次的第三过站类型。
[0295]
在第三过站类型为非停靠车站的情况下，根据第i+1车站的出发时间、第i车站的出发时间、第k车次在第i车站至第i+1车站间的运行时间和附加时间，确定相邻的第i车站和第i+1车站的第一出发时间条件。
[0296]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0297]
在一种实施方式中，其中，根据n个车站中第i+1车站对应第k车次的第三过站类型，确定相邻的第i车站和第i+1车站的第一出发时间条件，包括：
[0298]
确定n个车站中第i+1车站对应第k车次的第三过站类型。
[0299]
在第三过站类型为停靠车站的情况下，根据第i+1车站的出发时间、第i车站的出
发时间、第k车次在第i车站至第i+1车站间的运行时间、附加时间和停车时间阈值，确定相邻的第i车站和第i+1车站的第一出发时间条件。
[0300]
其中，附加时间包括第k车次的起车加速时间和/或停车减速时间。
[0301]
在一种实施方式中，构建列车运行图的装置，还包括：
[0302]
第四确定模块，用于在k
′
大于1的情况下，根据第一出发时间条件、第二出发时间条件和第k
″
车次在第i车站的优选出发时间，利用约束传播算法，确定第k
′
车次在第i车站的优选出发时间。其中，第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔，第k
″
车次为先于第k
′
车次途径第i车站的相邻车次。
[0303]
在一种实施方式中，构建列车运行图的装置，还包括：
[0304]
第五确定模块，用于在k
′
等于1的情况下，根据第一出发时间条件和第k
′
车次的始发时间，利用约束传播算法，确定第k
′
车次在第i车站的优选出发时间。
[0305]
本公开实施例的装置的各模块、子模块的具体功能和示例的描述，可以参见上述方法实施例中对应步骤的相关描述，在此不再赘述。
[0306]
本公开的技术方案中，所涉及的用户个人信息的获取，存储和应用等，均符合相关法律法规的规定，且不违背公序良俗。
[0307]
根据本公开的实施例，本公开还提供了一种电子设备、一种可读存储介质和一种计算机程序产品。
[0308]
图7示出了可以用来实施本公开的实施例的示例电子设备700的示意性框图。电子设备旨在表示各种形式的数字计算机，诸如，膝上型计算机、台式计算机、工作台、个人数字助理、服务器、刀片式服务器、大型计算机、和其它适合的计算机。电子设备还可以表示各种形式的移动装置，诸如，个人数字助理、蜂窝电话、智能电话、可穿戴设备和其它类似的计算装置。本文所示的部件、它们的连接和关系、以及它们的功能仅仅作为示例，并且不意在限制本文中描述的和/或者要求的本公开的实现。
[0309]
如图7所示，设备700包括计算单元701，其可以根据存储在只读存储器(rom)702中的计算机程序或者从存储单元708加载到随机访问存储器(ram)703中的计算机程序，来执行各种适当的动作和处理。在ram 703中，还可存储设备700操作所需的各种程序和数据。计算单元701、rom 702以及ram 703通过总线704彼此相连。输入/输出(i/o)接口705也连接至总线704。
[0310]
设备700中的多个部件连接至i/o接口705，包括：输入单元706，例如键盘、鼠标等。输出单元707，例如各种类型的显示器、扬声器等。存储单元708，例如磁盘、光盘等。以及通信单元709，例如网卡、调制解调器、无线通信收发机等。通信单元709允许设备700通过诸如因特网的计算机网络和/或各种电信网络与其他设备交换信息/数据。
[0311]
计算单元701可以是各种具有处理和计算能力的通用和/或专用处理组件。计算单元701的一些示例包括但不限于中央处理单元(cpu)、图形处理单元(gpu)、各种专用的人工智能(ai)计算芯片、各种运行机器学习模型算法的计算单元、数字信号处理器(dsp)、以及任何适当的处理器、控制器、微控制器等。计算单元701执行上文所描述的各个方法和处理，例如构建列车运行图的方法。例如，在一些实施例中，构建列车运行图的方法可被实现为计算机软件程序，其被有形地包含于机器可读介质，例如存储单元708。在一些实施例中，计算
机程序的部分或者全部可以经由rom 702和/或通信单元709而被载入和/或安装到设备700上。当计算机程序加载到ram 703并由计算单元701执行时，可以执行上文描述的构建列车运行图的方法的一个或多个步骤。备选地，在其他实施例中，计算单元701可以通过其他任何适当的方式(例如，借助于固件)而被配置为执行构建列车运行图的方法。
[0312]
本文中以上描述的系统和技术的各种实施方式可以在数字电子电路系统、集成电路系统、现场可编程门阵列(fpga)、专用集成电路(asic)、专用标准产品(assp)、芯片上系统的系统(soc)、负载可编程逻辑设备(cpld)、计算机硬件、固件、软件、和/或它们的组合中实现。这些各种实施方式可以包括：实施在一个或者多个计算机程序中，该一个或者多个计算机程序可在包括至少一个可编程处理器的可编程系统上执行和/或解释，该可编程处理器可以是专用或者通用可编程处理器，可以从存储系统、至少一个输入装置、和至少一个输出装置接收数据和指令，并且将数据和指令传输至该存储系统、该至少一个输入装置、和该至少一个输出装置。
[0313]
用于实施本公开的方法的程序代码可以采用一个或多个编程语言的任何组合来编写。这些程序代码可以提供给通用计算机、专用计算机或其他可编程数据处理装置的处理器或控制器，使得程序代码当由处理器或控制器执行时使流程图和/或框图中所规定的功能/操作被实施。程序代码可以完全在机器上执行、部分地在机器上执行，作为独立软件包部分地在机器上执行且部分地在远程机器上执行或完全在远程机器或服务器上执行。
[0314]
在本公开的上下文中，机器可读介质可以是有形的介质，其可以包含或存储以供指令执行系统、装置或设备使用或与指令执行系统、装置或设备结合地使用的程序。机器可读介质可以是机器可读信号介质或机器可读储存介质。机器可读介质可以包括但不限于电子的、磁性的、光学的、电磁的、红外的、或半导体系统、装置或设备，或者上述内容的任何合适组合。机器可读存储介质的更具体示例会包括基于一个或多个线的电气连接、便携式计算机盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦除可编程只读存储器(eprom或快闪存储器)、光纤、便捷式紧凑盘只读存储器(cd-rom)、光学储存设备、磁储存设备、或上述内容的任何合适组合。
[0315]
为了提供与用户的交互，可以在计算机上实施此处描述的系统和技术，该计算机具有：用于向用户显示信息的显示装置(例如，crt(阴极射线管)或者lcd(液晶显示器)监视器)。以及键盘和指向装置(例如，鼠标或者轨迹球)，用户可以通过该键盘和该指向装置来将输入提供给计算机。其它种类的装置还可以用于提供与用户的交互。例如，提供给用户的反馈可以是任何形式的传感反馈(例如，视觉反馈、听觉反馈、或者触觉反馈)。并且可以用任何形式(包括声输入、语音输入、或者触觉输入)来接收来自用户的输入。
[0316]
可以将此处描述的系统和技术实施在包括后台部件的计算系统(例如，作为数据服务器)、或者包括中间件部件的计算系统(例如，应用服务器)、或者包括前端部件的计算系统(例如，具有图形用户界面或者网络浏览器的用户计算机，用户可以通过该图形用户界面或者该网络浏览器来与此处描述的系统和技术的实施方式交互)、或者包括这种后台部件、中间件部件、或者前端部件的任何组合的计算系统中。可以通过任何形式或者介质的数字数据通信(例如，通信网络)来将系统的部件相互连接。通信网络的示例包括：局域网(lan)、广域网(wan)和互联网。
[0317]
计算机系统可以包括客户端和服务器。客户端和服务器一般远离彼此并且通常通
过通信网络进行交互。通过在相应的计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。服务器可以是云服务器，也可以为分布式系统的服务器，或者是结合了区块链的服务器。
[0318]
应该理解，可以使用上面所示的各种形式的流程，重新排序、增加或删除步骤。例如，本公开中记载的各步骤可以并行地执行也可以顺序地执行也可以不同的次序执行，只要能够实现本公开公开的技术方案所期望的结果，本文在此不进行限制。
[0319]
上述具体实施方式，并不构成对本公开保护范围的限制。本领域技术人员应该明白的是，根据设计要求和其他因素，可以进行各种修改、组合、子组合和替代。任何在本公开的原则之内所作的修改、等同替换和改进等，均应包含在本公开保护范围之内。

技术特征：
1.一种构建列车运行图的方法，包括：确定m个车次中第k车次对应的n个车站；其中，m、k、n均大于1；确定所述n个车站中第i车站对应的第k
′
车次；其中，k
′
和i均大于等于1，所述第k
′
车次为先于所述第k车次途径所述第i车站的相邻车次；根据第一出发时间条件、第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间；其中，所述第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，所述第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔；以及根据所述m个车次中的每个车次的优选出发时间，构建列车运行图。2.根据权利要求1所述的方法，其中，所述根据第一出发时间条件、第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间，包括：根据第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述第i车站的第一候选出发时间；根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间；根据所述第一候选出发时间和所述第二候选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。3.根据权利要求1所述的方法，其中，所述根据第一出发时间条件、第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间，包括：根据第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述第i车站的第一候选出发时间；根据第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。4.根据权利要求2或3所述的方法，其中，所述根据第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述i车站的第一候选出发时间，包括：确定所述第i车站相对所述第k车次的第一过站类型；确定所述第i车站相对所述第k
′
车次的第二过站类型；根据所述第一过站类型和所述第二过站类型，确定第二出发时间条件中的过站时间间隔条件；根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述i车站的第一候选出发时间。5.根据权利要求4所述的方法，其中，所述根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述i车站的第一候选出发时间，包括：根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定初始候选出发时间；
根据所述第k车次在所述第i车站至第i+1车站间的运行时间、附加时间、所述初始候选出发时间、所述第k
′
车次在所述第i车站至第i+1车站间的运行时间、第二附加时间和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次与所述第k
′
车次之间的越行时间间隔；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第二出发时间条件中的越行时间间隔条件、所述越行时间间隔和所述初始候选出发时间，确定所述第k车次在所述i车站的第一候选出发时间；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。6.根据权利要求2所述的方法，其中，所述根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间，包括：根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第k车次的始发时间、所述第一出发时间条件、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，确定所述第k车次在所述第i车站的第二候选出发时间。7.根据权利要求2所述的方法，其中，所述根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间，包括：在确定所述第k车次为接续车次的情况下，根据阈值时间间隔和所述第k车次接续前的历史车次的终点站到达时间，确定所述第k车次的始发时间；根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间。8.根据权利要求3所述的方法，其中，所述根据第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间，包括：根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。9.根据权利要求8所述的方法，其中，所述根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间，包括：在确定所述第k车次为接续车次的情况下，根据阈值时间间隔和所述第k车次接续前的历史车次的终点站到达时间，确定所述第k车次的始发时间；根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。10.根据权利要求6或8所述的方法，其中，所述根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件，
包括：确定所述n个车站中第i+1车站对应所述第k车次的第三过站类型；在所述第三过站类型为非停靠车站的情况下，根据所述第i+1车站的出发时间、所述所述第i车站的出发时间、所述第k车次在所述第i车站至第i+1车站间的运行时间和附加时间，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。11.根据权利要求6或8所述的方法，其中，所述根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件，包括：确定所述n个车站中第i+1车站对应所述第k车次的第三过站类型；在所述第三过站类型为停靠车站的情况下，根据所述第i+1车站的出发时间、所述所述第i车站的出发时间、所述第k车次在所述第i车站至第i+1车站间的运行时间、附加时间和停车时间阈值，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。12.根据权利要求1所述的方法，其中，所述确定所述n个车站中第i车站对应的第k
′
车次，之后，还包括：在k
′
大于1的情况下，根据第一出发时间条件、第二出发时间条件和第k
″
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k
′
车次在所述第i车站的优选出发时间；其中，所述第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，所述第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔，所述第k
″
车次为先于所述第k
′
车次途径所述第i车站的相邻车次。13.根据权利要求1所述的方法，其中，所述确定所述n个车站中第i车站对应的第k
′
车次，之后，还包括：在k
′
等于1的情况下，根据第一出发时间条件和所述第k
′
车次的始发时间，利用约束传播算法，确定所述第k
′
车次在所述第i车站的优选出发时间。14.一种构建列车运行图的装置，包括：第一确定模块，用于确定m个车次中第k车次对应的n个车站；其中，m、k、n均大于1；第二确定模块，用于确定所述n个车站中第i车站对应的第k
′
车次；其中，k
′
和i均大于等于1，所述第k
′
车次为先于所述第k车次途径所述第i车站的相邻车次；第三确定模块，用于根据第一出发时间条件、第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间；其中，所述第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，所述第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔；以及运行图模块，用于根据所述m个车次中的每个车次的优选出发时间，构建列车运行图。15.根据权利要求14所述的装置，其中，所述第三确定模块包括：第一确定子模块，用于根据第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述第i车站的第一候选出发时间；第二确定子模块，用于根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间；
第三确定子模块，用于根据所述第一候选出发时间和所述第二候选出发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。16.根据权利要求14所述的装置，其中，所述第三确定模块包括：第一确定子模块，用于根据第二出发时间条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述第i车站的第一候选出发时间；第四确定子模块，用于根据第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。17.根据权利要求15或16所述的装置，其中，所述第一确定子模块用于：确定所述第i车站相对所述第k车次的第一过站类型；确定所述第i车站相对所述第k
′
车次的第二过站类型；根据所述第一过站类型和所述第二过站类型，确定第二出发时间条件中的过站时间间隔条件；根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述i车站的第一候选出发时间。18.根据权利要求17所述的装置，其中，所述根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次在所述i车站的第一候选出发时间，包括：根据所述过站时间间隔条件和所述第k
′
车次在所述第i车站的优选出发时间，确定初始候选出发时间；根据所述第k车次在所述第i车站至第i+1车站间的运行时间、附加时间、所述初始候选出发时间、所述第k
′
车次在所述第i车站至第i+1车站间的运行时间、第二附加时间和所述第k
′
车次在所述第i车站的优选出发时间，确定所述第k车次与所述第k
′
车次之间的越行时间间隔；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第二出发时间条件中的越行时间间隔条件、所述越行时间间隔和所述初始候选出发时间，确定所述第k车次在所述i车站的第一候选出发时间；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。19.根据权利要求15所述的装置，其中，所述第二确定子模块用于：根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第k车次的始发时间、所述第一出发时间条件、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，确定所述第k车次在所述第i车站的第二候选出发时间。20.根据权利要求15所述的装置，其中，所述第二确定子模块用于：在确定所述第k车次为接续车次的情况下，根据阈值时间间隔和所述第k车次接续前的历史车次的终点站到达时间，确定所述第k车次的始发时间；根据第一出发时间条件和所述第k车次的始发时间，确定所述第k车次在所述第i车站的第二候选出发时间。21.根据权利要求16所述的装置，其中，所述第四确定子模块用于：根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i
车站和所述第i+1车站的第一出发时间条件；其中，所述第i+1车站为所述第i车站之后的相邻车站；根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。22.根据权利要求21所述的装置，其中，所述根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间，包括：在确定所述第k车次为接续车次的情况下，根据阈值时间间隔和所述第k车次接续前的历史车次的终点站到达时间，确定所述第k车次的始发时间；根据所述第一出发时间条件、所述第一候选出发时间、所述第k车次的始发时间、所述第k车次的预设行驶速度、所述第k车次的预设停车时间，利用约束传播算法，确定所述第k车次分别在所述n个车站的优选出发时间。23.根据权利要求19或21所述的装置，其中，所述根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件，包括：确定所述n个车站中第i+1车站对应所述第k车次的第三过站类型；在所述第三过站类型为非停靠车站的情况下，根据所述第i+1车站的出发时间、所述所述第i车站的出发时间、所述第k车次在所述第i车站至第i+1车站间的运行时间和附加时间，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。24.根据权利要求19或21所述的装置，其中，所述根据所述n个车站中第i+1车站对应所述第k车次的第三过站类型，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件，包括：确定所述n个车站中第i+1车站对应所述第k车次的第三过站类型；在所述第三过站类型为停靠车站的情况下，根据所述第i+1车站的出发时间、所述所述第i车站的出发时间、所述第k车次在所述第i车站至第i+1车站间的运行时间、附加时间和停车时间阈值，确定相邻的所述第i车站和所述第i+1车站的第一出发时间条件；其中，所述附加时间包括所述第k车次的起车加速时间和/或停车减速时间。25.根据权利要求14所述的装置，还包括：第四确定模块，用于在k
′
大于1的情况下，根据第一出发时间条件、第二出发时间条件和第k
″
车次在所述第i车站的优选出发时间，利用约束传播算法，确定所述第k
′
车次在所述第i车站的优选出发时间；其中，所述第一出发时间条件用于约束同一车次的相邻两车站的出发时间间隔，所述第二出发时间条件用于约束途径同一车站的相邻两车次的出发时间间隔，所述第k
″
车次为先于所述第k
′
车次途径所述第i车站的相邻车次。26.根据权利要求14所述的装置，还包括：第五确定模块，用于在k
′
等于1的情况下，根据第一出发时间条件和所述第k
′
车次的始发时间，利用约束传播算法，确定所述第k
′
车次在所述第i车站的优选出发时间。
27.一种电子设备，包括：至少一个处理器；以及与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行权利要求1至13中任一项所述的方法。28.一种存储有计算机指令的非瞬时计算机可读存储介质，其中，所述计算机指令用于使所述计算机执行根据权利要求1至13中任一项所述的方法。29.一种计算机程序产品，包括计算机程序，所述计算机程序在被处理器执行时实现根据权利要求1至13中任一项所述的方法。

技术总结
本公开提供了构建列车运行图的方法、装置、设备以及存储介质，涉及计算机技术领域，尤其涉及智能交通、云计算技术领域。具体实现方案为：确定M个车次中第k车次对应的N个车站；确定N个车站中第i车站对应的第k


技术研发人员：李飞 解鑫 刘颖 徐进 陈凯 许铭 袁晓敏 张金义 金莹 李瑞锋 张智俊 刘天源
受保护的技术使用者：重庆百智智慧科技有限公司
技术研发日：2022.11.14
技术公布日：2023/3/14