A New Dynamic Globe Pheromone Ant System and its Application in VRP

Abstract:

To solve the deficiency of ant colony optimization as falling into local optimal solution easily, the paper proposes a dynamic globe pheromone ant system which based on the small world network phenomenon of information exchange in ant colony system and simulates this mechanism by meanings of the wave equation of volatilization pheromone, and then constructs the particle wave function of diffuse pheromone as well as the corresponding condition shift formula. Through dynamic surveying proliferation wave information, the ant is able to effectively absorb the effective information containing in the inferior solutions during the process of seeking superior solution, and can carry on the condition shift using the globe distributed pheromone information, thus enhance the quality of solution. Taking vehicle routing problem as example, the computed result shows that compared the basis colony optimization DGPAS has higher globe search ability.

• Periodical: Advanced Materials Research (Volumes 129-131)
• Pages: 1361-1365
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.129-131.1361
• Online since: August 2010
• Authors: Lu Lin
• Keywords: Ant Colony Optimization (ACO), Globe Pheromone, Vehicle Routing Problem (VRP)

References

[1] Bullnheimer B, Hartl R. F, and Strauss C: Applying the ant system to the vehicle routing problem. In I. H. Osman S. Vo� , S. Martello and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academics, pp.109-120 (1998).

DOI: 10.1007/978-1-4615-5775-3_20

[2] Stutzle T, Hoos H: MAX－MIN ant system, Future Generation Computer Systems, Vol. 16(8), pp.889-914 (2000).

DOI: 10.1016/s0167-739x(00)00043-1

[3] Bullnheimer B, Hartl RF, Strauss C: A new rank based version of the ant system-a computational study. Central European J Oper Res Econom , Vol. 7, pp.25-38 (1999).

[4] SHI Libao, HAO Jin: The Numerical Characteristics Analysis and Convergence Proof for Ant Colony Optimization Algorithm with Random Perturbation Behavior, Journal of System Simulation, Vol. 11, pp.2421-2424 (2004).

[5] Pilat, M.L. and T. White: Using genetic algorithms to optimize ACS-TSP, Proceedings of Ant Algorithms: Third International Workshop, ANTS 2002, Brussels, Belgium, September 2002, M. Dorigo et al(Eds). LNCS 2463, Springer-Verlag, pp.282-287.

DOI: 10.1007/3-540-45724-0_28

[6] Information on http: /www. branchandcut. org/VRP/data Path length/m Evolutionary time/ number Figure 2 the optimal curves of B78k10VRP of two algorithms.