基于多邻域的车辆路径优化迭代局部搜索算法

针对物流配送中的带有容量约束的车辆路径优化问题,提出了一个基于多邻域的迭代局部搜索算法HILS.首先用简单插入法构造可行解,然后从该初始解出发,在多邻域内进行局部优化.当陷入局部最优解后,根据解的接受准则,选择某个解,并对该解进行扰动,然后从扰动后的解出发重新进行局部优化.为提高搜索效率,局部优化过程只在限定邻域内进行.在国际通用的14个benchmark问题上进行仿真实验,结果验证了本文算法HILS的有效性和稳定性,与文献中的其他几种算法的比较结果表明,算法HILS的总体性能更优.

A Multi-Operator Based Iterated Local Search Algorithm for the Capacitated Vehicle Routing Problem

A multi-operator based local search heuristic algorithm HILS is proposed for solving the capacitated vehicle routing problem （CVRP）. Firstly, a simple insertion heuristic method is used to construct a feasible initial solution. After that, the local search process improves the incumbent solution in the multi-neighborhood until no more improvement can be obtained. Select a solution according to the acceptance criterion, and perturb it to get a new solution, which is set as the starting point of the local search process in the next iteration. To accelerate the local search process, only the restricted neighborhood is searched. Experiments results on the 14 benchmark problems demonstrate the effectiveness and stability of the proposed HILS. Furthermore, the HILS performs better in a whole compared with the other state-of-the-art heuristics from the literature.