Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning
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-craft...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10854423/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832575599078539264 |
|---|---|
| author | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa |
| author_facet | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa |
| author_sort | Tatsuya Noguchi |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-8d68e356483342679ee7a648238e65f2 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-8d68e356483342679ee7a648238e65f22025-01-31T23:05:20ZengIEEEIEEE Access2169-35362025-01-0113197161972710.1109/ACCESS.2025.353452910854423Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip PlanningTatsuya Noguchi0https://orcid.org/0009-0007-2301-6901Keisuke Fukada1https://orcid.org/0000-0002-6087-1399Siya Bao2https://orcid.org/0000-0003-1993-9133Nozomu Togawa3https://orcid.org/0000-0003-3400-3587Department of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanThe 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.https://ieeexplore.ieee.org/document/10854423/Trip planning problemintermodalquantum annealerIsing modelsubQUBOcorrection process |
| spellingShingle | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning IEEE Access Trip planning problem intermodal quantum annealer Ising model subQUBO correction process |
| title | Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning |
| title_full | Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning |
| title_fullStr | Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning |
| title_full_unstemmed | Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning |
| title_short | Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning |
| title_sort | hybrid subqubo annealing with a correction process for multi day intermodal trip planning |
| topic | Trip planning problem intermodal quantum annealer Ising model subQUBO correction process |
| url | https://ieeexplore.ieee.org/document/10854423/ |
| work_keys_str_mv | AT tatsuyanoguchi hybridsubquboannealingwithacorrectionprocessformultidayintermodaltripplanning AT keisukefukada hybridsubquboannealingwithacorrectionprocessformultidayintermodaltripplanning AT siyabao hybridsubquboannealingwithacorrectionprocessformultidayintermodaltripplanning AT nozomutogawa hybridsubquboannealingwithacorrectionprocessformultidayintermodaltripplanning |