Efficient Shortest Path Computation for Electric Vehicles in Time-Dependent Networks

Conventional vehicles significantly contribute to fossil fuel consumption, straining the planet. As efforts to achieve net-zero emissions intensify, the adoption of Electric Vehicles (EVs) in transportation has become crucial to success. While calculating efficient shortest paths in road networks is a common task, most studies focus primarily on charging needs and energy consumption models, often overlooking other factors that can affect the travel time of EV. In this paper, we address two key factors that impact travel time for EVs: (i) the variability of traffic conditions throughout the day, which causes travel times of each edge of the road network to change from time to time; and (ii) the limited availability of charging stations, which can lead to significant waiting times. To tackle these challenges, we first propose the pareto-optimal search to find the efficient shortest path for EVs as the baseline algorithm. However, the pareto-optimal search requires to maintain the pareto frontier at each vertex of graph, thus can be time-consuming due to its exponential branching. To improve efficiency, we introduce a binning algorithm that effectively reduces runtime while keeping a balance with solution quality. While our binning algorithm returns an approximate solution, the bin size can be adjusted to balance between query runtime and solution quality. Experimental results show that our binning algorithm outperforms the pareto-optimal search by around two orders of magnitude while effectively exploring near-optimal solutions.