Stochastic Route Planning for Electric Vehicles

A method for stochastic electrical vehicle route planning associates weights with road segments, where the weights are probability distributions representing travel time along the segments. Weights representing energy consumption along the segments may be represented as a probability distribution or a deterministic value representing an expectation of a distribution. The method involves performing a Dijkstra search on the road network graph from the vehicle origin to the vehicle destination, where the Dijkstra search computes for each vertex along a path in the network from the vehicle origin to the vehicle destination a convolution of edge weights along the path. The Dijkstra search also includes computing and propagating along the path labels representing the tradeoffs between charging times and total travel-time.