Aiming at the green heterogeneous fleet vehicle routing problem(GHFVRP), a mixed integer programming (MIP) model with the optimization objective of minimizing the sum of vehicle fixed cost, driving cost and carbon emission cost was established, and an enhanced Lagrange relaxation heuristic algorithm (ELRHA) is proposed to solve it. Firstly, the dual problem is constructed by relaxation difficulty constraint and decomposed into two subproblems. Then the Lagrange multiplier is updated by subgradient method, and the lower bound of the original problem is obtained by solving the two subproblems. Secondly, a two-stage heuristic algorithm is designed to repair and optimize the lower bound to obtain a better feasible solution and update the upper bound. Finally, the simulation experiment is carried out. The experimental results show that 17 examples are tested for 20 times under the same experimental environment. The average solving gap of ELRHA is 4.49%, which is 3.28% higher than Gurobi. Meanwhile, the comparison with other algorithms further verifies that ELRHA can solve the problem with high quality upper bound. It can be seen that ELRHA can effectively solve GHFVRP.