A route planning method for the electric bus fleets (EBFs) system was proposed based on dynamic programming. It highlights the effect of working temperatures on capacity fading of batteries and route planning for EBFs. A case study was conducted to investigate the effect of varied temperature in a year on the route planning for EBFs. The results show that the optimal scheme of route planning for EBFs varies significantly with the change of working temperature. There are different choices for the specific route planning, including the number of optimal paths and the matches between the EBFs and the routes. Thus, the effect of temperature on the dynamic capacity fading of batteries should be considered when the route planning strategy is applied in a large-scale public transportation system. The operational costs of EBFs can then be reduced due to reducing replacement of the battery packs in EBFs. The proposed method provides useful guidance for the route planning for EBFs in practical applications.