There are increasing interests in improving public transportation systems. One of the proposed strategies for this improvement is the use of Battery Electric Vehicles (BEVs). This approach leads to a new challenge as the BEVs’ routing is exposed to the traditional routing problems of conventional vehicles, as well as the particular requirements of the electrical technologies of BEVs. Examples of BEVs’ routing problems include the autonomy, battery degradation, and charge process. This work presents a differential evolution algorithm for solving an electric vehicle routing problem (EVRP). The formulation of the EVRP to be solved is based on a scheme to coordinate the BEVs’ routing and recharge scheduling, considering operation and battery degradation costs. A model based on the longitudinal dynamics equation of motion estimates the energy consumption of each BEV. A case study, consisting of an airport shuttle service scenario, is used to illustrate the proposed methodology. For this transport service, the BEV energy consumption is estimated based on experimentally measured driving patterns.