一种面向超大规模公交网络的智能优化算法

1.本发明属于网络结构设计技术领域，具体涉及一种面向超大规模公交网络的智能优化算法。


背景技术：

2.公交网络优化自1925年由德国学者patz提出以来，由于其求解的non-deterministic polynomial hard特点，一直以来受到了学者的高度关注。从1979年经典的mandl网络，到1998年王炜教授提出的“逐条布设、优化成网”法，到2014年avishai ceder教授设计的遗传算法，再到2019年高自友教授团队考虑与轨道交通的接驳问题，设计的列生成算法。chao wang等基于一种多层次、多模式的网络设计方法，提出了一种城市公交线路网络设计的混合优化模型。liujiang kang等研究了多式联运巴士和火车的最佳时刻衔接服务，构建混合整数非线性规划模型，并使用辅助二元变量对模型进行线性化和重构。自1925年直至现在，公交网络优化问题一直是国内外研究的热点问题之一，普遍受到各界研究学者的重视，随着社会进步及城市扩张，公交面临更加复杂的运行场景，这对无论是建模还是算法，都提出了更高的要求。根据特大城市现实公交运行场景，项目组同时考虑碳排放、轨道交通、不确定性等构建模型设计算法。
3.当前，模型及算法适用于超大规模公交网络。公交网络规模大幅增长导致公交线网优化的计算复杂度呈现指数级增长，通过研究新的求解算法，提高求解速度，支持多方案的快速比选。模型算法支持多层级的公交线路优化。优化过程分层级开展并考虑层级之间的融合。公交线网优化算法需解决公交线网与轨道线网的一体化融合问题，处理好轨道与公交衔接换乘关系。公交线网优化算法以最小化乘客出行成本和公交服务成本为目标，实现在给定需求总量、公交场站及车辆规模等约束条件下，快速完成公交线网的优化计算。


技术实现要素：

4.本发明的目的在于提供一种提高遗传算法的全局搜索能力、快速完成公交线网的优化计算的面向超大规模公交网络的智能优化算法。
5.为了实现上述发明目的，本发明采用以下技术方案：
6.一种面向超大规模公交网络的智能优化算法，包括如下步骤：
7.1)构建干线层鲁棒优化模型：假设成本参数已知，在一定约束下，建立以乘客出行成本为优化目标的数学模型；
8.2)开发干线层混合智能优化算法：基于路径进行编码，在遗传算法的交叉算子中引入模拟退火算法，通过多种算法优点的结合来设计混合智能优化算法；
9.3)构建普线层鲁棒优化模型：针对普线层的特点考虑非直线系数约束，垂直行驶将导致公交与轨道的交汇点，进而构建普线层鲁棒优化模型；
10.4)开发普线层混合智能优化算法：输入前面优化的干线公交网络和发班频率，利用基于线路频率进行编码；
11.5)开发微循环层混合智能优化算法：在算法编码上与干线层、普线层有所区别，针对其特点项目组设计基于排列的编码；
12.6)构建“干+普+微”全网鲁棒优化模型：针对所有网络的公交线网密度约束、换乘次数约束以及碳排放等，并结合前面的分层优化模型构建由“干普微”构成的全网公交鲁棒优化模型。
13.根据以上特征，所述步骤1)中的模型范式可表达为：
[0014][0015]
进一步地，所述步骤1)中先对干线层进行建模求解，再对普线层，微循环层，最后对由“干+普+微”构成的三层网络融合叠加，循环迭代，进行优化调整。
[0016]
在一些示例中，所述步骤1)中在干线层，首先利用公交刷卡数据、出租车行驶数据以及手机信令等多源数据识别骨干走廊，在建模中，针对轨道站点运能不足的问题，设置指定节点。
[0017]
根据以上特征，所述步骤2)中利用yen算法，计算od对之间的k短路并编号，然后将最短的线路编号作为基因，即每一个基因代表一条干线公交线路，需要1000条线路就只需要1000个基因。
[0018]
在一些示例中，所述步骤4)中对于不满足该约束的初始线路，将其剔除重新生成k+n条。
[0019]
根据以上特征，所述步骤6)中设置触发机制，当影响超过触发值时启动发车频率优化，当频率优化不能满足要求时再启动全网优化。
[0020]
与现有技术相比，本发明的有益效果是：
[0021]
1)本发明在遗传算法的编码方面，以往有关公交网络优化的研究大多是用的01编码，而这一编码方式会产生大量的无效解。为此，我们设计基于线路的编码方式。同时还考虑发车频率。每一个基因代表一条线路，一条染色体就代表一个公交网络。
[0022]
2)本发明针对遗传算法容易陷入局部搜索的问题，我们综合利用模拟退火算法、禁忌搜索算法和小生境淘汰法来提高遗传算法的全局搜索能力。
[0023]
3)本发明综合考虑不确定性、轨道交通以及碳排放等构建的“干+普+微”超大规模公交网络鲁棒优化模型。
附图说明
[0024]
图1为本发明干线层混合智能优化算法示意图。
[0025]
图2为本发明公交网络改进前后示意图。
[0026]
图3为本发明微循环层优化的示意图。
[0027]
图4为本发明微循环层编码的示意图。
[0028]
图5为本发明微循环层混合智能优化算法流程图。
[0029]
图6为本发明全网公交鲁棒优化模型示意图。
[0030]
图7为本发明“干+普+微”全网混合智能优化算法示意图。
[0031]
图8为本发明一种面向超大规模公交网络的智能优化算法示意图
具体实施方式
[0032]
下面将参照附图更详细地描述本发明的实施例。虽然附图中显示了本发明的实施例，然而应该理解，可以以各种形式实现本发明而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了使本发明更加透彻和完整，并且能够将本发明的范围完整地传达给本领域的技术人员。本领域的技术人员可以在不偏离本发明精神和保护范围的基础上从下述描述得到替代技术方案。
[0033]
实施例1
[0034]
一种面向超大规模公交网络的智能优化算法，包括如下步骤：
[0035]
1)构建干线层鲁棒优化模型：假设成本参数已知，在一定约束下，建立以乘客出行成本为优化目标的数学模型；
[0036]
模型范式可表达为：
[0037]
先对干线层进行建模求解，再对普线层，微循环层，最后对由“干+普+微”构成的三层网络融合叠加，循环迭代，进行优化调整。在干线层，首先利用公交刷卡数据、出租车行驶数据以及手机信令等多源数据识别骨干走廊，在建模中，针对轨道站点运能不足的问题，设置指定节点。
[0038]
2)开发干线层混合智能优化算法：基于路径进行编码，在遗传算法的交叉算子中引入模拟退火算法，通过多种算法优点的结合来设计混合智能优化算法；利用yen算法，计算od对之间的k短路并编号，然后将最短的线路编号作为基因，即每一个基因代表一条干线公交线路，需要1000条线路就只需要1000个基因。这样编码与网络行成一对一映射。不仅如此，针对公交与轨道之间的竞合关系，在此基础上还同时对发车频率进行优化。
[0039]
另外针对遗传算法容易陷入局部最优的问题，在遗传算法的交叉算子中引入模拟退火算法，在变异算子中，利用在2018年“全球运筹优化挑战赛”中荣获总冠军的禁忌搜索算法来对个体进行局部操作，增强算法的局部搜索能力，以促使算法跳出局部最优，进而通过多种算法优点的结合来设计混合智能优化算法。干线层混合智能优化算法流程如图1所示。
[0040]
3)构建普线层鲁棒优化模型：针对普线层的特点考虑非直线系数约束，垂直行驶将导致公交与轨道的交汇点，进而构建普线层鲁棒优化模型；为此，设计如图2所示的公交网络，避免此类问题的发生，而使两者尽可能更好的合作。
[0041]
4)开发普线层混合智能优化算法：输入前面优化的干线公交网络和发班频率，利用基于线路频率进行编码；对于不满足该约束的初始线路，将其剔除重新生成k+n条。
[0042]
5)构建微循环层鲁棒优化模型：与干线层、普线层公交网络不同的是微循环层公交网络本质上是著名的vehicle routing problem(简称，vrp问题)。而且是节点带时间窗的有取有送的与轨道、干线衔接的vrp问题。因此，项目组将根据微循环层的特点构建微循环层vrp模型，微循环层公交网络优化模型如图3所示。
[0043]
6)开发微循环层混合智能优化算法：在算法编码上与干线层、普线层有所区别，针对其特点项目组设计基于排列的编码；微循环层混合智能优化算法编码如图4所示，流程如图5所示。
[0044]
6)构建“干+普+微”全网鲁棒优化模型：针对所有网络的公交线网密度约束、换乘
次数约束以及碳排放等，并结合前面的分层优化模型构建由“干普微”构成的全网公交鲁棒优化模型，如图6所示。设置触发机制，当影响超过触发值时启动发车频率优化，当频率优化不能满足要求时再启动全网优化。
[0045]
7)开发“干+普+微”全网混合智能优化算法：结合分层网络的优化构造出由“干普微”构成的全网公交综合智能优化算法。另外，公交在实际运行中不能随意变更线路和站点，乘客最能接受的当属发车频率变化。为此，项目组还将设置触发机制，当影响超过触发值时启动发车频率优化，当频率优化仍不能满足要求时再启动全网优化。针对模型的独特性，开发如图7所示的混合智能优化方法。
[0046]
本发明从系统分析的角度，通过实证研究数据挖掘相结合的方法、定性研究与定量研究相结合的方法以及运筹学、对比分析法等相关理论，采用鲁棒优化方法等辨识不确定环境下的路径选择机理，构建不确定环境下的优化模型，在模型求解中，针对模型的np难特点及模型的独特性，精确算法难以实现在可接受计算时间与资源情况下给出问题最优解，设计智能优化方法，最终完成对相关内容的研究。
[0047]
1)实证研究：实证研究是进行优化建模的基础，即通过现场访谈的形式，获取出行者等对同行时间、成本等服务属性的重要度排序，掌握现有的路径选择行为影响因素。进而以问卷调研的形式，模拟场景，根据可选的备选方案，做出相应的路径选择行为，从而获取路径选择行为数据。通过对选择行为数据的处理与分析，实现对乘客路径选择行为机理的研究。
[0048]
2)数据挖掘：数据挖掘是在对大量数据进行处理、分析的基础上，筛选出有效信息，并利用有效信息预测或揭示数据的发展趋势或潜在联系的过程。公交网络优化中，不确定性等增加了乘客路径选择行为数据的处理维度。通过数据挖掘技术，配合实证研究，能够根据路径选择行为数据，挖掘隐性变量对路径选择行为机理的影响，并利用粗糙集理论进行属性约简，去除冗余因素，降低模型的维度。
[0049]
本发明在算法方面，首先用精确算法与我们设计的算法结果进行对比，然后对中规模问题进行求解，最后，针对大规模问题无法利用精确算法求解对比我们所提算法的效果问题，利用拉格朗日松弛算法等求取大规模问题解的界限，分析我们的算法。
[0050]
本发明成果能够应用于公交线网工作中，对多层级公交线网进行合理规划。在干线层级，能够通过多源数据确定大客流骨干走廊，基于大客流走廊和各种交通方式的比较优势，布局公交线网，解决目前高峰轨道压力较大的问题；在普线层级，能够通过合并、减重复等措施优化提升线路，达到提质增效的目的；在微循环层级，能够充分利用轨道交通车站客流集散规律通过新增或长线变短线的方式布局公交接驳线路，形成与轨道与公交衔接融合的出行模式。成果可应用于以重庆为代表的特大城市公交线网优化工作中(重庆的公交线路已有770余条之多)，能为公交线网优化提供科学论据，提高公交线网优化技术水平，加强规划设计和运营管理的合理性。同时，能够进一步减小政府财政补贴压力，降低公交公司运营成本，提升公共交通的吸引力和绿色出行比例，提高公交服务能力和品质，改善居民公交出行的乘车体验，推动城市交通可持续发展。
[0051]
以上所述，仅为本公开的具体实施方式，但本公开实施例的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本公开实施例揭露的技术范围内或者在本公开实施例揭露的思想下，可轻易想到变化、替换或组合，都应涵盖在本公开实施例的保护范围之内。

技术特征：
1.一种面向超大规模公交网络的智能优化算法，其特征在于包括如下步骤：1)构建干线层鲁棒优化模型：假设成本参数已知，在一定约束下，建立以乘客出行成本为优化目标的数学模型；2)开发干线层混合智能优化算法：基于路径进行编码，在遗传算法的交叉算子中引入模拟退火算法，通过多种算法优点的结合来设计混合智能优化算法；3)构建普线层鲁棒优化模型：针对普线层的特点考虑非直线系数约束，垂直行驶将导致公交与轨道的交汇点，进而构建普线层鲁棒优化模型；4)开发普线层混合智能优化算法：输入前面优化的干线公交网络和发班频率，利用基于线路频率进行编码；5)开发微循环层混合智能优化算法：在算法编码上与干线层、普线层有所区别，针对其特点项目组设计基于排列的编码；6)构建“干+普+微”全网鲁棒优化模型：针对所有网络的公交线网密度约束、换乘次数约束以及碳排放等，并结合前面的分层优化模型构建由“干普微”构成的全网公交鲁棒优化模型。2.根据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤1)中的模型范式可表达为：3.根据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤1)中先对干线层进行建模求解，再对普线层，微循环层，最后对由“干+普+微”构成的三层网络融合叠加，循环迭代，进行优化调整。4.根据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤1)中在干线层，首先利用公交刷卡数据、出租车行驶数据以及手机信令等多源数据识别骨干走廊，在建模中，针对轨道站点运能不足的问题，设置指定节点。5.据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤2)中利用yen算法，计算od对之间的k短路并编号，然后将最短的线路编号作为基因，即每一个基因代表一条干线公交线路，需要1000条线路就只需要1000个基因。6.据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤4)中对于不满足该约束的初始线路，将其剔除重新生成k+n条。7.据权利要求1所述的一种面向超大规模公交网络的智能优化算法，其特征在于所述步骤6)中设置触发机制，当影响超过触发值时启动发车频率优化，当频率优化不能满足要求时再启动全网优化。

技术总结
本发明公开了一种面向超大规模公交网络的智能优化算法，属于网络结构设计技术领域。本发明通过构建干线层鲁棒优化模型、开发干线层混合智能优化算法、构建普线层鲁棒优化模型、开发普线层混合智能优化算法、开发微循环层混合智能优化算法、构建“干+普+微”全网鲁棒优化模型这六个步骤予以实现。本发明在遗传算法的编码方面，以往有关公交网络优化的研究大多是用的01编码，而这一编码方式会产生大量的无效解。每一个基因代表一条线路，一条染色体就代表一个公交网络。本发明针对遗传算法容易陷入局部搜索的问题，我们综合利用模拟退火算法、禁忌搜索算法和小生境淘汰法来提高遗传算法的全局搜索能力。法的全局搜索能力。法的全局搜索能力。


技术研发人员：刘松 林文婷 周思徽 刘狄 高新华 冯诗媛 蔺雅芝 李晶晶 屈杰庆 彭勇
受保护的技术使用者：重庆交通大学
技术研发日：2023.07.12
技术公布日：2023/10/15