A Hybrid Memetic Algorithm for the Competitive p-Median Problem

Abstract In the competitive p -median problem, two decision makers, the leader and the follower, compete to attract clients from a given market. The leader opens his facilities, anticipating that the follower will react to the decision by opening his/her own facilities. The leader and the follower try to maximize their own profits. This is the Stackelberg game. We present it as a linear bilevel 0–1 problem. It is known that the problem is Σ P 2 -complete. We develop a hybrid memetic algorithm for it where the follower problem is solved by commercial software. To obtain an upper bound for this maximization problem, we reformulate the bilevel problem as a single level mixed integer programming problem with exponential number of constraints and variables. Removing some of them, we get the desired upper bound. For finding an appropriate family of constraints and variables, we use metaheuristics again. As a result, we get near optimal solutions for the bilevel problem with an a posteriori bound for deviation from the global optimum. Computational results for Euclidian test instances are discussed.