Вычисление верхней границы для двухэтапной двухуровневой модели конкурентного размещения

Вычисление верхней границы для двухэтапной двухуровневой модели конкурентного размещения

Береснев В. Л., Мельников А. А.
Дискретный анализ и исследование операций, 29, 3, 7-23 (2022)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2022.29.740

Аннотация:

Рассматривается задача конкурентного размещения предприятий в условиях неопределённости параметров спроса, для которого представлен конечный набор возможных сценариев. Задача формулируется в виде двухуровневой модели, построенной на основе игры Штакельберга и классической модели размещения предприятий. В двухуровневой модели первый игрок (Лидер) имеет две возможности для открытия предприятия. Предполагается, что предприятие Лидера может быть открыто либо до того, как фактический сценарий спроса будет выявлен, либо после. Фиксированные затраты, связанные с открытием предприятия, в первом случае ниже. Таким образом, постоянные затраты могут быть снижены путём принятия заблаговременного решения об открытии предприятий на первом этапе и коррекции его на втором. 

Мы предлагаем процедуру вычисления верхней границы для значения прибыли Лидера в рассматриваемой модели. Подход основан на формировании семейства вспомогательных двухуровневых подзадач. Оптимальные решения подзадач образуют допустимое решение исходной задачи. Верхняя граница вычисляется путём применения процедуры генерации отсечений для усиления релаксаций подзадач. 
Табл. 1, ил. 1, библиогр. 10.

Литература:
  1. Береснев В. Л. О задаче конкурентного размещения предприятий со свободным выбором поставщиков // Автоматика и телемеханика. 2014. № 4. С. 93–106.
     
  2. Ashtiani M. G., Makui A., Ramezanian R. A robust model for a leader-follower competitive facility location problem in a discrete space // Appl. Math. Model. 2013. V. 37, No. 1–2. P. 62–71.
     
  3. Yu W. A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold // PLOS ONE. 2019. V. 14, No. 12, ID e0225693. 16 p.
     
  4. Иванов С. В., Морозова М. В. Стохастическая задача конкурентного размещения предприятий с квантильным критерием // Автоматика и телемеханика. 2016. № 3. С. 109–122.
     
  5. Beresnev V. L., Melnikov A. A. $\epsilon$-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario // EURO J. Comput. Optim. 2020. V. 8, No. 1. P. 33–59.
     
  6. Ivanov S. V., Akmaeva V. N. Two-stage stochastic facility location model with quantile criterion and choosing reliability level // Вестн. ЮУрГУ. Сер. Мат. моделирование и программирование. 2021. Т. 14, № 3. С. 5–17. 
     
  7. Beresnev V. L., Melnikov A. A. Approximation of the competitive facility location problem with MIPs // Comput. Oper. Res. 2019. V. 104. P. 139–148.
     
  8. Moore J. T., Bard J. F. The mixed integer linear bilevel programming problem // Oper. Res. 1990. V. 38, No. 5. P. 911–921.
     
  9. Beresnev V. L. Branch-and-bound algorithm for a competitive facility location problem // Comput. Oper. Res. 2013. V. 40, No. 8. P. 2062–2070.
     
  10. Gurobi optimizer reference manual. Beaverton: Gurobi Optimization, 2021. Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).

Исследование выполнено при финансовой поддержке Российского научного фонда (проект № 21–41–09017).

Береснев Владимир Леонидович
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: beresnev@math.nsc.ru

Мельников Андрей Андреевич
  1. Институт математики им. С. Л. Соболева,
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: melnikov@math.nsc.ru

Статья поступила 16 мая 2022 г. 
После доработки — 18 мая 2022 г. 
Принята к публикации 19 мая 2022 г.

Abstract:

We consider a competitive facility location problem with uncertainty represented by a finite number of possible demand scenarios. The problem is formulated as a bi-level model built on the base of a Stackelberg game and classic facility location model formalizing the players’ decision process. In the bi-level model, the first player (Leader) has two options to open a facility. We assume that a Leader’s facility could be opened either before the actual demand scenario is revealed or after the revelation. The fixed costs associated with the facility opening are lower in the first case. Thus the fixed costs could be reduced by making a preliminary location decision on the first stage and adjusting it on the second. 

We suggest a procedure to compute an upper bound for the Leader’s profit value. The approach is based on using a family of auxiliary bilevel subproblems. Optimal solutions of the subproblems form a feasible solution of the initial problem. The upper bound is computed by applying a cut generation procedure to strengthen high-point relaxations of the subproblems. 
Tab. 1, illustr. 1, bibliogr. 10.

References:
  1. V. L. Beresnev, On the competitive facility location problem with a free choice of suppliers, Avtom. Telemekh., No. 4, 93–106 (2014) [Russian] [Autom. Remote Control 75 (4), 668–676 (2014)].
     
  2. M. G. Ashtiani, A. Makui, and R. Ramezanian, A robust model for a leader-follower competitive facility location problem in a discrete space, Appl. Math. Model. 37 (1–2), 62–71 (2013).
     
  3. W. Yu, A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold, PLOS ONE 14 (12), ID e0225693, 16 p. (2019).
     
  4. S. V. Ivanov and M. V. Morozova, Stochastic problem of competitive location of facilities with quantile criterion, Avtom. Telemekh., No. 3, 109–122 (2016) [Russian] [Autom. Remote Control 77 (3), 451–461 (2016)].
     
  5. V. L. Beresnev and A. A. Melnikov, $\epsilon$-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario, EURO J. Comput. Optim. 8 (1), 33–59 (2020).
     
  6. S. V. Ivanov and V. N. Akmaeva, Two-stage stochastic facility location model with quantile criterion and choosing reliability level, Vestn. YuUrGU, Ser. Mat. Model. Program. 14 (3), 5–17 (2021).
     
  7. V. L. Beresnev and A. A. Melnikov, Approximation of the competitive facility location problem with MIPs, Comput. Oper. Res. 104, 139–148 (2019).
     
  8. J. T. Moore and J. F. Bard, The mixed integer linear bilevel programming problem, Oper. Res. 38 (5), 911–921 (1990).
     
  9. V. L. Beresnev, Branch-and-bound algorithm for a competitive facility location problem, Comput. Oper. Res. 40 (8), 2062–2070 (2013).
     
  10. Gurobi optimizer reference manual (Gurobi Optimization, Beaverton, 2021). Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).