Volume 27, No 4, 2020, P. 80-103

UDC 519.8
T. V. Levanova and A. Yu. Gnusarev
Variable neighborhood search algorithms for a competitive location problem with elastic demand

Abstract:
Under consideration is the situation in a competitive market when a new Company plans to make profit from opening its own facilities that offer goods or services. The Company have to take it into account that there are several projects for opening each facility, and similar facilities of the Competitor are already placed on the market. Moreover, customers themselves choose the places to meet their demand in dependence on where and which facilities are located. The Company’s goal is to choose locations and projects for opening new facilities in order to attract the largest share of all customer demand. The special type of demand leads to nonlinearity of the objective function and to additional difficulties in finding an optimal solution. In this article we construct some variants of variable neighborhood search algorithms, perform their experimental analysis by using the upper estimates, obtain a posteriori accuracy estimates, and discuss the results.
Tab. 4, illustr. 2, bibliogr. 44.

Keywords: location problem, competition, elastic demand, heuristic, variable neighborhood search.

DOI: 10.33048/daio.2020.27.575

Tatyana V. Levanova ^1,2
Aleksandr Yu. Gnusarev ¹
1. Omsk Branch of Sobolev Institute of Mathematics,
13 Pevtsov Street, 644099 Omsk, Russia
2. Dostoevsky Omsk State University,
55a Mir Avenue, 644077 Omsk, Russia
e-mail: levanova@ofim.oscsbras.ru, alexander.gnussarev@gmail.com

Received April 17, 2017
Revised June 7, 2020
Accepted June 19, 2020

References

[1] T. V. Levanova and A. S. Fedorenko, Variable neighborhood search for two-stage facility location problem, Diskretn. Anal. Issled. Oper. 15 (3), 43–57 (2008) [Russian].

[2] Discrete Location Theory (Wiley, New York, 1990).

[3] Yu. A. Kochetov, E. V. Alekseeva, T. V. Levanova, and M. A. Loresh, Large neighborhood local search for the p-median problem, Yugoslav J. Oper. Res. 15 (1), 53–63 (2005).

[4] R. Sridharan, The capacitated plant location problem, Eur. J. Oper. Res. 87 (1), 203–213 (1995).

[5] H. Hotelling, Stability in competition, Econ. J. 39, 41–57 (1929).

[6] W. J. Reilly, The Law of Retail Gravitation (Knickerbocker Press, New York, 1931).

[7] D. L. Huff, Defining and estimating a trade area, J. Mark. 28, 34–38 (1964).

[8] D. L. Huff, A programmed solution for approximating an optimum retail location, Land Econ. 42, 293–303 (1966).

[9] A. G. Wilson, Retailers’ profits and consumers’ welfare in a spatial interaction shopping mode, in Theory and Practice in Regional Science (Pion, London, 1976), pp. 42–59.

[10] O. Berman and D. Krass, Locating multiple competitive facilities: Spatial interaction models with variable expenditures, Ann. Oper. Res. 111, 197–225 (2002).

[11] R. Aboolian, O. Berman, and D. Krass, Competitive facility location model with concave demand, Eur. J. Oper. Res. 181 (2), 598–619 (2007).

[12] R. Aboolian, O. Berman, and D. Krass, Competitive facility location and design problem, Eur. J. Oper. Res. 182 (1), 40–62 (2007).

[13] T. Drezner and Z. Drezner, Lost demand in a competitive environment, J. Oper. Res. Soc. 59, 362–371 (2008).

[14] Z. Drezner and C. H. Scott, Optimizing the location of a production firm, Netw. Spat. Econ. 10, 411–425 (2010).

[15] T. Drezner, Z. Drezner, and D. Zerom, Competitive facility location with random attractiveness, Oper. Res. Lett. 46, 312–317 (2018).

[16] H. Küçükaydin, N. Necati Aras, and I. K. Altinel, A leader–follower game in competitive facility location, Comput. Oper. Res. 39 (2), 437–448 (2012).

[17] T. V. Levanova and A. Yu. Gnusarev, Variable neighborhood search approach for the location and design problem, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR 2016, Vladivostok, Russia, Sep. 19–23, 2016) (Springer, Heidelberg, 2016), pp. 159–170 (Lect. Notes Comput. Sci., Vol. 9869).

[18] T. V. Levanova and A. Yu. Gnusarev, Ant colony optimization for competitive facility location problem with elastic demand, in Optimization Problems and Their Applications (Proc. School-Seminar OPTA-SCL 2018, Omsk, Russia, July 8–14, 2018) (RWTH Aachen Univ., Aachen, 2018), pp. 239–248 (CEUR Workshop Proc., Vol. 2098). Available at http://ceur-ws.org/Vol-2098 (accessed July 2, 2020).

[19] T. V. Levanova and A. Yu. Gnusarev, Development of threshold algorithms for a location problem with elastic demand, in Large-Scale Scientific Computing (Rev. Sel. Pap. 11th Int. Conf. LSSC 2017, Sozopol, Bulgaria, June 5–9, 2017) (Springer, Cham, 2017), pp. 382–389 (Lect. Notes Comput. Sci., Vol. 10665).

[20] T. V. Levanova and A. Yu. Gnusarev, Simulated annealing for competitive $p$-median facility location problem, J. Phys. Conf. Ser. 1050, 012044.1–5 (2018). Available at https://iopscience.iop.org/article/10.1088/1742-6596/1050/1/012044/pdf (accessed July 2, 2020).

[21] T. V. Levanova and A. Yu. Gnusarev, Development of ant colony optimization algorithm for competitive $p$-median facility location problem with elastic demand, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 18th Int. Conf. MOTOR 2019, Ekaterinburg, Russia, July 8–12, 2019) (Springer, Cham, 2019), pp. 68–78 (Commun. Comput. Inf. Sci., Vol. 1090).

[22] R. G. McGarvey and T. M. Cavalier, Determining the location and capacity of competitive facilities, Int. J. Math. Oper. Res. 2 (6), 694–723 (2010).

[23] J. Perl and P. Ho, Public facilities location under elastic demand, Transp. Sci. 24 (2), 117–136 (1990).

[24] A. Pahlavani and M. Saidi-Mehrabad, A competitive facility location model with elastic demand and patronising behaviour sensitive to location, price and waiting time, Int. J. Logist. Syst. Manage. 10 (3), 293–312 (2011).

[25] X. Wang, Location and design decisions of facilities in a distribution system with elastic customer demand, J. Shanghai Jiaotong Univ. (Sci.) 14 (5), 606–612 (2009).

[26] M. G. Ashtiani, Competitive location: A state-of-art review, Int. J. Ind. Eng. Comput. 7, 1–18 (2016).

[27] O. Berman, T. Drezner, Z. Drezner, and D. Krass, Modeling competitive facility location problems: New approaches and results, in Decision Technologies and Applications (Inst. Oper. Res. Manage. Sci., Catonsville, 2009), pp. 156–181 (INFORMS Tutor. Oper. Res.).

[28] T. Drezner, Gravity models in competitive facility location, in Contributions to Location Analysis (Springer, Cham, 2019), pp. 253–275 (Int. Ser. Oper. Res. Manage. Sci., Vol. 281).

[29] H. A. Eiselt, V. Marianov, and T. Drezner, Competitive location models, in Location Science (Springer, Cham, 2015), pp. 365–398.

[30] A. Karakitsiou, Modeling Discrete Competitive Facility Location (Springer, Cham, 2015).

[31] D. Kress and E. Pesch, Sequential competitive location on networks, Eur. J. Oper. Res. 217 (3), 483–499 (2012).

[32] A. E. Bakhtin, A. A. Kolokolov, and Z. V. Korobkova, Discrete Problems of Production and Transport Type (Nauka, Novosibirsk, 1978) [Russian].

[33] R. Aboolian, O. Berman, and D. Krass, Capturing market share: Facility location and design problem, in Proc. Int. Conf. “Discrete Optimization and Operations Research”, Novosibirsk, Russia, June 24–28, 2013 (Izd. Inst. Mat., Novosibirsk, 2013), pp. 7–11.

[34] T. A. J. Nicholson, A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems, J. Inst. Math. Appl. 13, 362–375 (1965).

[35] Yu. A. Kochetov, N. Mladenovic and P. Hansen, Local search with alternating neighborhoods, Diskretn. Anal. Issled. Oper., Ser. 2, 10 (1), 11–43 (2003) [Russian].

[36] P. Hansen and N. Mladenovic, Variable neighborhood search: Principles and applications, Eur. J. Oper. Res. 130 (3), 449–467 (2001).

[37] A. Anokic, Z. Stanimirovic, T. Davidovic and Ð. Stakic, Variable neighborhood search based approaches to a vehicle scheduling problem in agriculture, Int. Trans. Oper. Res. 27 (1), 26–56 (2020).

[38] Handbook of Metaheuristics (Springer, New York, 2010) (Int. Ser. Oper. Res. Manage. Sci., Vol. 146).

[39] P. A. Kononova and Yu. A. Kochetov, The variable neighborhood search for the two machine flow shop problem with a passive prefetch, Diskretn. Anal. Issled. Oper. 19 (5), 63–82 (2012) [Russian] [J. Appl. Ind. Math. 7 (1), 54–67 (2013)].

[40] J. Pei, N. Mladenovic, D. Uroševic, J. Brimberg, and X. Liu, Solving the traveling repairman problem with profits: A novel variable neighborhood search approach, Inf. Sci. 507, 108–123 (2020).

[41] J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard, Metaheuristics for Hard Optimization (Springer, Heidelberg, 2006).

[42] T. V. Levanova and S. E. Belan, Application of upper bounds for analysis of approximate algorithms for a competitive location problem with elastic demand, Vestn. Omsk. Gos. Univ., No. 4, 4–10 (2017) [Russian].

[43] The General Algebraic Modeling System (GAMS Development, Fairfax, 2020). Available at http://www.gams.com (accessed July 2, 2020).

[44] LocalSolver (LocalSolver, Paris, 2020). Available at http://www.localsolver.com (accessed July 2, 2020).