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

摘要：

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

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

所属期刊栏目：45

分类号：TP18(自动化基础理论)

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

在线出版日期：2019-11-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：308-313