The comparably low driving ranges of battery electric vehicles (BEV) cause time-consuming recharging stops if long distances have to be covered. Thus, navigation systems not only have to compute routes leading from the BEV's current position to the destination, but also to plan recharging stops. This type of routing problem is often modeled as a constrained shortest path problem. The constraint ensures that the BEV does not run out of energy. In this paper, a de facto deterministic reformulation of this problem type is suggested, which allows handling uncertainty-particularly the risks resulting from imperfect energy consumption predictions. For this purpose, a certain part of the battery capacity is used as an energy buffer. Different approaches to dynamically optimize the size of this energy buffer in dependency of the expected level of uncertainty are proposed and a corresponding modification of a typical routing algorithm is described. Furthermore, a simulation study is conducted showing that the described framework allows keeping the probability to run out of energy close to zero (for the test settings: < 0.5%) as long as a suitable approach for defining the size of the energy buffer is applied.