全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

求解带时间窗车辆路径问题的动态混合蚁群优化算法*

DOI: 10.16451/j.cnki.issn1003-6059.201507008, PP. 641-650

Keywords: 动态最大最小蚂蚁系统,融合策略,带时间窗车辆路径问题,蚁群优化算法,遗传算法

Full-Text   Cite this paper   Add to My Lib

Abstract:

为求解带时间窗车辆路径问题,针对传统蚂蚁遗传混合算法中参数静态设置、冗余迭代及收敛速度慢等缺点,提出一种动态混合蚁群优化算法(DHACO).该算法首先借助最大最小蚁群得到初始解,利用蚁群优化算法求解带时间窗车辆路径问题的基本可行解.然后采用遗传算法交叉和变异操作对局部解和全局最优解进行二次优化,从而得到最优解.最后利用蚂蚁遗传混合算法融合策略,动态交叉调用蚂蚁算法、遗传算法,根据云关联规则自适应控制蚁群算法参数.DHACO有效减少无效迭代次数,加快收敛速度.仿真结果表明,与其他相关的启发式算法相比,DHACO优于某些实例的已知最优解.

References

[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]  Brysy 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]  Brysy 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]  Baos 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]  Vo B, Hong T P, Le B. A Lattice-Based Approach for Mining Most Generalization Association Rules. Knowledge-Based Systems, 2013, 45: 20-30
[24]  Cordeau J F, Maischberger M. A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems. Computers & Operations Research, 2012, 39(9): 2033-2050
[25]  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
[26]  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
[27]  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
[28]  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
[29]  Wang G Y, Xu C L, Li D Y. Generic Normal Cloud Model. Information Sciences, 2014, 280: 1-15

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133