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

Improved Genetic Algorithm for Vehicle Routing Problem in Packaging Waste Recycling

作　　者：张异[1] ZHANG Yi(Chongqing Technology and Business Institute, Chongqing 401520, China)

机构地区：[1]重庆工商职业学院,重庆401520

出　　处：《包装工程》2018年第17期147-152,共6页Packaging Engineering

基　　金：重庆市教委人文社科项目(16SKGH209);重庆工商职业学院重点项目(ZD2014-03)

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

关 键 词：包装废弃物 回收 车辆路径问题 遗传算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]