This paper presents a mathematical formulation and a heuristic solution method in order to locate optimal sites for afforestation of agricultural land. These sites must maximize levels of environmental performance, and must fulfill shape and size requirements. Since the criteria involved in the problem are represented by means of raster structures, the sites are composed by a given number of cells. The ultimate objective of this work is the development of a high performance heuristic able to find near to optimal afforestation sites. For validating the heuristic approach, a comparison with the mathematical method is carried out in limited sized areas within The Netherlands, Denmark, and Flanders. The comparison reveals that the heuristic is considerably faster than the mathematical method, and that the objective values obtained with the two approaches are significantly similar.