Comparing Heuristics for Solving Linear Bilevel Problems

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
• 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
  • Simulated Annealing
    • Variation of the Neighborhood Function
    • Implemented Simulated Annealing Variants
• 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.