An Improved Ant Colony Algorithm for the Time-Dependent Vehicle Routing Problem

Vehicle routing problem is an important combinatorial optimization problem. It has an important position in logistics optimization and supply chain management theory. Due to traffic flow, traffic incidents and other factors, the travel speed and travel time of road has large time-variability and randomness in real transport network. The study of vehicle routing problem in time-dependent network has even more practical value. This paper combines features of time-dependent networks and gives the mathematical models of time-dependent vehicle routing problem. On this basis, the traditional ant colony optimization algorithm is improved. A new path transfer strategy of ants and new dynamic pheromone update strategy applicable to time-dependent network are proposed. Based on these strategies, the improved ant colony algorithm is given for solving the vehicle routing problem in time-dependent network. The simulation results show that the algorithm can effectively solve the vehicle routing problem in time-dependent network and has better computational efficiency and convergence speed.