摘要
容量化车辆路径问题(CVRP)已被证明是NP完全问题,CVRP不仅在学术界受到关注,而且在许多工程领域得到了应用。提出了一种离散混合入侵杂草优化算法(DMIWO)来解决容量化车辆路径问题,引入遗传操作过程中的自适应变异和交叉算子,保证算法的多样性,防止算法陷入局部收敛早熟的局部最优解。使用实矩阵编码,并为父代区域中的子代构建离散化过程。针对容量化车辆路径问题的性质,提出了一种改进的2-Opt和交换操作结构,构建了两阶段混合变量域搜索方法,增强了算法的局部搜索能力和全局搜索能力。将仿真实验和文献中的遗传算法、粒子群算法及量子进化算法进行比较,证明了用DMIWO算法解决离散组合优化问题,简单、高效、适应性强。
Capacitated Vehicle Routing Problem（CVRP） has been proved to be a complete NP problem.CVRP has attracted attention not only in academia but also in many engineering applications. In this paper, a Discrete Invasive Weed Optimization（DIWO） algorithm is proposed to solve the problem of the capacity-based vehicle routing. The adaptive mutation and crossover operator in the genetic operation process are introduced to ensure the diversity of the algorithm and prevent the algorithm from falling into Local Convergence Premature Local Optimal Solution. Using real matrix coding and building a discretization process for children in the parent region, an improved 2-Opt and exchange operation structure is proposed based on the nature of the problem, and a two-phase mixed variable domain search method is constructed.Local search capabilities and global search capabilities of the algorithm are enhanced. Comparing the experimental simulation and the literature algorithm with the benchmarks of different scales, it is proved that the DIWO algorithm is simple, efficient and adaptable to the discrete combinatorial optimization problem.
作者
郇林
Huan Lin(Shaanxi Polytechnic Institute,Xianyang,Shaanxi,712000,China)
出处
《小型内燃机与车辆技术》
2018年第5期40-43,共4页
Small Internal Combustion Engine and Vehicle Technique
关键词
容量化车辆路径问题
离散混合入侵杂草优化算法
自适应变异
交叉算子
Capacitated vehicle routing problem
Discrete mixed invasive weed optimization
Adaptive mutation
Crossover operator
