基于中速磁浮线路通过能力的供电分区优化设置方法

摘要

本发明提供了一种基于中速磁浮线路通过能力的供电分区优化设置方法，包括：确定中速磁浮线路上的区间个数、区间长度和最大定子段个数；利用遗传算法生成供电分区设置方案；利用能力计算模型计算每种供电分区设置方案下的线路通过能力；利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，判断将通过能力最大的供电分区设置方案作为供电分区方案。本发明通过分析供电分区对中速磁浮线路通过能力的影响，构建基于中速磁浮线路通过能力的供电分区优化设置方法，解决了以提高线路通过能力为目标的供电分区优化设置问题，提高了中速磁浮线路上供电分区的适应性。

权利要求

1.一种基于中速磁浮线路通过能力的供电分区优化设置方法，其特征在于，包括如下步骤：S1确定中速磁浮线路上的区间个数、区间长度和最大定子段个数；

S2根据所述的线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案；

S3根据所述的供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力；

S4利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，判断供电分区设置方案下的线路通过能力是否大于最大的进化代数，若大于，则将通过能力最大的供电分区设置方案作为中速磁浮线路上的供电分区方案，否则，返回至步骤S2。

2.根据权利要求1所述的方法，其特征在于，所述的根据所述的线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案，包括：根据所述的线路上区间个数、区间长度和最大定子段个数，约束模型变量；

根据所述约束模型变量，将区间中每一个区间的定子段组合方式连接起来作为一个个体，采用二进制编码对每个个体进行编码，组成初始种群；

采用适应度函数对所述的初始种群的每个个体进行优化；

通过选择算子、交叉算子和变异算子对所述的优化后的每个个体进行进一步的优化，产生出新一代种群，即为供电分区设置方案。

3.根据权利要求1所述的方法，其特征在于，所述的根据所述的供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力，包括将所述的利用遗传算法生成的供电分区设置方案转化为线路上的节点、弧段、弧集合，并根据能力计算模型计算每种供电分区设置方案下的线路通过能力。

4.根据权利要求3所述的方法，其特征在于，所述的能力计算模型中还包括虚拟弧，所述的虚拟弧用于当列车数量大于线路所能承载的能力时，列车无法通过实际路径从起始节点运行至终到节点时，从虚拟弧上通过。

5.根据权利要求1所述的方法，其特征在于，所述的利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，包括：将能力计算模型中的能力约束作为惩罚项添加到目标函数中，并对其进行恒等变换和分解；

采用向前递推的动态规划算法策略求出列车运行的最短路径；

采用次梯度算法来更新拉格朗日乘子；

采用拉格朗日启发式算法，把求得的拉格朗日松弛问题结果中的拉格朗日乘子作为启发信息，并对线路上的每一列中速磁浮列车的运行顺序进行重新规划，求得可行解。

6.根据权利要求2所述的方法，其特征在于，所述的约束模型变量具体包括：区间c内铺设的定子段的最大数量 和区间c内设置的供电分区的数量nc受到约束如下式(1)和(2)所示：区间内部第i个供电分区的长度 如下式(3)所示：

区间c的长度如下式(4)所示：

供电分区的长度 满足的长度范围约束如下式(5)所示：

其中，lc为区间c的长度，lξ为定子段长度， 为区间c的供电分区的最大数量，为区间c内铺设的定子段的最大数量，nc为区间c内设置的供电分区的数量，nc为整数， 为区间c的第i个供电分区的长度， 表示供电分区长度的最小允许值； 表示供电分区长度的最大允许值。

7.根据权利要求2所述的方法，其特征在于，所述的采用适应度函数对所述的初始种群的每个个体进行优化，包括根据下式(6)的适应度函数对初始种群的每个个体进行优化：其中，f表示线路上运行的列车，F为所有列车的集合，(i,j)表示线路上的弧段，Ef表示列车f在线路上可能经过的所有弧段的集合，表示设置一个供电分区的广义成本相对于列车总运行时间的权重系数，nc表示区间c内供电分区的个数，wq表示区间内设置一个供电分区的广义成本，μf(i,j)表示列车f在弧段(i,j)的实际运行时间。

8.根据权利要求2所述的方法，其特征在于，所述的通过选择算子对所述的优化后的每个个体进行进一步的优化，包括采用下式(7)的轮盘赌法进行供电分区设置方案的选择：式中，pi为供电分区设置方案i被选中的概率为，Fi为供电分区设置方案i的适应度值，N为种群中供电分区设置方案的数目，Fj为供电分区设置方案j的适应度值。

说明书

基于中速磁浮线路通过能力的供电分区优化设置方法

技术领域

[0001] 本发明涉及磁浮交通领域，尤其涉及一种基于中速磁浮线路通过能力的供电分区优化设置方法。

背景技术

[0002] 目前，在磁浮交通领域中，关于磁浮的研究主要集中在牵引供电系统和列车运行控制等方面，面向线路通过能力的供电分区设置方案的研究较少，现有技术中有关于供电分区设置的研究主要从牵引供电系统的角度出发，没有从提高线路通过能力的角度考虑，然而供电分区是中速磁浮列车运行过程中占用的最小单元，对线路通过能力产生较大的影响。因此，为了更合理地安排中速磁浮的运力资源，亟需从提高线路通过能力的角度对供电分区的优化设置展开研究。

发明内容

[0003] 本发明提供了基于中速磁浮线路通过能力的供电分区优化设置方法，以合理地安排中速磁浮的运力资源。

[0004] 为了实现上述目的，本发明采取了如下技术方案。

[0005] 本发明提供了一种基于中速磁浮线路通过能力的供电分区优化设置方法，包括如下步骤：

[0006] S1确定中速磁浮线路上的区间个数、区间长度和最大定子段个数。

[0007] S2根据所述的线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案。

[0008] S3根据所述的供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力。

[0009] S4利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，判断供电分区设置方案下的线路通过能力是否大于最大的进化代数，若大于，则将通过能力最大的供电分区设置方案作为中速磁浮线路上的供电分区方案，否则，返回至步骤S2。

[0010] 进一步地，根据所述的线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案，包括：

[0011] 根据所述的线路上区间个数、区间长度和最大定子段个数，约束模型变量；

[0012] 根据所述约束模型变量，将区间中每一个区间的定子段组合方式连接起来作为一个个体，采用二进制编码对每个个体进行编码，组成初始种群；

[0013] 采用适应度函数对所述的初始种群的每个个体进行优化；

[0014] 通过选择算子、交叉算子和变异算子对所述的优化后的每个个体进行进一步的优化，产生出新一代种群，即为供电分区设置方案。

[0015] 进一步地，根据所述的供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力，包括将所述的利用遗传算法生成的供电分区设置方案转化为线路上的节点、弧段、弧集合，并根据能力计算模型计算每种供电分区设置方案下的线路通过能力。

[0016] 进一步地，能力计算模型中还包括虚拟弧，所述的虚拟弧用于当列车数量大于线路所能承载的能力时，列车无法通过实际路径从起始节点运行至终到节点时，从虚拟弧上通过。

[0017] 进一步地，利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，包括：

[0018] 将能力计算模型中的能力约束作为惩罚项添加到目标函数中，并对其进行恒等变换和分解；

[0019] 采用向前递推的动态规划算法策略求出列车运行的最短路径；

[0020] 采用次梯度算法来更新拉格朗日乘子；

[0021] 采用拉格朗日启发式算法，把求得的拉格朗日松弛问题结果中的拉格朗日乘子作为启发信息，并对线路上的每一列中速磁浮列车的运行顺序进行重新规划，求得可行解。

[0022] 进一步地，约束模型变量具体包括：

[0023] 区间c内铺设的定子段的最大数量 和区间c内设置的供电分区的数量 nc受到约束如下式(1)和(2)所示：

[0024]

[0025]

[0026] 区间内部第i个供电分区的长度 如下式(3)所示：

[0027]

[0028] 区间c的长度如下式(4)所示：

[0029]

[0030] 供电分区的长度 满足的长度范围约束如下式(5)所示：

[0031]

[0032] 其中，lc为区间c的长度，lξ为定子段长度， 为区间c的供电分区的最大数量，为区间c内铺设的定子段的最大数量，nc为区间c内设置的供电分区的数量(取整数)，区间c的第i个供电分区的长度， 表示供电分区长度的最小允许值； 表示供电分区长度的最大允许值。

[0033] 进一步地，采用适应度函数对所述的初始种群的每个个体进行优化，包括根据下式(6)的适应度函数对初始种群的每个个体进行优化：

[0034]

[0035] 其中，f表示线路上运行的列车，F为所有列车的集合，(i，j)表示线路上的弧段，Ef表示列车f在线路上可能经过的所有弧段的集合，表示设置一个供电分区的广义成本相对于列车总运行时间的权重系数，nc表示区间c内供电分区的个数，wq表示区间内设置一个供电分区的广义成本。

[0036] 进一步地，通过选择算子对所述的优化后的每个个体进行进一步的优化，包括采用下式(7)的轮盘赌法进行供电分区设置方案的选择：

[0037]

[0038] 式中，pi为供电分区设置方案i被选中的概率为，Fi为供电分区设置方案i 的适应度值，N为种群中供电分区设置方案的数目。

[0039] 由上述本发明提供的技术方案可以看出，本发明的基于中速磁浮线路通过能力的供电分区优化设置方法，通过分析供电分区对中速磁浮线路通过能力的影响，尤其是供电分区长度对区间追踪间隔的影响，构建基于中速磁浮线路通过能力的供电分区优化设置方法，解决了以提高线路通过能力为目标的供电分区优化设置问题，提高了中速磁浮线路上供电分区的适应性。

[0040] 本发明附加的方面和优点将在下面的描述中部分给出，这些将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

[0041] 为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0042] 图1为本发明实施例1提供的一种基于中速磁浮线路通过能力的供电分区优化设置方法的方法流程图；

[0043] 图2为本发明实施例1提供的一种基于中速磁浮线路通过能力的供电分区优化设置方法的处理流程图；

[0044] 图3为本发明实施例1提供的供电分区长度对区间追踪间隔的影响；

[0045] 图4为本发明实施例1提供的编码方式示例图；

[0046] 图5为本发明实施例1提供的个体编码示例图；

[0047] 图6为本发明实施例1提供的初始种群生成示例图；

[0048] 图7为本发明实施例1提供的多点交叉示意图；

[0049] 图8为本发明实施例1提供的多点变异示意图；

[0050] 图9为本发明实施例2提供的大规模算例线路拓扑结构图；

[0051] 图10为本发明实施例2提供的遗传算法迭代结果图；

[0052] 图11本发明实施例2提供的供电分区数量及线路通过能力对比图。

具体实施方式

[0053] 下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

[0054] 本技术领域技术人员可以理解，除非特意声明，这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。应该进一步理解的是，本发明的说明书中使用的措辞“包括”是指存在所述特征、整数、步骤、操作、元件和/或组件，但是并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。应该理解，当我们称元件被“连接”或“耦接”到另一元件时，它可以直接连接或耦接到其他元件，或者也可以存在中间元件。此外，这里使用的“连接”或“耦接”可以包括无线连接或耦接。这里使用的措辞“和/或”包括一个或更多个相关联的列出项的任一单元和全部组合。

[0055] 本技术领域技术人员可以理解，除非另外定义，这里使用的所有术语 (包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义。还应该理解的是，诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义，并且除非像这里一样定义，不会用理想化或过于正式的含义来解释。

[0056] 为便于对本发明实施例的理解，下面将结合附图以几个具体实施例为例做进一步的解释说明，且各个实施例并不构成对本发明实施例的限定。

[0057] 本发明的基于中速磁浮线路通过能力的供电分区优化设置方法的方法，旨在提高了中速磁浮线路上供电分区的适应性。

[0058] 实施例1

[0059] 图1为本发明实施例1提供的一种基于中速磁浮线路通过能力的供电分区优化设置方法的方法流程图；图2为本发明实施例1提供的一种基于中速磁浮线路通过能力的供电分区优化设置方法的处理流程图，参照图1和图2，该方法包括如下步骤：

[0060] S1确定中速磁浮线路上的区间个数、区间长度和最大定子段个数；

[0061] S2根据所述的线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案；

[0062] S3根据所述的供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力；

[0063] S4利用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，判断供电分区设置方案下的线路通过能力是否大于最大的进化代数，若大于，则将通过能力最大的供电分区设置方案作为中速磁浮线路上的供电分区方案，否则，返回至步骤S2。

[0064] 其中，供电分区是中速磁浮系统中列车占用的最小单元，一个供电分区由一个牵引变电单元控制，一个供电分区可以等效为一组较短的定子段。

[0065] 中速磁浮线路通过能力是指在设定类型的中速磁浮车辆和一定的行车组织方法的前提下，中速磁浮线路在某方向、在单位时间内能通过的标准列车的最大数量，优选地，单位时间为一天内列车可运行的时段。

[0066] 供电分区对中速磁浮线路通过能力的影响主要体现在供电分区长度对区间追踪间隔的影响上。从列车运行的角度来说，磁浮系统中的供电分区与轮轨系统中的闭塞分区类似，即同一时间内一个供电分区只能运行一列车。因此，列车在区间运行时，其追踪间隔受到供电分区长度的影响。

[0067] 示意性地，图3为本发明实施例1提供的供电分区长度对区间追踪间隔的影响。参照图3，(a)中供电分区②较短，(b)中供电分区②较长，供电分区①的长度相同。前行列车均在供电分区②中运行(位于供电分区②与③的边界处)且未离开，因为一个供电分区只能有一列车运行，所以此时追踪列车的目标追踪点均为A(距供电分区①和②的交界处一定的安全防护距离 ls)，因为前行列车还未离开供电分区②，所以追踪列车要保证能够在供电分区①内随时制动停车。因此，(a)中两列车之间的追踪距离为 lr+lb+ls+le+ll，其中lr表示追踪列车在反应时间内运行的距离，lb表示追踪列车的制动距离，le表示前行列车距供电分区①和②的交界处的距离，ll表示前行列车车长，(b)中两列车之间的追踪距离为lr+lb+ls+le′+ll。由于供电分区②长度不同，le与le′的长度不同，因此，在(a)与(b)的情况下，列车的区间追踪间隔不同，且(a)小于(b)。

[0068] 进一步地，根据线路上区间个数、区间长度和最大定子段个数，利用遗传算法生成供电分区设置方案，包括：

[0069] (1)约束模型变量：

[0070] 1)对于区间c，其内部可以设置供电分区的最大数量 与区间c内可以铺设的定子段的最大数量 相同，即一个供电分区仅由一个定子段组成，且该定子段的长度为最小值(即可铺设的定子段最大数量)，因此供电分区的最大数量与定子段的最大数量相同，为区间c的长度lc除以定子段长度 lξ(定子段长度取决于线路坡度、速度及加速度)，区间c内可以设置的供电分区的数量nc(取整数)受到约束如下式(1)和(2)所示。

[0071]

[0072]

[0073] 区间c内部第i个供电分区的长度 如下式(3)所示：

[0074]

[0075] 其中，lξ为定子段长度， 为组成该供电分区的定子段个数。

[0076] 区间c内各供电分区的长度之和即为区间c的长度，如下式(4)所示。

[0077]

[0078] 2)任一供电分区的长度 均需满足一定的长度范围约束。中速磁浮系统中，供电分区是列车运行过程中占用的一个最小单元，因此，供电分区的长度 需要至少要能容纳一列车的长度，且由于供电分区由定子段组成，故供电分区的长度至少大于一个定子段的额定长度，式(5)中 即表示供电分区长度的最小允许值；另外，由于任一供电分区均需由牵引供电装置对其进行供电，因此供电分区的长度 要满足牵引供电装置的供电长度范围约束， 为牵引供电装置的供电长度，任一供电分区的长度 需满足一定的长度范围约束如下式(5)所示。

[0079]

[0080] (2)根据所述约束模型变量，将区间中每一个区间的定子段组合方式连接起来作为一个个体，采用二进制编码对每个个体进行编码，组成初始种群。

[0081] 示意性地，将线路上的m个区间中每一个区间的定子段组合方式(即供电分区长度和数量的设置方式)连接起来作为一个个体(即一个解)。个体编码采用二进制编码，每个个体均为一个二进制串，由线路上的m个区间 (即m部分)组成，每个区间使用X位的二进制编码(X的取值由每个区间的最大定子段数决定)，构成定子段的每个节点对应染色体的一个基因，图4 为本发明实施例1提供的编码方式示例图，具体如图4所示，一个区间的定子段个数为11，由于两个节点组成一个定子段，因此该区间由12个节点(即12 个基因)组成。两个相邻的编码为1的基因构成一个供电分区，两个编码为1 的基因所在的位置编号之差表示组成一个供电分区的定子段个数，图5为本发明实施例1提供的个体编码示例图，具体如图5所示。将所有区间的编码连接起来即形成一个个体的编码。

[0082] 按照上述编码方式，根据线路上各区间的定子段个数，依次确定个体各部分(第1至第m个区间)的二进制编码位数。对于个体的各部分，规定第一位和最后一位二进制编码均为1，其余位置随机产生0或1，即形成一个个体。图6为本发明实施例1提供的初始种群生成示例图，如图6所示，继续按照上述方式产生不同的个体，即形成初始种群。

[0083] (3)采用适应度函数对所述的初始种群的每个个体进行优化。

[0084] 运用遗传算法对线路上各区间内供电分区长度和数量设置方案进行优化时，每个个体即为一种供电分区组合设计方案，需要通过适应度函数衡量每个个体的优劣，以指导算法求解的方向。所述的适应度函数f(X)定义如公式 (6)所示：

[0085]

[0086] 式中，f表示线路上运行的列车，F为所有列车的集合，(i，j)表示线路上的弧段(即供电分区)，Ef表示列车f在线路上可能经过的所有弧段的集合，表示设置一个供电分区的广义成本相对于列车总运行时间的权重系数， nc表示区间c内供电分区的个数，wq表示区间内设置一个供电分区的广义成本。

[0087] 进一步地，供电分区设置方案优化问题的求解目标是线路通过能力和供电分区建设成本两者最优，本发明中线路通过能力最大的目标用所有列车的总旅行时间最小来表示，因此供电分区设置方案优化问题的求解目标即是所有列车的总旅行时间最小和供电分区的建设成本最低。

[0088] (4)通过遗传算子对所述的优化后的每个个体进行交叉和变异，产生出新一代种群。

[0089] 1)选择算子

[0090] 选择的目的是为了从所有可能的供电分区设置方案中选出相对较优的方案，并保留下来作为下一次迭代寻优过程的父代。优选地，采用轮盘赌法进行供电分区设置方案的选择，供电分区设置方案i被选中的概率为：

[0091]

[0092] 式中，Fi为供电分区设置方案i的适应度值，N为种群中供电分区设置方案的数目。

[0093] 2)交叉算子

[0094] 交叉算子模拟生物进化过程中的基因重组，将不同优秀父代个体间的基因进行交换，从而产生新的个体。优选地，采用多点交叉方式进行交叉算子，图7为本发明实施例1提供的多点交叉示意图，具体过程如图7所示。

[0095] 3)变异算子

[0096] 变异算子的作用是提高种群的多样性，使供电分区的设置方案增多，防止算法求解陷入局部最优或过早收敛。优选地，采用多点变异方式进行变异算子，图8为本发明实施例1提供的多点变异示意图，具体过程如图8所示。

[0097] 其中，遗传算法是以自然界中的生物进化过程为背景，将生物进化过程中的繁殖、选择、杂交、变异和竞争等概念引入算法中，并利用随机化技术对参数空间进行高效搜索的进化算法，具有很强的全局优化搜索能力。算法在搜索之前，先以某种形式对变量编码(编码后的变量称为染色体)，不同的染色体构成一个群体。初始种群产生之后，以某种方法评估出其适应值，按照适者生存和优胜劣汰的原理，借助遗传算子进行交叉和变异，产生出新一代种群。最终搜索到的末代最优个体经过解码，即为问题的最优解或满意解。在基本遗传算法中，选择、交叉和变异构成了遗传算法的遗传操作，参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。优选地，在本算法中，采用二进制编码形式表达个体，在满足模型变量的约束条件的基础上随机生成初始群体。

[0098] 进一步地，能力计算模型是为计算中速磁浮线路通过能力而构建的模型，模型的本质是列车运行图铺画问题，即列车在有限的时空资源内的组合优化问题。其基本原理是采用节点、弧段、弧集合(路径)的形式将实际线路抽象成物理空间网路，并通过引入累积流变量将列车在弧段上运行的连续时间轴离散为多个相等的时间段，建立列车运行的“时间-空间”网络，输入一定的列车数，能在该“时间-空间”网络中运行且不发生冲突的列车数即为该线路上的通过能力。另外，不同于传统的列车组合优化问题。优选地，本发明在模型中引入了“虚拟弧”的概念，虚拟弧的作用是当列车数量大于线路所能承载的能力时，列车无法通过实际路径从起始节点运行至终到节点，但可以从虚拟弧上通过，因此在一定程度上降低了模型的求解难度。

[0099] 优选地，根据供电分区设置方案，利用能力计算模型计算每种供电分区设置方案下的线路通过能力，包括将所述的供电分区设置方案转化为线路上的节点、弧段、弧集合，并根据能力计算模型计算每种供电分区设置方案下的线路通过能力。能力计算模型的具体内容如下式(8)～(23)所示。

[0100]

[0101]

[0102]

[0103]

[0104]

[0105]

[0106]

[0107]

[0108]

[0109]

[0110]

[0111]

[0112]

[0113]

[0114]

[0115]

[0116] 上述式(8)～(23)中所有字母的含义分别如下表1-表3所示。

[0117] 表1集合的符号化表述

[0118]

[0119] 表2参数的符号化表述

[0120]

[0121] 表3决策变量的符号化表述

[0122]

[0123] 其中，目标函数为Z1，表示所有列车在线路上的总运行时间最小；约束条件(9)～(11)分别表示列车在初始节点、中间节点和终到节点的流平衡， (12)表示物理网络与时空网络之间的映射约束，(13)和(14)表示列车在初始节点的最早发车时间约束，(15)表示列车在相邻弧段的离开和进入时刻约束，(16)～(18)表示列车在弧段上的运行时间约束，(19)表示停站时间约束，(20)表示弧段占用映射约束，(21)表示能力约束，(22)和(23)表示累积流变量基本约束。

[0124] 其中，物理网络中的点为中速磁浮线路上供电分区的端点，弧段即为一个供电分区的两个端点组成的线段。

[0125] 供电分区设置方案是指中速磁浮线路上区间内设置的供电分区的数量和每个供电分区的长度。

[0126] 进一步地，用拉格朗日松弛算法对每种供电分区设置方案下的线路通过能力进行优化更新迭代，包括：

[0127] 通过求解拉格朗日松弛问题，首先获得原问题的最优边界，再通过不断迭代更新拉格朗日乘子的方式，使松弛问题的解逐渐逼近原问题的最优解。需要说明的是，拉格朗日松弛算法是将原问题中的复杂约束松弛，并将该复杂约束作为惩罚项添加到目标函数中，从而使原问题的约束条件得以简化。下面对运用拉格朗日松弛算法求解中速磁浮线路通过能力计算模型的求解过程进行介绍。

[0128] (1)拉格朗日松弛问题

[0129] 将能力约束作为惩罚项添加到目标函数中，并对其进行恒等变换和分解：在所述的中速磁浮线路通过能力计算模型中，制约模型求解效率的约束是能力约束，即式(21)。该约束引起中速磁浮线路通过能力计算过程中列车之间的相互作用，大大增加了模型的求解规模，因此，将式(21)松弛，并作为惩罚项添加到目标函数中。

[0130]

[0131] 式中，ρi，j，t为式(21)的拉格朗日乘子，表示列车在时刻t占用(i，j)所产生的资源费用。对上式(24)进行恒等变换，得到下式(25)。

[0132]

[0133] 在拉格朗日松弛问题中，目标函数式(25)可以分解为1个常数项与所有列车LRf之和，如式下(26)所示，其中LRf由两部分组成，一部分为所有列车的时间效益，另一部分为列车占用行车资源的拉格朗日乘子之和。

[0134]

[0135] (2)基于动态规划的子问题的求解方法

[0136] 采用向前递推的动态规划算法策略求出列车运行的最短路径：将拉格朗日松弛子问题转化为多阶段的决策问题，并采用向前递推的动态规划算法策略求出列车运行的最短路径。动态规划算法中所涉及到的符号如下表4所示。

[0137] 表4动态规划算法中相关符号的表述

[0138]

[0139] 动态规划算法中的状态转移方程如公式(27)所示，即用来计算在第k+1 阶段的最优目标函数值ok+1，其中Δk，k+1对应于公式(21)中列车占用供电分区行车资源的资源费用。根据下式(27)得到各阶段每一状态的最优目标函数值。

[0140] ok+1＝min{ok+Δk，k+1} (27)

[0141] 动态规划算法的求解具体过程如下所述：

[0142] Step I：基础输入

[0143] 1)线路信息：车站、区间、供电分区(主要是弧段信息)；

[0144] 2)列车运行基本信息：列车数、列车起终点、列车可运行路径(包括实际弧和虚拟弧)等。

[0145] Step II：初始化

[0146] 创建初始路网VE，设置初始节点(of，σf)到任意中间节点(j，t′)的最小“费用”为o(j，t′)＝+∞， t＝1，...，T，o(of，σf)＝0。

[0147] Step III：更新标签

[0148] 根据上述信息，动态规划算法进行如下的标签更新步骤：

[0149]

[0150] Step IV：获取最短路径

[0151] 1)通过动态规划算法寻找节点(j*，t′*)，并将其作为初始节点到正在运算的节点(j，t′)处路径最短的最优节点；

[0152] 2)当节点(j，t′)不是路网的终到节点时，将节点(j，t′)添加到路网中，并更新节点(i，t)处的数据；

[0153] 3)反向回溯节点(j，t′)到节点(i，t)的最短路径；

[0154] 4)算法终止。

[0155] Step V：输出

[0156] 输出初始节点到终到节点的最短路径。

[0157] (3)拉格朗日乘子更新方法

[0158] 采用次梯度算法来更新拉格朗日乘子：需要说明的是，次梯度算法的基本思想是使线性规划问题的下界尽可能大，并且按照一定的上升方向逐渐趋近最优解，采用次梯度算法来更新拉格朗日乘子的更新表达式如下式(28) 所示：

[0159]

[0160] 式中，q为当前的迭代次数，αq＝1/(q+1)。

[0161] 次梯度算法是根据迭代过程中列车对行车资源的占用情况来确定梯度的下降方向，从而实现对拉格朗日乘子的更新。通过不断地调整拉格朗日乘子以及各列车对路径的选择，进而实现对行车资源的合理分配。

[0162] (4)拉格朗日启发式算法

[0163] 使用拉格朗日松弛算法后，原问题中的复杂约束被松弛，使得原问题解的可行域被扩大，可能出现得到的解是不可行解的情况。因此需要通过一定的方法高效的得到可行解。优选地，本发明将采用拉格朗日启发式算法，把求得的拉格朗日松弛问题结果中的拉格朗日乘子作为启发信息，并对线路上的每一列中速磁浮列车的运行顺序进行重新规划，进而求得可行解。具体步骤如下：

[0164] Step I：初始化

[0165] 初始化迭代次数，令q＝1；

[0166] 初始化上界值，将拉格朗日松弛算法得到的下界值作为当前上界的初始值，即：

[0167] Step II：求当前上界的最优解

[0168] 1)根据列车优先级的高低规划列车在线路上运行的顺序，列车的优先级由LRPf值的大小决定，LRPf的计算方法如下式(29)所示：

[0169]

[0170] 式(29)中LRPf的值越大，说明该列车f在线路上运行时的冲突越严重，即可调整的范围较小，LRPf的值越小则反之。优选地，本发明按照LRPf值从大到小的顺序依次对列车进行规划。

[0171] 2)根据列车优先级排序的结果，依次对列车f运用动态规划算法求得列车运行的最短路径；

[0172] 3)如果输入的列车无法在规定的能力利用范围时间段内被规划，则该列车会选择从虚拟弧上通过。

[0173] Step III：更新上界

[0174] 1)对比当前上界值与上一迭代次数上界值，利用公式 对当前上界值进行更新；

[0175] 2)利用公式 计算上下界之间的间隔；

[0176] 3)利用公式q＝q+1更新迭代次数。

[0177] 需要说明的是，运用拉格朗日启发式算法求解的过程中，最关键的步骤是确定每列车的铺画顺序，通过公式(29)依次计算出每列车的LRPf值确定其被铺画的顺序，并采用与拉格朗日松弛子问题相同的最短路径求解算法求解列车的最短路径，在求解的过程中，如果有列车因线路上行车资源的冲突较严重而无法铺画，则列车会选择从虚拟弧上通过，只是此时由于列车在虚拟弧上的运行时间较长，会使原函数的目标函数值增大。

[0178] 实施例2

[0179] 本发明实施例2提供了一个基于线路通过能力的供电分区优化设置方法算例。首先，根据算例的线路条件(包括车站、区间等)进行编码，通过遗传算法产生供电分区设置方案；其次，计算每种供电分区设置方案下的线路通过能力，并进行更新迭代；最后，直至目标函数收敛，选出线路通过能力最大的供电分区设置方案。

[0180] (1)算例线路介绍

[0181] 图9为本发明实施例2提供的大规模算例线路拓扑结构图，参照图9，中速磁浮设计线路为双线线路，全长为90km，全线共设5个车站，全线共有4个区间，每个区间的长度及可设定子段的最大个数分别如表5所示。根据中车唐山机车车辆有限公司设计的中速磁浮试验线的实际情况，取每个定子段的长度为500m。选取设计速度为200km/h的中速磁浮列车为研究对象，列车的运行时段取06：00-23：00。

[0182] 表5线路基础数据

[0183]

[0184] 本发明实施例只对区间内的供电分区设置方案进行优化，因此车站内部的供电分区长度和数量均设为定值，并将列车下行方向的始发站和终到站作为节点考虑(即不分析列车在车站内部的供电分区数量和长度，当列车离开区间4的最后一个弧段时，即表示列车进入终点站)。

[0185] (2)遗传算法迭代结果

[0186] 图10为本发明实施例2提供的遗传算法迭代结果图，参照图10，随着迭代次数的增加，模型的目标函数值逐渐变小。当迭代至第60次时，模型开始收敛，即第60次迭代求得的解为模型的最终解，模型的最终目标函数值为4220 min。

[0187] (3)供电分区设置方案及对应的线路通过能力求解结果

[0188] 选取遗传算法迭代过程中出现突变的第1、10和60次的迭代结果，分别找到其对应的供电分区设置方案，以及该供电分区设置方案下的线路通过能力求解结果，表6-表8分别表示第1、10和60次的遗传算法迭代结果对应的供电分区设置方案，图11本发明实施例2提供的供电分区数量及线路通过能力对比图，参照图11和表6-表8。

[0189] 表6第1次迭代

[0190]

[0191] 表7第10次迭代

[0192]

[0193] 表8第60次迭代

[0194]

[0195] 从上表6-表8中的数据可得，第1次迭代时供电分区个数为11，第10和60 次时供电分区个数分别为31和36。随着目标的渐优，供电分区的个数逐渐增加，且各供电分区(行车资源)的长度逐渐变短。模型收敛时，最终的供电分区设置方案如表5，从每个区间的供电分区的数量和长度的分布来看，其呈现的特点基本符合区间两端(进站和出站处)的供电分区长度较短，区间内部的供电分区较长，因为列车在进站和出站处的运行速度较低，在区间内部的运行速度较高，与实际相符，也验证了本发明所提出的方法的适用性。

[0196] 图11本发明实施例2提供的供电分区数量及线路通过能力对比图，参照图 11，其中第1次迭代时线路的通过能力为81列车，第10次迭代为135列车，第 60次迭代为158列车，由此可见，不同的供电分区设置方式对线路通过能力的影响非常大，其中，从第1次迭代至第10次迭代，线路通过能力提高了 66.7％，第10次至第60次迭代，线路通过能力提高了17.0％。

[0197] 通过图11的求解结果验证了遗传算法求解基于中速磁浮线路通过能力的供电分区优化设置方案的有效性，通过不断地迭代，即可求得能提高线路通过能力的供电分区设置方案，且线路通过能力提高的幅度比较明显。

[0198] 本领域技术人员应能理解上述优化设置方法的应用类型仅为举例，其他现有的或今后可能出现的优化设置方法如可适用于本发明实施例，也应包含在本发明保护范围以内，并在此以引用方式包含于此。

[0199] 综上所述，本发明实施例的基于线路通过能力的供电分区优化设置方法，通过从提高线路通过能力角度出发，克服了传统方法仅从牵引供电角度考虑的局限，使得实用性增强；从定子段角度分析供电分区的优化设置，更符合中速磁浮线路的实际情况；考虑了遗传算法和拉格朗日松弛算法的结合，提高了计算的效率和计算结果的可靠性。

[0200] 通过以上的实施方式的描述可知，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。

[0201] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。