Sponsor: IFPEN
Context
IFPEN is dedicated to advancing sustainable mobility by refining vehicle routing to minimize energy use across all vehicle types. Our current projects focus on strategically positioning charging stations and tailoring battery capacities for electric vehicles to enhance efficiency. We employ sophisticated graph optimization methods, particularly constrained shortest path optimization, to determine optimal routes. This approach considers both the vehicle's physical attributes and the battery's current charge level, ensuring that each route maximizes energy efficiency and supports the broader goal of decarbonization.
Objectives
This route planning problem is formulated as a bi-objective optimization aiming to find the best compromise between travel time and energy consumption. To solve the problem, it is necessary to construct a routing graph, modeled as a directed graph. Let G = (V, A) be such a graph, where V represents the set of vertices (i.e., the endpoints of each road segment), and A represents the set of edges (i.e., the road segments connecting the nodes of the graph). In any route planning strategy, the underlying optimization problem presents an obvious decision variable, namely the edges of the graph composing the feasible path (according to the network connectivity) from a specified origin to a destination.
The objective function of the optimization problem is expressed as a weighted sum of time and energy costs on each edge of the routing graph, as estimated by the travel time and energy consumption models developed at IFPEN. When route planning involves electric vehicles (EVs), the problem becomes more complex. Indeed, electric vehicles have a lower range than conventional vehicles, and the charging infrastructure is less widespread than fuel stations. Therefore, it is necessary to integrate additional constraints into the optimization problem, specifically constraints on the battery's state of charge (dynamic state). This type of constraint is particularly challenging to manage because ensuring the battery does not exceed its physical limits must be verified for every possible sub-path between origin and destination. This results in the highly combinatorial nature of the problem, which cannot be solved with polynomial complexity algorithms.
Another aspect of this problem is that the costs on the edges of the graph can take negative values (EVs can regenerate energy and have negative consumption on certain downhill road portions, for example). Consequently, if one wants to solve the problem using an "exact" method, the constrained Bellman-Ford algorithm is necessary to ensure the optimality of the routing solution. However, this algorithm shows poor scalability, and its time complexity grows exponentially, which makes it impractical for large graphs. [2] proposed a solution method and its practical implementation for standard technologies (in the classical domain). This approach is designed to enhance user acceptance by delivering precise solutions with minimal computational requirements.
Several studies have revealed the effectiveness of quantum algorithms [1], highlighting their potential to revolutionize various fields including complex optimization. These research efforts demonstrate a significant improvement in processing speed compared to classical solutions. In this project, our aim is to examine the feasibility of this approach for solving the shortest path problem, enriched by the introduction of new specific constraints. This research seeks to evaluate the performance and added value of quantum solutions in solving constrained eco-charging problems on graphs.
References
[1] Dalyac, C., Henriet, L., Jeandel, E. et al. Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. EPJ Quantum Technol. 8, 12 (2021). doi:10.1140/epjqt/s40507-021-00100-3
[2] G. De Nunzio, I. Ben Gharbia and A. Sciarretta, "A Time- and Energy-Optimal Routing Strategy for Electric Vehicles with Charging Constraints," 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Rhodes, Greece, 2020, pp. 1-8, doi:10.1109/ITSC45102.2020.9294622