A discrete competitive facility location model with variable attractiveness

Abstract

We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time.

Keywords:

• competitive facility location
• variable facility attractiveness
• mixed-integer nonlinear programming
• Lagrangean heuristic
• branch-and-bound

Acknowledgements

This work was partially supported by Boğaziçi Research Fund Grant No: 08HA301D.

Notes

1 They are available electronically on the website located at URL address http://www.ie.boun.edu.tr/~aras/hande/datasets.htm.