Comparison of metaheuristics for the bilevel facility location and mill pricing problem

We consider the bilevel nonlinear facility location and pricing problem. We assume that facilities can charge different prices and the objective is to maximize the total revenue. It is known that the problem is NP-hard in the strong sense even for the given facility location. We show that it belongs to class Poly-APX. We present two hybrid algorithms based on local search: variable neighborhood descent and genetic local search. Being compared with previously known algorithms and CPLEX software, these algorithms show their competitiveness. Computational experiments were conducted on instances from the benchmark library “Discrete Location Problems”. Tab. 2, bibliogr. 30.