基于环交换的ACO&CT算法求解车辆路径问题

An ACO&CT hybrid algorithm based on cyclic transfer for solving vehicle routing problem

以著名的车辆路径问题为研究对象,提出了一种基于自适应环交换的ACO&CT混合算法。为了提高蚁群优化算法的搜索能力,将蚁群优化算法的构解机制与环交换的同时移动多个点的邻域结构结合起来。解的改进采用自适应环交换邻域的搜索算法,即当一种长度类型的环交换不能再改进目标函数时,自动转向其它长度类型的环交换开始进行新的搜索。同时针对环交换的大规模邻域,针对问题特征,提出算法加速策略。实验结果证明了基于自适应环交换的混合算法(ACO&CT)在求解车辆路径问题时的有效性。

For the well-known vehicle routing problem,a hybrid algorithm,namely,ACO&CT based on adaptive cyclic transfer is proposed.In order to improve the diversification search ability of ant colony optimization(ACO)algorithm,the main feature of the ACO&CT algorithm is to hybridize the solution construction mechanism of the ACO algorithm with multi-exchange neighborhood structure of cyclic transfer(CT)algorithm.During implementing the hybrid algorithm,the adaptive cyclic transfer algorithm can also be embedded into the ACO algorithm to improve solutions.That is,when a length type of cyclic transfers cannot be modified to improve the objective function,it is automatically switched to another type of the cycle length to start a new search.Despite the size of the cyclic transfer neighborhood is very large,an acceleration strategy is adopted according to the characteristics of the problem.Experimental results have proven that the proposed hybrid algorithm(ACO&CT)is effective for solving the vehicle routing problem.