基于最大最小蚂蚁系统的动态车辆路径问题研究

在描述动态车辆路径问题的基础上,通过对计划周期分片,将动态车辆路径问题转换为一系列的静态子问题,并采用改进的最大最小蚂蚁系统对静态子问题进行求解。在最大最小蚂蚁系统中,针对聚类分布和随机分布的客户,分别采用顺序法和并行法构建路线,信息素的更新量随着可选客户数量的不同而改变,同时在算法执行过程中对期望启发式因子、选择概率、信息素持续因子和蚂蚁数量等参数进行自适应调整。以整个路线的行驶距离作为目标,采用该算法对9个算例进行测试,与其他文献中算法的计算结果相比较,在使用车辆数量基本一致的情况下,9个问题都得到了最好解和最好平均解,表明了算法的有效性。

Research of dynamic vehicle routing problem based on max-min ant system

In the paper, planning period is divided and the dynamic vehicle routing problem is partitioned into a series of static sub problems, which is solved by an improved max min ant system. In the max min ant system, routes are constructed by sequence method and parallel method for customers with clustering distribution and random distribution respectively. The value of pheromone updating is altered with the number of customers which can be selected by an ant. Due to the behavior of ant colony algorithms depends strongly on the value of 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. Nine instances were tested with the objective to minimize total travelling distance of all routes. Compared with results obtained by other algorithms in literature, the number of used vehicles is basically the same, best solutions and the best average solutions have been found for all instances by max min ant system with parameter adaptation. It demonstrates the effectiveness and robustness of the algorithm in solving these problems.