In this article, a synergy of Enhanced Heuristic Descent Gradient (EHDG) algorithm and Voronoi diagram is applied for the optimal planning of electrical Fast Charging Stations (FCSs) for electric buses. The proposed novel technique aims at achieving the optimal locations of charging stations based on route distributions, consumption profiles, and operating costs. The Enhanced Descent Gradient is applied to produce the optimal layout that is graphically represented by Voronoi diagram. A real world case study is presented to the bus network in city of Toronto to be replaced with electric buses that need electrical charging stations. The proposed technique is based on two incorporated stages: analyzing and estimating of the energy consumption of the bus network, then optimizing the allocation of charging stations to minimize the energy consumption and operating cost. The proposed technique is verified and compared with a well-established benchmark algorithm, which is particle swarm optimizer.