The Electric Vehicle Routing Problem (EVRP) is a multi-objective, NP-hard optimization problem focused on efficiently managing various constraints involved in routing single or multiple electric vehicles. Recently, several evolutionary algorithms have been applied to EVRP, particularly those that incorporate battery State of Health (SoH) as a key constraint in the optimization process. However, most existing optimization algorithms treat SoH deterministically and do not account for the uncertainty inherent in its estimation. As a result, these methods may yield solutions that do not accurately reflect real-world battery conditions. To address this limitation, we propose a hybrid genetic algorithm that incorporates the stochastic process distribution of battery SoH estimation into the optimization procedure. Results from a lithium-ion battery-based fleet scenario show that incorporating uncertainty into the optimization improves battery SoH prediction accuracy by up to 70% compared to baseline methods.