Einsatz metaheuristischer Verfahren zur wirtschaftlich optimalen Ausstattung von Bankfilialen

Author
W. Hink
Master Thesis
MT0806 (September, 2008)
Supervised by
o. Univ.-Prof. Dr. Michael Schrefl
Instructed by
Mag. Christian Eichinger
Accomplished at
University Linz, Institute of Business Informatics - Data & Knowledge Engineering

Abstract (English)

This thesis investigates the cost optimization of bank branches. More precisely, the total costs of ownership of self-service components and counters located in bank branches are optimized. Two initial situations can be optimized. On the one hand the optimal configuration of a new bank branch and on the other hand the optimization of an existing configuration of a bank branch. The factors to be considered are the type of components (e.g. ATM, Deposit machine etc.) the amount of these components and the individual configuration of each component. This procedure represents a so called combinatorial optimization.

As there are several possible ways to cope with combinatorial optimization problems, the various problem- and complexity classes have to be analyzed. A variety of optimization algorithms already exist for solving well known combinatorial optimization problems. The most suitable algorithms for this special problem are: Taboo search, simulated annealing, greedy randomized local search, genetic algorithm and ant colony optimization.

Two of these analyzed algorithms, the genetic algorithm and the ant colony optimization, have been selected to solve the optimization problem. The genetic algorithm is implemented with the use of the JGAP library in Java. The ant colony optimization is implemented without the use of any libraries. It is a Java implementation of the pseudo code from the literature. Both algorithms achieve high quality solutions and have the same numerical result.

Abstract (German)

Die Arbeit beschäftigt sich mit der wirtschaftlichen Optimierung von Bankfilialen. Es werden die einzelnen Ausstattungskomponenten über die Geldtransaktionen abgewickelt werden können, z.B. Geldautomat und Bankschalter, hinsichtlich ihrer Konfiguration und Anzahl in der Filiale optimiert. Dabei sind zwei Szenarien denkbar, zum einen die optimale Erstausstattung einer Bankfiliale und zum anderen die Optimierung einer bestehenden Bankfiliale. Beide Fälle benötigen verschiedene Inputparameter wie Informationen über die abgewickelten Transaktionen in der Filiale und Constraints, wie etwa die geforderte Mindestausstattung mit einem gewissen Ausstattungskomponententyp. Beide Szenarien stellen im Allgemeinen ein kombinatorisches Optimierungsproblem mit vielen verschiedenen Optimierungsparametern dar. Die Arbeit geht daher auf diese Optimierungsprobleme ein und erläutert die verschiedenen Problem- und deren zugehörigen Komplexitätsklassen. Die zur Lösung von kombinatorischen Optimierungsproblemen vorhandenen Algorithmen (auch als Metaheuristiken bezeichnet) werden eingehend analysiert und die Anwendbarkeit auf das vorliegende, konkrete Optimierungsproblem wird diskutiert. Betrachtet wurden unter anderem folgende Metaheuristiken: Tabu Suche, Simulierte Abkühlung, Greedy Randomized Local Search, Genetischer Algorithmus und Ant Colony Optimization. Entsprechend den Anforderungen der Aufgabenstellung wurden die Metaheuristiken „Genetischer Algorithmus" und „Ant Colony Optimization" für die Umsetzung des Optimierungsproblems ausgewählt. Mit jedem der beiden Algorithmen wurde die gegebene Problemstellung modelliert, da diese speziell auf den Algorithmus angepasst werden musste. Nach der Modellierung erfolgte die Implementierung der gegebenen Problemstellung. Der Genetische Algorithmus wurde mithilfe der Bibliothek JGAP in Java implementiert. Der Ant Colony Optimization Algorithmus wurde unter Verwendung der ACO Metaheuristik ebenfalls in Java umgesetzt. Beide Algorithmen erzielen, ausgehend von der gleichen Datenbasis, die gleichen Ergebniswerte. In beiden Fällen sind die Ergebnisse der Optimierung von hoher Qualität.