最小最大车辆路径问题的动态自适应蚁群优化算法

摘要

为求解最小最大车辆路径问题，提出动态自适应蚁群优化算法。该算法采用动态最大最小蚂蚁系统策略调整最优解，每次迭代更新τmin ，将τmin作为当前信息素矩阵最大值的函数，根据当前最优弧调整选择弧的概率。采用一种灰色模型预测及控制信息素矩阵的边界，以增强蚁群算法参数的自适应性能。对信息素浓度相对较高的多个节点及其附近的边，利用信息素关联累积规则进行信息素更新。将文中算法进行场景的实例测试，仿真结果表明，该算法与线性规划、其他相关的蚁群算法相比，收敛速度更快，具有更好的优化性能和应用效果。%To solve the min-max vehicle routing problem ( MMVRP ), a dynamic adaptive ant colony optimization algorithm is proposed. The dynamic max-min ant system is adopted to adjust the optimal solution. τmin is updated per iteration, it is regarded as the function of maximum in the pheromone matrix, and the probability of selecting arc is adjusted according to the optimal arc. A kind of gray model is employed to forecast and control the boundary of pheromone matrix to enhance the self-adaption of parameters in ant colony algorithm. Advantage of pheromone associated with accumulation rules is taken to update multiple nodes with relatively high concentration of pheromone and edges nearby. The proposed algorithm is tested on examples. The simulation results show that compared with linear programming algorithm and other related ant colony algorithms, the proposed algorithm has a higher convergence speed and better optimization performance and applicability.