变邻域遗传算法在车间物流调度中的应用

Application of Variable Neighborhood Genetic Algorithm in Workshop Logistics Scheduling

针对含有自动引导小车(Automated Guided Vehicle,AGV)的离散化车间物流调度问题,以最小化物流任务时间惩罚成本和最小化运载小车的总行驶距离为优化目标,构建离散化车间多目标物流调度优化模型,设计一种基于Pareto寻优的多目标混合变邻域搜索遗传算法(VNSGA-II).以遗传算法为基础,通过使用NSGA-II的Pareto分层和拥挤度计算方法评估种群优劣实现多目标优化,为了提高算法的寻优能力,避免算法陷入局部最优,通过添加保优记忆库对精英个体进行保护,并利用变邻域搜索算法在搜索过程中的局部寻优能力,针对本文模型特点,设计6个随机邻域结构,来达到算法求解最优值的目标.并提出了基于关键AGV小车的插入邻域和基于关键物流任务的交换邻域调整策略以进一步降低成本.最后,以某离散车间物流调度为实例,分别使用VNSGA-II、带精英策略的快速非支配排序遗传算法II(Nondominated Sorting Genetic Algorithm II,NSGA-II)和强Pareto进化算法(Strong Pareto Evolutionary Algorithm 2,SPEA2)对问题进行求解,计算结果表明,VNSGA-II能得到更好的Pareto解集,验证了算法的有效性和可行性.

Aiming at the discrete job-shop logistics scheduling problem with Automated Guided Vehicles(AGVs),a multi-objective discrete job-shop logistics scheduling optimization model is constructed to minimize the time penalty cost of the transfer task and the total travel distance of the vehicle.A multi-objective hybrid Variable Neighborhood Search Genetic Algorithm(VNSGA-II)based on Pareto optimization is designed.Based on the genetic algorithm,the Pareto stratification and crowding-degree calculation method of NSGA-II are used to evaluate the population to achieve multiobjective optimization.The elite individuals are protected by adding the optimal memory to improve the optimization ability of the algorithm and avoid falling into the local optimum.Moreover,the local optimization ability of the variable neighborhood search algorithm is used to design six random neighborhood structures in light of the model features in this paper,thereby solving the optimal value.For a lower cost,the insertion neighborhood based on the critical AGV and the exchange neighborhood adjustment based on the critical transfer task are proposed.Finally,with a discrete job-shop logistics scheduling problem as an example,VNSGA-II,Nondominated Sorting Genetic Algorithm II(NSGA-II),and Strong Pareto Evolutionary Algorithm 2(SPEA2)are adopted respectively.The results show that VNSGA-II can get a better Pareto solution set,which verifies the effectiveness and feasibility of the algorithm.