Дополнительные ограничения для динамической задачи конкурентного размещения

Дополнительные ограничения для динамической задачи конкурентного размещения

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

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

Аннотация:

Рассматривается математическая модель конкурентного размещения объектов (предприятий), в которой соперничающие стороны (Лидер и Последователь) принимают решения с учётом изменяющегося множества потребителей на рассматриваемом горизонте планирования, состоящего из заданного числа периодов времени. При этом предполагается, что Лидер принимает решение об открытии своих объектов в начале горизонта планирования, а Последователь имеет возможность обновлять своё решение на каждом из периодов времени. В работе исследуется возможность применения для рассматриваемой динамической задачи конкурентного размещения способа построения наилучшего решения, базирующегося на использовании HP-релаксации исследуемой двухуровневой модели. Основным элементом этого подхода является построение дополнительных ограничений для усиления HP-релаксации исследуемой двухуровневой задачи и вычисления верхних границ значений целевой функции этой задачи. В работе предлагаются семейства дополнительных ограничений для усиления HP-релаксации рассматриваемой динамической задачи, позволяющие вычислять нетривиальные верхние границы. 
Библиогр. 13.

Литература:
  1. Aras N., Küçükaydın H. Bilevel models on the competitive facility location problem // Spatial interaction models: Facility location using game theory. Cham: Springer, 2017. P. 1–19. 
     
  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. Drezner T. A review of competitive facility location in the plane // Logist. Res. 2014. V. 7, No. 1. Paper ID 114. 12 p. 
     
  4. Karakitsiou A. Modeling discrete competitive facility location. Cham: Springer, 2015. 54 p. 
     
  5. Kress D., Pesch E. Sequential competitive location on networks // Eur. J. Oper. Res. 2012. V. 217, No. 3. P. 483–499. 
     
  6. Mishra M., Singh S. P., Gupta M. P. Location of competitive facilities: A comprehensive review and future research agenda // Benchmarking. 2022. V. 30, No. 4. P. 1171–1230. 
     
  7. Current J., Ratick S., ReVelle C. Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach // Eur. J. Oper. Res. 1998. V. 110, No. 3. P. 597–609. 
     
  8. Eiselt H. A., Marianov V., Drezner T. Competitive location models // Location science. Cham: Springer, 2019. P. 391–429. 
     
  9. Castro J., Nasini S., Saldanha-da-Gama F. A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method // Math. Program. 2017. V. 163, No. 1. P. 411–444.  
     
  10. Береснев В. Л. О задаче конкурентного размещения предприятий со свободным выбором поставщиков // Автоматика и телемеханика. 2014. № 4. С. 94–105. 
     
  11. Beresnev V. L., Melnikov A. A. Approximation of the competitive facility location problem with MIPs // Comput. Oper. Res. 2019. V. 104. P. 139–148. 
     
  12. Santos-Peñate D. R., Suárez-Vega R., Dorta-González P. The leader-follower location model // Netw. Spat. Econ. 2007. V. 7, No. 1. P. 45–61.
     
  13. Dempe S. Bilevel optimization: Theory, algorithms, applications and a bibliography // Bilevel optimization: Advances and next challenges. Cham: Springer, 2020. P. 581–672.

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

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

E-mail: beresnev@math.nsc.ru

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

E-mail: melnikov@math.nsc.ru

Статья поступила 17 мая 2023 г. 
После доработки — 25 мая 2023 г. 
Принята к публикации 29 мая 2023 г.

Abstract:

We consider a competitive facility location model, where competing parties (Leader and Follower) make decisions considering changes of the set of customers happening during the planing horizon, having known number of time periods. It is supposed that the Leader makes a decision on opening their facilities at the beginning of the planning horizon, while the Follower can revise their decision in each time period. In the present paper, we study perspectives to apply a method for finding the best solution which is based on using HP-relaxation of the bi-level problem considered. The key element of this method is construction of additional inequalities strengthening the HP-relaxation and computation of upper bounds for the objective function of the problem. In the work, new families of additional constraints are proposed to strengthen the HP-relaxation, that allow us to compute non-trivial upper bounds. 
Bibliogr. 13.

References:
  1. N. Aras and H. Küçükaydın, Bilevel models on the competitive facility location problem, in Spatial Interaction Models: Facility Location Using Game Theory (Springer, Cham, 2017), pp. 1–19.
     
  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), pp. 62–71 (2013).
     
  3. T. Drezner, A review of competitive facility location in the plane, Logist. Res. 7 (1), ID 114, 12 p. (2014).
     
  4. A. Karakitsiou, Modeling Discrete Competitive Facility Location (Springer, Cham, 2015).
     
  5. D. Kress and E. Pesch, Sequential competitive location on networks, Eur. J. Oper. Res. 217 (3), 483–499 (2012). 
     
  6. M. Mishra, S. P. Singh, and M. P. Gupta, Location of competitive facilities: A comprehensive review and future research agenda, Benchmarking 30 (4), 1171-1230 (2022).
     
  7. J. Current, S. Ratick, and C. ReVelle, Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach, Eur. J. Oper. Res. 110 (3), 597–609 (1998).
     
  8. H. A. Eiselt, V. Marianov, and T. Drezner, Competitive location models, in Location Science (Springer, Cham, 2019), pp. 391–429.
     
  9. J. Castro, S. Nasini, and F. Saldanha-da-Gama, A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method, Math. Program. 163 (1), 411–444 (2017).
     
  10.  V. L. Beresnev, On the competitive facility location problem with a free choice of suppliers, Avtom. Telemekh., No. 4, 94–105 (2014) [Russian] [Autom. Remote Control 75 (4), 668–676 (1997)].
     
  11. V. L. Beresnev and A. A. Melnikov, Approximation of the competitive facility location problem with MIPs, Comput. Oper. Res. 104, 139–148 (2019).
     
  12. D. R. Santos-Peñate, R. Suárez-Vega, and P. Dorta-González, The leader follower location model, Netw. Spat. Econ. 7 (1), 45–61 (2007).
     
  13. S. Dempe, Bilevel optimization: Theory, algorithms, applications and a bibliography, in Bilevel Optimization: Advances and Next Challenges (Springer, Cham, 2020), pp. 581–672.