In this research paper, we employ D-Wave’s quantum annealer to address the NP-hard problem of optimizing new metro station locations while considering both points of interest and existing stations. By formulating the problem as Quadratic Unconstrained Binary Optimization (QUBO) and Binary Quadratic Model (BQM), our approach harnesses the power of quantum computing to yield superior solutions compared to classical methods. This research has the potential to revolutionize urban transportation planning by efficiently balancing accessibility to points of interest and minimizing congestion around existing stations, offering a compelling solution to a complex urban development challenge. Notably, we emphasize the NP-hard nature of this problem, underlining its computational complexity and the significance of our quantum computing approach.
In this research paper, we employ D-Wave’s quantum annealer to address the NP-hard problem of optimizing new metro station locations while considering both points of interest and existing stations. By formulating the problem as Quadratic Unconstrained Binary Optimization (QUBO) and Binary Quadratic Model (BQM), our approach harnesses the power of quantum computing to yield superior solutions compared to classical methods. This research has the potential to revolutionize urban transportation planning by efficiently balancing accessibility to points of interest and minimizing congestion around existing stations, offering a compelling solution to a complex urban development challenge. Notably, we emphasize the NP-hard nature of this problem, underlining its computational complexity and the significance of our quantum computing approach.
Abstract As consequences of disruptions in railway traffic affect passenger experience and satisfaction, appropriate rerouting and/or rescheduling is necessary. These problems are known to be NP-hard, given the numerous restrictions of traffic nature. With the recent advances in quantum technologies, quantum annealing has become an alternative method to solve such optimization problems. To use quantum annealing, the problem needs to be encoded in quadratic unconstrained binary optimization (QUBO) or higher-order binary optimization (HOBO) formulation that can be recast as a QUBO. This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management; the latter is a new approach up to our knowledge. This new approach takes into account not only the single-track lines but also the double- and multi-track lines, as well as stations composed of tracks and switches. We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation. Furthermore, a hybrid quantum-classical procedure is presented that includes rerouting. We demonstrate the proof of concept implementation on the D-Wave Quantum Processing Unit and D-Wave hybrid solver.
It is imperative to reduce carbon dioxide emissions and fossil fuel consumption to ensure the Earth's sustainable future and mitigate negative impacts like extreme climate changes caused by greenhouse gases. Electric vehicles (EVs) play a pivotal role in this context, where the convenience of charging stations is crucial in influencing consumer choices. This paper formulates the placement of charging stations as an optimization problem, considering factors like station density, accessibility, coverage, and regional cost variations, to minimize total construction costs. The problem is mapped onto a quadratic unconstrained binary optimization (QUBO) model. The QUBO can efficiently represent and solve complex combinatorial optimization problems, making it suitable for quantum and advanced classical algorithms. Utilizing digital quantum annealing, the optimal or near-optimal solutions are efficiently identified. The performance of the proposed approach is compared with classical algorithms, including mixed linear programming and simulated annealing, demonstrating significant advancements of digital annealing.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.
Traffic congestion remains a significant challenge in urban environments, necessitating innovative solutions for efficient traffic management. This paper explores the use of quantum annealing for traffic optimization, building on the pioneering work of Volkswagen and D-Wave. In 2017, a collaborative team demonstrated the potential of quantum annealing to optimize traffic flow by addressing a complex 418-car Quadratic Unconstrained Binary Optimization problem. Using a hybrid classical and quantum computing approach, they achieved notable improvements in traffic distribution. In this paper, we introduce a novel approach: Quantum Congestion-Focused Traffic Optimization (Q-CFTO). Our approach is designed to enhance traffic management optimization by breaking down the problem of optimizing traffic flow into smaller and more manageable subproblems rather than dealing with a single large optimization challenge. This decomposition facilitates the handling of the problem's complexity as embedding a large problem into a Quantum Processing Unit can be difficult. We successfully embedded the problem directly into the D-Wave Advantage Quantum Processing Unit with the "Pegasus" topology, significantly accelerating the solution process. The results demonstrate that our approach is both faster and more effective in real-world scenarios.
Transport network design problem (TNDP) is a well-studied problem for planning and operations of transportation systems. They are widely used to determine links for capacity enhancement, link closures to schedule maintenance, identify new road or transit links and more generally network enhancements under resource constraints. As changes in network capacities result in a redistribution of demand on the network, resulting in changes in the congestion patterns, TNDP is generally modelled as a bi-level problem, which is known to be NP-hard. Meta-heuristic methods, such as Tabu Search Method are relied upon to solve these problems, which have been demonstrated to achieve near optimality in reasonable time. The advent of quantum computing has afforded an opportunity to solve these problems faster. We formulate the TNDP problem as a bi-level problem, with the upper level formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem that is solved using quantum annealing on a D-Wave quantum computer. We compare the results with Tabu Search. We find that quantum annealing provides significant computational benefit. The proposed solution has implications for networks across different contexts including communications, traffic, industrial operations, electricity, water, broader supply chains and epidemiology.