Αλγόριθμοι συνδυαστικής βελτιστοποίησης με έμφαση σε μεταευρετικές τεχνικές

Abstract

The main topic of this thesis is the combination of metaheuristics and other methods for solving combinatorial optimization problems (COPs). In particular, focus is given in a special category of COPs known as timetabling problems. Timetabling problems belong in general to the class of NP-hard problems meaning that exact methods are usually unable to solve problem instances with sizes of practical importance. In the first three chapters optimization problems are analyzed and four major disciplines regarding optimization approaches are examined: Mathematical Programming, Artificial Intelligence, Computational Intelligence and Metaheuristics. Borders are not always clear between them while a recent trend is to hybridize approaches originating from the same or different disciplines. Even with the progress in optimization that occurred during the last decades programming successful optimization application still is an intricate mission. Nevertheless, software developing techniques, open source software and exploitation of the processing power of modern hardware can assist in constructing applications that are expected to be of much benefit for their users. Key ideas of achieving this are described in Chapter 4. The first application, presented in Chapter 5, is a pump scheduling system for a water distribution network. The objective is to achieve a way of operation for the pumps of each reservoir that results in diminished electricity cost. A model of the problem was constructed and the metaheuristic technique of genetic algorithms with the addition of several heuristics solved the problem. The second application, presented in Chapter 6, is the examination timetabling problem for Universities. Educational timetabling problems in general attract much interest from the scientific community. Our approach targeted various models of the examination timetabling problem and constituted by two major phases: construction and improvement. A number of metaheuristics were hybridized (Simulated Annealing, GRASP, VNS, Taboo Search and others) while certain sub-problems were solved using exact methods (Integer Programming). The results that we achieved in known datasets for evaluating the performance of such methods were most promising. In particular, for the publicly available datasets of the second International Timetabling Competition our approach achieved the best published score for 6 out of 8 datasets. The third application, presented in Chapter 7, is the construction of timetables for Greek high schools. A model of the problem that had publicly available problem instances and published results was used. Better results were able to be obtained by reformulating the problem and subsequently using a branch and cut approach implemented using entirely open source software. In summary, successful results of our approaches suggest that metaheuristics and hybridized metaheuristics with other metaheuristic or exact methods appears to be a promising research direction for handling complex combinatorial optimization problems.