The international archives of the photogrammetry, remote sensing and spatial information sciences/International archives of the photogrammetry, remote sensing and spatial information sciences
EXPLORING QUANTUM COMPUTING POTENTIALS IN SOLVING A COMBINATORIAL OPTIMIZATION PROBLEM TO MINIMIZE EXPOSURE TO COVID-19 DURING A CITY JOURNEY
Amirhossein Nourbakhshrezaei, M. Jadidi, K. Shahriari
Abstract. COVID-19 is an airborne virus that can be spread directly or indirectly from one person to another. Spreading the virus strongly depends on the location and time and hence, a Spatio-temporal event. Moreover, traffic congestion will increase the spread of the virus not only because of the vicinity but also because of increased temperature and humidity in these spaces for a short or long time. This paper introduces a vehicle routing optimization model to reduce COVID-19 exposure risk during a city journey by solving it as a quadratic unconstrained binary optimization problem on a quantum annealing computer. Indeed, the objective of the COVID-19 prevention optimization problem is to minimize the risk of exposure for a given set of road users between origins and destinations. Microsoft Taxi data from the city of Beijing have been used to simulate road users’ movement. The problem has been run onto three different solvers. One of the solvers is executed on classical computers, and two other solvers are executed on hybrid quantum solvers. Hybrid solvers return the solution within less than 0.03 seconds on quantum processing unit time. However, the results will be returned at least 5 seconds after the execution in the classical solver. It is worth mentioning that, as there is no direct access to the quantum computers, it is hard to compare the results on the same scale as the queries will go on a queue in D-wave quantum computers. Applying the proposed model on the trajectory data shows a better distribution of the vehicles on the road network.
Abstract. COVID-19 is an airborne virus that can be spread directly or indirectly from one person to another. Spreading the virus strongly depends on the location and time and hence, a Spatio-temporal event. Moreover, traffic congestion will increase the spread of the virus not only because of the vicinity but also because of increased temperature and humidity in these spaces for a short or long time. This paper introduces a vehicle routing optimization model to reduce COVID-19 exposure risk during a city journey by solving it as a quadratic unconstrained binary optimization problem on a quantum annealing computer. Indeed, the objective of the COVID-19 prevention optimization problem is to minimize the risk of exposure for a given set of road users between origins and destinations. Microsoft Taxi data from the city of Beijing have been used to simulate road users’ movement. The problem has been run onto three different solvers. One of the solvers is executed on classical computers, and two other solvers are executed on hybrid quantum solvers. Hybrid solvers return the solution within less than 0.03 seconds on quantum processing unit time. However, the results will be returned at least 5 seconds after the execution in the classical solver. It is worth mentioning that, as there is no direct access to the quantum computers, it is hard to compare the results on the same scale as the queries will go on a queue in D-wave quantum computers. Applying the proposed model on the trajectory data shows a better distribution of the vehicles on the road network.
Quantum annealing technologies aim to solve computational optimization and sampling problems. QPU (Quantum Processing Unit) machines such as the D-Wave system use the QUBO (Quadratic Unconstrained Binary Optimization) formula to define model optimization problems for quantum annealing. This machine uses quantum effects to speed up computing time better than classical computers. We propose a vehicle routing problem that can be formulated in the QUBO model as a combinatorial problem, which gives the possible route solutions increases exponentially. The solution aims to optimize the vehicle's journey to reach a destination. The study presents a QUBO formulation to solve traffic congestion problems on certain roads. The resulting route selection by optimizing the distribution of the flow of alternative road vehicles based on the weighting of road segments. Constraints formulated as a condition for the level of road density. The road weight parameter influences the cost function for each road choice. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles. So that each vehicle will be able to go through different road options and reduce road congestion accurately. This solution provides an opportunity to develop QUBO modeling for more complex vehicle routing problems for road congestion.
Efficient transportation management is an important aspect of urban sustainability, impacting economic growth, environmental sustainability, and quality of life. This research explores the potential of Quantum Computing (QC) to address spatial optimization problems in transportation systems. By leveraging the principles of quantum mechanics, this research aims to enhance the efficiency and effectiveness of transportation networks through QC-based solutions to challenges such as reducing the spread of viruses on road networks, dynamic rebalancing of \nomenclature{BSS}{Bike Sharing Systems}Bike Sharing Systems (BSS), clustering of BSS stations, and Feature Selection (FS) for predictive models. The study begins by examining the potential of QC in solving combinatorial optimization problems, specifically focusing on minimizing exposure to COVID-19 during city journeys. A novel QC-based approach is developed for the dynamic rebalancing of BSS, which is a critical component of BSS management. The research further explores the clustering of BSS stations using \nomenclature{QML}{Quantum Machine Learning}Quantum Machine Learning (QML) techniques to enhance system management and improve user satisfaction. Additionally, this research introduces a QC-based FS method to improve the accuracy of predictive models, utilizing spatial data to optimize station placement and service availability. The proposed methodologies are validated through different experiments and real-world data, demonstrating significant improvements in computational efficiency and solution quality compared to traditional methods. Overall, this research advances the application of QC in transportation systems, providing a QC-based framework for future studies and practical implementations in urban transportation management. It highlights the transformative potential of QC in addressing pressing urban mobility challenges, paving the way for more sustainable and efficient transportation networks.
2020 year has been a turning point for the entire humanity. The COVID-19 pandemic has not only revolutionized our way of thinking, but it has changed the way we live, leading to having limitations on any aspect of our daily life, from the smallest things to the biggest. This extraordinary situation has afflicted the railway world, too, since the movements have been limited drastically and new rules have been introduced. This thesis focuses on analyzing passenger transport's current situation on high-speed trains in this particular historical period we are experiencing, the COVID-19 Era. It aims to create hypothetical scenarios of passengers' distribution inside a train wagon with current health and hygiene rules. The main goal of what has been defined as the Seating Arrangement Optimization problem is to fill the train wagon as much as possible and therefore transport the largest number of people by maximizing the number of passengers belonging to the same family sitting in nearest seats. In this work, two different optimization models for formalizing the identified problem are presented and compared: a Mixed-Integer Linear Programming (MILP) model, one of the most common formulations in literature in the optimization field, and a Quadratic Unconstrained Binary Optimization (QUBO) model, a novel type of problem that can be solved on a quantum computer. In particular, for the resolution of the first type of model, the Gurobi commercial solver is used while, for the latter one, the QBSolv and a classical-quantum hybrid solver provided by D-Wave Systems Inc., a leader company in the quantum computing field, are considered. Quantum computing is an innovative research field currently still under development, on which time and money have begun to be invested only in recent years. What makes this research field attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. Due to the current physical capabilities, quantum computers' computational resources are not sufficient to execute too large optimization problems. Still, even with small instances like the ones considered in this work, it can be seen how much they can find highly optimized solutions in a short time.
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.
Traffic congestion continues to pose a significant challenge in urban environments, necessitating innovative approaches to traffic management. This paper explores the application of Quantum Annealing (QA) for real-world traffic optimization, expanding on the pioneering work of Volkswagen and D-Wave. In 2017, a collaborative team demonstrated the potential of QA to optimize traffic flow by solving a complex Quadratic Unconstrained Binary Optimization (QUBO) problem involving 418 cars, which required 1,254 qubits. Later, this research culminated in a pilot project at the Web Summit conference in Lisbon, one of Europe's largest technology events, showcasing quantum computing-based traffic optimization. Since the QPU alone could not directly handle the full problem size, the team employed a hybrid classical-quantum approach, leading to significant improvements in traffic distribution. This paper builds on that foundation by investigating potential speedups using a purely quantum approach, particularly by utilizing the QPU for smaller QUBO problems. The proposed method (MTF) enhances traffic management by decomposing the overall optimization problem into smaller, more manageable subproblems. This decomposition enables us to harness the advantages of the QPU while tackling more complex traffic scenarios that previous approaches struggled to manage. By breaking the problem into smaller parts, we mitigate the challenges associated with embedding large-scale problems into the QPU, which often presents computational difficulties. To evaluate our approach, we conducted experiments involving 100, 200, 300, 400, and 500 cars on a complex traffic map featuring multiple start and end points. We successfully embedded the problem into the D-Wave Advantage Quantum Processing Unit, utilizing the "Pegasus" topology, which resulted in a significant acceleration of the solution process. The experiment results show improved speed and effectiveness in real-world scenarios by leveraging the QPU for better traffic optimization.
Traffic congestion is one of the major issues in urban areas, particularly when traffic loads exceed the road’s capacity, resulting in higher petrol consumption and carbon emissions as well as delays and stress for road users. In Asia, the traffic situation can be further deteriorated by road sharing of scooters. How to control the traffic flow to mitigate the congestion has been one of the central issues in transportation research. In this study, we employ a quantum annealing approach to optimize the traffic signals control at a real-life intersection with mixed traffic flows of vehicles and scooters. Considering traffic flow is a continuous and emerging phenomenon, we used quadratic unconstrained binary optimization (QUBO) formalism for traffic optimization, which has a natural equivalence to the Ising model and can be solved efficiently on the quantum annealers, quantum computers or digital annealers. In this article, we first applied the QUBO traffic optimization to artificially generated traffic for a simple intersection, and then we used real-time traffic data to simulate a real "Dongda-Keyuan" intersection with dedicated cars and scooter lanes, as well as mixed scooter and car lanes. We introduced two types of traffic light control systems for traffic optimization: C-QUBO and QUBO. Our rigorous QUBO optimizations show that C-QUBO and QUBO outperform the commonly used fixed cycle method, with QUBO outperforming C-QUBO in some instances. It has been found that QUBO optimization significantly relieves traffic congestion for the unbalanced traffic volume. Furthermore, we found that dynamic changes in traffic light signal duration greatly reduce traffic congestion.