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

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

Abstract: The Bike-sharing Rebalancing Problem (BRP) is an extension of the Single Commodity Traveler Problem (1-PDTSP) and a type of NP-hard problem.To address the slow solution speed of the existing algorithms,which is not conducive to real-time scheduling optimization,a non-intergenerational genetic algorithm for solving BRP is proposed.The excellent individuals are retained based on the individual search mechanism,and the line crossover operator and k-point destroy and repair mutation operator are designed.The destroy and repair mechanism is introduced,and when the convergence speed of the algorithm slows down,new individuals are automatically generated into the crowd to avoid falling into the local optimal solution.Computational results on the benchmark problems show that the algorithm can find the optimal solution for the small-scale benchmark problems with an average CPU consumption of 3.8 s.For the medium-scale and large-scale benchmark problems,the algorithm finds the best solutions for 9 benchmark problems,and the speed is improved by over 77% than those of B&C and D&R algorithms.

Key words: Vehicle Route Problem(VRP), Bike-sharing Rebalancing Problem(BRP), genetic algorithm, line cross, destroy and repair mutation

中图分类号: 

• TP18