近邻域搜索算法求解带容量约束的选址-路径问题

Solutions of the Location-Routing Problem with capacity constraints using Nearest Neighbor Search algorithm

针对遗传算法求解选址-路径问题存在收敛速度慢、易早熟等缺点,提出了一种近邻域搜索算法(Nearest Neighbor Search algorithm,NNS)。首先,在构造初始解阶段利用贪婪策略产生初始种群,提高初始解的质量;其次,在交叉阶段采用复制交叉的方式,增强算法的全局搜索;最后,在突变阶段使用近邻域局部搜索过程。此外,还设计了种群管理方案,以促进遗传算法种群多样性。在2个基准集上进行了试验,结果表明,与GRASP、MAPM、LRGTS等算法相比,该算法不仅显著提高了收敛速度,而且具有较强的寻优能力。

The genetic algorithm has the shortcomings of slow convergence speed and easy precocious maturity to solve the location-routing problem,the Nearest Neighbor Search algorithm is proposed.Firstly,the greedy strategy is used to generate the initial population in the stage of constructing the initial solution to improve the quality of the initial solution.Secondly,in the intersection stage,the hybrid crossover mode of copying intersection is adopted to enhance the global search of the algorithm.Finally,the near-domain local search process is used in the mutation stage.In addition,population management programmes have been designed to promote genetic algorithm population diversity.Experiments are carried out on two benchmark sets,and the results show that compared with GRASP,MAPM,LRGTS and other algorithms,the proposed algorithm not only significantly improves the convergence speed,but also has strong optimization ability when solving the location-routing problem.