Optimization of Electric Vehicles Routes and Charging Locations
This paper presents a practical use-case for quantum, namely how to optimize routes including charging stations for electric vehicles.
This is a really hard problem when you consider limited range, route variables, traffic, construction, and suboptimal EV charging station locations for not just one EV, but for the more than 4 million that are currently on the road in the United States.
With more than 30 million EVs expected to be on the road by 2030, optimizing for the future becomes incredibly important.
To expand outside the scope of this paper, a quantum computer could also help by:
(1) Designing more efficient and lighter batteries to extend the range and lifecycles between charges; and (2) Develop new energy materials and chemistry that would obviate the need to charge/recharge in the first place.
These too are hard problems but would compound the optimization effect outlined in this paper.
Below and linked is the full arXiv preprint.
And I know this is run on a quantum annealing system and not a gate-based quantum computer, but this is impactful to me nonetheless.
--
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 annealer 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.
Then, we propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which method 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 confirmed that the learning process works well and efficient searches find good solutions. This result enhances the possibility that the QUBO solver could be applied to the constraints contained problems which is difficult to formulate into QUBO form without a large number of ancilla qubits.
In conclusion, this study addressed the simultaneous optimization of electric vehicle routing with battery constraints and the placement of charging stations. Given a configuration of charging stations, we formulated the vehicle routing problem—considering battery capacity in a simplified manner—as a QUBO model, which is compatible with quantum annealing, and used it to determine the corresponding tour. To optimize the placement of charging stations, we employed BOCS, a sequential optimization method. The tour cost used for learning was computed based on the routing results obtained from the QUBO formulation. As a result, the BOCS framework effectively learned the impact of battery constraints through its sequential search process, enabling efficient exploration and yielding solutions that satisfied all constraints.