基于自感应蚁群算法的VRPSDP问题研究

Vehicle Routing Problem with Simultaneous Delivery and Pick-up Studied Based on Self-telepathy Ant Colony Algorithm

同时供货和取货的车辆路径问题是车辆路径问题的重要组成部分之一,问题的复杂性使得目前的主要求解方法局限于各种插入式启发算法。本文引用了近年来出现的蚁群算法,并通过对蚂蚁行为的深入研究,首次提出了感应因子、期望程度因子、距离性比因子以及加速因子的概念,在信息素更新方面融入了当前路径的距离特征,构建了一种全新的自感应蚁群算法。该方法充分利用全局分布的信息素感应信息,并且根据车辆容量支配值以及节点间距和节点-中心点间距性比进行状态转移,利用信息素更新公式中加速因子的动态调节有效地解决了算法快速收敛与陷入局部最优的矛盾。仿真试验证明了自感应蚁群算法的有效性,同时,该算法也拓展了车辆路径问题的算法空间。

Vehicle routing problem with simultaneous delivery and pick-up is one of the important components of the vehicle routing question, and the complexity of the question makes the present solving methods confined to various kinds of insert heuristics algorithm. By quoting the ant colony algorithm appearing in recent years and the further investigation of anfs behavior, the paper puts forward to the definitions of reaction factor, expect degree factor, relative distance quality factor and accelerate factor for the first time, incorporates the distance characteristic of the present route in the field of pheromone upgrading, and finally structures a new selftelepathy ant colony algorithm （STACA）. STACA method fully utilizes the overall distributed pheromone to respond to information, shifts the state according to the arranging value of capacity of vehicle and the proportion between nodal interval and the node and interval of central point, and effectively solves the contradiction between fast searching and falling into local optima by utilizing the dynamic regulation accelerate factor in the pheromone newer formula. The artificial test has proved the validity of STACA, meanwhile, this algorithm expanded the algorithm space of VRP too.