Improved ant colony optimization algorithm for time-dependent vehicle routing problem
时间依赖型车辆路径问题的一种改进蚁群算法

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 NPhard 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.