基于改进NSGA-Ⅱ的多目标车间物料配送方法

Multi-objective workshop material distribution method based on improved NSGA-Ⅱ

针对车间物料配送效率低的问题,建立以配送路径最短和时间窗惩罚值最小为目标的物料配送多目标优化模型,提出基于快速非支配排序遗传算法(NSGA-Ⅱ)的混合优化算法INSGA-Ⅱ.该算法采用密度峰值聚类(DPC)初始化种群,缩减问题规模;在NSGA-Ⅱ遗传操作阶段,采用差分进化(DE)算法,避免陷入局部最优;通过变异向量的差分操作与部分映射交叉加快迭代速度,同时提高种群多样性.通过求解不同基准函数与不同规模算例验证算法的有效性,结果表明,与传统NSGA-Ⅱ算法相比,改进算法具有更优帕累托前沿,同时算法结果的均匀性和多样性更好,求解时间更短.研究结果表明,新算法生成的结果更优;相比NSGA-Ⅱ算法、多目标粒子群算法(MOPSO),生成的总配送距离减少26.65%,总时间窗惩罚减少32.5%,能有效提高车间物料的配送效率.

Addressing the inefficient distribution of materials in workshops,a multi-objective optimization model with the shortest distribution path and the smallest time window penalty value was established.A hybrid optimization algorithm,INSGA-Ⅱ,based on a fast non-dominated sorting genetic algorithm(NSGA-Ⅱ)was proposed.Density peak clustering(DPC)was adopted to initialize the population and reduce the problem size.To avoid falling into local optimums,the differential evolution(DE)algorithm was used in the genetic operation stage of NSGA-Ⅱ.The differential operation of mutation vectors was used with partial mapped crossover to accelerate the iteration speed and improve the population diversity.Different benchmark functions were solved with different sizes of arithmetic cases,and the results showed that the improved algorithm had better Pareto front compared to the traditional NSGA-Ⅱalgorithm.Meanwhile,the results of the proposed algorithm had better uniformity and diversity,and the solution time was shorter.Experimental results showed that the proposed algorithm generated,compared with the NSGA-Ⅱand the multi-objective particle swarm optimization(MOPSO),the total distribution distance could be reduced by up to 26.65%and the total time window penalty could be reduced by up to 32.5%.The new method can effectively improve the distribution efficiency of workshop material.