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

作     者：刘喜梅 潘立军 LIU Ximei;PAN Lijun

作者机构：湖南工程学院管理学院 

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

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

年 卷 期：2019年第45卷第10期

页      码：308-313页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

D　O　I：10.19678/j.issn.1000-3428.0054037

馆 藏 号：203794918...