【摘要】 针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题。采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度。基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法。更多还原

【Abstract】 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.更多还原