Evolutionary Dynamic Optimisation for Network Problems

• Applicant: Professor Dr. Martin Middendorf
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems ; Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2018 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 392050753

• Final Report Year: 2023

Final Report Abstract

Since most of the network optimisation problems (NOPs) are NP-hard, exact algorithms cannot deal with large problems efficiently. Thus, metaheuristic algorithms are often used to solve NOPs in practice. Most research and applications in NOPs so far have assumed static or quasi-static conditions, where both the network environments and the optimisation problems are known in advance and remain unchanged in the problem-solving process. However, most NOPs in the real world are subject to dynamic changes, where, e.g., the network topologies or availability of resources, change with time and are not known a priori. To address real-world NOPs, we need to consider NOPs under continuously changing network environments (DNOPs). A DNOP is much harder than its static version since the dynamics in the network environment and the problem itself bring in many additional difficulties. To successfully solve a DNOP, a series of high-quality solutions should be provided over time instead of a one-off solution as in the static environment. In recent years, there has been a rapidly growing interest in studying metaheuristics for dynamic optimisation problems (DOPs), however it is still unknown, either theoretically or computationally, what makes which type of metaheuristic effective and efficient for what types of dynamics. In this project we have develop advanced (hybrid) metaheuristic methods for DNOPs, and further our understanding of why and how metaheuristics methods can solve DNOPs efficiently, through computational, theoretical and applied studies.

Publications

• 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