最小-最大车辆路径问题的蚁群算法

Min-max vehicle routing problem based on ant colony algorithm

为了最小化车辆路径问题中行程最长子线路的长度,提出了一种可应用于不同数据集特点的参数自适应最大最小蚂蚁系统。针对聚类分布和随机分布的客户,分别采用顺序法和并行法构建路线,同时在算法执行过程中对期望启发式因子、选择概率、信息素持续参数和蚂蚁数量等参数进行自适应调整,既强化最优解附近的搜索,加快算法的收敛速度,也从一定程度上保证解的多样性,避免陷入局部优化。将该算法应用于7个经典算例的最小-最大车辆路径问题,计算结果表明,不仅可以取得较好的计算结果,而且算法的计算效率较高,收敛速度较快。

To minimize travelling distance of the longest route among all routes, max-min ant system with parameter adaptation was adopted to solve vehicle routing problem, and it can be applied to different data- sets in practice. Routes are constructed by sequence and paralleling method for datasets with customers clustering and random distribution respectively. Since the behavior of ant colonies algorithms depends strongly on the values given to parameters, multi-parameters including distance heuristic factor, choice probability, level of pheromone persistence and the number of ants are self-adapted at different stages in the course of algorithm execution, which helps to accelerate convergence with intensity search around best solution, as well as to maintain diversity to avoid failing into local optimization. Seven classical instances were tested for min-max vehicle routing problem. The results demonstrate the effectiveness and robustness of max-rain ant system with parameter adaptation in solving these problems.