Vehicle routing is an important combinatorial optimization problem. In real transport networks,the travel speed and travel time of roads have large time-variability and randomness. The study of vehicle routing problem in time-dependent network has even more practical value than static network VRP problem. This paper combines the features of time-dependent networks and gives the mathematical models of the 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 timedependent network are proposed. Based on these strategies, the improved ant colony algorithm is given for solving the vehicle routing problem in time-dependent networks. 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. © 2011 The Institute of Electronics, Information and Communication Engineers.
https://doi.org/10.1587/transcom.E94.B.1506Cite as:
@article{LIU_2011,
doi = {10.1587/transcom.e94.b.1506},
url = {https://doi.org/10.1587%2Ftranscom.e94.b.1506},
year = 2011,
publisher = {Institute of Electronics, Information and Communications Engineers ({IEICE})},
volume = {E94-B},
number = {5},
pages = {1506--1510},
author = {Yongqiang LIU and Qing CHANG and Huagang XIONG},
title = {An Improved Ant Colony Algorithm for the Vehicle Routing Problem in Time-Dependent Networks},
journal = {{IEICE} Transactions on Communications}
}