In order to explore the impact of using electric vehicles on the cost and environment of logistics enterprises, this paper studies the optimization of vehicle routing problems with the consideration of carbon trading policies. Both the electric vehicle routing model and the traditional fuel vehicle routing model are constructed aiming at minimizing the total costs, which includes the fixed costs of vehicles, depreciation costs, penalty costs for violating customer time window, energy costs and carbon trading costs. Then a hybrid genetic algorithm (HGA) is proposed to address these two models, the advantages of greedy algorithm and random full permutation are combined to set the initial population, at the same time, the crossover operation is improved to retain the excellent gene fragments effectively and the hill climbing algorithm is embedded to enhance the local search ability of HGA. Furthermore, a case data is used with HGA to carry out computational experiments in these two models and the results indicate that first using electric vehicles for distribution can indeed reduce the carbon emissions, but results in a low customer satisfaction compared with using fuel vehicles. Besides, the battery capacity and charge rate have a great influence on total costs of using electric vehicles. Second, carbon price plays an important role in the transformation of logistics companies. As the carbon price changes, the total costs, carbon trading costs, and carbon emissions of using electric vehicles and fuel vehicles are affected accordingly, yet the trends are different. The changes of carbon quota have nothing to do with the distribution scheme and companies' transformation but influence the total costs of using electric and fuel vehicles for distribution, and the trends are the same. These reasonable proposals can support the government on carbon trading policy, and also the logistics companies on dealing the relationship between economic and social benefits.