Solving in real-time the dynamic and stochastic shortest path problem for electric vehicles by a prognostic decision making strategy

Abstract

The adoption of Electric Vehicles (EVs) has substantially increased during the last decade, creating the need for customized EV-oriented routing strategies capable of using the enormous amount of historical, and real-time, traffic data that is collected through Intelligent Transport Systems (ITSs). Existing EV routing algorithms, however, concentrate mostly on the usage historical data to compute offline optimal paths, whereas the use of real-time traffic information to compute en-route path updates is still an almost unexplored topic; mainly due to its inherent computational challenges. This research effort proposes a Prognostic Decision Making (PDM) strategy to solve in real-time the Electric Vehicle Dynamic Stochastic Shortest Path Problem (EV-DSSPP); aiming at the simultaneous utilization of historical and real-time traffic data. Factors such as recurring and non-recurring traffic congestion, elevation, velocity and EV's parameters are incorporated into the decision-making process. The proposed strategy has two hierarchical functional layers. The lower layer consists of a fast-computing routing algorithm that, by construction, guarantees a real-time execution. The higher layer organizes the periodic enroute execution of the first layer to compute en-route path updates during a trip. This strategy can hence serve as an expert router that works jointly with an ITS to assist EV drivers on route. The proposal is validated through a simulation study based on real-world traffic data collected in Santiago, Chile. The results show that periodic en-route path updates can generate a reduction in both travel time and energy consumption, which evidences the benefits of incorporating real-time traffic information into the EV-routing problems.