Metaheuristics for bilevel optimization: A comprehensive review

A bilevel programming model represents the relationship in a specific decision process that involves decisions within a hierarchical structure of two levels. The upper-level problem is associated with the decision maker with higher hierarchy, and the nested problem is associated with a lower-level. This modeling approach has been applied to diverse real-life situations. However, exact solution methods are limited due to the inherent complexity of bilevel optimization models. Therefore, alternative solution methods are needed, such as metaheuristics. The design and implementation of effective metaheuristic algorithms that produce good-quality solutions in acceptable computational time has been an active research area. Recently, there has been an increase in this area of research. This study aims to review all the published papers devoted to implementing metaheuristics for solving bilevel problems up-to-date. A bibliometric analysis is performed to track the evolution of this topic. Also, the journals and authors with more contributions are identified. The specific components of the proposed metaheuristics are described in detail, independent of the inspiration behind the metaheuristics. A detailed analysis of the combination of components is included to determine the more common ones. Additionally, classification of the manner in which the crucial bilevel aspects of the problem are handled in the metaheuristics, is detailed, for example, the type of approach considered for designing the metaheuristic, what can be nested, single-level reformulation, co-evolutionary, and biobjective transformation. Also, the metaheuristics that assume a unique follower's reaction, the optimistic or pessimistic approaches are noted. A discussion regarding the interesting findings is included, in which a critic of lax practices is conducted. Some areas of opportunity for research and promising recent approaches are listed. Finally, relevant conclusions of this exhaustive review are presented.