This paper presents a mixed integer linear programming model to optimize the costs of maintenance and extra hours for scheduling a fleet of battery electric vehicles (BEVs) so that the products are delivered to prespecified delivery points along a route. On this route, each BEV must have an efficient charging strategy at the prespecified charging points. The proposed model considers the average speed of the BEVs, the battery states of charge, and a set of deliveries allocated to each BEV. The charging points are located on urban roads and differ according to their charging rate (fast or ultra-fast). Constraints that guarantee the performance of the fleet's batteries are also taken into consideration. Uncertainties in the navigation of urban roads are modeled using the probability of delay due to the presence of traffic signals, schools, and public works. The routes and the intersections of these routes are modeled as a predefined graph. The results and the evaluation of the model, with and without considering the extra hours, show the effectiveness of this type of transport technology. The models were implemented in AMPL and solved using the commercial solver CPLEX.