Advanced Quantum Annealing for the Biobjective Traveling Thief Problem: An $\varepsilon$-Constraint-Based Approach
Nguyen Hoang Viet, Nguyen Xuan Tung, Trinh Van Chien, Won-Joo Hwang · IEEE Transactions on Quantum Engineering · 2026
This article addresses the biobjective traveling thief problem (BI-TTP), a challenging multiobjective optimization problem that requires the simultaneous optimization of travel cost and item profit. Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions, as well as the inherent complexity and large problem size. These difficulties render classical computing approaches increasingly inapplicable. To tackle this, we propose an advanced hybrid approach that combines quantum annealing (QA) with the $\varepsilon$ -constraint method. Specifically, we reformulate the biobjective problem into a single-objective formulation by restricting the second objective through adjustable $\varepsilon$ -levels, determined within established upper and lower bounds. The resulting subproblem involves a sum of fractional terms, which is reformulated with auxiliary variables into an equivalent form. Subsequently, the equivalent formulation is transformed into a quadratic unconstrained binary optimization model, enabling direct solution via a QA solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance the overall performance. By leveraging the flexibility in selecting $\varepsilon$ parameters, our approach effectively captures a broad Pareto front, enhancing solution diversity. Experimental results on benchmark instances demonstrate that the proposed method effectively balances two objectives and outperforms baseline approaches in time efficiency.