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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2169-3536 |