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.
Table of Contents
1 Introduction
2 Review on Literature and Research
2.1 Literature on Bilevel Programming
2.1.1 General Definition of Bilevel Programs
2.1.2 A Bilevel Decentralized Capacitated Facility Location Problem
2.2 Literature on Metaheuristics
2.2.1 Tabu Search
2.2.1.1 Basic Principles
2.2.1.2 Neighborhood Creation and Evaluation
2.2.1.3 Tabu List and Tabu Tenure
2.2.1.4 Aspiration Criteria
2.2.1.5 Evaluation Metrics and Candidate List Strategies
2.2.1.6 Intensification and Diversification Strategies
2.2.1.7 Further Aspects of Tabu Search
2.2.2 Simulated Annealing
2.2.2.1 Basic Principles
2.2.2.2 Mathematical and Thermodynamical Background
2.2.2.3 Inhomogeneous and Homogeneous Simulated Annealing
2.2.2.4 Cooling Schemes
2.2.2.5 Modifications of the Standard Procedure
3 Development and Implementation of Appropriate Heuristics
3.1 General Topics
3.1.1 Initial Solutions
3.1.2 Stop Criteria
3.1.3 Neighborhood Generation
3.2 Tabu Search
3.2.1 Implementation of a Tabu List
3.2.1.1 Actualization of the Tabu List and Tabu Tenure Arrays
3.2.1.2 Evaluation of the Neighborhood
3.2.2 Implemented Tabu Search Variants
3.3 Simulated Annealing
3.3.1 Variation of the Neighborhood Function
3.3.2 Implemented Simulated Annealing Variants
4 Numerical Studies
5 Conclusions and Outlook
Research Objectives and Key Topics
The primary objective of this thesis is to deduce, implement, and assess metaheuristic solution approaches for the decentralized capacitated facility location problem. As this problem is characterized as a combinatorial bilevel problem with NP-hard complexity, it cannot be solved efficiently through standard linear programming. The study aims to evaluate the effectiveness of Tabu Search and Simulated Annealing in finding optimal or near-optimal solutions by testing various algorithm configurations.
- Metaheuristic comparison between Tabu Search and Simulated Annealing.
- Transformation of bilevel problems into mixed-integer linear programming models.
- Implementation and parameterization of Tabu Search variants (static vs. dynamic tenures, candidate list strategies).
- Analysis of Simulated Annealing cooling schemes and neighborhood function variations.
- Empirical evaluation of algorithm performance based on varied problem instance sizes.
Extract from the Book
2.2.1.1 Basic Principles
The methodology of Tabu Search has been developed by Fred W. Glover and was first published in 1986 in a journal article (Glover, 1986). In particular, the same author's book Tabu Search provides considerable information and exemplification on this metaheuristic technique (Glover, Laguna, 1997).
Tabu Search is an iterative metaheuristic optimization approach. It is a systematical method for searching for local optimums in a solution space. While scanning the solution space, the basic principle is to set candidate solutions that possess certain attributes characterizing them as “tabu-active” (this term is described below) on a tabu list in order to avoid going in circles. With the aid of an appropriate neighborhood function a new set of potentially optimal solutions is generated. The best solution is selected as a starting point of the continued search.
In formal mathematical notation the basic structure of a Tabu Search iteration can be formulated as follows (Glover, Laguna, 1997, pp. 25-27; Dréo et al., 2006, pp. 51-52):
f: A → B with A ⊆ ℝⁿ and B ⊆ ℝ is a scalar-valued objective function and min_{s∈S} f(s) subject to x ∈ X an optimization problem. S ⊆ ℝⁿ is its solution space (its elements do not necessarily have to be feasible solutions) and X ∈ ℝᵐ the vector of all its constraints. Furthermore N: S → Sˡ is a vector-valued neighborhood function, whereupon it assigns l proximate solutions to a checked solution. The tabu list T ⊆ S is a set of t solutions {s₁, ..., sₜ}. n, m, l and t are positive integer numbers. Accordingly, a Tabu Search iteration mainly consists of the following three steps:
1. Arbitrary or systematical choice of an initial solution s ∈ S.
2. Determination of proximate solutions N(s).
3. Evaluation of N(s):
• Discard elements that are on the tabu list ⇒ generation of a modified neighborhood Ñ(s) = N(s)\(N(s) ∩ T).
• Determine the best candidate: e.g. s′ = arg max_{σ∈Ñ(s)} (f(s) - f(σ)).
Chapter Summary
1 Introduction: Provides an overview of the facility location problem, explaining its bilevel nature and the necessity of using metaheuristics due to NP-hard complexity.
2 Review on Literature and Research: Discusses the theoretical background of bilevel programming and introduces the core concepts of Tabu Search and Simulated Annealing.
3 Development and Implementation of Appropriate Heuristics: Details the practical implementation of the metaheuristic algorithms, including initial solution generation, stop criteria, and neighborhood transformation.
4 Numerical Studies: Presents the experimental results of the algorithms tested on 60 data sets of varying sizes and discusses the impact of parameter settings.
5 Conclusions and Outlook: Summarizes findings, noting that Tabu Search generally outperformed Simulated Annealing, and suggests avenues for future research such as implementing more sophisticated influence measures.
Keywords
Bilevel programming, Facility location problem, Metaheuristics, Tabu Search, Simulated Annealing, Combinatorial optimization, NP-hard, Local optimum, Neighborhood function, Tabu tenure, Cooling schedule, Intensification, Diversification, Linear programming, Algorithm performance.
Frequently Asked Questions
What is the core focus of this academic work?
This thesis focuses on comparing different metaheuristic methods to solve the decentralized capacitated facility location problem, which is structured as a complex combinatorial bilevel optimization problem.
What are the primary algorithmic approaches compared in the research?
The research primarily evaluates and compares the performance of Tabu Search and Simulated Annealing as metaheuristic techniques for navigating the solution space.
What is the main objective of the thesis?
The main objective is to determine which metaheuristic algorithms and parameter settings yield the best solutions for a hierarchical facility location model that cannot be solved through simple linear programming.
Which scientific methodology is employed to solve the problem?
The author employs a combination of heuristic search and linear programming, where the subordinate facility location problem is solved as a linear program embedded within the metaheuristic superstructure.
What is discussed in the main body of the work?
The main body covers the theoretical foundations of bilevel programming, detailed explanations of Tabu Search and Simulated Annealing principles, and the development and testing of specific algorithm variants using Xpress IVE.
Which terms best characterize this research?
Key terms include bilevel programming, combinatorial optimization, metaheuristics, facility location, and performance analysis of search algorithms.
Why is the "decentralized" nature of the facility location problem significant?
The decentralized nature means the decision-making process is divided into two hierarchical levels—the principal firm (leader) and the plants (followers)—which creates reciprocal constraints that preclude simple monolithic linear optimization.
How does Tabu Search differ from Simulated Annealing in this study?
Tabu Search is characterized as a deterministic approach utilizing memory (tabu lists) to avoid cycling, while Simulated Annealing is a randomized approach that uses a temperature-based cooling scheme to escape local optima.
What do the numerical results reveal about algorithm performance?
The results indicate that while some Tabu Search variants can find the global optimum reliably, Simulated Annealing performed worse, often struggling with "swinging" effects between solutions at low temperatures.
- Quote paper
- Florian Grodeke (Author), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, Munich, GRIN Verlag, https://www.grin.com/document/336709
