In this thesis, metaheuristic solution approaches for the decentralized capacitated facility location problem are deduced, implemented and assessed. As the mentioned problem is a combinatorial bilevel problem it is not easily solvable by means of linear programming. Therefore, different metaheuristic techniques, namely Tabu Search and Simulated Annealing, are used. Each of them is split into several variants. Tabu Search has turned out to deliver better results than Simulated Annealing and converges also from bad initial solutions towards the global optimum. However, the performance of the algorithms is highly dependent on the concrete parameter settings. Thus, the gap between the optimum found and the global optimum can vary from 0 to a multiple of the global optimum depending on the used variant.
The thesis on hand describes the comparison of different metaheuristics in order to generate solutions for the bilevel decentralized capacitated facility location problem. This optimization problem consists of choosing a set of facilities to be opened out of a superset of potential facilities. The objective is to minimize cost, while taking certain constraints into account.
This usual facility location model, which can relatively easily be solved as a linear optimization problem, will be expanded. There is an additional submodel that is intended to develop an optimal production plan for the facilities chosen within the superordinate model. On the sublevel, also cost has to be minimized and as one major constraint the entire external demand has to be satisfied. Such a bilevel problem containing two hierarchically arranged objective functions cannot be solved using the usual methods of linear programming any more.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Review on Literature and Research
- Literature on Bilevel Programming
- General Definition of Bilevel Programs
- A Bilevel Decentralized Capacitated Facility Location Problem
- Literature on Metaheuristics
- Tabu Search
- Basic Principles
- Neighborhood Creation and Evaluation
- Tabu List and Tabu Tenure
- Aspiration Criteria
- Evaluation Metrics and Candidate List Strategies
- Intensification and Diversification Strategies
- Further Aspects of Tabu Search
- Simulated Annealing
- Basic Principles
- Mathematical and Thermodynamical Background
- Inhomogeneous and Homogeneous Simulated Annealing
- Cooling Schemes
- Modifications of the Standard Procedure
- Tabu Search
- Literature on Bilevel Programming
- Development and Implementation of Appropriate Heuristics
- General Topics
- Initial Solutions
- Stop Criteria
- Neighborhood Generation
- Tabu Search
- Implementation of a Tabu List
- Actualization of the Tabu List and Tabu Tenure Arrays
- Evaluation of the Neighborhood
- Implemented Tabu Search Variants
- Implementation of a Tabu List
- Simulated Annealing
- Variation of the Neighborhood Function
- Implemented Simulated Annealing Variants
- General Topics
- Numerical Studies
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This thesis explores metaheuristic solution approaches for the decentralized capacitated facility location problem, a complex combinatorial bilevel problem not easily solved by linear programming. The primary objective is to develop, implement, and assess the effectiveness of different metaheuristic techniques, specifically Tabu Search and Simulated Annealing, in finding optimal solutions.
- Bilevel programming and its application to the decentralized capacitated facility location problem
- Metaheuristic approaches for solving complex optimization problems
- Implementation and comparison of Tabu Search and Simulated Annealing algorithms
- Assessment of algorithm performance and parameter sensitivity
- Evaluation of the effectiveness of different algorithm variants
Zusammenfassung der Kapitel (Chapter Summaries)
The first chapter provides an introduction to the research topic, outlining the problem of decentralized capacitated facility location and its relevance in the context of bilevel programming. Chapter two presents a comprehensive review of relevant literature, covering both bilevel programming and metaheuristic techniques, particularly Tabu Search and Simulated Annealing. The chapter delves into the theoretical foundations and practical considerations of each technique, highlighting key concepts and methodologies. Chapter three focuses on the development and implementation of appropriate heuristics. It discusses general topics such as initial solutions, stop criteria, and neighborhood generation, followed by detailed explanations of the implementation of Tabu Search and Simulated Annealing variants. Chapter four presents numerical studies, analyzing the performance of the developed algorithms on various test instances. The results are discussed and compared, evaluating the effectiveness and limitations of each approach.
Schlüsselwörter (Keywords)
This work focuses on the intersection of bilevel programming, metaheuristic optimization, and the decentralized capacitated facility location problem. Key terms include: bilevel programming, metaheuristics, Tabu Search, Simulated Annealing, decentralized capacitated facility location, combinatorial optimization, algorithm performance, parameter sensitivity, and solution quality.
- Arbeit zitieren
- Florian Grodeke (Autor:in), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, München, GRIN Verlag, https://www.grin.com/document/336709
