Multi-Day Intermodal Trip Planning Using subQUBO Annealing with Correction Processing

The multi-day intermodal trip planning problem (MITPP) is an optimization problem that finds the optimal route to visit points of interest (POIs) and hotels over days with multiple transportation such as walking and trains. Meanwhile, quantum annealers effectively solve the optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO). However, the possible input QUBO size of the current quantum annealer is quite limited. In this paper, we propose a subQUBO annealing method for solving large-scale MITPPs. Also, we apply a correction processing to avoid constraint violation. Evaluation experiments show that the proposed method succeeds in obtaining high-quality solutions for large-scale MITPPs.