Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach

Quantum Physics [Submitted on 13 Mar 2026] Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An \varepsilon-Constraint-based Approach Nguyen Hoang Viet, Nguyen Xuan Tung, Trinh Van Chien, Won-Joo Hwang This paper addresses the Bi-Objective Traveling Thief Problem (BI-TTP), a challenging multi-objective 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 bi-objective 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 (QUBO) model, enabling direct solution via a quantum annealing (QA) solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance 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. Comments: 14 pages, 5 figures, and 3 tables. Accepted by IEEE Transactions on Quantum Engineering Subjects: Quantum Physics (quant-ph); Information Theory (cs.IT) Cite as: arXiv:2603.18038 [quant-ph]   (or arXiv:2603.18038v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.18038 Focus to learn more Submission history From: Trinh Van Chien [view email] [v1] Fri, 13 Mar 2026 05:26:25 UTC (783 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.IT math math.IT References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)