Volume 26, No 3, 2019, P. 27-45

UDC 519.8+518.25
A. V. Kononov, A. A. Panin, and A. V. Plyasunov
A bilevel competitive location and pricing model with nonuniform split of demand

Abstract:
Under study is the bilevel competitive facility location and pricing problem which is formulated in terms of the Stackelberg game. The problem involves the two producers: the Leader and the Competitor. They consistently place their facilities and set prices. The choice of prices is based on the Bertrand model of price competition and the possibility of dividing a client’s demand if this will be profitable for both players. In this case, the demand is divided between the players in a given proportion. The complexity is investigated of finding the optimal solution of the problem and its particular cases. It is shown that the problem is $\Sigma_2^P$-hard. However, under certain conditions on the input parameters, the complexity decreases significantly and in some cases the problem becomes polynomially solvable.
Illustr. 3, bibliogr. 25.

Keywords: bilevel problem, Stackelberg game, facility location, pricing, Bertrand model, nonuniform split of demand, complexity, polynomial hierarchy.

DOI: 10.33048/daio.2019.26.638

Aleksandr A. Kononov ^1,2
Artem A. Panin ^1,2
Aleksandr V. Plyasunov ^1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: alvenko@math.nsc.ru, arteam1897@gmail.com, apljas@math.nsc.ru

Received November 22, 2018
Revised April 2, 2019
Accepted June 5, 2019

References

[1] H. Hotelling, Stability in competition, Econom. J. 39 (153), 41–57 (1929).

[2] H. A. Eiselt, G. Laporte, and J.-F. Thisse, Competitive location models: A framework and bibliography, Transport. Sci. 27 (1), 44–54 (1993).

[3] H. A. Eiselt and G. Laporte, Sequential location problems, Europ. J. Oper. Res. 96 (2), 217–242 (1996).

[4] H. W. Hamacher and S. Nickel, Classification of location models, Locat. Sci. 6 (1), 229–242 (1998).

[5] F. Plastria, Static competitive facility location: An overview of optimization approaches, Europ. J. Oper. Res. 129 (3), 461–470 (2001).

[6] A. A. Panin, M. G. Pashchenko, and A. V. Plyasunov, Bilevel competitive facility location and pricing problems, Automat. Remote Control 75 (4), 715–727 (2014).

[7] A. Kononov, A. Panin, and A. Plyasunov, A new model of competitive location and pricing with the uniform split of the demand, in Optimization Problems and Their Applications. OPTA 2018, Ser. Communications in Computer and Information Science, Vol. 871 (Springer, Cham, 2018), pp. 16–28.

[8] M. D. Garcia, P. Fernandez, and B. Pelegrin, On price competition in location-price models with spatially separated markets, TOP 12, 351–374 (2004).

[9] B. Pelegrin, P. Fernandez, M. D. Garcia, and S. Cano, On the location of new facilities for chain expansion under delivered pricing, Omega 40 (2), 149–158 (2012).

[10] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (Springer, Berlin, 1999).

[11] E. Alekseeva and Yu. Kochetov, Metaheuristics and exact methods for the discrete ($r | p$)-centroid problem, in Studies in Computational Intelligence, Vol. 482: Metaheuristics for Bilevel Optimization, (Springer, Berlin, 2013), pp. 189–219.

[12] E. Alekseeva, Yu. Kochetov, and A. Plyasunov, An exact method for the discrete ($r | p$)-centroid problem, J. Global Optim. 63 (3), 445–460 (2015).

[13] V. L. Beresnev and A. A. Melnikov, A cut generation algorithm to find an optimal solution in a market competition, Diskretn. Anal. Issled. Oper. 26 (2), 5–29 (2019) [Russian] [J. Appl. Indust. Math. 13 (2), 351–367 (2019)].

[14] E. Alekseeva, Yu. Kochetov, and A. Plyasunov, Complexity of local search for the p-median problem, Europ. J. Oper. Res. 191 (3), 736–752 (2008).

[15] I. Davydov, Yu. Kochetov, and S. Dempe, Local search approach for the competitive facility location problem in mobile networks, Internat. J. Artif. Intell. 16 (1), 130–143 (2018).

[16] I. A. Davydov, Yu. A. Kochetov, and E. Carrizosa, A local search heuristic for the ($r | p$)-centroid problem in the plane, Comput. Oper. Res. 52, 334–340 (2014).

[17] S. M. Lavlinskii, A. A. Panin, and A. V. Plyasunov, Comparison of models of planning public-private partnership, Diskretn. Anal. Issled. Oper. 23 (3), 35–60 (2016) [Russian] [J. Appl. Indust. Math. 10 (3), 356–369 (2016)].

[18] Yu. A. Kochetov, A. A. Panin, and A. V. Plyasunov, Comparison of metaheuristics for the bilevel facility location and mill pricing problem, Diskretn. Anal. Issled. Oper. 22 (3), 36–54 (2015) [Russian] [J. Appl. Indust. Math. 9 (3), 392–401 (2015)].

[19] Z. Diakova and Yu. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron. Notes Discrete Math. 39 (1), 29–34 (2012).

[20] I. A. Davydov, Yu. A. Kochetov, N. Mladenovic, and D. Urosevic, Fast metaheuristics for the discrete ($r | p$)-centroid problem, Automat. Remote Control. 75 (4, 677–687, 2014.

[21] E. Alekseeva, Yu. Kochetov, and E.-G. Talbi, A metaheuristic for the discrete bilevel problem with multiple objectives at the lower level, Intern. Trans. Oper. Res. 24 (5), 959–981 (2017).

[22] I. A. Davydov, Yu. A. Kochetov, and A. V. Plyasunov, On the complexity of the ($r | p$)-centroid problem in the plane, TOP 22 (2), 614–623 (2014).

[23] S. Iellamo, E. Alekseeva, L. Chen, M. Coupechoux, and Yu. Kochetov, Competitive location in cognitive radio networks, 4OR 13 (1), 81–110 (2015).

[24] A. A. Panin and A. V. Plyasunov, On complexity of the bilevel location and pricing problems, Diskretn. Anal. Issled. Oper. 21, No. 5, 54–66 (2014) [Russian] [J. Appl. Indust. Math. 8 (4), 574–581 (2014)].

[25] A. V. Plyasunov and A. A. Panin, The pricing problem. II: Computational complexity, Diskretn. Anal. Issled. Oper. 19 (6), 56–71 (2012) [Russian] [J. Appl. Indust. Math. 7 (3), 420–430 (2013)].