求解车辆路径问题的多邻域下降搜索蚁群优化算法

Ant colony optimization algorithm for capacitated vehicle routing problem based on multiple neighborhood descent searching

本文提出一种结合改进蚁群优化算法和多邻域下降搜索的混合启发式算法IACO_MND,求解运力限制的车辆路径问题.利用改进的蚁群系统算法构造方法产生多个可行解,再将产生的解作为多邻域下降搜索的初始解.在搜索过程中使用三种不同的邻域结构:插入,交换和2-opt以扩大局部搜索的范围.实验对不同规模的benchmark算例进行求解,结果表明本文算法能在较短的时间内获得若干算例的已知最好解,求解效率高,收敛速度快,稳定性强.

A hybrid heuristic algorithm IACO_MND is proposed and applied to solving the capacitated vehicle routing problem,which combines two meta-heuristics,i.e.,ant colony optimization(ACO) and multiple neighborhood descent(MND).Capacitated vehicle routing problem is a non-deterministic polynomial problem.With the increase of the number of customers,the optional number of vehicle routing solutions will grow exponentially.Ant colony optimization is a meta-heuristics groups algorithm,and it is good at finding area may be the optimal solution.However,multiple neighborhood descent is the locus method,and it is good at finding a better solution in the region.So,take full advantage of the two algorithms can improve the algorithm's search efficiency and performance.First of all,several feasible solutions are built by an insertion based improved ACO(IACO) solution construction method,which is taken as the initial solution of the MND procedure.IACO is have some different with ACO.In our algorithm,a distance-based greedy method is used to create a strong feasible solution.Then one heuristic based on backpack is used to create a weakly feasible solution.We also make some improvement in local pheromone update and global pheromone update.During the MND procedure,three different neighborhood structures,i.e.,insertion,swap and 2-opt are successively used.Computational results on the benchmark problems with the size ranging from 20 to 100,show that the proposed hybrid algorithm can find the best known solution for some problems in a short time,which indicates that the proposed IACO_MND outperforms other algorithms in literatures.However,we also find some problem in the experimental procedure.First one is the execution time increases significantly as the model of the increasing trend.That is because we carry out local search in each iteration.Second one is the algorithm iterations is less,and we think that is because we can obtained the better solution after several iterations,but it will lead to we cannot make full use of the advantages of ACO.In the further,we will further balance the advantage of the ACO and MND.