As environmental awareness grow, many organizations seek to implement Electric Vehicle (EV) fleets. Nonetheless, EVs’ low driving ranges and high recharging times, and the limited Charging Stations (CS) availability make their management more challenging than conventional vehicles. The Electric Vehicle Routing Problem (E-VRP) tackles these challenges. However, many E-VRP variants drop relevant operational constraints, use overly simple models, or do not address route update solutions during operation. This work introduces a strategy to compute EV routes and update them according to observed traffic scenarios. By using an event-based EV state-space model, the strategy tracks relevant variables to account for multiple realistic elements, including nonlinear recharging function, partial recharging, mass-dependent energy consumption, maximum CS capacities, and time-dependent travel times. First, an Offline E-VRP (Off-E-VRP) variant is solved to find initial route candidates. Then, routes are periodically updated during operation according to traffic and EV state measurements by solving an Online E-VRP (On-E-VRP) variant. Genetic Algorithms (GA) are implemented to solve the problems via novel encoding and genetic operators. Finally, simulation results show that the strategy enables the fleet to fulfil its delivery duties, the pre-operation stage provides adequate initial route candidates, and the online stage can improve performance and service quality.