A hybrid genetic algorithm with solution archive for the discrete (r|p)-centroid problem

In this article we propose a hybrid genetic algorithm for the discrete $(r|p)$ ‐centroid problem. We consider the competitive facility location problem where two non‐cooperating companies enter a market sequentially and compete for market share. The first decision maker, called the leader, wants to maximize his market share knowing that a follower will enter the same market. Thus, for evaluating a leader’s candidate solution, a corresponding follower’s subproblem needs to be solved, and the overall problem therefore is a bi‐level optimization problem. This problem is ${\mathrm{\sum }}_2^P$ ‐hard, i.e., harder than any problem in NP (if $\text{P}\ne \text{NP}$ ). A heuristic approach is employed which is based on a genetic algorithm with tabu search as local improvement procedure and a complete solution archive. The archive is used to store and convert already visited solutions in order to avoid costly unnecessary re‐evaluations. Different solution evaluation methods are combined into an effective multi‐level evaluation scheme. The algorithm is tested on well‐known benchmark sets of both Euclidean and non‐Euclidean instances as well as on larger newly created instances. Especially on the Euclidean instances our algorithm is able to exceed previous state‐of‐the‐art heuristic approaches in solution quality and running time in most cases.