English version:
Journal of Applied and Industrial Mathematics, 2017, 11:4, 472-480

Volume 24, No 4, 2017, P. 5-21

UDC 519.85
V. L. Beresnev and A. A. Melnikov
An upper bound for the competitive location and capacity choice problem with multiple demand scenarios

A new mathematical model is considered related to competitive location problems where two competing parties, the Leader and the Follower, successively open their facilities and try to win customers. In the model, we consider a situation of several alternative demand scenarios which differ by the composition of customers and their preferences. We assume that the costs of opening a facility depend on its capacity; therefore, the Leader, making decisions on the placement of facilities, must determine their capacities taking into account all possible demand scenarios and the response of the Follower. For the bilevel model suggested, a problem of finding an optimistic optimal solution is formulated. We show that this problem can be represented as a problem of maximizing a pseudo-Boolean function with the number of variables equal to the number of possible locations of the Leader’s facilities. We propose a novel system of estimating the subsets that allows us to supplement the estimating problems, used to calculate the upper bounds for the constructed pseudo-Boolean function, with additional constraints which improve the upper bounds.
Bibliogr. 13.

Keywords: competitive facility location, bilevel programming, upper bound.

DOI: 10.17377/daio.2017.24.578

Vladimir L. Beresnev 1,2
Andrey A. Melnikov 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: beresnev@math.nsc.ru, melnikov@math.nsc.ru

Received 2 May 2017


[1] V. L. Beresnev, On the competitive facility location problem with a free choice of suppliers, Avtom. Telemekh., No. 4, 94–105, 2014 [Russian]. Translated in Autom. Remote Control, 75, No. 4, 668–676, 2014.

[2] V. L. Beresnev and A. A. Mel’nikov, A capacitated competitive facility location problem, Diskretn. Anal. Issled. Oper., 23, No. 1, 35–50, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 1, 61–68, 2016.

[3] A. A. Mel’nikov, Randomized local search for the discrete competitive facility location problem, Avtom. Telemekh., No. 4, 134–152, 2014 [Russian]. Translated in Autom. Remote Control, 75, No. 4, 700–714, 2014.

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

[5] V. L. Beresnev, Branch-and-bound algorithm for a competitive facility location problem, Comput. Oper. Res., 40, No. 8, 2062–2070, 2013.

[6] 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, Pt. B, 334–340, 2014.

[7] S. Dempe, Foundations of Bilevel Programming, Kluwer Acad. Publ., Dordrecht, 2002.

[8] T. Drezner, Z. Drezner, and P. Kalczynski, A leader-follower model for discrete competitive facility location, Comput. Oper. Res., 64, 51–59, 2015.

[9] H. A. Eiselt and G. Laporte, Sequential location problems, Eur. J. Oper. Res., 96, No. 2, 217–231, 1996.

[10] A. Jakubovskis, Strategic facility location, capacity acquisition, and technology choice decisions under demand uncertainty: Robust vs. non-robust optimization approaches, Eur. J. Oper. Res., 260, No. 3, 1095–1104, 2017.

[11] A. Karakitsiou, Modeling Discrete Competitive Facility Location, Springer, Cham, 2015 (SpringerBriefs in Optimization).

[12] H. von Stackelberg, The Theory of the Market Economy, Oxf. Univ. Press, Oxford, 1952.

[13] Y. Zhang, L. V. Snyder, T. K. Ralphs, and Z. Xue, The competitive facility location problem under disruption risks, Transp. Res., Part E, 93, 453–473, 201
 © Sobolev Institute of Mathematics, 2015