Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows
作者: James B. Holliday, Darren Blount, Eneko Osaba, Khoa Luu
发布时间: 2025-04-02
来源: arxiv
研究方向: 量子优化与物流优化
主要内容
本文研究了量子退火在解决带时间窗的车辆路径问题中的应用，重点关注旅行商问题（TSP）和时间窗车辆路径问题（VRPTW）。研究者使用D-Wave的量子退火器和约束二次模型（CQM）求解器，在混合框架中解决这些问题。
主要贡献
1. 将混合量子禁忌搜索（HQTS）方法扩展到带时间窗的车辆路径问题（CVRPTW），以解决更复杂的问题。
2. 将问题从二次无约束二进制优化（QUBO）公式转换为D-Wave的CQM求解器，以处理时间窗约束。
3. 引入了一种新的后处理启发式方法，通过一系列交换操作修复不可行解，确保了实际应用的可行性。
4. 使用Solomon基准数据集进行了实验，证明了方法的有效性，平均最优性差距为3.86%。
研究方法
1. 混合量子禁忌搜索（HQTS）方法
2. 约束二次模型（CQM）求解器
3. 后处理启发式方法（交换操作）
4. Solomon基准数据集
实验结果
实验结果表明，CQM求解器在优化路径成本方面表现良好，但在问题规模增加时难以保持时间窗可行性。通过后处理启发式方法，HQTS在所选紧密时间窗实例上实现了平均最优性差距为3.85%，证明了其有效性。
未来工作
未来工作将扩展评估到更广泛、更多样化的CVRPTW数据集，并改进混合量子计算策略，以解决现实世界的优化挑战。