PDF(665 KB)
PDF(665 KB)
PDF(665 KB)
带时间窗车辆路径问题的量子蚁群算法
Quantum-inspired ant colony algorithm for vehicle routing problem with time windows
带时间窗的车辆路径问题(VRPTW)是VRP的一种重要扩展类型, 是组合优化中的一个NP难题, 针对蚁群算法在求解VRPTW问题时易陷入局部最优和收敛速度慢的问题, 本文结合量子计算提出一种求解VRPTW的量子蚁群算法(QACA). 通过定义人工蚂蚁的转移概率, 增加量子比特启发式因子, 以及用量子旋转门实现信息素更新, 从而提高算法的全局搜索能力, 有效避免了算法陷入局部最优. 经一系列VRPTW的仿真实验表明, 量子蚁群算法较蚁群算法在求解VRPTW问题上具有更好的性能, 通过与其他算法的比较, 进一步说明量子蚁群算法是可行有效的.
Vehicle routing problem with time windows (VRPTW) is an important extended type of vehicle routing problem (VRP), and it's a NP-hard problem in combinatorial optimization. A quantum-inspired ant colony algorithm (QACA) for solving vehicle routing problem with time windows is proposed hereof based upon the combination of ant colony optimization and quantum computing. With the transition probability of artificial ants, the heuristic factor with quantum bits, quantum logic gates combined, the capacity as well as the velocity of the algorithm for global search undergoes significant improvability. And the disadvantage of getting into the local optimum can be effectively avoided by the QACA. The computational comparison of series of numerical examples shows that the QACA has a better performance than the ant colony algorithm (ACA) and other algorithms for solving the VRPTW.
带时间窗的车辆路径问题 / 蚁群算法 / 量子计算 / 量子蚁群算法 {{custom_keyword}} /
vehicle routing problem with time windows / ant colony algorithm / quantum computing / quantum-inspired ant colony algorithm {{custom_keyword}} /
[1] Dantizig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] Gambardella L M, Taillard R, Agazzi G. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows[J]. New Ideas in Optimization, 1999: 63-76.
[3] Kolen A, Rnnooy Kan A, Trienekens H. Vehicle routing with time windows[J]. Operations Research, 1987, 35(2): 266-273.
[4] 李大卫, 王莉, 王梦光. 遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践, 1999, 19(8): 65-69. Li D W, Wang L, Wang M G. Genetic a1gorithm for vehicle routing problem with time windows[J]. Systems Engineering — Theory & Practice, 1999, 19(8): 65-69.
[5] 张丽萍, 柴跃廷, 曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统, 2002, 8(6): 451-454. Zhang L P, Chai Y T, Cao R. Improved genetic a1gorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2002, 8(6): 451-454.
[6] 刘云忠, 宣慧玉.动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国工程科学, 2005, 7(12): 35-40. Liu Y Z, Xuan H Y. Application research on vehicle routing problem with time windows based on dynamic ant algorithm[J]. Engineering Science, 2005, 7(12): 35-40.
[7] 崔雪丽, 朱道立.带时间窗车辆路径问题的混合改进型蚂蚁算法[J].计算机工程与应用, 2009, 45(4): 16-19. Cui X L, Zhu D L. Hybrid improved ant algorithm for vehicle routing problem with time windows[J]. Computer Engineering and Applications, 2009, 45(4): 16-19.
[8] 李宁, 邹彤, 孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践, 2004, 4(4): 130-135. Li N, Zou T, Sun D B. Particle swarm optimization for vehicle routing problem with time windows[J]. Systems Engineering — Theory & Practice, 2004, 4(4): 130-135.
[9] 吴耀华, 张念志.带时间窗车辆路径问题的改进粒子群算法研究[J].计算机工程与应用, 2010, 46(15): 230-234. Wu Y H, Zhang N Z. Modified particle swarm optimization algorithm for vehicle routing problem with time windows[J]. Computer Engineering and Applications, 2010, 46(15): 230-234.
[10] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions On Systems, Man, and Cybernetics, 1996, 26(1): 29-41.
[11] 马良, 朱刚, 宁爱兵. 蚁群优化算法[M]. 北京:科学出版社, 2008. Ma L, Zhu G, Ning A B. Ant colony optimization[M]. Beijing: Science Press, 2008.
[12] Deutsch D. Quantum computational networks[C]// Proc Roy Soc London, 1988, A. 425: 73-90.
[13] Shor P W. Algorithms for quantum computation[C]// Discrete Logarithms and Factoring, Proc of the 35th Annual Symp on Foundations of Computer Science, New York, USA: IEEE Computer Society Press, 1994, 11: 124-134.
[14] Grover L K. A fast quantum mechanics algorithm for database search[C]// Proc of the 28th Annual ACM Symp on Theory of Computing, New York, USA: ACM Press, 1996, 6: 212-219.
[15] 杨佳, 许强, 张金荣, 等. 一种新的量子蚁群优化算法[J]. 中山大学学报:自然科学版, 2009, 48(3): 22-27. Yang J, Xu Q, Zhang J R, et al. A novel quantum ant colony optimizing algorithm[J]. Acta Scientiarum Naturalium Universitaties Sunyatseni, 2009, 48(3): 22-27.
[16] Han K H, Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.
[17] Li B B, Wang L. A hybrid quantum-inspired genetic algorithm for multi-objective flow shop scheduling[J]. IEEE Transactions on Systems, Man and Cybernetics, 2007, 37(3): 576-591.
[18] 刘利强, 戴运桃, 王丽华. 蚁群算法参数优化[J]. 计算机工程, 2008, 34(11): 208-210. Liu L Q, Dai Y T, Wang L H. Ant colony algorithm parameters optimization[J]. Computer Engineering, 2008, 34(11): 208-210.
[19] 李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京: 中国物资出版社, 2001. Li J, Guo Y H. Optimization of logistics delivery vehicle scheduling theory and methods[M]. Beijing: China Logistics Publishing House, 2001.
国家自然科学基金(70871081); 上海市重点学科建设资助项目(S30504)
/
| 〈 |
|
〉 |
