This paper presents a multiobjective methodology for optimal zoning design (OZ), based on the grouping of geographic data with characteristics of territorial aggregation. The two objectives considered are the minimization of the geometric compactness on the geographical location of the data and the homogeneity of any of the descriptive variables. Since this problem is NP hard [1], our proposal provides an approximate solution taking into account properties of partitioning algorithms and design restrictions for territorial space. Approximate solutions are generated through the set of optimum values (Maxima) and the corresponding minimals (dual Minima) [2] of the bi-objective function using Variable Neighborhood Search (VNS) [3] and the Pareto order defined over this set of values. The results obtained by our proposed approach constitute good solutions and are generated in a reasonably low computational time.