Includes bibliographical references (leaves 148-150). ; The problem of regrouping service sites into a smaller number of service centers, such that a number of criteria are satisfied, is a realistic problem. Each service center then serves several customer-sites (e.g. towns) in a region. The objectives of regrouping are usually to consolidate human resources, improve service quality, reduce the cost of services, and centralize company branches, in addition to other application-dependent objectives. This regrouping problem is intractable and needs to be automated. Our approach is based on a weighted graph problem formulation, and the solution has two phases. In the first phase, the graph is decomposed into the required number of sub-graphs (regions) using a tuned hybrid genetic algorithm (Tuned HGA). The second phase finds a suitable center within each region by applying a heuristic algorithm. Genetic algorithms are stochastic algorithms based on the mechanics of natural evolution. They are adapted in our work by using a problem-specific objective function for the fitness of individuals. The algorithm is hybridized by a hill climbing procedure in order to direct the search into profitable search sub-domains. The results of the HGA are tuned by using a problem-specific iterative improvement heuristic (IIH) that aim to remove anomalies and hence improve the final solution's quality. We also explore using a pre-processing step to reduce the graph vertex granularity for the purpose of further reducing the objective function value and improving the solution's quality. In the second phase, the heuristic algorithm favors higher-weight and well-centered vertices for selection to be centers within a region. We empirically explored the behavior of the Tuned HGA and the center selecting heuristic algorithm using a number of graphs, representing service sites with their inner-site distances. The empirical results show that: (a) The two-phase approach can be used for solving this problem, (b) Hybridization of the GA improves ...