Genetic and heuristic algorithms for regrouping service sites. (c2000)

LAUR Repository

Show simple item record

dc.contributor.author Tabbara, Hiba
dc.date.accessioned 2011-05-16T09:23:52Z
dc.date.available 2011-05-16T09:23:52Z
dc.date.copyright 2000 en_US
dc.date.issued 2011-05-16
dc.date.submitted 2000-07-05
dc.identifier.uri http://hdl.handle.net/10725/465
dc.description Includes bibliographical references (leaves 148-150). en_US
dc.description.abstract 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 both its solution quality and evolution time, (c) The tuning IIH does improve the results by removing most anomalies, (d) Breaking up graph vertex granularity can be useful for graphs where vertex weights vary significantly, and (e) The center selection heuristic selects reasonable centers within regions. en_US
dc.language.iso en en_US
dc.subject Genetic algorithms -- Data processing en_US
dc.subject Mathematical optimization -- Data processing en_US
dc.subject Graphic methods -- Computer programs en_US
dc.title Genetic and heuristic algorithms for regrouping service sites. (c2000) en_US
dc.type Thesis en_US
dc.term.submitted Summer I en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.commembers Dr. Haidar Harmanani
dc.author.commembers Dr. George Nasr
dc.author.woa RA en_US
dc.description.physdesc 1 bound copy: vii, 150 leaves; ill. (some col.); 30 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Nashat Mansour
dc.identifier.doi https://doi.org/10.26756/th.2000.2 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account