面向动态公交的离散分层记忆粒子群优化算法

作     者：黄君泽 吴文渊 李轶 石明全 王正江 HUANG Junze;WU Wenyuan;LI Yi;SHI Mingquan;WANG Zhengjiang

作者机构：中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室重庆400714 中国科学院大学重庆学院人工智能学院重庆400714 重庆市凤筑科技有限公司重庆401120 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2024年第50卷第4期

页      面：20-30页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：重庆市院士牵头科技创新引导专项(cstc2020yszx-jcyjX0005 cstc2021yszx-jcyjX0004 cstc2022YSZX-JCX0011CSTB) 

主　　题：智慧交通 动态公交问题 电召问题 粒子群优化算法 预计算路径集 自适应变异 

摘      要：随着智慧城市、智慧交通的发展,移动互联网和公交智能基础设施以及相关数据的不断完善,通过用户手机预约公交服务的新型公交运营方式——动态公交,已经成为许多城市公交发展的重要探索方向。但目前,对动态公交问题的建模、算法研究不足。基于这一研究现状,提出动态公交问题模型和面向动态公交的离散分层记忆粒子群优化(PSO)算法。首先给出动态公交问题的目标函数和约束条件,给出动态公交问题的解的形式,并定义解的编辑距离;其次提出使用数据驱动的预计算路径集生成PSO算法的优质初始解的方法,给出基于解的编辑距离的PSO算法中粒子的变异概率和自适应收敛系数的计算方式;最后提出将粒子群分层求解的方法,其中低层粒子群可复用、可继承,从而减少单时间片内、时间片间复制和重初始化带来的性能损耗。基于重庆市北碚区蔡家岗街道的真实场景和亿级历史数据建立仿真环境进行实验,实验结果表明:相对于不分层PSO算法,分层PSO算法通过复用和继承能缩短超80%计算用时;自适应参数和变异机制能帮助算法更稳定地收敛到更优解;相对于传统公交系统,动态公交能在同等运力限制下,提高22%的乘客接单率,节省39.1%的乘客出行时间,所提算法能满足公交运营商在片区内进行动态公交调度的需求;相对于对比算法,所提算法平均缩短了85.3%的计算用时,并且在仅耗用80%里程的情况下提高了至少12%的接单率。