Transportation is not only a large energy consumption user, but also an important source of carbon dioxide (CO2) emissions. The environmental issues of road transportation, which accounts for about 17% of CO2 emissions in Europe Union (EU)-27 countries in 2009, are chief concerns in logistics. In this paper, a mathematical model for Green Vehicle Routing Problem (GVRP) considering the energy consumption and carbon emission in the objective function is developed, and an improved Genetic Algorithm (GA) is proposed to solve the model for GVRP. The results show that the GVRP model can save much more energy and reduce CO2 emissions thus the total cost is saved without sacrificing too much distance.