[en] 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.
Disciplines :
Production, distribution & supply chain management
Aboolian, R., Berman, O., Krass, D., Competitive facility location model with concave demand (2007) European Journal of Operational Research, 181 (2), pp. 598-619. , DOI 10.1016/j.ejor.2005.10.075, PII S0377221706004991
Aboolian, R., Berman, O., Krass, D., Competitive facility location and design problem (2007) European Journal of Operational Research, 182 (1), pp. 40-62. , DOI 10.1016/j.ejor.2006.07.021, PII S0377221706008009
Achabal, D.D., Gorr, W.L., Mahajan, V., MULTILOC: A multiple store location decision model (1982) J Retailing, 2, pp. 5-25
Beasley, J.E., Lagrangean heuristics for location problems (1993) Eur J Opl Res, 65, pp. 383-399
Beasley, J.E., Lagrangean relaxation (1993) Modern Heuristic Techniques for Combinatorial Problems, pp. 243-343. , Reeves CR (ed) Halsted Press: New York
Benati, S., Hansen, P., The maximum capture problem with random utilities: Problem formulation and algorithms (2002) Eur J Opl Res, 143, pp. 518-530
Berman, O., Krass, D., Locating multiple competitive facilities: Spatial interaction models with variable expenditures (2002) Annals of Operations Research, 111 (1-4), pp. 197-225. , DOI 10.1023/A:1020957904442
Bertsekas, D.P., (1995) Nonlinear Programming, , Athena Scientific: Boston
Drezner, T., Locating a single new facility among existing, unequally attractive facilities (1994) J Regional Sci, 2, pp. 237-252
Drezner, T., Drezner, Z., Replacing continuous demand with discrete demand in a competitive location model (1997) Naval Research Logistics, 44 (1), pp. 81-95
Drezner, T., Drezner, Z., Validating the gravity-based competitive location model using inferred attractiveness (2002) Annals of Operations Research, 111 (1-4), pp. 227-237. , DOI 10.1023/A:1020910021280
Drezner, T., Drezner, Z., Finding the optimal solution to the Huff based competitive location model (2004) Comput Mngt Sci, 2, pp. 193-208
Drezner, Z., Drezner, T., Multiple facilities location in the plane using the gravity model (2006) Geographical Analysis, 38 (4), pp. 391-406. , DOI 10.1111/j.1538-4632.2006.00692.x
Drezner, T., Drezner, Z., Lost demand in a competitive environment (2008) Journal of the Operational Research Society, 59 (3), pp. 362-371. , DOI 10.1057/palgrave.jors.2602330, PII 2602330
Drezner, T., Drezner, Z., Salhi, S., Solving the multiple competitive facilities location problem (2002) European Journal of Operational Research, 142 (1), pp. 138-151. , DOI 10.1016/S0377-2217(01)00168-0, PII S0377221701001680
Fernandez, J., Pelegrin, B., Plastria, F., Toth, B., Solving a Huff-like competitive location and design model for profit maximization in the plane (2007) European Journal of Operational Research, 179 (3), pp. 1274-1287. , DOI 10.1016/j.ejor.2006.02.005, PII S0377221706000841
Fernandez, J., Pelegrn, B., Plastria, F., Toth, B., Planar location and design of a new facility with inner and outer competition: An interval lexicographical-like solution procedure (2007) Netw Spat Econ, 7, pp. 19-44
Grossmann, I.E., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E., (2004) DICOPT Solver Manual, , http://www.gams.com/dd/docs/solvers/dicopt.pdf, accessed 31 January 2010
Held, M., Wolfe, P., Crowder, H.P., Validation of subgradient optimization (1974) Math Program, 6, pp. 62-88
Hotelling, H., Stability in competition (1929) Econ J, 39, pp. 41-57
Huff, D.L., Defining and estimating a trading area (1964) J Marketing, 28, pp. 34-38
Huff, D.L., A programmed solution for approximating an optimum retail location (1966) Land Econ, 42, pp. 293-303
Laguna, M., Mart, R., (2003) Scatter Search: Methodology and Implementations in C, , Kluwer Academic Publishers: Norwell, Massachusetts
Murtagh, B.A., Saunders, M.A., Murray, W., Gill, P.E., (2004) MINOS Solver Manual, , http://www.gams.com/dd/docs/solvers/minos.pdf, accessed 31 January 2010
Nakanishi, M., Cooper, L.G., Parameter estimation for a multiplicative competitive interaction model: Least squares approach (1974) J Marketing Res, 11, pp. 303-311
Plastria, F., Carrizosa, E., Optimal location and design of a competitive facility (2004) Mathematical Programming, 100 (2), pp. 247-265. , DOI 10.1007/s10107-003-0468-5
Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T., (1986) Numerical Recipes: The Art of Scientific Computing, , Cambridge University Press: New York
Toth, B., Fernandez, J., Pelegrn, B., Plastria, F., Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models (2009) Comput Opns Res, 36, pp. 1393-1405