Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

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

Tatsuya Noguchi, Keisuke Fukada, Siya Bao, Nozomu Togawa

Published Jan 1, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/access.2025.3534529

Related papers

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

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Trip Planning Based on subQUBO Annealing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.

IEEE Access•Jan 1, 2023•9 citations

Multi-Day Intermodal Travel Planning for Urban Cities Using Ising Machines

Siya Bao, Nozomu Togawa

The multi-day intermodal travel planning problem (MITPP) is an optimization problem (OP) and it generates the optimal sequences of point-of-interests (POIs) and hotels while searching for the most suitable transport modes between POIs and hotels. Conventional methods and solvers using von Neumann computers provide good approximate solutions to the OPs, but the computation time grows exponentially dealing with large-scale or complex OPs. Meanwhile, Ising machines or quantum annealing machines are non-von Neumann computers that are designed to solve complex OPs. In this paper, we focus on solving the MITPP by a two-phase Ising-based method. The first POI clustering phase aims at generating POIs clusters for sightseeing days and the second POI routing phase generates travel routes for each day with the optimal transport modes. Practical factors such as POI satisfaction, POI duration, hotel fee, and transportation fee are included in the MITPP. We map these elements onto quadratic unconstrained binary optimization (QUBO) models. For evaluation, we use a real-world dataset in Sapporo, Japan. Empirical results confirm that the proposed method can effectively solve the MITPP both in terms of solution quality and execution time and outperforms a conventional solver, a conventional method, and the latest Ising-based method.

IEEE International Conference on Intelligent Transportation Systems (ITSC)•Sep 24, 2023•3 citations

Multi-day Travel Planning Using Ising Machines for Real-world Applications

Siya Bao, Masashi Tawada, Shu Tanaka +1 more

The multi-day travel planning assists users with realistic travel itineraries by searching for the optimal travel routes through a set of candidate hotels and point-of-interests (POIs). The multi-day travel planning problem (MTPP) can be solved as an optimization problem. Although conventional methods using von Neumann computers obtain good approximate solutions to the optimization problems, large computation costs are required to solve large-scale or complex problems due to the combinatorial explosion. On the other hand, Ising machines or quantum annealing machines are non-von Neumann computers, and those machines are developed to deal with complex optimization problems. In this paper, we propose an Ising-machine-based method for the MTPP. Practical factors of the MTPP include the POI satisfaction, travel expenses, and time limits. Those factors are mapped onto quadratic unconstrained binary optimization (QUBO) forms. We evaluate the proposed method using two real-world datasets including Sapporo and Tokyo, Japan. Experimental results show that the MTPP can be effectively solved using Ising machines compared with the conventional methods in terms of the solution quality and the execution time. To the best of our knowledge, this study is the first solution of the MTPP using Ising machines.

IEEE International Conference on Intelligent Transportation Systems (ITSC)•Sep 19, 2021•14 citations

Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach

Nguyen Hoang Viet, Nguyen Xuan Tung, Trinh Van Chien +1 more

This paper addresses the Bi-Objective Traveling Thief Problem (BI-TTP), a challenging multi-objective optimization problem that requires the simultaneous optimization of travel cost and item profit. Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions, as well as the inherent complexity and large problem size. These difficulties render classical computing approaches increasingly inapplicable. To tackle this, we propose an advanced hybrid approach that combines quantum annealing (QA) with the $\varepsilon$-constraint method. Specifically, we reformulate the bi-objective problem into a single-objective formulation by restricting the second objective through adjustable $\varepsilon$-levels, determined within established upper and lower bounds. The resulting subproblem involves a sum of fractional terms, which is reformulated with auxiliary variables into an equivalent form. Subsequently, the equivalent formulation is transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model, enabling direct solution via a quantum annealing (QA) solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance overall performance. By leveraging the flexibility in selecting $\varepsilon$ parameters, our approach effectively captures a broad Pareto front, enhancing solution diversity. Experimental results on benchmark instances demonstrate that the proposed method effectively balances two objectives and outperforms baseline approaches in time efficiency.

quant-pharXiv:2603.18038•Mar 16, 2026•0 citations

Using Quantum Annealing to Solve Large-Scale Optimization Problems in Logistics and Scheduling

Sandeep Kumar

In planning and scheduling, large-scale optimization problems often have complex limits and a lot of factors, which makes them hard to answer with standard methods. Quantum annealing has become a hopeful way to deal with these problems because it can quickly look into a lot of possible solutions. This essay looks into how quantum annealing might be used to solve optimization problems in transportation and scheduling, with a focus on how it could be used for route planning, inventory management, and arranging workers. To do these optimization jobs, quantum annealing is used. This is a quantum computing method that gets the global minimum of a cost function. We use the D-Wave quantum annealer in this method. It turns the problem's limits and objective function into a quadratic unconstrained binary optimization (QUBO) model. The quantum annealer then works on this model to find the best answers. The suggested method combines traditional preparation methods with quantum annealing to get the best results for big schedule and transportation issues. We use quantum annealing to solve difficult multi-objective optimization problems, like reducing shipping time, cost, and resource use all at the same time. Preliminary results show that quantum annealing can make solutions much better and use computers much more efficiently than traditional methods for optimizing supplies and schedules. Quantum annealing works especially well with problems that have a lot of dimensions. It can provide scalable answers that sometimes work better than standard methods.

International Conference on Emerging Smart Computing and Informatics (ESCI)•Mar 5, 2025•0 citations
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.
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.
The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.
The multi-day intermodal travel planning problem (MITPP) is an optimization problem (OP) and it generates the optimal sequences of point-of-interests (POIs) and hotels while searching for the most suitable transport modes between POIs and hotels. Conventional methods and solvers using von Neumann computers provide good approximate solutions to the OPs, but the computation time grows exponentially dealing with large-scale or complex OPs. Meanwhile, Ising machines or quantum annealing machines are non-von Neumann computers that are designed to solve complex OPs. In this paper, we focus on solving the MITPP by a two-phase Ising-based method. The first POI clustering phase aims at generating POIs clusters for sightseeing days and the second POI routing phase generates travel routes for each day with the optimal transport modes. Practical factors such as POI satisfaction, POI duration, hotel fee, and transportation fee are included in the MITPP. We map these elements onto quadratic unconstrained binary optimization (QUBO) models. For evaluation, we use a real-world dataset in Sapporo, Japan. Empirical results confirm that the proposed method can effectively solve the MITPP both in terms of solution quality and execution time and outperforms a conventional solver, a conventional method, and the latest Ising-based method.
The multi-day travel planning assists users with realistic travel itineraries by searching for the optimal travel routes through a set of candidate hotels and point-of-interests (POIs). The multi-day travel planning problem (MTPP) can be solved as an optimization problem. Although conventional methods using von Neumann computers obtain good approximate solutions to the optimization problems, large computation costs are required to solve large-scale or complex problems due to the combinatorial explosion. On the other hand, Ising machines or quantum annealing machines are non-von Neumann computers, and those machines are developed to deal with complex optimization problems. In this paper, we propose an Ising-machine-based method for the MTPP. Practical factors of the MTPP include the POI satisfaction, travel expenses, and time limits. Those factors are mapped onto quadratic unconstrained binary optimization (QUBO) forms. We evaluate the proposed method using two real-world datasets including Sapporo and Tokyo, Japan. Experimental results show that the MTPP can be effectively solved using Ising machines compared with the conventional methods in terms of the solution quality and the execution time. To the best of our knowledge, this study is the first solution of the MTPP using Ising machines.
Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An ε\varepsilonε-Constraint-based Approach
This paper addresses the Bi-Objective Traveling Thief Problem (BI-TTP), a challenging multi-objective optimization problem that requires the simultaneous optimization of travel cost and item profit. Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions, as well as the inherent complexity and large problem size. These difficulties render classical computing approaches increasingly inapplicable. To tackle this, we propose an advanced hybrid approach that combines quantum annealing (QA) with the ε\varepsilonε-constraint method. Specifically, we reformulate the bi-objective problem into a single-objective formulation by restricting the second objective through adjustable ε\varepsilonε-levels, determined within established upper and lower bounds. The resulting subproblem involves a sum of fractional terms, which is reformulated with auxiliary variables into an equivalent form. Subsequently, the equivalent formulation is transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model, enabling direct solution via a quantum annealing (QA) solver. The solutions obtained from the quantum annealer are subsequently refined using a tailored heuristic procedure to further enhance overall performance. By leveraging the flexibility in selecting ε\varepsilonε parameters, our approach effectively captures a broad Pareto front, enhancing solution diversity. Experimental results on benchmark instances demonstrate that the proposed method effectively balances two objectives and outperforms baseline approaches in time efficiency.
In planning and scheduling, large-scale optimization problems often have complex limits and a lot of factors, which makes them hard to answer with standard methods. Quantum annealing has become a hopeful way to deal with these problems because it can quickly look into a lot of possible solutions. This essay looks into how quantum annealing might be used to solve optimization problems in transportation and scheduling, with a focus on how it could be used for route planning, inventory management, and arranging workers. To do these optimization jobs, quantum annealing is used. This is a quantum computing method that gets the global minimum of a cost function. We use the D-Wave quantum annealer in this method. It turns the problem's limits and objective function into a quadratic unconstrained binary optimization (QUBO) model. The quantum annealer then works on this model to find the best answers. The suggested method combines traditional preparation methods with quantum annealing to get the best results for big schedule and transportation issues. We use quantum annealing to solve difficult multi-objective optimization problems, like reducing shipping time, cost, and resource use all at the same time. Preliminary results show that quantum annealing can make solutions much better and use computers much more efficiently than traditional methods for optimizing supplies and schedules. Quantum annealing works especially well with problems that have a lot of dimensions. It can provide scalable answers that sometimes work better than standard methods.