This paper explores approaches to find optimal locations for charging stations in the context of a private delivery company that is attempting to electrify its fleet of delivery vehicles. Although the possible total set of customers is known in advance, the organization has uncertainty in realizing the actual customers on a particular day and this ambiguity leads to uncertainty in the location of charging stations. To address this, we divide the routes based on their frequencies as frequent and infrequent. We further consider three sets of frequent routes and develop three sets of models and heuristics that determine the locations of the charging stations. The first model maximizes the number of chargers located on arcs which are common to multiple routes. The second model explores the possibility of locating chargers at the customer locations as a combinatorial problem and solves it to optimality. The last model, which considers routes with chargers on the last arcs of two or more different routes, consolidates those stations. To showcase the efficacy and efficiency of our proposed approaches, we present results obtained by applying these models to various instances. We find that, although the number of routes that can fall into the first set is comparatively less, the algorithm reduces the chargers that should be located in those routes. The total time spent on routes in the second set is reduced by almost 15 percent on average. For the last set, the important metric while evaluating the efficacy of the model is the increase in travel time, which is relatively small for the number of chargers that are being consolidated. These findings can serve as valuable insights for decision-makers planning to electrify their fleet.