基于改进遗传算法的家电回收车辆路径规划方法

Path Planning Method for Household Appliance Recycling Vehicle Based on Improved Genetic Algorithm

摘要:

为了提高家电回收效率以及降低回收成本，提出了一种基于改进遗传算法（GA）的家电回收车辆路径优化方法。将家电回收车辆路径规划问题建模为一个变体的旅行商问题（TSP）以最小化运输成本，但该问题难以在多项式时间内进行求解。提出了一种基于高斯矩阵变异（GMM）算子的改进遗传算法，利用原始站点数据信息中隐含的站点位序分布特性建立高斯概率矩阵，并采用轮盘赌选择法将高斯概率矩阵作用于个体基因突变，在保证种群基因多样性的同时，引导种群向高适应度方向进化。最后，采用上海地区的家电回收点实际数据开展实验仿真以验证所提出算法的有效性，并与其他算法进行对比。结果表明，与传统遗传算法相比，在将求解精度差保持在1%以内的情况下，所提出改进遗传算法的平均收敛速度可以提升50%~60%，算法耗时降低48%。

Abstract:

In order to improve the recycling efficiency and reduce the cost of recycling disused products， a path optimization method for recycling vehicles based on a modified genetic algorithm （GA） was proposed. Firstly， the path planning problem for the recycling vehicle was modeled as a variant of the traveling salesman problem （TSP）， aiming at minimizing transportation costs， which， however， is an NP-hard problem. Then， an improved genetic algorithm based on the Gaussian matrix mutation （GMM） operator was put forward. The algorithm leveraged the site order distribution characteristics hidden behind the original station data information to establish a Gaussian probability matrix. The Gaussian probability matrix was then applied to individual gene mutations combined with the roulette selection method， so as to guide the population to evolve towards high fitness while maintaining the genetic diversity. Finally， comprehensive simulations were carried out using the actual data collected from recycling sites in Shanghai to validate the proposed algorithm， and compared with other algorithms. The simulation results show that the proposed algorithm can increase the average convergence speed by 50%~60% and reduce the time consumption by 48% compared with the traditional genetic algorithm， under the precision gap within 1%.