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

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

Quantum-inspired ant colony algorithm for vehicle routing problem with time windows

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.