This paper proposes a novel dispatch formulation for micro-mobility vehicles using a Quantum Annealer (QA). In recent years, QA has gained increasing attention as a high-performance solver for combinatorial optimization problems. Meanwhile, micro-mobility services have been rapidly developed as a promising means of realizing efficient and sustainable urban transportation. In this study, the dispatch problem for such micro-mobility services is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling efficient solving through QA. Furthermore, the proposed formulation incorporates historical usage data to enhance operational efficiency. Specifically, customer arrival frequencies and destination distributions are modeled into the QUBO formulation through a Bayesian approach, which guides the allocation of vacant vehicles to designated stations for waiting and charging. Simulation experiments are conducted to evaluate the effectiveness of the proposed method, with comparisons to conventional formulations such as the vehicle routing problem. Additionally, the performance of QA is compared with that of classical solvers to reveal its potential advantages for the proposed dispatch formulation. The effect of reverse annealing on improving solution quality is also investigated.
This paper proposes a novel dispatch formulation for micro-mobility vehicles using a Quantum Annealer (QA). In recent years, QA has gained increasing attention as a high-performance solver for combinatorial optimization problems. Meanwhile, micro-mobility services have been rapidly developed as a promising means of realizing efficient and sustainable urban transportation. In this study, the dispatch problem for such micro-mobility services is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling efficient solving through QA. Furthermore, the proposed formulation incorporates historical usage data to enhance operational efficiency. Specifically, customer arrival frequencies and destination distributions are modeled into the QUBO formulation through a Bayesian approach, which guides the allocation of vacant vehicles to designated stations for waiting and charging. Simulation experiments are conducted to evaluate the effectiveness of the proposed method, with comparisons to conventional formulations such as the vehicle routing problem. Additionally, the performance of QA is compared with that of classical solvers to reveal its potential advantages for the proposed dispatch formulation. The effect of reverse annealing on improving solution quality is also investigated.
This paper proposes a novel dispatch formulation for micro-mobility vehicles using a quantum annealing (QA). In recent years, QA has gained increasing attention as a high-performance solver for combinatorial optimization problems. Meanwhile, micro-mobility services have been rapidly developed as a promising means of realizing efficient and sustainable urban transportation. In this study, the dispatch problem for such micro-mobility services is formulated as a quadratic unconstrained binary optimization (QUBO) problem, enabling efficient solving through QA. Furthermore, the proposed formulation incorporates historical usage data to enhance operational efficiency. Specifically, customer arrival frequencies and destination distributions are modeled into the QUBO formulation through a Bayesian approach, which guides the allocation of vacant vehicles to designated stations for waiting and charging. Simulation experiments are conducted to evaluate the effectiveness of the proposed method, with comparisons to conventional formulations such as the vehicle routing problem. Additionally, the performance of QA is compared with that of classical solvers to reveal its potential advantages for the proposed dispatch formulation. The effect of reverse annealing on improving solution quality is also investigated.
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.
This paper presents a quantum-inspired optimization scheme for patient allocation, aimed at the expedient and efficient distribution of medical resources. The objective is to minimize patients' waiting times and optimize the usage of available medical capacity by allocating patients to the most appropriate hospitals based on the severity of their injuries. This allocation problem is situated within the urban context, seeking to minimize the distance between patients and hospitals. Traditionally, solving such large-scale allocation problems in expansive urban areas poses significant computational challenges. However, by incorporating quantum-inspired methods, we model this problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using a digital annealer. We conducted an experimental study on the digital annealing device and compared its performance with that of a conventional simulated annealing algorithm. The results demonstrate that our proposed digital annealing approach to patient allocation offers superior performance and effectiveness.
Optimal routing problems of electric vehicles (EVs) have attracted much attention in recent years, and installation of charging stations is an important issue for EVs. Hence, we focus on the joint optimization of the location of charging stations and the routing of EVs. When routing problems are formulated in the form of quadratic unconstrained binary optimization (QUBO), specialized solvers such as quantum annealers are expected to provide optimal solutions with high speed and accuracy. However, battery capacity constraints make it hard to formulate into QUBO form without a large number of auxiliary qubits. Here, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which the battery capacity constraints are automatically learned. This method enables us to optimize the number and location of charging stations and the routing of EVs with a small number of searches. Applying this method to a routing problem of 20 locations, we observed consistent convergence toward battery-feasible solutions across independent runs, demonstrating stable learning behavior of the proposed framework. Small-scale validation experiments using exhaustive enumeration show that the framework reliably discovers feasible configurations close to the global optimum, while runtime and QUBO-size analyses clarify its computational characteristics.
Quantum annealing (QA) is a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC), and it has shown significant computational advantages in solving combinatorial optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This paper presents a QA approach for solving a variant VRP known as multi-depot capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management. We consider heterogeneous depots and vehicles with different capacities. Given a set of heterogeneous depots, the number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a set of spatially distributed customer locations, the MDCVRP attempts to identify routes of various vehicles satisfying the capacity constraints such as that all the customers are served. We model MDCVRP as a quadratic unconstrained binary optimization (QUBO) problem, which minimizes the overall distance traveled by all the vehicles across all depots given the capacity constraints. Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer requests. We discuss the problem complexity and a solution approach to solving MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.