摘要
针对物流配送中具有容量限制的车辆路径问题,设计了一种结合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.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2007年第10期2047-2052,共6页
Computer Integrated Manufacturing Systems
基金
安徽高校自然科学研究基金资助项目(2006KJ253B)。~~
关键词
物流配送
车辆路径问题
混合遗传算法
双层染色体
2-OPT子路径优化
logistics distribution
vehicle routing problem
hybrid genetic algorithm
double layers chromosome
2- OPT sub-routes optimization
