Dynamic Hybrid Ant Colony Optimization Algorithm for Solving the Vehicle Routing Problem with Time Windows
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.GOCOM Information Technology Co., Ltd, Hefei 230088
Abstract To solve the vehicle routing problem with time windows (VRPTW), a dynamic hybrid ant colony optimization algorithm (DHACO) is proposed, so as to avoid the disadvantages of traditional ant genetic hybrid algorithm, such as static setting, redundant iteration and slow convergence. Firstly, an initial solution is obtained through max-min ant system, and the ant colony optimization algorithm is adopted to get a basic feasible solution to VRPTW. Then, the crossing and mutation operations of genetic algorithm are employed to re-optimize local and global solutions, thus the optimal solution is obtained. Finally, based on the fusion strategy of ant genetic hybrid algorithm, and by employing ant algorithm and genetic algorithm dynamically and alternately, the parameters of ant colony algorithm is self-adaptively controlled according to cloud association rules. DHACO reduces the times of redundant iteration and speeds up the rate of the convergence. Simulation results show that DHACO is better than the other related heuristic algorithms as to the optimal solutions.
[1] Golden B L, Assad A A. Perspectives on Vehicle Routing: Exciting New Developments. Operations Research, 1986, 34(5): 803-810 [2] Golden B L, Assad A A. Vehicle Routing: Methods and Studies. Amsterdam, The Netherlands: Elsevier Science Publishers, 1988 [3] Desrochers M, Desrosiers J, Solomon M M. A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research, 1992, 40(2): 342-354 [4] Desrosiers J, Dumas Y, Solomon M M, et al. Time Constrained Routing and Scheduling // Ball M O, Magnanti T L, Monma C L, et al., eds. Handbooks in Operations Research and Management Science 8. Amsterdam, The Netherlands: Elsevier Science Publi-shers, 1995: 35-139 [5] Brysy O, Gendreau M. Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 2005, 39(1): 104-118 [6] Brysy O, Gendreau M. Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, 2005, 39(1): 119-139 [7] Hu X P, Ding Q L, Wang Y Z. A Hybrid Ant Colony Optimization and Its Application to Vehicle Routing Problem with Time Windows // Proc of the International Conference on Life System Modeling and Simulation and International Conference on Intelligent Computing for Sustainable Energy and Environment. Wuxi, China, 2010, I: 70-76 [8] Pang K W. An Adaptive Parallel Route Construction Heuristic for the Vehicle Routing Problem with Time Windows Constraints. Expert Systems with Applications, 2011, 38(9): 11939-11946 [9] Baos R, Ortega J, Gil C, et al. A Hybrid Meta-Heuristic for Multi-objective Vehicle Routing Problems with Time Windows. Computers & Industrial Engineering, 2013, 65(2): 286-296 [10] He X F, Ma L. Quantum-Inspired Ant Colony Algorithm for Vehicle Routing Problem with Time Windows. Systems Engineering-Theory & Practice, 2013, 33(5): 1255-1261 (in Chinese) (何小锋,马 良.带时间窗车辆路径问题的量子蚁群算法.系统工程理论与实践, 2013, 33(5): 1255-1261) [11] Cao Q K, Zhao F. Port Trucks Route Optimization Based on GA-ACO. Systems Engineering-Theory & Practice,2013, 33(7): 1820-1828 (in Chinese) (曹庆奎,赵 斐.基于遗传蚁群算法的港口集卡路径优化.系统工程理论与实践, 2013, 33(7): 1820-1828) [12] 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) [13] Xia Y M, Cheng B, Chen J L, et al. Optimizing Service Composition Based on Improved Ant Colony Algorithm. Chinese Journal of Computers, 2012, 35(2): 270-281 (in Chinese) (夏亚梅,程 渤,陈俊亮,等.基于改进蚁群算法的服务组合优化.计算机学报, 2012, 35(2): 270-281) [14] Liu Q, Chen H, Zhang Y G, et al. An Ant Colony Optimization Algorithm Based on Dynamic Evaporation Rate and Amended Heuristic. Journal of Computer Research and Development, 2012, 49(3): 620-627 (in Chinese) (刘 全,陈 浩,张永刚,等.一种动态挥发率和启发式修正的蚁群优化算法.计算机研究与发展, 2012, 49(3): 620-627) [15] Pan L J, Fu Z. Genetic Algorithm for the Pickup and Delivery Problem with Time Windows. Systems Engineering-Theory & Practice, 2012, 32(1): 120-126 (in Chinese) (潘立军,符 卓.求解带时间窗取送货问题的遗传算法.系统工程理论与实践, 2012, 32(1): 120-126) [16] Wang Y, Yang H Q, Zhang R J. Research on Vehicle Routing Problem with Time Window Based on Strong Gene Schema Combination Algorithm. Control and Decision, 2011, 26(4): 606-610 (in Chinese) (汪 勇,杨海琴,张瑞军.基于强基因模式组织算法的VRPTW研究.控制与决策, 2011, 26(4): 606-610) [17] Zhao N, Wu Z L, Zhao Y Q, et al. Ant Colony Optimization Algorithm with Mutation Mechanism and Its Applications. Expert Systems with Applications, 2010, 37(7): 4805-4810 [18] Zhang L M, Zhang Y, Liu W B. The Design of Target Assignment Model Based on the Reverse Mutation Ant Colony Algorithm. Procedia Engineering, 2012, 29: 1554-1558 [19] Peng C L, Liang C H, Zhou H. Improved Genetic Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deli-veries. Journal of System Simulation, 2008, 20(9): 2266-2270 (in Chinese) (彭春林,梁春华,周 泓.求解同时取货和送货车辆路径问题的改进遗传算法.系统仿真学报, 2008, 20(9): 2266-2270) [20] Wang Y H, Wang W X, Yu H X, et al. Dynamic Balance Adaptive Colony Algorithm Solving Job-Shop Scheduling. Computer Integrated Manufacturing Systems, 2013, 19(10): 2521-2527 (in Chinese) (王艳红,王文霞,于洪霞,等. 一类求解作业车间调度问题的动态平衡自适应蚁群算法.计算机集成制造系统, 2013, 19(10): 2521-2527) [21] Jia S J, Du B, Yue H. Local Search and Hybrid Diversity Strategy Based Multi-objective Particle Swarm Optimization Algorithm. Control and Decision, 2012, 27(6): 813-818 (in Chinese) (贾树晋,杜 斌,岳 恒.基于局部搜索与混合多样性策略的多目标粒子群算法.控制与决策, 2012, 27(6): 813-818) [22] Liang X, Liu P F, Huang M. Application of New Dynamic Ant Algorithm-Genetic Algorithm. Computer Integrated Manufacturing Systems, 2008, 14(8): 1566-1570 (in Chinese) (梁 旭,刘鹏飞,黄 明.一种新的动态蚂蚁遗传混合算法应用研究.计算机集成制造系统, 2008, 14(8): 1566-1570) [23] Wang J Q, Lu P, Zhang H Y, et al. Method of Multi-criteria Group Decision-Making Based on Cloud Aggregation Operators with Linguistic Information. Information Sciences, 2014, 274: 177-191 [24] Wang G Y, Xu C L, Li D Y. Generic Normal Cloud Model. Information Sciences, 2014, 280: 1-15 [25] Vo B, Hong T P, Le B. A Lattice-Based Approach for Mining Most Generalization Association Rules. Knowledge-Based Systems, 2013, 45: 20-30 [26] Cordeau J F, Maischberger M. A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems. Computers & Operations Research, 2012, 39(9): 2033-2050 [27] Balseiro S R, Loiseau I, Ramonet J. An Ant Colony Algorithm Hybridized with Insertion Heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, 2011, 38(6): 954-966 [28] Yu B, Yang Z Z, Yao B Z. A Hybrid Algorithm for Vehicle Routing Problem with Time Windows. Expert Systems with Applications, 2011, 38(1): 435-441 [29] Ioannou G, Kritikos M, Prastacos G. A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, 2001, 52(5): 523-537
2015, Vol. 28 
