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 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 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 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 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 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.
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.
Combinatorial optimization problems are of great significance in many fields, and this paper explores the application of quantum annealing-based QUBO (Quadratic Unconstrained Binary Optimization) model to combinatorial optimization problems, including the 0/1 knapsack problem, the traveler's problem, the maximum cut problem, and the graph coloring problem. The quantum annealing algorithm can effectively avoid falling into local optimal solutions by virtue of its unique quantum tunneling advantage, and shows significant advantages in solving complex combinatorial optimization problems, especially in dealing with large-scale data and multiple constraints, quantum annealing provides an efficient solution.