Sequential Competitive Facility Location: Exact and Approximate Algorithms

References

• Alekseeva E, Kochetov Y, Plyasunov A (2015) An exact method for the discrete (r\ p)-centroid problem. J. Global Optim. 63(3):445–460.Crossref, Google Scholar
• Aros-Vera F, Marianov V, Mitchell JE (2013) p-hub approach for the optimal park-and-ride facility location problem. Eur. J. Oper. Res. 226(2):277–285.Crossref, Google Scholar
• Bard JF (1998) Practical Bilevel Optimization: Algorithms and Applications (Kluwer Academic Publishers, Norwell, MA).Crossref, Google Scholar
• Ben-Akiva ME, Lerman SR, Lerman SR (1985) Discrete Choice Analysis: Theory and Application to Travel Demand, vol. 9 (MIT Press, Cambridge, MA).Google Scholar
• Benati S, Hansen P (2002) The maximum capture problem with random utilities: Problem formulation and algorithms. Eur. J. Oper. Res. 143(3):518–530.Crossref, Google Scholar
• Colson B, Marcotte P, Savard G (2005) Bilevel programming: A survey. 4OR 3(2):87–107.Crossref, Google Scholar
• Dan T, Marcotte P (2019) Competitive facility location with selfish users and queues. Oper. Res. 67(2):479–497.Abstract, Google Scholar
• Dimitrov NB, Morton DP (2013) Interdiction models and applications. Hermann J, ed. Handbook of Operations Research for Homeland Security (Springer, Berlin), 73–103.Crossref, Google Scholar
• Drezner T, Drezner Z (1998) Facility location in anticipation of future competition. Location Sci. 6(1-4):155–173.Crossref, Google Scholar
• Drezner T, Drezner Z, Kalczynski P (2015) A leader-follower model for discrete competitive facility location. Comput. Oper. Res. 64:51–59.Crossref, Google Scholar
• Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36(3):307–339.Crossref, Google Scholar
• Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy FH, ed. Combinatorial Structures and Their Applications (Gordon and Breach Science Publishers, Philadelphia), 69–87.Google Scholar
• Eiselt HA, Laporte G (1997) Sequential location problems. Eur. J. Oper. Res. 96(2):217–231.Crossref, Google Scholar
• Fischer K (2002) Sequential discrete p-facility models for competitive location planning. Ann. Oper. Res. 111(1-4):253–270.Crossref, Google Scholar
• Freire AS, Moreno E, Yushimito WF (2016) A branch-and-bound algorithm for the maximum capture problem with random utilities. Eur. J. Oper. Res. 252(1):204–212.Crossref, Google Scholar
• Gentile J, Alves Pessoa A, Poss M, Costa Roboredo M (2018) Integer programming formulations for three sequential discrete competitive location problems with foresight. Eur. J. Oper. Res. 265(3):872–881.Crossref, Google Scholar
• Godinho P, Dias J (2010) A two-player competitive discrete location model with simultaneous decisions. Eur. J. Oper. Res. 207(3):1419–1432.Crossref, Google Scholar
• Haase K (2009) Discrete location planning. Institute of Transport and Logistics Studies Working Paper No. ITLS-WP-09-07, Institute of Transport and Logistics Studies, University of Sydney, Sydney, Australia. Accessed August 1, 2022, https://trid.trb.org/view/891853.Google Scholar
• Haase K, Müller S (2014) A comparison of linear reformulations for multinomial logit choice probabilities in facility location models. Eur. J. Oper. Res. 232(3):689–691.Crossref, Google Scholar
• Hakimi SL (1983) On locating new facilities in a competitive environment. Eur. J. Oper. Res. 12(1):29–35.Crossref, Google Scholar
• Henrici P (1961) Two remarks on the Kantorovich inequality. Amer. Math. Monthly 68(9):904–906.Crossref, Google Scholar
• Huff DL (1964) Defining and estimating a trading area. J. Marketing 28(3):34–38.Crossref, Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kantorovich L (1948) Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk 3(28):89–185.Google Scholar
• Kleinert T, Labbé M, Ljubić I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9(2021):1000007.Google Scholar
• Krause A, McMahan HB, Guestrin C, Gupta A (2008) Robust submodular observation selection. J. Machine Learning Res. 9:2761–2801.Google Scholar
• Kress D, Pesch E (2012) Sequential competitive location on networks. Eur. J. Oper. Res. 217(3):483–499.Crossref, Google Scholar
• Küçükaydn H, Aras N, Kuban Altnel I (2011) Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution. Eur. J. Oper. Res. 208:206–220.Crossref, Google Scholar
• Küçükaydn H, Aras N, Kuban Altnel I (2012) A leader-follower game in competitive facility location. Comput. Oper. Res. 39(2):437–448.Crossref, Google Scholar
• Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• Ljubić I, Moreno E (2018) Outer approximation and submodular cuts for maximum capture facility location problems with random utilities. Eur. J. Oper. Res. 266(1):46–56.Crossref, Google Scholar
• Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Wiley, Hoboken, NJ).Google Scholar
• Mai T, Lodi A (2020) A multicut outer-approximation approach for competitive facility location under random utilities. Eur. J. Oper. Res. 284(3):874–881.Crossref, Google Scholar
• McFadden D (1973) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics (Economic Theory and Mathematical Economics) (Academic Press, Cambridge, MA), 105–142.Google Scholar
• Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans. 39(1):3–14.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1981) Maximizing submodular set functions: Formulations and analysis of algorithms. North-Holland Math. Stud. 59(1981):279–301.Crossref, Google Scholar
• O’Kelly ME (1999) Trade-area models and choice-based samples: Methods. Environ. Planning A Econom. Space 31(4):613–627.Crossref, Google Scholar
• Plastria F (2001) Static competitive facility location: An overview of optimisation approaches. Eur. J. Oper. Res. 129(3):461–470.Crossref, Google Scholar
• Plastria F, Vanhaverbeke L (2008) Discrete models for competitive location with foresight. Comput. Oper. Res. 35(3):683–700.Crossref, Google Scholar
• Ralphs T, Tahernajad S, Besançon M, Vigerske S (2021) A solver for mixed integer bilevel programs. Accessed August 1, 2022, https://github.com/coin-or/MiBS.Google Scholar
• Ralphs T, Tahernajad S, DeNegre S, Güzelsoy M, Hassanzadeh A (2015) Bilevel integer optimization: Theory and algorithms. Internat. Sympos. Math. Programming.Google Scholar
• ReVelle C (1986) The maximum capture or “sphere of influence” location problem: Hotelling revisited on a network. J. Regional Sci. 26(2):343–358.Crossref, Google Scholar
• ReVelle C, Serra F (1995) Competitive location in discrete space. Drezner Z, ed. Facility Location: A Survey of Applications and Methods (Springer, Berlin), 367–386.Google Scholar
• Roboredo MC, Pessoa AA (2013) A branch-and-cut algorithm for the discrete (r|p)-centroid problem. Eur. J. Oper. Res. 224(1):101–109.Crossref, Google Scholar
• Sáiz ME, Hendrix EM, Fernández J, Pelegrín B (2009) On a branch-and-bound approach for a Huff-like Stackelberg location problem. OR Spectrum 31(3):679–705.Crossref, Google Scholar
• Serra D, ReVelle C (1994) Market capture by two competitors: The preemptive location problem. J. Regional Sci. 34(4):549–561.Crossref, Google Scholar
• Shen S (2011) Reformulation and cutting-plane approaches for solving two-stage optimization and network interdiction problems. PhD thesis, University of Florida, Gainesville, FL.Google Scholar
• Slater D (1975) Underdevelopment and spatial inequality: Approaches to the problems of regional planning in the third world. Progress Planning 4(2):97–167.Crossref, Google Scholar
• Smith JC, Song Y (2020) A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3):797–811.Crossref, Google Scholar
• Song Y, Shen S (2016) Risk-averse shortest path interdiction. INFORMS J. Comput. 28(3):527–539.Link, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Programming Comput. 12(4):529–568.Crossref, Google Scholar
• Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• von Stackelberg H (1934) Marktform und Gleichgewicht (Springer, Berlin).Google Scholar
• Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243–251.Link, Google Scholar
• Wood R (2010) Bilevel network interdiction models: Formulations and solutions. Cochran JJ, ed. Wiley Encyclopedia of Operations Research and Management Science, https://onlinelibrary.wiley.com/doi/10.1002/9780470400531.eorms0932.Google Scholar
• Zhang Y, Berman O, Verter V (2012) The impact of client choice on preventive healthcare facility network design. OR Spectrum 34(2):349–370.Crossref, Google Scholar