A Nested Evolutionary Algorithm for Solving a Bilevel Competitive Location Problem: Optimistic vs. Pessimistic Approaches

Competitive facility location problems involve two different firms competing for customers, each aiming to increase its market share. Typically, there exists a hierarchy between the firms based on factors such as size, power, or influence in the market. In this type of problem, it is commonly assumed that both firms will open a fixed number of facilities. Moreover, the firm acting as the leader in the market must consider the reaction of the other firm, considered as the follower. The follower's decisions are conditioned by the leader's decisions, as the facilities opened by the leader directly affect the follower's choices. Both firms aim to maximize their own market share. Additionally, in this study, it is assumed that the follower is interested in locating its facilities as far apart from each other as possible. Therefore, a bilevel optimization problem is formulated, where the leader considers a mono-objective problem, and the follower considers a bi-objective problem. It is important to note that obtaining the follower's reaction introduces some ambiguity since the follower's response is given as a Pareto front. An assumption must be made regarding this crucial issue. In this study, two well-known approaches are considered: the optimistic and the pessimistic ones. To solve the problem, two versions of an evolutionary algorithm embedded with an
$\varepsilon$
-constraint method and with an NSGA-II are proposed. Hence, two variants of the algorithm are implemented, one for each approach assumed. Computational experimentation is conducted to validate the performance of the proposed algorithms in solving this complex problem. Moreover, a comparison regarding the impact caused by assuming the optimistic or the pessimistic approaches is performed. The obtained results reveal relevant findings, and an interesting direction for further research is identified.