Quadratic Unconstrained Binary Formulation for Traffic Signal Optimization on Real-World Maps

• URL: http://arxiv.org/abs/2308.14462v2
• Date: Tue, 10 Dec 2024 01:59:06 GMT
• Title: Quadratic Unconstrained Binary Formulation for Traffic Signal Optimization on Real-World Maps
• Authors: Reo Shikanai, Masayuki Ohzeki, Kazuyuki Tanaka,
• Abstract summary: The D-Wave quantum annealing machine can quickly find the optimal solution for quadratic unconstrained binary optimization (QUBO)<n>We propose a different formulation of QUBO that can also deal with T-junctions and multi-forked roads.<n>Our results show that the D-Wave machine could not find the optimal solution and was slower than the Gurobi in time.
• Score: 0.4915744683251151
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The D-Wave quantum annealing machine can quickly find the optimal solution for quadratic unconstrained binary optimization (QUBO). One of the applications where the use of quantum annealing is desired is in problems requiring rapid calculations. One such application is the traffic signal optimization. Several studies have used quantum annealing; however, they are formulated in relatively unrealistic settings, such as only crossroads on a map. We propose a different formulation of QUBO that can also deal with T-junctions and multi-forked roads. The simulation of urban mobility (SUMO) was used to validate the efficiency of our approach and verify the feasibility of real-time control using geographical information data that were very similar to the real world. Our model could reduce the waiting time at red lights for vehicles. In addition, we compared our results with those of the Gurobi Optimizer to confirm whether the D-Wave machine could find the ground state. Unfortunately, our results show that the D-Wave machine could not find the optimal solution and was slower than the Gurobi Optimizer in computation time.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory [2.2131426229426405]
  We implement a quantum adiabatic algorithm and achieve algorithmic speedup by introducing gauge symmetry into the algorithm. Gauge symmetry enforces the state to be in the instantaneous ground state, further speeding up the computation.
  arXiv  Detail & Related papers  (2024-06-10T01:37:18Z)
• Traffic signal optimization in large-scale urban road networks: an adaptive-predictive controller using Ising models [4.408586742026574]
  We propose a control method called AMPIC that guarantees both scalability and optimality. The proposed method employs model predictive control to solve an optimal control problem at each control interval with explicit consideration of a predictive model of vehicle flow. Results show that AMPIC enables faster vehicle cruising speed with less waiting time than that achieved by classical control methods.
  arXiv  Detail & Related papers  (2024-06-06T02:20:34Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  We propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution.
  arXiv  Detail & Related papers  (2024-05-05T21:20:46Z)
• Simulating photonic devices with noisy optical elements [0.615738282053772]
  In the near-term, the performance of any quantum algorithm should be tested and simulated in the presence of noise. We apply the recently proposed noisy gates approach to efficiently simulate noisy optical circuits. We also evaluate the performance of a photonic variational quantum algorithm to solve the MAX-2-CUT problem.
  arXiv  Detail & Related papers  (2023-11-17T16:06:20Z)
• Energy-Efficient On-Board Radio Resource Management for Satellite Communications via Neuromorphic Computing [59.40731173370976]
  We investigate the application of energy-efficient brain-inspired machine learning models for on-board radio resource management. For relevant workloads, spiking neural networks (SNNs) implemented on Loihi 2 yield higher accuracy, while reducing power consumption by more than 100$times$ as compared to the CNN-based reference platform.
  arXiv  Detail & Related papers  (2023-08-22T03:13:57Z)
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers [49.1574468325115]
  We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series. Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
  arXiv  Detail & Related papers  (2023-05-30T18:00:05Z)
• Resource frugal optimizer for quantum machine learning [0.7046417074932257]
  Quantum-enhanced data science, also known as quantum machine learning (QML), is of growing interest as an application of near-term quantum computers. Variational QML algorithms have the potential to solve practical problems on real hardware, particularly when involving quantum data. We advocate for simultaneous random sampling over both the datasets as well as the measurement operators that define the loss function.
  arXiv  Detail & Related papers  (2022-11-09T15:29:03Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  We propose a Laplacian enhanced low-rank tensor (LETC) framework featuring both lowrankness and multi-temporal correlations for large-scale traffic speed kriging. We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed model to network-wide kriging.
  arXiv  Detail & Related papers  (2022-10-21T07:25:57Z)
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks [31.228956832890393]
  We show that classical algorithms can't efficiently hit one well knowing the other well but Q can when given proper initial states the well. We construct a specific double-well landscape, where classical algorithms cannot efficiently hit one well knowing the other well but Q can when given proper initial states the well.
  arXiv  Detail & Related papers  (2022-09-29T01:39:20Z)
• Multipoint-BAX: A New Approach for Efficiently Tuning Particle Accelerator Emittance via Virtual Objectives [47.52324722637079]
  We propose a new information-theoretic algorithm, Multipoint-BAX, for black-box optimization on multipoint queries. We use Multipoint-BAX to minimize emittance at the Linac Coherent Light Source (LCLS) and the Facility for Advanced Accelerator Experimental Tests II (FACET-II)
  arXiv  Detail & Related papers  (2022-09-10T04:01:23Z)
• Travel time optimization on multi-AGV routing by reverse annealing [0.966840768820136]
  We propose a formulation to control the traveling routes to minimize the travel time. We validate our formulation through simulation in a virtual plant and authenticate the effectiveness for faster distribution. This study extends a use of optimization with general problem solvers in the application of multi-AGV systems.
  arXiv  Detail & Related papers  (2022-04-25T17:01:56Z)
• Quantum Annealing for Vehicle Routing Problem with weighted Segment [0.0]
  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. The simulations on the D-Wave quantum annealer show optimal results on the route deployment of several vehicles.
  arXiv  Detail & Related papers  (2022-03-25T06:38:18Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Bayesian Optimization and Deep Learning forsteering wheel angle prediction [58.720142291102135]
  This work aims to obtain an accurate model for the prediction of the steering angle in an automated driving system. BO was able to identify, within a limited number of trials, a model -- namely BOST-LSTM -- which resulted, the most accurate when compared to classical end-to-end driving models.
  arXiv  Detail & Related papers  (2021-10-22T15:25:14Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• Benchmark test of Black-box optimization using D-Wave quantum annealer [0.8602553195689513]
  An efficient method by use of inference by sparse prior for a black-box objective function with binary variables has been proposed. We employ the D-Wave 2000Q quantum annealer, which can solve QUBO by driving the binary variables by quantum fluctuations. We investigate effects from the output of the D-Wave quantum annealer in performing black-box optimization.
  arXiv  Detail & Related papers  (2021-03-23T05:27:09Z)
• Sampling electronic structure QUBOs with Ocean and Mukai solvers [44.62475518267084]
  The most advanced D-Wave Advantage quantum annealer has 5000+ qubits, however, every qubit is connected to a small number of neighbors. To compensate for the reduced number of qubits, one has to rely on special software such as qbsolv. We find that the Mukai QUBO solver outperforms the Ocean qbsolv for all calculations done in the present work.
  arXiv  Detail & Related papers  (2021-02-01T23:16:42Z)
• Fast and differentiable simulation of driven quantum systems [58.720142291102135]
  We introduce a semi-analytic method based on the Dyson expansion that allows us to time-evolve driven quantum systems much faster than standard numerical methods. We show results of the optimization of a two-qubit gate using transmon qubits in the circuit QED architecture.
  arXiv  Detail & Related papers  (2020-12-16T21:43:38Z)
• Enhance the performance of navigation: A two-stage machine learning approach [13.674463804942837]
  Real time traffic navigation is an important capability in smart transportation technologies. In this paper, we adopt the ideas of ensemble learning and develop a two-stage machine learning model to give accurate navigation results.
  arXiv  Detail & Related papers  (2020-04-02T08:55:27Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.