This paper addresses the traveling salesman problem with multiple depots, facility location and stochastic travel times, considering electric vehicles with limited battery capacity. Due to stochastic variations in travel times, vehicles may risk running out of battery during their routes, leading to penalty costs for route failures. Given the NP-hard nature of this problem, we propose a simheuristic approach that integrates Monte Carlo simulation with a metaheuristic algorithm. This approach handles both the stochastic aspects and the optimization requirements. Results show that our simheuristic outperforms the optimal or near-optimal solutions designed for traditional deterministic scenarios when applied in stochastic settings.