带时间窗车辆路径问题的量子蚁群算法

作者：何小锋; 马良

来源：系统工程理论与实践, 2013, (05): 1255-1261.

• 带时间窗的车辆路径问题
• 蚁群算法
• 量子计算
• 量子蚁群算法 vehicle routing problem with time windows
• ant colony algorithm
• quantum computing
• quantum-inspired ant colony algorithm

带时间窗的车辆路径问题(VRPTW)是VRP的一种重要扩展类型,是组合优化中的一个NP难题,针对蚁群算法在求解VRPTW问题时易陷入局部最优和收敛速度慢的问题,本文结合量子计算提出一种求解VRPTW的量子蚁群算法(QACA).通过定义人工蚂蚁的转移概率,增加量子比特启发式因子,以及用量子旋转门实现信息素更新,从而提高算法的全局搜索能力,有效避免了算法陷入局部最优.经一系列VRPTW的仿真实验表明,量子蚁群算法较蚁群算法在求解VRPTW问题上具有更好的性能,通过与其他算法的比较,进一步说明量子蚁群算法是可行有效的.

• 出版日期2013
• 单位上海理工大学