求解车辆路径问题的混合遗传算法  

Hybrid genetic algorithm for capacitated vehicle routing problem

作　　者：姜昌华[1] 戴树贵[1] 胡幼华[1] 

机构地区：[1]华东师范大学信息科学技术学院,上海200062

出　　处：《计算机集成制造系统》2007年第10期2047-2052,共6页Computer Integrated Manufacturing Systems

基　　金：安徽高校自然科学研究基金资助项目(2006KJ253B)。~~

摘　　要：针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题。采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度。基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法。A hybrid genetic algorithm with 2-OPT sub-routes optimization was presented for Capacitated Vehicle Routing Problem （CVRP） in the logistics distribution optimization area. In this method, a Double Layers Chromosome （DLC） coding scheme was proposed which could assure each sub-route was feasible and generate chromosome according to customer＇s number in DLC without knowing the optimal vehicle number of the CVRP in advance. Profit from above-mentioned features, the hybrid genetic algorithm was more suitable to solve the practical VRP whose minimal vehicle number was unknown in advance. 2-OPT algorithm was used to optimize sub-routes to accelerate convergence speed. Simulations based on typical benchmark problems showed that the algorithm was feasible and effective.

关 键 词：物流配送 车辆路径问题 混合遗传算法 双层染色体 2-OPT子路径优化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]