Related Experiment Video
Updated: May 16, 2026
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
Large-scale evacuation route optimization leveraging sampling diversity in quantum annealing
Reo Shikanai1,2, Renichiro Haba3, Yusuke Okazaki4
1Sigma-i Co., Ltd., Tokyo, Japan. r-shikanai@sigmailab.com.
Scientific Reports
|May 14, 2026
Summary
Optimizing evacuation routes using binary quadratic programming (BQP) and quantum annealing can significantly reduce disaster evacuation times. This approach balances travel distance and route overlap to improve efficiency, even with imperfect adherence to optimized paths.
Area of Science:
- Operations Research and Optimization
- Disaster Management and Emergency Response
- Computational Science and Quantum Computing
Background:
- Natural disasters necessitate swift evacuations, but self-interested routing by evacuees causes traffic congestion and delays.
- Existing evacuation strategies often lead to suboptimal outcomes due to localized decision-making.
- Efficient disaster response requires advanced methods to overcome human behavioral tendencies that impede evacuation.
Purpose of the Study:
- To formulate an evacuation route optimization problem as a binary quadratic programming (BQP) problem to enhance evacuation efficiency.
- To investigate the use of quantum annealing for rapid computation of optimal evacuation routes.
- To develop a decomposition method for large-scale problems suitable for current quantum annealing hardware.
Main Methods:
- Formulation of the evacuation problem as a binary quadratic programming (BQP) model.
- Application of quantum annealing (D-Wave Systems Inc.) for solving the BQP formulation.
- Development and implementation of a decomposition method to handle large-scale instances on quantum annealers.
- Validation using traffic simulations with varying adherence rates to optimized routes.
Main Results:
- The proposed BQP formulation significantly reduced evacuation completion time by up to 33.6% compared to a locally optimal shortest-path approach.
- The decomposition method, while not guaranteeing a global optimum, drastically reduced computation time while achieving substantial improvements.
- Even with a small percentage (1%) of vehicles deviating from optimized routes, efficiency decreased sharply, yet the proposed method still outperformed the baseline.
Conclusions:
- Quantum-annealing-based optimization offers a practical approach to improving disaster evacuation efficiency in time-critical situations.
- The method provides valuable insights for evacuation planning, prioritizing rapid action under uncertainty over strict optimality.
- Addressing route overlap and travel distance simultaneously is key to mitigating congestion and accelerating mass evacuations.
Related Concept Videos
01:09Random Sampling Method
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
01:20Cluster Sampling Method
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
01:23Sampling Plans
Sampling is a crucial step in analytical chemistry, allowing researchers to collect representative data from a large population. Common sampling methods include random, judgmental, systematic, stratified, and cluster sampling.
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
Random sampling is a method where each member of the population has an equal chance of being selected for the sample. It involves selecting individuals randomly, often using random number generators or lottery-type methods. For example, when analyzing the properties of a...
01:17Ampere-Maxwell's Law: Problem-Solving
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the problem,...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the problem,...
01:06Sampling Methods: Overview
A sample refers to a smaller subset representative of a larger population. In analytical chemistry, studying or analyzing an entire population is often impractical or impossible. Therefore, samples are used to draw inferences and generalize the whole population. The sampling method selects individuals or items from a population to create a sample. Standard sampling methods include random, judgemental, systematic, stratified, and cluster sampling.
In analytical chemistry, the choice of sampling...
In analytical chemistry, the choice of sampling...
01:28Methods of Medium Optimization
Optimizing growth media enhances microbial proliferation and maximizes product yield. Statistical experimental design methodologies provide structured and reproducible approaches, offering progressively higher levels of robustness and efficiency.The One-Factor-at-a-Time (OFAT) MethodThe One-Factor-at-a-Time (OFAT) method involves adjusting a single variable while keeping all others constant. However, it cannot detect interactions between variables, often leading to suboptimal outcomes when...