A Improved Pareto of Ant Colony Algorithm to Solve the Vehicle Routing Problem with Time Windows

Abstract:

Vehicle routing problem with time Windows (VRPTW) that is a kind of important extension type for VPR. In view of problem which the ant colony algorithm in solving VRPTW easily plunged into local optimum , this paper defines a new ant transition probability of saving ideas, and uses the Pareto optimal solution set of global pheromone updating rule, and puts forward a kind of improved Pareto ant colony algorithm (IPACA) . Through the simulation experiments show that IPACA improves the global search ability of ACA, effectively avoids the algorithm falls into local optimum, and reduces the total distribution cost (distance), so as to verify the effectiveness of the proposed algorithm.

• Periodical: Advanced Materials Research (Volumes 1030-1032)
• Pages: 1941-1944
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1030-1032.1941
• Online since: September 2014
• Authors: Hong Dou Zhang*, Ning Guo, Jian Lin Mao, Hai Feng Wang
• Keywords: Ant Colony Algorithm, Pareto Optimal, Vehicle Routing Problem with Time Windows

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80-91.

DOI: 10.1287/mnsc.6.1.80

[2] Binglei Xie，Jun Li，Huihuang Guo. The genetic algorithm with time window and non full loaded vehicle scheduling problem [J]。Journal of systems engineering，2000, 15（3）；290-294.

[3] ZHANG Jiong, LANG Maoxiang. the tabu search algorithm of distribution vehicle scheduling problem with time windows[J]. Journal of Northern Jiaotong University, 2004, 28(2): 103-106.

[4] DORIFOM，MANIEZZOV，COLORNI A. Ant system: optimization by a colony of ooperating agents [A]. IEEE Transaction on System, Man，and Cybernetics, 1996, 26(1)：29-41.

DOI: 10.1109/3477.484436

[5] Zhong qiu Yang, Yanhua Zhang，Research on Improved Ant Colony Algorithm in the traffic system of the shortest path problem [J]. Information processing scientific computing，2009, 32（8）：76-78.

[6] Xiaofeng He, Liang Ma. Vehicle routing problem with time Windows of quantum ant colony algorithm [J]。Journal of Systems Science and Information，2013, 33（05）：1255-1261.

[7] Yingxin Chen，Vehicle routing optimization problem based on improved ant colony algorithm research [J]。Application Research of Computers，2012, 29（6）：2031-(2034).

[8] CLARCK G, WRIGHT J W. Scheduling of vehicles form a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581.

DOI: 10.1287/opre.12.4.568

[9] Geilen M , Basten T, Theelen B, et al. An algebra of pareto points [J]. Fundameta Informaticae, 2007, 78(1): 35-74.

[10] Shiquan Zhong，Guoguang He. Optimization of vehicle scheduling problem with time Windows a tabu algorithm [J]. Systems Engineering Theory. Methodology. Applications，2005, 14（6）：522-526.

[11] Linli，Xinshi Liu，Jiafu Tang。Improved ant colony algorithm for solving vehicle routing problem with time Window [J]. Control and Decision 2010, 25（9）：1379-1383.