This work addresses the Electric Vehicle Routing Problem with Time Windows (E-VRPTW), incorporating stochastic consumption and travel times due to possible uncertainties in road conditions and unforeseen events. Unlike traditional approaches that assume deterministic variables, this study formulates a more realistic version of the E-VRPTW, where both energy consumption and travel times are subject to fluctuations. Furthermore, the problem is complicated by the need for electric vehicles (EVs) to recharge at stations en-route, given their limited driving range. In order to address this complexity, a solution methodology combining Approximate Dynamic Programming (ADP) and Column Generation (CG) is proposed. The ADP agents are created to optimize energy consumption and time management while accounting for factors such as partial recharging and the dynamic state of charge (SOC) of the vehicles.