The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.

翻译：旅行商问题（TSP）是组合优化领域的一个基本挑战，广泛应用于物流与运输领域。随着TSP实例规模的增大，传统算法往往难以在合理时间内产生高质量解。本研究探讨了量子近似优化算法（QAOA）——一种混合量子-经典方法——在现实约束条件下解决TSP的潜力。我们采用基于QUBO的TSP建模方法，整合了反映实际运营条件的物流约束，如车辆容量、道路可达性和时间窗口，同时确保与当前量子硬件的限制兼容。实验在高性能计算（HPC）资源的模拟环境中进行，以评估QAOA在不同问题规模和量子电路深度下的性能。为提高可扩展性，我们提出了聚类QAOA（Cl-QAOA），这是一种将经典机器学习与QAOA相结合的混合方法。该方法将大型TSP实例分解为较小的子问题，使得即使在量子比特数有限的设备上也能实现量子优化。研究结果全面评估了QAOA在解决约束TSP场景中的优势与局限。本研究推动了量子优化的发展，并为未来大规模应用奠定了基础。