面向可持续城市用户多模态交通路径规划的Dijkstra辅助进化多目标优化

《Swarm and Evolutionary Computation》:Dijkstra-assisted evolutionary multiobjective optimization for a sustainable user urban multimodal transport routing

【字体: 大 中 小 】 时间:2026年08月29日 来源:Swarm and Evolutionary Computation 9.6

编辑推荐:

   摘要 本文在出行即服务(MaaS)范式下,针对大规模公共交通网络中的可持续多模式用户路径规划问题进行了研究,通过联合最小化总出行时间和二氧化碳排放量来实现该目标。我们提出了增强型Dijkstra辅助非支配排序遗传算法II(eD50N-II)方法,这是一种进化多目标方法,利用

  

摘要

本文在出行即服务(MaaS)范式下,针对大规模公共交通网络中的可持续多模式用户路径规划问题进行了研究,通过联合最小化总出行时间和二氧化碳排放量来实现该目标。我们提出了增强型Dijkstra辅助非支配排序遗传算法II(eD50N-II)方法,这是一种进化多目标方法,利用Dijkstra(DJ)最短路径算法生成具有针对性交叉和变异算子的知情种子策略。该方法在实际多模式多重图上运行,支持灵活的基于整数的解决方案表示,并考虑了真实的公共交通时刻表、换乘时间、步行连接和体力消耗约束。实验评估在两个大型都会区案例研究——波尔图和里斯本——上进行,这两组数据首次公开发布。结果表明,eD50N-II在超体积、Pareto最优解数量以及步行距离约束的可行性方面,持续优于其他进化方法,包括DJ种子NSGA-II(D2N-II,基线算法)、eN-II(一种改进的NSGA-II变体)和Haq*(一种先进方法的改编)。对于更简单的DJ配置,如加权的D50变体,其计算量更少,可能适用于对解质量要求不高的时间敏感型应用。然而,eD50N-II在合理的计算努力下获得了更丰富的Pareto最优解集合,当需要高质量且具有实际意义(对体力消耗友好)的路径时,是最佳选项。结果还证实了该方法在不同城市环境下的可扩展性和鲁棒性,强化了其在实际MaaS决策支持系统中的适用性。

引言

气候变化和不断增长的全球人口正在施加越来越大的压力,要求加速绿色转型并减少人类活动的碳足迹。交通部门在这一挑战中发挥着核心作用,2019年欧盟约四分之一的温室气体排放来自交通部门,其中道路交通占这一总量的72%。尽管有现行政策,预计到2050年该部门排放量仅比1990年水平减少22%,远低于欧洲绿色协议设定的2050年减排90%的目标[1]。

在此背景下,城市出行已成为缓解二氧化碳排放和促进可持续性的关键领域。现代城市交通系统日益增长的复杂性需要创新解决方案来优化出行并减轻环境影响。出行即服务(MaaS)的概念作为对此需求的综合应对方案应运而生,它允许在单一数字平台上组合不同的交通方式(如公共交通、私人交通、拼车、骑行)[2]。在本项大型研发项目的框架下,本研究提出了一种智能多模式交通规划MaaS模块,旨在为城市用户最小化出行时间和气体排放(CO?)。MaaS的目标是通过在用户遵循推荐路径时提供公共交通票价折扣或其他交通激励来促进绿色出行。

已知的Dijkstra(DJ)最短路径算法[3]被广泛用于单目标多模式交通路径规划(如Google Maps [4])。然而,如[5]所示,多目标DJ版本,如多目标最短路径(MOSP)[6]或多目标DJ算法(MDA)[7],在具有可变公共交通时刻表的复杂多模式交通路径规划任务中无法扩展,这在都会区尤为典型。在这些场景下,一个有趣的替代方法是使用进化多目标优化(EMO),因为它有可能提供高质量的Pareto权衡解。然而,如第2节所示,该领域的EMO研究很少,特别是在最小化出行时间和CO?并促进公共交通(如地铁、公交、步行、骑行)方面。

在我们之前的工作[8]中,我们提出了一种EMO方法,称为DJ种子非支配排序遗传算法II(本文中我们将其标记为D2N-II),其中包含以下使用:多重图数据和可变长度整数染色体,每个整数代表一条交通边(这种灵活表示使D2N-II几乎可以适用于任何都会区和交通类型集合);2个DJ解(分别针对出行时间和CO?目标优化)被插入随机初始种群;标准遗传算子生成新解(单点交叉和单整数变异);以及DJ修复机制来修正不可行解(当未到达目的节点时)。当应用于波尔图区域案例,涉及20个与三种交通类型(公交、地铁和步行)相关的简单、中等和困难的真实实例时,D2N-II在与非种子NSGA-II和2个DJ解的比较中获得了有竞争力的结果。

在我们之前工作的基础上,如第2节所述,本研究提出了一种大幅改进的进化系统,称为增强型DJ辅助NSGA-II(eD50N-II)。eD50N-II算法集成了:

(i)新的计算加速机制,通过使用多处理器(每个个体一个,每个DJ路径查询一个)、为先前计算的DJ CO?路径序列设置缓存内存(用于DJ修复、变异和交叉算子)以及通过经验研究获得有效的D2N-II种群规模(在不损害多样性的情况下加速收敛),从而实现更高效的EMO搜索;

(ii)搜索算法创新,具体包括:更丰富的种子策略,现在包含50个不同的DJ加权解(提高初始种群质量并减少修复解的需要);以及新的多重图专用变异和交叉算子,能够在利用DJ信息指导变异(DM)和交叉(DX)的同时重组个体。

此外,在本文中,我们扩展了[8]中进行的经验分析,通过:

1. 提出并探索一个新的里斯本都会区案例,包含更大的多重图(具有4427个节点)和更多类型的公共交通,即火车、渡轮和共享单车;以及

2. 考虑代谢当量(METS)[9]指标来评估完成行程的整体人体体力消耗,当采用不同的手动交通活动(如步行和骑行)时,这特别有用。

实验结果表明,eD50N-II始终优于先进方法的改编版本(本文中称为Haq*)[10]和先前的D2N-II方法,在波尔图和里斯本分别实现了对Haq*高达158.4%和121.0%的超体积改进,以及分别高达58.4%和37.4%对D2N-II的改进。

本文其余部分组织如下。第2节讨论相关工作。然后,第3节描述多模式交通路径规划方法。接着,第4节介绍波尔图和里斯本都会区案例。然后,第5节分析实验结果。最后,第7节讨论主要结论和Future工作。

分节片段

相关工作

表1总结了多模式交通路径优化的相关工作。该表按交通对象(货物或人员)组织,并在每个组内按时间顺序排列。为了比较目的,最后两行刻画了我们之前的工作[8]和提出的扩展研究,突出了主要差异和贡献,如下所述。

多模式路径优化研究已在不同的交通对象场景(列O)中发展,问题描述——本文解决的是一个可持续的人体多模式路径规划问题,该问题包括在都会区内根据一组M个优化标准选择公共交通和步行/骑行路径的合适组合,以在起点(???????)和终点(???????)之间出行。目标是支持真实的出行即服务(MaaS)系统,提供环境感知且以用户为中心的路径推荐,平衡可持续性与可用性。

使用案例——在本研究中,我们分析了两个主要的葡萄牙都会区(波尔图和里斯本),完全依赖开放的GTFS数据来构建多重图(??)。GTFS数据以压缩归档形式获得,包含关于公共交通运营的信息,包括终点站位置、服务日历、路线、到达和出发时间以及线路标识符。由于GTFS是公共交通的标准格式,相同的计算代码和——

结果——本节呈现并分析了实验结果。接下来的小节描述了按照第3.4节所述实验方法进行的实证分析。特别是,首先使用波尔图案例来设置和评估几个设计选择:在D2N-II中减小种群规模的影响(第5.1节);(ii)通过更大的、更多样的DJ衍生种子解丰富初始种群的影响(第5.2节);以及(iii)——

讨论与局限

结果表明了解质量与计算效率之间的明确权衡。所提出的eD50N-II方法持续产生更高质量的解,但代价是增加了计算时间。这种行为是可以预见的,因为该方法进行了更彻底的搜索空间探索,从而提高了优化性能。从实际角度来看,这种权衡暗示了不同的使用场景。eD50N-II变体更适合离线——

结论

公共交通部门正在经历由可持续性目标和减少城市出行环境影响的需求所驱动的深刻变革。在此背景下,多模式路径规划在支持出行即服务(MaaS)平台方面发挥着关键作用,使用户能够做出平衡出行效率、环境影响和体力消耗知情的决策。本文解决了以用户为中心的城市多模式交通路径优化问题,——

作者贡献声明

Guilherme Barbosa:撰写——审阅与编辑,撰写——原稿,可视化,验证,软件,资源,方法论,调查,概念化。

代码可用性

由于知识产权限制,源代码无法公开发布。然而,D2N-II和eD50N-II实现的可共享组件可在合理要求下提供。要求应通过电子邮件向本手稿中提供的通讯作者地址提交。

利益冲突声明

作者声明他们没有已知的可能影响本文工作的竞争财务利益或个人关系。

致谢

本研究由欧盟在NextGenerationEU下通过葡萄牙共和国的恢复和韧性计划(PRR)提供资助,范围涵盖BE.NEUTRAL项目——"城市碳中和出行议程"[项目编号35 – C644874240-00000016]。作者还感谢匿名审稿人的有益意见。

Guilherme Barbosa | Pedro José Pereira | Rui Mendes | Paulo Cortez
CCG/ZGDV研究所,Universidade大道,Azurém校区,14号楼,Guimar?es,4800-058,Braga,葡萄牙
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号