时间依赖型车辆路径问题的一种改进蚁群算法

Improved ant colony optimization algorithm for time-dependent vehicle routing problem

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.

Time-dependent vehicle routing problem （TDVRP） is concerned with vehicle routing optimization in road networks with fluctuant link travel time. The traditional vehicle routing problem （VRP） has been proven to be an NP- hard problem, so it is difficult to solve TDVRP in considering traffic conditions. We design an improved ant colony optimization algorithm （ACO） for TDVRP. It uses nearest neighbor algorithm based on minimum cost（NNC algorithm） to generate the initial solution, improves feasible solution by local search operations, and updates pheromone with max/min ant system strategy. Test results show that compared with the nearest neighbor algorithm and genetic algorithm, the improved ACO algorithm is more efficient and able to get better solutions. Furthermore, this improved ACO algorithm show good performance in large scale TDVRP instances, even if the customer number of TDVRP reaches 1000, the computation time is still in an acceptable range.