开放式车辆路径问题的蚁群优化算法

Research on ant colony optimization algorithm for the open vehicle routing problem

研究了开放式车辆路径问题,该问题中车辆在服务完最后一个顾客点后不需要回到车场,若要求回到车场,则必须沿原路返回.提出了一种混合蚁群优化算法,该算法主体是一个在超立方框架下执行的MAX-MIN蚂蚁系统,算法混合了禁忌搜索算法作为局部优化算法,同时算法集成了一个后优化过程来进一步优化最优解.基于标准测试问题,最后给出了算法同文献中其它算法的性能比较结果,计算结果表明本文提出的算法是一个有效的求解开放式车辆路径问题的方法.

This paper studies the open vehicle routing problem, in which the vehicles do not return to the starting depot after serving the last customers or, if they do, they must make the same trip in the reverse order. We propose an Ant Colony Optimization metaheuristic hybridized with tabu search algorithm for the open vehicle routing problems. The proposed algorithm is a MAX-MIN Ant System hybridized with tabu search, which is implemented in the hyper-cube framework. Additionally, a post - optimization procedure is incorporated in the proposed algorithm to further improve the best- found solutions. The computational results of the proposed algorithm compared to those of other algorithms are reported. The computation results experimentally indicate that the proposed algorithm is an efficient method for solving the open vehicle routing problems.