Approximation algorithms for the competitive facility location problem

V. L. Beresnev ; A. A. Melnikov

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 3-19

Résumé

The paper deals with the competitive facility location problem, where two players, the leader and the follower, sequentially establish their facilities and every consumer chooses one of the established facilities in accordance with his own preference. The problem consists in placing the leader's facilities so as to acquire the maximal profit, taking the follower's facilities placing into account, who seeks to maximize his profit as well. The problem is formulated in terms of bi-level integer programming. The paper offers a method for calculating the upper bound for the leader's maximum profit value. The corresponding algorithm consists in designing the classical maximization facility location problem and finding its optimal solution. Along with the calculation of the upper bound, an initial approximate solution for the problem of competitive facility location is generated. The paper offers local search algorithms for improving the initial approximate solution and gives the results of a computational experiment employing the proposed algorithms. The experiment makes it possible to estimate the precision of the obtained approximate solutions and a comparative evaluation of the quality of the algorithms under examination for designing approximate solutions of the examined problem. Tab. 1, bibliogr. 13.

Détail

Keywords: bi-level programming problem, optimal uncooperative solution, upper bound, approximate solution, local search.