基于混合遗传算法的生鲜配送路径优化研究

Research on Fresh Food Delivery Route Optimization based on Hybrid Genetic Algorithm

生鲜农产品配送路径规划问题是复杂的NP难问题,为提高配送路径规划效率,有效指导生鲜企业的配送路径规划,文章分析了生鲜配送及带时间窗的车辆路径问题的特点,考虑时间窗约束构建了配送路径最短的数学模型。在传统遗传算法的基础上,引入C-W节约算法改进种群初始化,大规模邻域搜索算法改进局部搜索操作,提出一种混合遗传算法,并进行算例仿真。经计算,算例的最优配送路径包括4条线路,最短配送距离为68.72 km,优于传统遗传算法所得最短路径。验证结果表明:本研究给出的混合遗传算法能较好地解决有时间窗的车辆路径问题,所得方案较优,可以指导企业配送车辆的路径规划。

The fresh agri-product delivery route programming problem is a complex NP-hard problem.In order to improve the efficiency of delivery route planning and effectively guide the delivery route planning of fresh food enterprises,this paper analyses the characteristics of fresh food delivery and vehicle route problem with time windows(VRPTW)problems,and builts a mathematical model of the shortest delivery route considering the time window constraint.Based on the traditional genetic algorithm,the C-W saving algorithm is introduced to improve the population initialization and the large-scale neighborhood search algorithm to improve the local search operation,and a hybrid genetic algorithm is proposed and applied for simulation.The optimal distribution route of the algorithm is calculated to include four routes and the shortest distribution distance is 68.72 km,which is better than the shortest route obtained by the traditional genetic algorithm.The validation results show that the hybrid genetic algorithm given in this paper can better solve the VRPTW,and the resulting solution is better and can guide the enterprise to plan the route of distribution vehicles.