用于双目标旅行商问题的高级量子退火算法：一种基于ε约束的方法

《IEEE Transactions on Quantum Engineering》：Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An ε -Constraint-Based Approach

　　

摘要：

本文研究了双目标旅行商问题（BI-TTP），这是一种具有挑战性的多目标优化问题，需要同时优化旅行成本和物品利润。由于路径规划与物品装载决策之间的复杂相互关系，以及问题本身的复杂性和大规模特性，传统方法在处理BI-TTP时往往存在严重的可扩展性问题。这些难题使得传统计算方法越来越难以适用。为了解决这一问题，我们提出了一种先进的混合方法，将量子退火技术与该ε-约束方法相结合。具体而言，我们通过设定可在既定上下限内调整的ε-水平，将双目标问题转化为单目标问题。由此产生的子问题包含多个分数项，我们通过引入辅助变量将其转化为等价形式。随后，该等价形式被进一步转化为二次无约束二进制优化模型，从而可以通过量子退火求解器直接得到解。从量子退火器获得的解还会通过定制的启发式算法进行优化，以进一步提升整体性能。通过灵活调整ε参数，我们的方法能够有效覆盖更广泛的帕累托前沿，提升解决方案的多样性。在基准测试实例上的实验结果表明，所提出的方法能够在平衡两个目标方面表现出色，并且在时间效率上优于传统方法。