一种求解共享单车再平衡问题的遗传算法

• 作者: 刘喜梅 潘立军
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 车辆路径问题 共享单车再平衡问题 遗传算法 线路交叉 破坏修复变异
• 年，卷（期）: 2019,（10）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 308-313
• 页数: 6页
• 分类号: TP18
• 字数: 4631字
• 语种: 中文
• DOI: 10.19678/j.issn.1000-3428.0054037

摘要

共享单车再平衡问题(BRP)是单一商品旅行商问题(1-PDTSP)的扩展,是一类NP难问题.针对已有算法求解速度慢,不利于实现实时调度优化的缺点,提出一种求解BRP的非代际遗传算法.基于个体搜索机制保留优异个体,设计线路交叉算子和k点破坏修复变异算子,引入破坏修复机制,当算法收敛变慢时自动生成新个体进入种群以避免陷入局部最优解.应用BRP标准算例测试表明:在小规模算例上该算法均能找到最优解,平均CPU消耗为3.8s;在中等规模与大规模算例上,该算法找到9个算例的最优解,并且其运算速度相较于分支定界算法和线路破坏与修复启发式算法提升77％以上.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘立军	湖南工程学院管理学院	27	165	6.0	12.0
2	刘喜梅	湖南工程学院管理学院	23	23	3.0	3.0