In this thesis, a new Green Vehicle Routing Problem (GVRP) as well as a novel Pollution-routing Problem (PRP) are formulated and corresponding algorithms to solve these problems are designed. The GVRP is a problem of routing green vehicles and the PRP is a problem of routing vehicles to minimize pollution. Both problems reflect the intensive need for eliminating the negative environmental effects of using conventional vehicles. On the one hand, the routing plan of green vehicles needs to take into account the refueling issue, so more new constraints need to be considered. On the other hand, the routing plan should not only seek to minimize the economic costs (e.g. travel distance, travel time, etc.), but also the environmental cost (e.g. GHG emissions). To solve these problems, two heuristics and two meta-heuristics have been designed. Meanwhile, extensive numerical experiments are conducted to illustrate the efficiency and validity of our proposed algorithms. Based on the analysis of numerical results, some managerial insights are concluded.