Metaheuristics for dynamic combinatorial optimization problems

Abstract

Many real-world optimization problems are combinatorial optimization problems subject to dynamic environments. In such dynamic combinatorial optimization problems (DCOPs), the objective, decision variables and/or constraints may change over time, and so solving DCOPs is a challenging task. Metaheuristics are a good choice of tools to tackle DCOPs because many metaheuristics are inspired by natural or biological evolution processes, which are always subject to changing environments. In recent years, DCOPs have attracted a growing interest from the metaheuristics community. This paper is a tutorial on metaheuristics for DCOPs. We cover the definition of DCOPs, typical benchmark problems and their characteristics, methodologies and performance measures, real-world case study and key challenges in the area. Some future research directions are also pointed out in this paper.