Due to the ever increasing concern about the environment, the resulting policies and advances in technology, zero and low emission electrical and hybrid vehicles become much more important and popular. Despite the advantages of electrical vehicles, their relatively limited cruising range (in comparison to traditional diesel/petrol vehicles) and significant battery loading time provide major challenges for their usage.

As a result, in order for electrical vehicles to be viable, it is necessary to have a sufficient number of charging stations effectively distributed throughout a road network. Given a particular road network layout, determining optimal locations and capacities for these charging stations is a challenging multi-objective optimisation problem with many constraints. One of the key objectives is to minimise travel time by requiring detours necessary for battery recharging to be as short as possible. On the other hand, constraints require the number of charging stations to be reasonably small, the distance between neighbouring stations must not exceed the cruising range of electrical vehicles, and capacities of the charging stations should be sufficient enough to avoid bottlenecks.

Before one can solve the above optimization problem it is necessary to compute a reachability graph for the street network. A reachability graph encodes which locations in the street network are reachable from a given location. The aim of this project is to investigate methods for computing such a graph.