本发明提供了一种基于路径分配客流的高铁列车开行路径优化方法及装置，首先基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，并进一步确定出高铁列车开行的候选始发站与候选终到站；然后结合计算出的高铁出行路径客流量分布，选择路径作为高铁列车候选开行路径；接着以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；最后设计列车候选路径开行数量方案的解编码，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解。本发明具有操作性强、计算速度快等优点。
1.基于路径分配客流的高铁列车开行路径优化方法，其特征在于，包括：S1：基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
S2：根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
S3：结合计算出的高铁出行路径客流量分布，在步骤S2中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
S4：以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
S5：设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径，染色体的长度为开行列车数量；
S401：选择各高铁列车候选开行路径组织的开行列车数量作为模型决策变量 ；
S402：选择模型优化目标，构建高铁列车候选路径开行数量优化模型：其中，第一部分 为开行列车总运营里程，表示列车运营每公里的平均成本，为路径 的运营里程；第二部分 为开行列车组织成本，表示组织一列列车的平均成本， 表示列车候选路径集合，高铁列车候选路径开行数量优化模型的约束条件包括：约束条件1：
其中， 表示路径 上开行列车的定员， 表示路径 与区间 的关联关系，若区间 属于路径 ，则 ；否则， ， 为区间 的总出行量；
其中， 为线路区间 全天运营时间范围开行的最大列车数量， 为列车开行路径 与线路区间 的关联参数，若线路区间 属于列车开行路径 ，则为，否则为0；
其中，为给定的浮动列车数， 与 分别表站点 需要组织开行的始发列车数和终到列车数；
S501：构造候选路径开行列车数量方案的解编码，其编码长度为候选路径的数量，每个位编码对应一条候选路径，编码采用非负整数表示，其中，当某位编码为0时表示相对应候选路径不组织开行列车；否则，组织开行相应整数数量的列车；
S502：按设计的编码方案随机生成 个初始个体，添加到初始种群 中，若产生不符合要求的个体，则抛弃该个体重新随机生成，直至获得 个初始个体；
S503：选择操作：计算种群 中全部个体的适应度 ，按适应度从大到小排序，并按如下公式计算各个体的选择概率 与累积概率 ，作为群体中每个个体被选择到下一代种群中的概率：随机产生一个随机数 ，并选择满足 的个体 ，重复此直至选择获得个个体作为下一代种群个体；其中，为个体 ，为个体 的适应度， 表示从种群 中选择出适应度最大的个体的适应度，为个体的选择概率；
S504：交叉操作：随机产生一个随机数 ，若其小于设置的交叉概率 ，则选择两个染色体 与 进行交叉：其中， 均为0‑1的随机数， , 为染色体 与 交叉后的子代染色体；
S505：变异操作：随机产生一个随机数 ，若其小于设置的变异概率 ，则随机选择染色体上的第 个基因作为变异位点，并随机产生新的基因值替代原来的基因值；
S506：返回S503进行选择操作以及交叉操作、变异操作，若种群保持最优值连续代不变或达到最大迭代次数，算法终止，返回最优染色体；否则，算法将继续迭代寻优，其中，最优染色体为遗传算法的最优解，染色体的长度为候选路径数量，每个位编码对应一条候选路径。
2.如权利要求1所述的基于路径分配客流的高铁列车开行路径优化方法，其特征在于，步骤S1中高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量的计算方式为：其中，为高铁线路的区间， 为客流出行路径集合，表示一条客流出行路径， 为选择客流出行路径 的出行客流量， 分别为客流出行路径的起始区间方向与终到区间方向， 、 、 分别为高铁线路的区间 上的通过客流量、终到客流量以及始发客流量。
3.如权利要求1所述的基于路径分配客流的高铁列车开行路径优化方法，其特征在于，步骤S2包括：对于仅衔接一个区间 的站点 ，此时 为端点站，若其始发客流量满足 ，则将其选择为候选始发站；若其终到客流量满足 ，则将其选择为候选终到站；
对于仅衔接两个区间 与 的站点 ，此时 为非叉点站，若从区间 的始发客流量与从区间 终到站点 的终到客流量之差大于开行一列始发列车需要的最少客流量，则将其确定为候选始发站：若从区间 终到 的终到客流量与从区间 始发的始发客流量之差大于开行一列终到列车需要的最少客流量，则将其确定为候选终到站：其中，为列车定员，为车站组织开行始发列车需要的最低始发上座率， 为站点在区间 方向上的始发客流量， 为从区间 终到站点 的终到客流量， 为从区间终到站点 的终到客流量， 为站点 在区间 方向上的始发客流量；
对于衔接三个及其以上区间的站点 ，此时 为叉点站，首先根据站点的总始发客流量、总终到客流量计算得到站点需要开行的始发列车数、终到列车数，然后计算站点 从区间到达车站后再从区间 离开的通过列车数量，同时保证通过列车在服务两个区间时前一个区间的终到客流量与后一个区间的始发客流量相等，最后，确定站点 是否为候选始发站或者候选终到站。
4.如权利要求3所述的基于路径分配客流的高铁列车开行路径优化方法，其特征在于，对于衔接三个及其以上区间的站点 ,确定出需要组织开行的始发列车数、终到列车数，确定站点 是否为候选始发站或者候选终到站，具体包括：计算站点需要开行的始发列车数、终到列车数：
其中， 表示站点 为始发客流出行需要组织开行的总列车数， 表示站点 为终到客流出行需要组织开行的总列车数，总列车数包括终到与通过列车，为列车定员，为车站组织开行始发列车需要的最低始发上座率；
其中， 为所有区间的集合，线性规划模型的约束条件包括：
1）经区间 到达以及从其他区间出发的所有通过列车提供的载客能力不高于区间 的终到客流量，即其中， 为区间 的终到客流量；
2）经其他区间到达以及从区间 出发的所有通过列车提供的载客能力不高于从区间始发的始发客流量，即其中， 为从区间 始发的始发客流量；
通过求解线性规划模型计算站点需要组织开行的始发列车数和终到列车数：其中， 与 分别表示站点 需要组织开行的始发列车数和终到列车数，当为小数时，往上取整数。
5.如权利要求1所述的基于路径分配客流的高铁列车开行路径优化方法，其特征在于，步骤S3包括：S301：初始化列车候选路径集合 ；
S302：针对任意候选始发站‑区间 ，循环从客流出行路径集合中选择以 作为起点的客流出行路径 ，若 的终点区间‑车站属于集合 ，则将该客流出行路径 添加至集合 ；否则，从 的终点区间‑车站开始往其它衔接方向找到最近的一个属于集合 的终点区间‑车站，将此路径添加至 中，其中，候选始发站‑区间表示候选到区间， 表示候选始发站到区间的集合，终点区间‑车站表示终点区间到车站， 表示候选区间到终到站的集合；
S303：将获得的列车候选路径集合中包含的重复路径删除，保留下的路径作为列车候选开行路径；
S304：对于列车候选开行路径中的候选始发站与候选终到站，判断是否具备始发、终到列车设备条件，如果不具备，则将候选始发站或者候选终到站删除。
6.基于路径分配客流的高铁列车开行路径优化装置，其特征在于，包括：高铁出行路径客流量分布计算模块，用于基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
候选始发站与终到站确定模块，用于根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
高铁列车候选开行路径确定模块，用于结合计算出的高铁出行路径客流量分布，在候选始发站与终到站确定模块中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
高铁列车候选路径开行数量优化模型构建模块，用于以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
模型求解模块，用于设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径，染色体的长度为开行列车数量；
其中，高铁列车候选路径开行数量优化模型构建模块具体用于执行下述步骤：S401：选择各高铁列车候选开行路径组织的开行列车数量作为模型决策变量 ；
S402：选择模型优化目标，构建高铁列车候选路径开行数量优化模型：其中，第一部分 为开行列车总运营里程，表示列车运营每公里的平均成本，为路径 的运营里程；第二部分 为开行列车组织成本，表示组织一列列车的平均成本， 表示列车候选路径集合，高铁列车候选路径开行数量优化模型的约束条件包括：约束条件1：
其中， 表示路径 上开行列车的定员， 表示路径 与区间 的关联关系，若区间 属于路径 ，则 ；否则， ， 为区间 的总出行量；
其中， 为线路区间 全天运营时间范围开行的最大列车数量， 为列车开行路径 与线路区间 的关联参数，若线路区间 属于列车开行路径 ，则为1，否则为0；
其中，为给定的浮动列车数， 与 分别表站点 需要组织开行的始发列车数和终到列车数；
S501：构造候选路径开行列车数量方案的解编码，其编码长度为候选路径的数量，每个位编码对应一条候选路径，编码采用非负整数表示，其中，当某位编码为0时表示相对应候选路径不组织开行列车；否则，组织开行相应整数数量的列车；
S502：按设计的编码方案随机生成 个初始个体，添加到初始种群 中，若产生不符合要求的个体，则抛弃该个体重新随机生成，直至获得 个初始个体；
S503：选择操作：计算种群 中全部个体的适应度 ，按适应度从大到小排序，并按如下公式计算各个体的选择概率 与累积概率 ，作为群体中每个个体被选择到下一代种群中的概率：随机产生一个随机数 ，并选择满足 的个体 ，重复此直至选择获得个个体作为下一代种群个体；其中，为个体 ，为个体 的适应度， 表示从种群 中选择出适应度最大的个体的适应度，为个体的选择概率；
S504：交叉操作：随机产生一个随机数 ，若其小于设置的交叉概率 ，则选择两个染色体 与 进行交叉：其中， 均为0‑1的随机数， , 为染色体 与 交叉后的子代染色体；
S505：变异操作：随机产生一个随机数 ，若其小于设置的变异概率 ，则随机选择染色体上的第 个基因作为变异位点，并随机产生新的基因值替代原来的基因值；
S506：返回S503进行选择操作以及交叉操作、变异操作，若种群保持最优值连续代不变或达到最大迭代次数，算法终止，返回最优染色体；否则，算法将继续迭代寻优，其中，最优染色体为遗传算法的最优解，染色体的长度为候选路径数量，每个位编码对应一条候选路径。
7.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被执行时实现如权利要求1至5任一项所述的方法。
8.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求至1至5任一项所述的方法。
基于路径分配客流的高铁列车开行路径优化方法及装置
技术领域
[0001] 本发明涉及铁路运输技术领域，尤其涉及一种基于路径分配客流的高铁列车开行路径优化方法及装置。
背景技术
[0002] 编制旅客列车开行方案是高速铁路运营运输组织的重要环节，同时作为一项指导性的技术文件其对新建高铁线路实施预可研阶段，完成评估线路社会效益、经济效益等工作具有重要意义。新线设计阶段编制列车开行方案以客流需求为核心，分析其需求时空分布、结构等特征，以路网的实际运输能力、动车组运用等资源为限约束条件，根据铁路运输企业和出行旅客的效用目标，确定开行方案的开行径路、数量等重要内容，以求能合理分配资源，实现网络化合理运输。合理的开行方案不仅能够在运营阶段使得旅客运输组织合理化、运输企业运营效益最大化，其在新线设计预可研阶段也能够使得评估新线更加合理、客观准确，有效提高高速铁路运营效率。
[0003] “按流开车”作为组织高速铁路列车开行的基本原则能够体现客流对于开行方案编制的重要影响，其具体表现在客流预测以及客流分配两方面的研究；近年来随着高速路网逐步完善，在成网条件下对客流分配以及列车开行径路的研究也逐步深入，对于编制合理的开行方案奠定基础。
[0004] 然而现有技术中关于开行方案的研究多是面向运营阶段的开行方案的编制流程、优化等问题，其通过构建现有的高速铁路运输网络物理模型进行客流分配，从而完成开行方案的编制及优化。如此一来，使得开行方案所能发挥的作用具有局限性，如现状过多的高铁中转客流，导致诸多大型节点车站能力、候车面积等严重不足（如郑州东、广州南等），不仅延长了引起客流旅行时间，也影响了高铁服务质量，更增加了高铁系统费用。
发明内容
[0005] 本发明通过公开一种基于路径分配客流的高铁列车开行路径优化方法及装置，用以解决或者至少部分解决现有技术中存在的开行方案编制效果不佳的技术问题。
[0006] 为了解决上述技术问题，本发明第一方面提供了基于路径分配客流的高铁列车开行路径优化方法，包括：
[0007] S1：基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
[0008] S2：根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
[0009] S3：结合计算出的高铁出行路径客流量分布，在步骤S2中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
[0010] S4：以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
[0011] S5：设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径，染色体的长度为开行列车数量。
[0012] 在一种实施方式中，步骤S1中高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量的计算方式为：
[0013]
[0014]
[0015]
[0016] 其中，为高铁线路的区间， 为客流出行路径集合，表示一条客流出行路径，为选择客流出行路径 的出行客流量， 分别为客流出行路径的起始区间方向与终到区间方向， 、 、 分别为高铁线路的区间 上的通过客流量、终到客流量以及始发客流量。
[0017] 在一种实施方式中，步骤S2包括：
[0018] 对于仅衔接一个区间 的站点 ，此时 为端点站，若其始发客流量满足 ，则将其选择为候选始发站；若其终到客流量满足 ，则将其选择为候选终到站；
[0019] 对于仅衔接两个区间 与 的站点 ，此时 为非叉点站，若从区间 的始发客流量与从区间 终到站点 的终到客流量之差大于开行一列始发列车需要的最少客流量，则将其确定为候选始发站：
[0020]
[0021] 若从区间 终到 的终到客流量与从区间 始发的始发客流量之差大于开行一列终到列车需要的最少客流量，则将其确定为候选终到站：
[0022]
[0023] 其中，为列车定员，为车站组织开行始发列车需要的最低始发上座率， 为站点 在区间 方向上的始发客流量， 为从区间 终到站点 的终到客流量， 为从区间 终到站点 的终到客流量， 为站点 在区间 方向上的始发客流量；
[0024] 对于衔接三个及其以上区间的站点 ，此时 为叉点站，首先根据站点的总始发客流量、总终到客流量计算得到站点需要开行的始发列车数、终到列车数，然后计算站点 从区间 到达车站后再从区间 离开的通过列车数量，同时保证通过列车在服务两个区间时前一个区间的终到客流量与后一个区间的始发客流量相等，最后，确定站点 是否为候选始发站或者候选终到站。
[0025] 在一种实施方式中，对于衔接三个及其以上区间的站点 ,确定出需要组织开行的始发列车数、终到列车数，确定站点 是否为候选始发站或者候选终到站，具体包括：
[0026] 计算站点需要开行的始发列车数、终到列车数：
[0027]
[0028]
[0029] 其中， 表示站点 为始发客流出行需要组织开行的总列车数， 表示站点 为终到客流出行需要组织开行的总列车数，总列车数包括终到与通过列车，为列车定员，为车站组织开行始发列车需要的最低始发上座率；
[0030] 构建线性规划模型：
[0031]
[0032] 其中， 为所有区间的集合，线性规划模型的约束条件包括：
[0033] 1）经区间 到达以及从其他区间出发的所有通过列车提供的载客能力不高于区间的终到客流量，即
[0034]
[0035] 其中， 为区间 的终到客流量；
[0036] 2）经其他区间到达以及从区间 出发的所有通过列车提供的载客能力不高于从区间 始发的始发客流量，即
[0037]
[0038] 其中， 为从区间 始发的始发客流量；
[0039] 通过求解线性规划模型计算站点需要组织开行的始发列车数和终到列车数：
[0040]
[0041]
[0042] 其中， 与 分别表示站点 需要组织开行的始发列车数和终到列车数，当为小数时，往上取整数。
[0043] 在一种实施方式中，步骤S3包括：
[0044] S301：初始化列车候选路径集合 ；
[0045] S302：针对任意候选始发站‑区间 ，循环从客流出行路径集合中选择以作为起点的客流出行路径 ，若 的终点区间‑车站属于集合 ，则将该客流出行路径添加至集合 ；否则，从 的终点区间‑车站开始往其它衔接方向找到最近的一个属于集合 的终点区间‑车站，将此路径添加至 中，其中，候选始发站‑区间表示候选到区间，表示候选始发站到区间的集合，终点区间‑车站表示终点区间到车站， 表示候选区间到终到站的集合；
[0046] S303：将获得的列车候选路径集合中包含的重复路径删除，保留下的路径作为列车候选开行路径；
[0047] S304：对于列车候选开行路径中的候选始发站与候选终到站，判断是否具备始发、终到列车设备条件，如果不具备，则将候选始发站或者候选终到站删除。
[0048] 在一种实施方式中，步骤S4包括：
[0049] S401：选择各高铁列车候选开行路径组织的开行列车数量作为模型决策变量 ；
[0050] S402：选择模型优化目标，构建高铁列车候选路径开行数量优化模型：
[0051]
[0052] 其中，第一部分 为开行列车总运营里程，表示列车运营每公里的平均成本，为路径 的运营里程；第二部分 为开行列车组织成本，表示组织一列列车的平均成本，高铁列车候选路径开行数量优化模型的约束条件包括：
[0053] 约束条件1：
[0054]
[0055] 其中， 表示路径 上开行列车的定员， 表示路径 与区间 的关联关系，若区间属于路径 ，则 ；否则， ， 为区间 的总出行量；
[0056] 约束条件2：
[0057]
[0058] 其中， 为线路区间 全天运营时间范围开行的最大列车数量， 为列车开行路径与线路区间 的关联参数，若线路区间 属于列车开行路径 ，则为1，否则为0；
[0059] 约束条件3：
[0060] ① 对于仅衔接一个或两个线路区间的非叉点站：
[0061]
[0062]
[0063] 其中， 、 为路径p的起始区间与终止区间；
[0064] ② 对于衔接两个以上线路区间的叉点站：
[0065] 从叉点站 经各衔接区间始发列车数量满足：
[0066]
[0067] 经各衔接区间终到叉点站 的终到列车数量满足：
[0068]
[0069] 其中，为给定的浮动列车数， 与 分别表站点 需要组织开行的始发列车数和终到列车数。
[0070] 在一种实施方式中，步骤S5包括：
[0071] S501：构造候选路径开行列车数量方案的解编码，其编码长度为候选路径的数量，每个位编码对应一条候选路径，编码采用非负整数表示，其中，当某位编码为0时表示相对应候选路径不组织开行列车；否则，组织开行相应整数数量的列车；
[0072] S502：按设计的编码方案随机生成 个初始个体，添加到初始种群 中，若产生不符合要求的个体，则抛弃该个体重新随机生成，直至获得 个初始个体；
[0073] S503：选择操作：计算种群 中全部个体的适应度 ，按适应度从大到小排序，并按如下公式计算各个体的选择概率 与累积概率 ，作为群体中每个个体被选择到下一代种群中的概率：
[0074]
[0075]
[0076] 随机产生一个随机数 ，并选择满足 的个体 ，重复此直至选择获得 个个体作为下一代种群个体；其中，为个体 ，为个体的适应度，表示从种群 中选择出适应度最大的个体的适应度，为个体的选择概率；
[0077] S504：交叉操作：随机产生一个随机数 ，若其小于设置的交叉概率 ，则选择两个染色体 与 进行交叉：
[0078]
[0079]
[0080] 其中， 均为0‑1的随机数， , 为染色体 与 交叉后的子代染色体；
[0081] S505：变异操作：随机产生一个随机数 ，若其小于设置的变异概率 ，则随机选择染色体上的第 个基因作为变异位点，并随机产生新的基因值替代原来的基因值；
[0082] S506：返回S503进行选择操作以及交叉操作、变异操作，若种群保持最优值连续代不变或达到最大迭代次数，算法终止，返回最优染色体；否则，算法将继续迭代寻优，其中，最优染色体为遗传算法的最优解，染色体的长度为候选路径数量，每个位编码对应一条候选路径。
[0083] 基于同样的发明构思，本发明第二方面提供了基于路径分配客流的高铁列车开行路径优化装置，包括：
[0084] 高铁出行路径客流量分布计算模块，用于基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
[0085] 候选始发站与终到站确定模块，用于根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
[0086] 高铁列车候选开行路径确定模块，用于结合计算出的高铁出行路径客流量分布，在步骤S2中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
[0087] 高铁列车候选路径开行数量优化模型构建模块，用于以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
[0088] 模型求解模块，用于设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径
[0089] 基于同样的发明构思，本发明第三方面提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被执行时实现第一方面所述的方法。
[0090] 基于同样的发明构思，本发明第四方面提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现第一方面所述的方法。
[0091] 相对于现有技术，本发明的优点和有益的技术效果如下：
[0092] 本发明公开的基于路径分配客流的高铁列车开行路径优化方法，首先基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，并根据车站衔接区间的始发、终到客流量分布，从所有高铁车站中筛选出部分可能为列车始发、终到站的车站集，同时根据出行路径客流分布从这些车站间路径中选择部分合理路径作为列车候选开行路径集，再通过对客流路网分配、获得各OD客流出行路径集的基础上，根据客流出行路径生成高铁线路可能开行列车的路径，最后构建高铁列车候选路径开行数量优化模型并采用遗传算法进行求解，得出最优路径规划方案：高铁列车开行路径，染色体的长度为开行列车数量。本发明具有操作性强、计算速度快等优点，通过该方法优化得到的高铁列车开行路径能够最大程度地降低长途旅客换乘、节省旅客出行里程，实现高铁列车开行路径与旅客出行路径的高度吻合。同时通过该方法还可获得各列车开行路径开行列车数量，既保证了各线路区间开行列车数量满足区间列车开行能力与客流输送能力要求，又节省了列车开行成本。
附图说明
[0093] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0094] 图1为本发明实施例提供的基于路径分配客流的高铁列车开行路径优化方法的流程示意图。
具体实施方式
[0095] 本发明目的在于提供一种基于路径分配客流的高铁列车开行路径优化方法，通过该方法优化获得的高铁列车开行路径及其相应开行列车数量能够与旅客出行路径高度一致，最大程度地减少旅客出行换乘、缩短旅客出行里程，同时提高高铁列车开行效率。
[0096] 为了达到上述目的，本发明需要解决以下关键技术：
[0097] （1）高铁网络客流分配：“按流开车”是组织开行高铁列车的最基本原则，因在高铁网络化运营条件下OD客流可能存在两条及以上出行路径，这个“流”不应仅局限于OD客流，而应为涵盖路径信息的出行路径客流。在高铁线路区间客流输送能力限制下将各OD出行客流需求量以一定原则分配到OD间多条出行路径上，形成出行路径客流是本发明需要解决的第一个关键技术。
[0098] （2）列车候选始发、终到站选择：根据车站衔接区间的始发、终到客流量分布，从所有高铁车站中筛选出部分可能为列车始发、终到站的车站集，同时根据出行路径客流分布从这些车站间路径中选择部分合理路径作为列车候选开行路径集是本发明需要解决的第二个关键技术；
[0099] （3）列车候选路径的优化：通过对客流路网分配、获得各OD客流出行路径集的基础上，根据客流出行路径生成高铁线路可能开行列车的路径。在给定列车候选开行路径集的基础上，结合客流出行路径集合中每条客流出行路径的客流量，优化计算每条候选列车路径的开行列车数量是本发明需要解决的第三个关键技术。
[0100] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0101] 实施例一
[0102] 本发明实施例提供了基于路径分配客流的高铁列车开行路径优化方法，包括：
[0103] S1：基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
[0104] S2：根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
[0105] S3：结合计算出的高铁出行路径客流量分布，在步骤S2中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
[0106] S4：以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
[0107] S5：设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径，染色体的长度为开行列车数量。
[0108] 请参见图1为本发明实施例提供的基于路径分配客流的高铁列车开行路径优化方法的流程示意图。
[0109] 具体来说，给定高铁路网上各出行路径的分配客流量是指在高铁网络化运营条件下的OD客流量。
[0110] 在一种实施方式中，步骤S1中高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量的计算方式为：
[0111]
[0112]
[0113]
[0114] 其中，为高铁线路的区间， 为客流出行路径集合，表示一条客流出行路径，为选择客流出行路径 的出行客流量， 分别为客流出行路径的起始区间方向与终到区间方向， 、 、 分别为高铁线路的区间 上的通过客流量、终到客流量以及始发客流量。
[0115] 在一种实施方式中，步骤S2包括：
[0116] 对于仅衔接一个区间 的站点 ，此时 为端点站，若其始发客流量满足 ，则将其选择为候选始发站；若其终到客流量满足 ，则将其选择为候选终到站；
[0117] 对于仅衔接两个区间 与 的站点 ，此时 为非叉点站，若从区间 的始发客流量与从区间 终到站点 的终到客流量之差大于开行一列始发列车需要的最少客流量，则将其确定为候选始发站：
[0118]
[0119] 若从区间 终到 的终到客流量与从区间 始发的始发客流量之差大于开行一列终到列车需要的最少客流量，则将其确定为候选终到站：
[0120]
[0121] 其中，为列车定员，为车站组织开行始发列车需要的最低始发上座率， 为站点 在区间 方向上的始发客流量， 为从区间 终到站点 的终到客流量， 为从区间 终到站点 的终到客流量， 为站点 在区间 方向上的始发客流量；
[0122] 对于衔接三个及其以上区间的站点 ，此时 为叉点站，首先根据站点的总始发客流量、总终到客流量计算得到站点需要开行的始发列车数、终到列车数，然后计算站点 从区间 到达车站后再从区间 离开的通过列车数量，同时保证通过列车在服务两个区间时前一个区间的终到客流量与后一个区间的始发客流量相等，最后，确定站点 是否为候选始发站或者候选终到站。
[0123] 具体来说，对于不同的站点，确定该站点是否作为候选始发站或者候选终到站。
[0124] 在一种实施方式中，对于衔接三个及其以上区间的站点 ,确定出需要组织开行的始发列车数、终到列车数，确定站点 是否为候选始发站或者候选终到站，具体包括：
[0125] 计算站点需要开行的始发列车数、终到列车数：
[0126]
[0127]
[0128] 其中， 表示站点 为始发客流出行需要组织开行的总列车数， 表示站点 为终到客流出行需要组织开行的总列车数，总列车数包括终到与通过列车，为列车定员，为车站组织开行始发列车需要的最低始发上座率；
[0129] 构建线性规划模型：
[0130]
[0131] 其中， 为所有区间的集合，线性规划模型的约束条件包括：
[0132] 1）经区间 到达以及从其他区间出发的所有通过列车提供的载客能力不高于区间的终到客流量，即
[0133]
[0134] 其中， 为区间 的终到客流量；
[0135] 2）经其他区间到达以及从区间 出发的所有通过列车提供的载客能力不高于从区间 始发的始发客流量，即
[0136]
[0137] 其中， 为从区间 始发的始发客流量；
[0138] 通过求解线性规划模型计算站点需要组织开行的始发列车数和终到列车数：
[0139]
[0140]
[0141] 其中， 与 分别表示站点 需要组织开行的始发列车数和终到列车数，当为小数时，往上取整数。
[0142] 具体来说，通过构建线性规划模型可以计算得到叉点站从区间 到达车站后再从区间 离开的通过列车数量 。模型期望为所有始发、终到客流安排通过列车为其服务，故选择以最大化开行的通过列车数量作为模型优化目标，同时，要求每列通过列车在前后经由区间服务的终到客流量与始发客流量相等（即通过列车在服务两个区间时，前一个区间的终到客流量与后一个区间的始发客流量相等），如若不等，超出部分的始发客流量或者终到客流量考虑用始发列车或者终到列车为其服务，而不考虑组织通过列车为其服务。因此，可以得到线性模型的约束条件。
[0143] 对于衔接三个及其以上区间的站点，如果计算出的车站需要组织开行的始发、终到列车数为正整数，那么说明此站可作为始发站或者终到站。
[0144] 可以看出，以上构建的模型为典型的线性规划模型、且规模较小，故可直接采用相关求解器，如Cplex、Lingo等直接快速求解。
[0145] 在一种实施方式中，步骤S3包括：
[0146] S301：初始化列车候选路径集合 ；
[0147] S302：针对任意候选始发站‑区间 ，循环从客流出行路径集合中选择以作为起点的客流出行路径 ，若 的终点区间‑车站属于集合 ，则将该客流出行路径添加至集合 ；否则，从 的终点区间‑车站开始往其它衔接方向找到最近的一个属于集合 的终点区间‑车站，将此路径添加至 中，其中，候选始发站‑区间表示候选到区间，表示候选始发站到区间的集合，终点区间‑车站表示终点区间到车站， 表示候选区间到终到站的集合；
[0148] S303：将获得的列车候选路径集合中包含的重复路径删除，保留下的路径作为列车候选开行路径；
[0149] S304：对于列车候选开行路径中的候选始发站与候选终到站，判断是否具备始发、终到列车设备条件，如果不具备，则将候选始发站或者候选终到站删除。
[0150] 具体来说，对于列车候选开行路径中的候选始发站和候选终到站具备始发、终到列车设备条件，是指起始车站为列车候选始发站、且起始区间为该车站的一个客流始发区间；结束车站为列车候选终到站、且结束区间为该车站的一个客流终到区间；至少存在一只OD客流完整使用该路径出行。
[0151] 在一种实施方式中，步骤S4包括：
[0152] S401：选择各高铁列车候选开行路径组织的开行列车数量作为模型决策变量 ；
[0153] S402：选择模型优化目标，构建高铁列车候选路径开行数量优化模型：
[0154]
[0155] 其中，第一部分 为开行列车总运营里程，表示列车运营每公里的平均成本，为路径 的运营里程；第二部分 为开行列车组织成本，表示组织一列列车的平均成本，高铁列车候选路径开行数量优化模型的约束条件包括：
[0156] 约束条件1：
[0157]
[0158] 其中， 表示路径 上开行列车的定员， 表示路径 与区间 的关联关系，若区间属于路径 ，则 ；否则， ， 为区间 的总出行量；
[0159] 约束条件2：
[0160]
[0161] 其中， 为线路区间 全天运营时间范围开行的最大列车数量， 为列车开行路径与线路区间 的关联参数，若线路区间 属于列车开行路径 ，则为1，否则为0；
[0162] 约束条件3：
[0163] ① 对于仅衔接一个或两个线路区间的非叉点站：
[0164]
[0165]
[0166] 其中， 、 为路径p的起始区间与终止区间；
[0167] ② 对于衔接两个以上线路区间的叉点站：
[0168] 从叉点站 经各衔接区间始发列车数量满足：
[0169]
[0170] 经各衔接区间终到叉点站 的终到列车数量满足：
[0171]
[0172] 其中，为给定的浮动列车数， 与 分别表站点 需要组织开行的始发列车数和终到列车数。
[0173] 在选择模型优化目标时，为了降低列车开行成本，应在保证客流出行的前提下尽可减少列车开行数量。考虑到不同开行列车因开行距离长短不同，故相应开行成本也不同，简便起见，以最小化列车路径旅行总公里数为优化目标；同时为了避免组织过多的短途列车、将长途列车组织成多列短途列车来满足长途客流出行需求，考虑单列列车组织成本，从而可以得到模型优化目标。
[0174] 对于模型的约束条件，区间提供的列车客流输送能力不低于区间客流出行量，即经过某区间方向所有列车提供的客流载客能力应不低于该区间的总出行量，包括各OD通过该区间的客流量、以该区间为始发或者终到的客流量，故得到约束条件1。
[0175] 区间开行列车数量小于线路开行能力，即某区间方向运行的通过、始发、终到列车之和必须小于该区间方向最大列车数量，从而得到约束条件2。
[0176] 为了避免出现用大量短途列车来满足长途客流出行的不利情况，即长途客流需要在多个短途列车之间换乘完成出行，故需要对车站开行的始发、终到列车数量进行约束控制。
[0177] 对于非叉点站（仅衔接一个或两个线路区间）
[0178] 终到区间 的终到客流与从区间 始发的始发客流可由经区间 到达、从区间 离开的通过列车服务，这样一来既满足此两部分客流的出行要求，同时相比分别组织一列终到列车、一列始发列车而言，避免了经区间 到达、从区间 离开的通过客流的一次换乘。因此，只要终到区间 的终到客流量 不高于从区间 始发的始发客流量 时，就不需要组织终到区间 的终到列车。同理，只要从区间 始发的始发客流量 不高于终到区间的终到客流量 时，就不需要组织从区间 始发的始发列车，因此得到约束条件3中非叉点站的约束。
[0179] 对于叉点站（衔接两个以上线路区间）
[0180] 对于叉点站，终到区间 的终到客流可与多个其它区间始发的始发客流一起组织开行通过列车；同样，区间 始发的始发客流亦可与多个其它区间终到的终到客流一起组织开行通过列车。此外，同区间上下行方向列车通常不应组织通过列车（若组织开行，该通过列车将经区间 到达车站，然后再由该区间离开车站，这样的通过列车通常组织为一列终到列车与一列始发列车）。如此一来，首先可获得叉点站 需要组织开行的始发、终到列车数与 。在此基础上，使得从叉点站 经各衔接区间始发列车数量满足约束条件3中叉点站的公式。
[0181] 在一种实施方式中，步骤S5包括：
[0182] S501：构造候选路径开行列车数量方案的解编码，其编码长度为候选路径的数量，每个位编码对应一条候选路径，编码采用非负整数表示，其中，当某位编码为0时表示相对应候选路径不组织开行列车；否则，组织开行相应整数数量的列车；
[0183] S502：按设计的编码方案随机生成 个初始个体，添加到初始种群 中，若产生不符合要求的个体，则抛弃该个体重新随机生成，直至获得 个初始个体；
[0184] S503：选择操作：计算种群 中全部个体的适应度 ，按适应度从大到小排序，并按如下公式计算各个体的选择概率 与累积概率 ，作为群体中每个个体被选择到下一代种群中的概率：
[0185]
[0186]
[0187] 随机产生一个随机数 ，并选择满足 的个体 ，重复此直至选择获得 个个体作为下一代种群个体；其中，为个体 ，为个体的适应度，表示从种群 中选择出适应度最大的个体的适应度，为个体的选择概率；
[0188] S504：交叉操作：随机产生一个随机数 ，若其小于设置的交叉概率 ，则选择两个染色体 与 进行交叉：
[0189]
[0190]
[0191] 其中， 均为0‑1的随机数， , 为染色体 与 交叉后的子代染色体；
[0192] S505：变异操作：随机产生一个随机数 ，若其小于设置的变异概率 ，则随机选择染色体上的第 个基因作为变异位点，并随机产生新的基因值替代原来的基因值；
[0193] S506：返回S503进行选择操作以及交叉操作、变异操作，若种群保持最优值连续代不变或达到最大迭代次数，算法终止，返回最优染色体；否则，算法将继续迭代寻优，其中，最优染色体为遗传算法的最优解，染色体的长度为候选路径数量，每个位编码对应一条候选路径。
[0194] 具体来说，否则，组织开行相应整数数量的列车是指某位编码为一个整数a时，则组织开行a量列车。
[0195] 最优染色体即为遗传算法的最优解，对染色体进行解码就能够得到高铁列车开行路径和开行列车数量。染色体解码即：染色体长度为候选路径数量，每个位编码对应一条候选路径，编码采用非负整数表示。当某位编码为0时表示，相对应候选路径不组织开行列车；否则，组织开行相应整数数量的列车。
[0196] 总体来说，本发明的基于路径分配客流的高铁列车开行路径的优化方法，具有操作性强、计算速度快等优点，通过该方法优化得到的高铁列车开行路径能够最大程度地降低长途旅客换乘、节省旅客出行里程，实现高铁列车开行路径与旅客出行路径的高度吻合。同时通过该方法还可获得各列车开行路径开行列车数量，既保证各线路区间开行列车数量满足区间列车开行能力与客流输送能力要求，又节省列车开行成本。
[0197] 实施例二
[0198] 基于同样的发明构思，本实施例提供了基于路径分配客流的高铁列车开行路径优化装置，该装置包括：
[0199] 高铁出行路径客流量分布计算模块，用于基于给定高铁路网上各出行路径的分配客流量，计算高铁出行路径客流量分布，其中，高铁出行路径客流量分布包括高铁各线路各区间方向上的通过客流量、终到客流量以及始发客流量；
[0200] 候选始发站与终到站确定模块，用于根据计算出的高铁出行路径客流量分布以及区间是否具备始发、终到列车设备条件，确定出高铁列车开行的候选始发站与候选终到站；
[0201] 高铁列车候选开行路径确定模块，用于结合计算出的高铁出行路径客流量分布，在步骤S2中确定出的候选始发站与候选终到站之间选择路径作为高铁列车候选开行路径；
[0202] 高铁列车候选路径开行数量优化模型构建模块，用于以各高铁列车候选开行路径组织的开行列车数量为决策变量，以高铁列车开行成本最小为优化目标，以区间开行列车能力限制、输送客流能力限制为约束条件，构建高铁列车候选路径开行数量优化模型；
[0203] 模型求解模块，用于设计列车候选路径开行数量方案的解编码，并设计选择、交叉、变异的操作策略，采用遗传算法对高铁列车候选路径开行数量优化模型进行求解，得到最优解，其中，最优解对应的染色体的编码为高铁列车开行路径，染色体的长度为开行列车数量。
[0204] 由于本发明实施例二所介绍的装置为实施本发明实施例一中基于路径分配客流的高铁列车开行路径优化方法所采用的装置，故而基于本发明实施例一所介绍的方法，本领域所属人员能够了解该装置的具体结构及变形，故而在此不再赘述。凡是本发明实施例一中方法所采用的装置都属于本发明所欲保护的范围。
[0205] 实施例三
[0206] 基于同一发明构思，本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被执行时实现如实施例一中所述的方法。
[0207] 由于本发明实施例三所介绍的计算机可读存储介质为实施本发明实施例一中基于路径分配客流的高铁列车开行路径优化方法所采用的计算机可读存储介质，故而基于本发明实施例一所介绍的方法，本领域所属人员能够了解该计算机可读存储介质的具体结构及变形，故而在此不再赘述。凡是本发明实施例一的方法所采用的计算机可读存储介质都属于本发明所欲保护的范围。
[0208] 实施例四
[0209] 基于同一发明构思，本申请还提供了一种计算机设备，包括存储、处理器及存储在存储器上并可在处理器上运行的计算机程序，处理器执行上述程序时实现实施例一中的方法。
[0210] 由于本发明实施例四所介绍的计算机设备为实施本发明实施例一中基于路径分配客流的高铁列车开行路径优化方法所采用的计算机设备，故而基于本发明实施例一所介绍的方法，本领域所属人员能够了解该计算机设备的具体结构及变形，故而在此不再赘述。凡是本发明实施例一中方法所采用的计算机设备都属于本发明所欲保护的范围。
[0211] 本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质（包括但不限于磁盘存储器、CD‑ROM、光学存储器等）上实施的计算机程序产品的形式。
[0212] 本发明是参照根据本发明实施例的方法、设备（系统）、和计算机程序产品的流程图和／或方框图来描述的。应理解可由计算机程序指令实现流程图和／或方框图中的每一流程和／或方框、以及流程图和／或方框图中的流程和／或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和／或方框图一个方框或多个方框中指定的功能的装置。
[0213] 尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。
[0214] 显然，本领域的技术人员可以对本发明实施例进行各种改动和变型而不脱离本发明实施例的精神和范围。这样，倘若本发明实施例的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。
