计算机工程

作者：刘喜梅, 潘立军

单位：湖南工程学院 管理学院, 湖南 湘潭 411104

关键词：车辆路径问题,共享单车再平衡问题,遗传算法,线路交叉,破坏修复变异

基金：湖南省自然科学基金（2019JJ60038）；湖南省双一流应用特色学科工商管理资助项目（湘教通[2018]469号）。

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

来源：2019年第10期

《计算机工程》期刊编辑部

查看计算机工程杂志2019年第10期