A bilevel competitive location and pricing model with nonuniform split of demand

A. V. Kononov ; A. A. Panin ; A. V. Plyasunov

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 3, pp. 27-45.

Résumé

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.

Détail

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

Bibliographie

[1] Hotelling H., “Stability in competition”, Econ. J., 39:153 (1929), 41–57 | DOI

[2] Eiselt H. A., Laporte G., Thisse J.-F., “Competitive location models: a framework and bibliography”, Transp. Sci., 27:1 (1993), 44–54 | DOI | Zbl

[3] Eiselt H. A., Laporte G., “Sequential location problems”, Eur. J. Oper. Res., 96:2 (1996), 217–242 | DOI | MR

[4] Hamacher H. W., Nickel S., “Classification of location models”, Loc. Sci., 6:1 (1998), 229–242 | DOI

[5] Plastria F., “Static competitive facility location: an overview of optimisation approaches”, Eur. J. Oper. Res., 129:3 (2001), 461–470 | DOI | MR | Zbl

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

[7] Kononov A., Panin A., Plyasunov A., “A new model of competitive location and pricing with the uniform split of the demand”, Optimization problems and their applications, Commun. Comput. Inform. Sci., 871, Springer, Cham, 2018, 16–28 | DOI

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

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

[10] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and approximation: combinatorial optimization problems and their approximability properties, Springer-Verl., Berlin, 1999, 524 pp. | MR | Zbl

[11] Alekseeva E., Kochetov Yu., “Metaheuristics and exact methods for the discrete $({r\mid p)}$-centroid problem”, Metaheuristics for bi-level optimization, Stud. Comput. Intell., 482, Springer-Verl., Berlin, 2013, 189–219 | MR

[12] Alekseeva E., Kochetov Yu., Plyasunov A., “An exact method for the discrete ${(r\mid p)}$-centroid problem”, J. Global Optim., 63:3 (2015), 445–460 | DOI | MR | Zbl

[13] V. L. Beresnev, A. A. Melnikov, “A cut generation algorithm to find an optimal solution in a market competition”, J. Appl. Indust. Math., 13:2 (2019), 351–367 | DOI | MR

[14] Alekseeva E., Kochetov Yu., Plyasunov A., “Complexity of local search for the $p$-median problem”, Eur. J. Oper. Res., 191:3 (2008), 736–752 | DOI | MR | Zbl

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

[16] Davydov I. A., Kochetov Y. A., Carrizosa E., “A local search heuristic for the ${(r\mid p)}$-centroid problem in the plane”, Comput. Oper. Res., 52 (2014), 334–340 | DOI | MR | Zbl

[17] S. M. Lavlinskii, A. A. Panin, A. V. Plyasunov, “Comparison of models of planning public-private partnership”, J. Appl. Indust. Math., 10:3 (2016), 356–369 | DOI | MR | Zbl

[18] Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Comparison of metaheuristics for the bilevel facility location and mill pricing problem”, J. Appl. Indust. Math., 9:3 (2015), 392–401 | DOI | MR | Zbl

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

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

[21] Alekseeva E., Kochetov Y., Talbi E.-G., “A metaheuristic for the discrete bilevel problem with multiple objectives at the lower level”, Int. Trans. Oper. Res., 24:5 (2017), 959–981 | DOI | MR | Zbl

[22] Davydov I., Kochetov Yu., Plyasunov A., “On the complexity of the $(r\mid p)$-centroid problem in the plane”, TOP, 22:2 (2014), 614–623 | DOI | MR | Zbl

[23] Iellamo S., Alekseeva E., Chen L., Coupechoux M., Kochetov Yu., “Competitive location in cognitive radio networks”, 4OR, 13:1 (2015), 81–110 | DOI | MR | Zbl

[24] A. A. Panin, A. V. Plyasunov, “On complexity of the bilevel location and pricing problems”, J. Appl. Indust. Math., 8:4 (2014), 574–581 | DOI | MR | Zbl

[25] A. V. Plyasunov, A. A. Panin, “The pricing problem. II: Computational complexity”, J. Appl. Indust. Math., 7:3 (2013), 420–430 | DOI | MR | Zbl