Dynamische evolutionäre Optimierung von Netzwerkproblemen

• Antragsteller: Professor Dr. Martin Middendorf
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme ; Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 392050753

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Da die meisten Netzwerkoptimierungsprobleme (NOPs) NP-schwer sind, können exakte Algorithmen große Probleminstanzen nicht effizient lösen. In der Praxis werden daher häufig metaheuristische Algorithmen zur Lösung von NOPs eingesetzt. Bisher gingen die meisten Forschungen und Anwendungen zu NOPs von statischen oder quasistatischen Bedingungen aus, bei denen sowohl die Netzwerkumgebungen als auch die Optimierungsprobleme im Voraus bekannt sind und im Problemlösungsprozess unverändert bleiben. Die meisten NOPs in der realen Welt unterliegen jedoch dynamischen Änderungen, bei denen sich z.B. die Netzwerktopologie oder die Verfügbarkeit von Ressourcen ändern und nicht a priori bekannt sind. Um reale NOPs lösen zu können, muss deren Dynamik berücksichtigt werden (DNOPs). Um ein DNOP zu lösen, muss über die Zeit eine Reihe hochwertiger Lösungen bereitgestellt werden. In den letzten Jahren hat das Interesse an der Untersuchung von Metaheuristiken für dynamische Optimierungsprobleme (DOPs) stark zugenommen. Es ist jedoch weder aus theoretischer Sicht noch aus rechnerischer Sicht klar, wodurch welche Art von Metaheuristik für welche Arten von Dynamik effizient funktioniert. In diesem Projekt haben wir fortgeschrittene (hybride) metaheuristische Methoden für DNOPs entwickelt und unser Verständnis darüber, warum und wie metaheuristische Methoden DNOPs effizient lösen können, durch theoretische und empirische Studien vertieft.

Projektbezogene Publikationen (Auswahl)

• An Iterated Local Search Algorithm for the Two-Machine Flow Shop Problem with Buffers and Constant Processing Times on One Machine. Lecture Notes in Computer Science, 50-65. Springer International Publishing.
  Le, Hoang Thanh; Geser, Philine & Middendorf, Martin
  
• A Hybrid Swarm Intelligence Algorithm for Vehicle Routing Problem With Time Windows. IEEE Access, 8, 93882-93893.
  Shen, Yang; Liu, Mingde; Yang, Jian; Shi, Yuhui & Middendorf, Martin
  
• An Improvement Heuristic Based on Variable Neighborhood Search for a Dynamic Orienteering Problem. Lecture Notes in Computer Science, 68-83. Springer International Publishing.
  Le, Hoang Thanh; Middendorf, Martin & Shi, Yuhui
  
• Iterated Local Search and Other Algorithms for Buffered Two-Machine Permutation Flow Shops with Constant Processing Times on One Machine. Evolutionary Computation, 29(3), 415-439.
  Le, Hoang Thanh; Geser, Philine & Middendorf, Martin
  
• An Improvement Heuristic Based on Variable Neighborhood Search for Dynamic Orienteering Problems with Changing Node Values and Changing Budgets. SN Computer Science, 3(4).
  Le, Hoang Thanh; Middendorf, Martin & Shi, Yuhui
  
• Evolutionary Dynamic Multiobjective Optimization via Learning From Historical Search Process. IEEE Transactions on Cybernetics, 52(7), 6119-6130.
  Zhao, Qi; Yan, Bai; Shi, Yuhui & Middendorf, Martin
  
• On permutation schedules for two-machine flow shops with buffer constraints and constant processing times on one machine. European Journal of Operational Research, 303(2), 593-601.
  Geser, Philine; Le, Hoang Thanh; Hartmann, Tom & Middendorf, Martin
  
• “Two-Stage Vehicle Routing Problems with Profits and Buffers: Analysis and Metaheuristic Optimization Algorithms.” Dissertation, Fakultät für Mathematik und Informatik der Universität Leipzig Universität Leipzig, 2023.
  Hoang Thanh Le