Quantum Annealing Achieves Efficient Micro-Mobility Dispatch Via Historical Data Incorporation

Researchers are tackling the complex challenge of optimising dispatch for micro-mobility services, such as bike and scooter sharing, using the power of quantum annealing. Takeru Goto from Tohoku University and Honda R&D, alongside Masayuki Ohzeki from Tohoku University, the Institute of Science Tokyo, and Sigma-i Co., Ltd., present a new formulation of this dispatch problem as a Quadratic Unconstrained Binary Optimisation (QUBO) suitable for quantum solvers. This work is significant because it integrates historical usage data , including customer arrival patterns and destination choices , via a Bayesian approach, potentially leading to substantially more efficient vehicle allocation and improved service availability. By comparing quantum annealing against classical methods, the study demonstrates the potential for quantum computing to revolutionise urban transport logistics.

By comparing quantum annealing against classical methods, the study demonstrates the potential for quantum computing to revolutionise urban transport logistics.

Quantum annealing for micro-mobility dispatch optimisation

Scientists are investigating the use of Quantum Annealers (QA) for micro-mobility vehicle dispatch. QA has gained attention as a high-performance solver for Combinatorial optimisation problems, while micro-mobility services are rapidly developing as a means of efficient and sustainable urban transportation. The performance of QA is also compared with that of classical solvers to reveal its potential advantages for the proposed dispatch formulation, and the effect of reverse annealing on improving solution quality is investigated. Traditionally, dispatch and routing problems have been formulated as variants of Vehicle Routing Problems (VRPs), an NP-hard class of combinatorial optimisation problems.

Numerous extensions of the VRP exist, such as the Capacitated VRP (CVRP), the VRP with Time Windows (VRPTW), and the Distance-Constrained VRP (DCVRP). These are typically formulated as mathematical optimisation models, with a range of solution methods developed to solve them efficiently. Metaheuristic approaches like genetic algorithms and simulated annealing have also demonstrated versatility for various combinatorial problems. More recently, quantum computing paradigms, including Quantum Annealers (QA), have emerged as potential alternatives for solving large-scale NP-hard problems. Commercial quantum annealers developed by D-Wave Systems have enabled practical experimentation with QA in domains such as traffic optimisation, logistics, finance, manufacturing, materials science, marketing, and machine learning.

To overcome hardware limitations, relaxation and quantum-classical hybrid approaches have been proposed, alongside Reverse Annealing (RA), which refines solutions from high-quality initial states. Several studies have applied QA to VRP formulations and related problems, proposing comprehensive QUBO formulations incorporating constraints such as time, vehicle state, and capacity. Decomposition schemes have been introduced to reduce problem size and enhance scalability, and QA-based approaches have been extended to ride-hailing and ride-pooling settings. However, the suitability of VRP-based formulations for micro-mobility dispatch remains unclear.

Micro-mobility systems are characterised by highly dynamic, stochastic demand and frequent vehicle reassignments, making long-horizon route planning less relevant. This research proposes a novel formulation for the Micro-Mobility Dispatch Problem (MMDP), estimating the optimal distribution of idle vehicles across stations based on historical usage data through Bayesian modelling, prioritising customers with longer waiting times, and minimising total travel time. By omitting service sequence variables, the formulation reduces the number of binary variables, improving scalability for real-time optimisation. The validity of the proposed formulation is evaluated by comparing it with a distance-based greedy heuristic and a VRP-based QUBO formulation modified for MMDP, using a grid-based simulation environment.

The MMDP formulation is implemented on the D-Wave Advantage, and its performance is compared with that of the Gurobi Optimizer, with the effect of RA also investigated. The system considers a micro-mobility dispatch system composed of autonomous single-passenger vehicles operating within an urban area, with multiple designated stations for charging and standby. Customers request rides through an application, after which the dispatch system determines whether each available vehicle should be assigned to a customer or repositioned to a specific station. All vehicles are continuously assigned either to a customer or to a station.

The system has access to historical operational data, such as the spatiotemporal distribution of customer demand, destination patterns, and estimated travel times. The total number of vehicles is denoted by N, with the current position and destination of vehicle vi denoted by xvi and xdi, respectively. If xdi = xvi, the vehicle is occupied; otherwise, it is vacant. Let ns and nc denote the number of stations and customers, respectively. Two types of binary variables are introduced: σv,s ∈{0,1}Nns and σv,c ∈{0,1}Nnc.

If vehicle vi is dispatched to station sj, σvi,s j in σv,s is set to one, and σvi,ck = 1 indicates that customer ck is assigned to vehicle vi. A Hamiltonian HA0 = ∑ i 1−∑ j σvi,sj −∑ k σvi,ck .2 expresses the constraint that each vehicle can be assigned to only one target. Each customer must be assigned to exactly one vehicle, formulated as HA1 = ∑ k 1−∑ i σvi,ck .2. The total travel time cost is represented by the Hamiltonian HB0 = 1 tavg ( ∑ i,j t(xvi,xdi,xs j)σvi,sj +∑ i,k t(xvi,xdi,xck)σvi,ck ), where tavg = ∑i,j t(xvi,xdi,xs j)+∑i,kt(xvi,xdi,xck) N(ns +nc). Here, t(x0,x1,x2) denotes the travel time from x0 to x2 via x1.

To encourage more vehicles to be allocated to stations near areas with higher customer appearance frequencies, the Hamiltonian HB1 = ∑ j τ j −∑ i σvi,sj .2 is used, where τ j represents the desirable number of vehicles allocated to station sj. The total Hamiltonian is defined as H = HA0 +HA1 +B0HB0 +B1HB1, where Bi are weights for the cost sub-Hamiltonians. τj is defined as the expected number of new customer requests that will arise during the expected travel time to the station (ts j): τj ≜tsj fcP(s j), where fc is the frequency of customer appearances, and P(s j) is the selection probability of vehicles allocated to station sj. By setting the target inventory τ j equal to this expected demand, the system aims to maintain a supply-demand equilibrium. P(s j) is formulated by marginalising the conditional selection probability over the customer location xck: P(sj) = Z xck p(xck)P(sj | xck)dxck. Assuming a uniform prior, the conditional probability P(sj | xck) is proportional to the likelihood as P(s j | xck) ∝p(xck | sj), approximated by an exponential distribution that decreases with the travel time t(xsj,xck) as: p(xck | s j) ≈1 θc e−t(xs j ,xck)/θc, where θc is the average dispatch time.

Quantum Annealing for Micro-mobility Vehicle Dispatch offers promising

Scientists developed a novel dispatch formulation for micro-mobility vehicles utilising Quantum Annealing (QA). This innovative approach moves beyond traditional Vehicle Routing Problem formulations, recognising the dynamic and stochastic nature of micro-mobility demand. To implement this, the team engineered a system where incoming customer demand triggers a dispatch process, beginning with predictions of travel times between vehicle-customer and vehicle-station pairings. These predicted travel times, alongside historical distribution data, were then used to construct the QUBO matrix, which was subsequently solved using a quantum annealer.

This contrasts with conventional VRP approaches that often rely on pre-defined routes and static constraints. The team harnessed a commercial quantum annealer developed by D-Wave Systems to solve the QUBO problems, assessing its capabilities against classical solvers. Specifically, the performance was benchmarked to reveal potential advantages of QA for this dispatch formulation. The study also detailed the implementation of RA, a technique where solutions are refined from high-quality initial states by carefully adjusting the transverse field. This method achieves improved solution quality by leveraging the quantum annealer’s capabilities to explore the solution space more effectively. Experiments revealed that the proposed dynamic approach consistently outperformed other methods in key service quality metrics under both low and high request frequency scenarios. Conversely, the static approach exhibited similar characteristics, effectively guiding vehicles to high-frequency request areas without relying on real-time vehicle positions. Results demonstrate that calibrating the weight ratio B1/B0 is crucial, balancing the trade-off between assigning distant stations and minimizing immediate travel time, with optimal values empirically determined as B1 = 0.3 and B0 = 0.1.

The ablation study, removing a key component (HA1), confirmed its importance in achieving optimal performance. The simulation framework, depicted in Fig0.2, assumed a constant vehicle speed of 4m/s and modelled customer requests using a Poisson distribution, providing a realistic testing environment. This breakthrough delivers a promising solution for efficient and sustainable urban transportation through optimised micro-mobility dispatch.

QUBO and Bayesian optimisation for micro-mobility dispatch offer

Simulation experiments demonstrate that both dynamic and static approaches to incorporating historical data outperform conventional methods like Greedy heuristics and Vehicle Routing Problem formulations in terms of customer service metrics. The findings establish that a dynamic approach, utilising real-time vehicle positions, minimises customer waiting times, although at the cost of increased total travel time. Conversely, the static approach, based on statistical data, offers a balanced improvement in service quality without substantially increasing travel distance. Quantum Annealing, specifically the RA algorithm, showed superior performance to the Gurobi Optimizer under certain conditions, and achieved lower residual energy compared to the FA algorithm when incorporating initial states. The authors acknowledge limitations related to approximations within the probability distributions used and the cyclical interplay between operational parameters and performance metrics. Future research should focus on assessing the stability of this feedback loop and exploring model-free estimation methods, such as neural networks, to refine the accuracy of the dispatch logic and potentially improve the balance between service quality and energy consumption through a hybrid dynamic-static scheme.