Abstract
Competitive facility location problems arise in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. We assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. For this bi-level optimization problem we consider six different customer behavior scenarios from the literature: binary, proportional and partially binary, each combined with essential and unessential demand. The decision making for the leader and the follower depends on these scenarios. In this work we present mixed integer linear programming models for the follower problem of each scenario and use them in combination with an evolutionary algorithm to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them efficiently into similar, not yet considered ones. We present numerical results of our algorithm and compare them to so far state-of-the-art approaches from the literature. Our method shows good performance in all customer behavior scenarios and is able to outperform previous solution procedures on many occasions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alekseeva, E., Kochetov, Y.: Matheuristics and Exact Methods for the Discrete (r|p)-Centroid Problem. In: Talbi, E.G. (ed.) Metaheuristics for Bi-level Optimization, Studies in Computational Intelligence, vol. 482, pp 189–219. Springer Berlin Heidelberg (2013)
Alekseeva, E., Kochetova, N., Kochetov, Y.: Plyasunov, A.: A Hybrid Memetic Algorithm for the Competitive P-Median Problem. In: Bakhtadze, N., Dolgui, A. (eds.) Information Control Problems in Manufacturing, Vol. 13, pp 1533–1537. International Federation of Automatic Control (2009)
Alekseeva, E., Kochetova, N., Kochetov, Y.: Plyasunov, A.: Heuristic and Exact Methods for the Discrete (r|p)-Centroid Problem. In: Cowling, P., Merz, P. (eds.) Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 6022, pp 11–22. Springer Berlin Heidelberg (2010)
Bhadury, J., Eiselt, H., Jaramillo, J.: An alternating heuristic for medianoid and centroid problems in the plane. Comput. Oper. Res. 30(4), 553–565 (2003)
Biesinger, B., Hu, B., Raidl, G.: An evolutionary algorithm for the leader-follower facility location problem with proportional customer behavior. In: Pardalos, P.M., Resende, M.G., Vogiatzis, C., Walteros, J.L. (eds.) Learning and Intelligent Optimization, Lecture Notes in Computer Science, pp 203–217. Springer International Publishing (2014)
Biesinger, B., Hu, B., Raidl, G.: A hybrid genetic algorithm with solution archive for the discrete (r|p)-centroid problem. Technical Report TR 186–1–14–03, Vienna University of Technology, Vienna. Submitted to Journal of Heuristic, Austria (2014)
Fernández, J., Hendrix, E.M.: Recent insights in huff-like competitive facility location and design. Eur. J. Oper. Res. 227(3), 581–584 (2013)
Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, NY, USA (1997)
Hakimi, S.: On locating new facilities in a competitive environment. Eur. J. Oper. Res. 12(1), 29–35 (1983)
Hakimi, S.: Locations with spatial interactions: Competitive locations and games. In: Mirchandani, P.B., Francis, R.L. (eds.) Discrete Location Theory, pp 439–478. Wiley, New York (1990)
Hotelling, H.: Stability in competition. Econ. J. 39(153), 41–57 (1929)
Hu, B., Raidl, G.: An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem. In: Soule, T. (ed.) Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO 2012), pp 393–400. ACM Press, Philadelphia, PA, USA (2012)
Kochetov, Y., Kochetova, N.: Plyasunov, A.: A matheuristic for the leader-follower facility location and design problem. In: Lau, H., Van Hentenryck, P., Raidl, G. (eds.) Proceedings of the 10th Metaheuristics International Conference (MIC 2013), pp 32/1–32/3, Singapore (2013)
Kress, D., Pesch, E.: (r|p)-centroid problems on networks with vertex and edge demand. Comput. Oper. Res. 39, 2954–2967 (2012)
Küçükaydin, H., Aras, N., Altınel, I.K.: Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution. Eur. J. Oper. Res. 208(3), 206–220 (2011)
Laporte, G., Benati, S.: Tabu Search Algorithms for the (r|X p )-medianoid and (r|p)-centroid Problems. Locat. Sci. 2, 193–204 (1994)
Mladenović, N., Brimberg, J., Hansen, P., Moreno-Pérez, J.A.: The p-median problem: A survey of metaheuristic approaches. Eur. J. Oper. Res. 179(3), 927–939 (2007)
Noltemeier, H., Spoerhase, J., Wirth, H.C.: Multiple voting location and single voting location on trees. Eur. J. Oper. Res. 181(2), 654–667 (2007)
Raidl, G., Hu, B.: Enhancing genetic algorithms by a trie-based complete solution archive. In: Cowling, P., Merz, P. (eds.) Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 6022, pp 239–251. Springer Berlin Heidelberg (2010)
Roboredo, M., Pessoa, A.: A branch-and-cut algorithm for the discrete (r|p)-centroid problem. Eur. J. Oper. Res. 224(1), 101–109 (2013)
Saidani, N., Chu, F., Chen, H.: Competitive facility location and design with reactions of competitors already in the market. Eur. J. Oper. Res. 219(1), 9–17 (2012)
Sáiz, M.E., Hendrix, E.M., Pelegrín, B.: On nash equilibria of a competitive location-design problem. Eur. J. Oper. Res. 210(3), 588–593 (2011)
Serra, D., Colomé, R.: Consumer choice and optimal locations models: Formulations and heuristics. Pap. Reg. Sci. 80(4), 439–464 (2001)
Suárez-Vega, R., Santos-Peñate, D., Pablo, D.G.: Competitive Multifacility Location on Networks: the (r|X p )-Medianoid Problem. J. Reg. Sci. 44(3), 569–588 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the Austrian Science Fund (FWF) under grant P24660-N23.
Rights and permissions
About this article
Cite this article
Biesinger, B., Hu, B. & Raidl, G. Models and algorithms for competitive facility location problems with different customer behavior. Ann Math Artif Intell 76, 93–119 (2016). https://doi.org/10.1007/s10472-014-9448-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-014-9448-0