包装废弃物回收车辆路径问题的改进遗传算法

目的采用优化传统遗传算法(GA)研究包装废弃物回收车辆路径问题(VRP)的性能。方法提出改进遗传算法(IGA)。首先,设计基于贪婪算法的初始种群生成算子,提高初始种群质量;其次,设计根据适应度值大小、进化代数等自适应调整的交叉和变异概率;然后,设计最大保留交叉算子,保证种群的多样性;最后,对企业实例和标准算例进行仿真测试。结果采用IGA算法、蚁群算法(ACO)能求得算例最优解,且IGA算法运行速度快于ACO算法,分支界定算法(BBM)、传统GA算法无法求得算例最优解。结论与BBM算法、传统GA算法和ACO算法相比,IGA算法求解包装废弃物回收VRP问题的整体性能更优。

Improved Genetic Algorithm for Vehicle Routing Problem in Packaging Waste Recycling

The work aims to optimize the performance of traditional genetic algorithm (GA) used to solve the vehicle routing problem (VRP) in packaging waste recycling. An improved genetic algorithm (IGA) was put forward. Firstly, in order to improve the quality of initial population, the initial population generation operator based on greedy algorithm was designed; secondly, the crossover and mutation probabilities adaptively adjusted based on fitness values and evolutionary algebras were designed; then, the maximum preserved crossover operator was designed to ensure population diversity. Finally, simulation tests were carried out on an enterprise instance and standard examples. IGA and ant colony algorithm (ACO) were used to get the optimal solution of the example, and IGA ran faster than ACO. The branch and bound algorithm (BBM) and traditional GA could not find the optimal solution of the example. Compared with the BBM, traditional GA and ACO, IGA has better overall performance in solving the VRP problem of packaging waste recycling.