Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning

作     者：Noguchi, Tatsuya Fukada, Keisuke Bao, Siya Togawa, Nozomu 

作者机构：Waseda Univ Dept Comp Sci & Commun Engn Shinjuku Tokyo 1698555 Japan 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2025年第13卷

页      面：19716-19727页

核心收录：

基　　金：Council for Science, Technology and Innovation (CSTI) Cross-Ministerial Strategic Innovation Promotion Program (SIP) The "Promoting Application of Advanced Quantum Technologies to Social Challenges" through QST (National Institute for Quantum Science and Technology) 

主　　题：Annealing Quantum annealing Optimization Costs Planning Solid modeling Computational modeling Public transportation Magnetic fields Linear programming Trip planning problem intermodal quantum annealer Ising model subQUBO correction process 

摘      要：The multi-day intermodal trip planning problem (MITPP) is an optimization problem that seeks to create the optimal route to visit Point-of-Interest (POI) and hotels over days. This problem involves coordinating intermodal transportation, such as walking, public transportation, to create a well-crafted travel itinerary. Quantum annealers have recently been explored as a powerful tool for solving combinatorial optimization problems by converting the problems into Quadratic Unconstrained Binary Optimization (QUBO). However, current quantum annealers have a small QUBO input size so that they cannot directly solve large-scale MITPPs. In this paper, we address this issue by extracting a subQUBO from the original large QUBO based on variable (spin) deviations and randomness. Then, we iteratively solve the subQUBOs by the quantum annealer and update the (quasi-)optimal solution. As the obtained (quasi-)optimal solution may violate constraints, we apply the correction processing till all constraints are satisfied. According to the experiment results using a real quantum annealer, our proposed method obtained high-quality solutions for large-scale MITPPs in the Tokyo area, and compared to the full QUBO method, we achieve a maximum spin reduction of 98.9%. Especially, compared to the method by a conventional computer and two conventional subQUBO methods, POI satisfaction is improved by 10.2%, and travel costs are improved by 23.2% respectively.