Metaheuristics for problems with limited budget of evaluations : doctoral thesis - Molnar, Goran 1985. (G. Molnar; Faculty of electrical engineering and computing, 2020)
Metaheuristic techniques are an essential set of optimisation techniques with broad applications in numerous problems of great practical importance. Despite their success, using metaheuristics also has notable drawbacks: they are highly complex algorithms whose implementation process still lacks a formal development methodology. Their development is expensive as it requires highly trained experts, considerable time and computational resources. This work proposes a bottom-up development methodology for metaheuristic development, based on a component-based view of metaheuristics and gradual addition of more complex elements. The development methodology has the potential to reduce development time and costs while providing high-quality results. This development methodology was experimentally validated on three difficult problems: (1) call centre workforce scheduling, (2) carsharing reservations optimisations, (3) carsharing variable trip pricing problem. The second and third problems were especially difficult given their resource-intensive objective function, that requires long evaluation times, this way restricting the evaluations budget. Solutions to these two problems are to the best of the author's knowledge, the first applications of the iterated local search metaheuristic on problems with a limited budget of evaluations. Further, these solutions do not use surrogate modelling, which is common practice with such problems. The work concludes with a set of guidelines for surrogate-free solving of optimisation problems with a limited budget of evaluations, based on the experiences solving these two problems. Keywords: metaheuristics, development methodology, Iterated local search, workforce scheduling, carsharing, transportation optimisation