%0 Journal Article
%T Improved ant colony optimization algorithm for time-dependent vehicle routing problem<br>时间依赖型车辆路径问题的一种改进蚁群算法
%A DUAN Zheng-yu
%A YANG Dong-yuan
%A WANG Shang
%A <br>段征宇
%A 杨东援
%A 王上
%J 控制理论与应用
%D 2010
%I 
%X 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.
%K time-dependent vehicle routing problem
%K ant colony optimization algorithm
%K nearest neighbor algorithm<br>时间依赖型车辆路径规划问题
%K 蚁群算法
%K 最邻近算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=970898A57DFC021F93AB51667BAED7F7&aid=EE1D8A3BBC24E400D76095E29DE84A20&yid=140ECF96957D60B2&vid=DB817633AA4F79B9&iid=708DD6B15D2464E8&sid=CDD86F65AA3A5D34&eid=3F0F3A1477A0E1FE&journal_id=1000-8152&journal_name=控制理论与应用&referenced_num=0&reference_num=0