One of the most significant extension problems of the vehicle routing problem (VRP) is the heterogeneous fixed fleet vehicle routing problem (HFFVRP), which aims to provide service to a specific customers' group using a limited number of vehicles. This is vital in ensuring if a business can meet customers' demand while simultaneously maximizing its profit. The HFFVRP is concerned with determinations of the minimum cost routes for a fleet of vehicles in order to satisfy the demand of the customer population. The fleet composition consists of various types of vehicles, which differ with respect to their maximum carrying load and variable cost per distance unit. This research will take the CO2 emission as a contributing factor to the green VRP (GVRP). In this thesis, at first a comprehensive introduction of the mentioned problem will be discussed. Then recent studies in this area will be reviewed and based on the literature review the research gap will be clarified. A hybrid meta-heuristic algorithm named imperialist competitive algorithm (ICA) will then be introduced. Uncertainty as an important issue in todays' real world industry is considered in this thesis. Also in order to solve the problem optimally, the mentioned solution approach will be implemented. By enhancing the traditional ICA, a new approach named hybrid ICA (HICA) is developed, which its performance is compared to the traditional ICA and genetic algorithm (GA). Results show that HICA is considerably out performing other algorithms in regard to objective function value. The impact of changes in each constraint on the objective value is also investigated.