  Electric vehicles are a central component of future mobility systems as they
promise to reduce local noxious and fine dust emissions and CO2 emissions, if
fed by clean energy sources. However, the adoption of electric vehicles so far
fell short of expectations despite significant governmental incentives. One
reason for this slow adoption is the drivers' perceived range anxiety,
especially for individually owned vehicles. Here, bad user-experiences, e.g.,
conventional cars blocking charging stations or inconsistent real-time
availability data, manifest the drivers' range anxiety. Against this
background, we study stochastic search algorithms, that can be readily deployed
in today's navigation systems in order to minimize detours to reach an
available charging station. We model such a search as a finite horizon Markov
decision process and present a comprehensive framework that considers different
problem variants, speed-up techniques, and three solution algorithms: an exact
labeling algorithm, a heuristic labeling algorithm, and a rollout algorithm.
Extensive numerical studies show that our algorithms significantly decrease the
expected time to find a free charging station while increasing the solution
quality robustness and the likelihood that a search is successful compared to
myopic approaches.
