Dynamic Adaptive Ant Colony Optimization Algorithm for Min-Max Vehicle Routing Problem
GE Bin1,2, HAN Jiang-Hong1, WEI Zhen3, CHENG Lei3, HAN Yue2
1.School of Computer and Information, Hefei University of Technology, Hefei 230009 2.College of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001 3.GO COM Information Technology Co., Ltd, Hefei 230088
Abstract To solve the min-max vehicle routing problem (MMVRP), a dynamic adaptive ant colony optimization algorithm is proposed. The dynamic max-min ant system is adopted to adjust the optimal solution. τmin is updated per iteration, it is regarded as the function of maximum in the pheromone matrix, and the probability of selecting arc is adjusted according to the optimal arc. A kind of gray model is employed to forecast and control the boundary of pheromone matrix to enhance the self-adaption of parameters in ant colony algorithm. Advantage of pheromone associated with accumulation rules is taken to update multiple nodes with relatively high concentration of pheromone and edges nearby. The proposed algorithm is tested on examples. The simulation results show that compared with linear programming algorithm and other related ant colony algorithms, the proposed algorithm has a higher convergence speed and better optimization performance and applicability.
[1] Dantzing G, Ramser J H. The Truck Dispatching Problem. Management Science, 1959, 10(6): 80-91 [2] Colorni A, Dorigo M, Maffioli F, et al. Heuristics from Nature for Hard Combinatorial Optimization Problems. International Transactions in Operational Research, 1996, 3(1): 1-21 [3]Dorigo M,Gambardella L M. Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Trans on Evolutionary Computation, 1997, 1(1): 53-66
[4] Stützle T, Hoos H H. MAX-MIN Ant System. Future Generation Computer Systems, 2000, 16(9): 889-914 [5] Dorigo M, Birattari M, Stützle T. Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39 [6] Favaretto D, Moretti E, Pellegrini P. On the Explorative Behavior of MAX-MIN Ant System // Proc of the 2nd International Workshop on Engineering Stochastic Local Search Algorithms, Designing, Implementing and Analyzing Effective Heuristics. Brussels, Belgium, 2009: 115-119 [7] Crawford B, Soto R, Johnson F, et al. A Max-Min Ant System Algorithm to Solve the Software Project Scheduling Problem. Expert Systems with Applications, 2014, 41(15): 6634-6645 [8] Benavent E, Corberán , Sanchis J M. A Metaheuristic for the Min-Max Windy Rural Postman Problem with k Vehicles. Computational Management Science, 2010, 7(3): 269-287 [9] Liu X, Qi H. Tabu Search Algorithm of Min-Max Vehicle Routing Problem. Journal of Systems Engineering, 2007, 25(1): 49-52 (in Chinese) (刘 霞,齐 欢.最小-最大车辆路径问题的禁忌搜索算法.系统工程学报, 2007, 25(1): 49-52) [10] Liu X, Yang C. Min-Max Vehicle Routing Problem Based on Ant Colony Algorithm. Journal of PLA University of Science and Technology: Natural Science Edition, 2012, 13(3): 336-341 (in Chinese) (刘 霞,杨 超.最小-最大车辆路径问题的蚁群算法.解放军理工大学学报:自然科学版, 2012, 13(3): 336-341) [11] Su C, Tu J. An Adaptive Max-Min Ant Colony Algorithm. Pattern Recognition and Artificial Intelligence, 2007, 20(5): 688-691(in Chinese) (苏 畅,徒 君.一种自适应最大最小蚁群算法.模式识别与人工智能, 2007, 20(5): 688-691) [12] Bai J, Yang G K, Chen Y W, et al. A Model Induced Max-Min Ant Colony Optimization for Asymmetric Traveling Salesman Pro-blem. Applied Soft Computing, 2013, 13(3): 1365-1375 [13] Yu J P, Wang C G. A Max-Min Ant Colony System for Assembly Sequence Planning. International Journal of Advanced Manufac-turing Technology, 2013, 67(9/10/11/12): 2819-2835 [14] Ren C Y. Solving Min-Max Vehicle Routing Problem. Journal of Software, 2011, 6(9): 1851-1856 [15] Mavrovouniotis M, Yang S X. Ant Colony Optimization with Immi- grants Schemes for the Dynamic Travelling Salesman Problem with Traffic Factors. Applied Soft Computing, 2013, 13(10): 4023-4037 [16] Tang J F, Ma Y Y, Guan J, et al. A Max-Min Ant System for the Split Delivery Weighted Vehicle Routing Problem. Expert Systems with Applications, 2013, 40(18): 7468-7477 [17] Christofides N, Mingozzi A, Toth P. Contributions to the Quadratic Assignment Problem. European Jonrnal of Operational Research, 1980, 4(4): 243-247 [18] Zhang Y, Liu Y C. An Improved Ant Colony Optimisation and Its Application on Multicast Routing Problem. International Journal of Wireless and Mobile Computing, 2011, 5(1): 18-23 [19] Deng X Y, Zhang L M, Lin H W, et al. Pheromone Mark Ant Colony Optimization with a Hybrid Node-Based Pheromone Update Strategy. Neurocomputing, 2014, 148: 46-53 [20] Krynicki K, Jaen J, Mocholi J A. Ant Colony Optimization for Resource Searching in Dynamic Peer-to-Peer Grids. International Journal of Bio-inspired Computation, 2014, 6(3): 153-165 [21] Wang C, Chen Z Q. Parallel Ant Colony Optimisation Algorithm for Continuous Domains on Graphics Processing Unit. International Journal of Computing Science and Mathematics, 2013, 4(3): 231-241 [22] Geng J Q, Weng L P, Liu S H. An Improved Ant Colony Optimization Algorithm for Nonlinear Resource-Leveling Problems. Computer & Mathematics with Applications, 2011, 61(8): 2300-2305 [23] Saenphon T, Phimoltares S, Lursinsap C. Combining New Fast Opposite Gradient Search with Ant Colony Optimization for Solving Travelling Salesman Problem. Engineering Application of Artificial Intelligence, 2014, 35: 324-334 [24] Chen L, Sun H Y, Wang S. A Parallel Ant Colony Algorithm on Massively Parallel Processors and Its Convergence Analysis for the Travelling Salesman Problem. Information Sciences, 2012, 199: 31-42 [25] Narasimha K S V, Kumar M. Ant Colony Optimization Technique to Solve the Min-Max Single Depot Vehicle Routing Problem // Proc of the American Control Conference. San Francisco, USA,2011: 3257-3262 [26] Carlsson J G, Armbruster B, Ye Y Y. Finding Equitable Convex Partitions of Points in a Polygon Efficiently
2015, Vol. 28 
