The rapid proliferation of electric vehicles (EVs) has emerged as a vital solution to reduce greenhouse gas emissions and our reliance on fossil fuels. However, the limited driving range of EVs, along with the sparse distribution of recharging stations, poses significant challenges for fleet operators and transportation planners. In this context, the Time-Dependent Electric Vehicle Routing Problem with Recharging Stations (TDEVRP-RS) serves as an indispensable optimization model, designed to streamline the operational efficiency of electric vehicle fleets while minimizing operational costs and ensuring optimal energy utilization. The TDEVRP-RS model comprehensively considers various factors, such as time-dependent travel times, recharging station availability, energy consumption, and driving range restrictions. This dynamic approach not only enables efficient route planning but also promotes the incorporation of renewable energy sources, encouraging a sustainable transportation ecosystem. In addition, floating car data is employed to estimate the travel speed for each link on an hourly basis throughout the operational day. As a result, this paper introduces a comprehensive mathematical formulation, which is implemented in the General Algebraic Modeling System (GAMS) to enable solution through exact methods and ensure subsequent validation. A variety of efficient metaheuristic algorithms are proposed to tackle the presented mathematical model in real-sized scenarios. In the end, the road network of Rome is utilized to visualize vehicle routes, offering a precise and high-quality depiction of the generated tours.