基于混合遗传算法的城市固体废弃物运输路径优化研究

Research on Transportation Route Optimization of Municipal Solid Waste Based on Hybrid Genetic Algorithm

针对城市固体废弃物运输成本不确定的特点,文章在车辆路径问题的基础上对带时间窗的城市固体废弃物运输问题进行研究。考虑到遗传算法存在局部搜索能力不足的缺陷,在遗传算法的基础上结合变邻域搜索算法的思想提出了混合遗传算法。(1)采用三种邻域搜索算子用于改进遗传算法的变异算子;(2)采用模拟退火算法中的Metropolis判别法则来更新邻域搜索最优解;(3)采用自适应交叉变异概率和最优个体保留策略提高算法的运算效率。采用Solomen算例中的7个标准例题对算法性能进行测试,实验结果表明,混合遗传算法能够求得质量更高的解。最后通过算例来验证该模型的可行性,在满足时间窗和载重约束下缩短行驶距离。

In view of the uncertainty of transportation cost of municipal solid waste, this paper studies the transportation problem of municipal solid waste with time window on the basis of vehicle routing problem. Considering the shortage of local search ability of genetic algorithm, a hybrid genetic algorithm is proposed based on genetic algorithm and the idea of variable neighborhood search algorithm.(1) Three neighborhood search operators are used to improve the mutation operator of genetic algorithm;(2) The Metropolis criterion in simulated annealing algorithm is used to update the neighborhood search optimal solution;(3) Adaptive crossover mutation probability and optimal individual reservation strategy are used to improve the efficiency of the algorithm.The performance of the algorithm is tested by using 7 standard examples in the solomen example. The experimental results show that the hybrid genetic algorithm can obtain higher quality solutions. Finally, an example is given to verify the feasibility of the model and shorten the driving distance under the time window and load constraints.