Citation

Santo, Istiyak Amin and Lim, Siow Chun and Nabi, Md Serajun and Hossen, Md Sabbir and Bannah, Hasanul and Kabir, Fardin (2025) Travelling Salesman Problem in the Classical to Quantum Era: A Comparative Review of Algorithms and Computational Complexity. In: https://ieeexplore.ieee.org/xpl/conhome/11275886/proceeding, 12-14 November 2025, Phuket, Thailand.

Text 486.pdf - Published Version Restricted to Repository staff only Download (1MB)

Abstract

The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.

Item Type:	Conference or Workshop Item (Paper)
Uncontrolled Keywords:	Travelling Salesman Problem, Quantum Optimization, QAOA, VQE, Quantum Annealing, Complexity Analysis, Heuristics
Subjects:	Q Science > QA Mathematics > QA801-939 Analytic mechanics
Divisions:	Faculty of Artificial Intelligence & Engineering (FAIE)
Depositing User:	Ms Suzilawati Abu Samah
Date Deposited:	17 Mar 2026 03:27
Last Modified:	19 Mar 2026 01:38
URII:	http://shdl.mmu.edu.my/id/eprint/15474

Downloads

Edit (login required)