Алгоритм ветвей, границ и отсечений для неявной динамической задачи конкурентного размещения

Алгоритм ветвей, границ и отсечений для неявной динамической задачи конкурентного размещения

Береснев В. Л., Мельников А. А.
Дискретный анализ и исследование операций, 31, 4, 5-26 (2024)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2024.31.814

Аннотация:

Рассматривается динамическая задача конкурентного размещения, моделирующая взаимодействие двух соперничающих сторон (Лидера и Последователя), размещающих свои объекты на рассматриваемом горизонте планирования, состоящего из некоторого числа периодов времени. Предполагается, что Лидер открывает свои объекты в начале горизонта планирования и не изменяет это решение внутри горизонта планирования. При этом Последователь может корректировать своё решение в каждом периоде горизонта планирования. Предлагается алгоритм поиска наилучшего решения, построенный на основе вычислительной схемы ветвей и границ. Для вычисления верхних границ используется специальная релаксация исходной двухуровневой задачи, усиленная дополнительными ограничениями. Предлагаются процедуры построения таких ограничений, в которых используются вспомогательные оптимизационные задачи для получения наиболее сильных отсечений. На примере задачи динамического конкурентного размещения на сети с тремя вершинами демонстрируются возможности модели учитывать информацию об изменениях параметров с течением времени. Реализация алгоритма ветвей и границ демонстрирует значительный эффект от использования отсечений, предложенных специально для динамических моделей: верхняя граница вычисляется более точно и сокращается число вершин дерева ветвления. 
Ил. 2, библиогр. 8.

Литература:
  1. Stackelberg H. The theory of the market economy. Oxford: Oxford Univ. Press, 1952. 289 p.
     
  2. 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. DOI: 10.1108/BIJ-11-2021-0638.
     
  3. Eiselt H. A., Drezner Z. Competitive location models: A review // Eur. J. Oper. Res. 2024. V. 316, No. 1. P. 5–18. DOI: 10.1016/j.ejor.2023.10.030.
     
  4. Santos-Penate D. R., Suarez-Vega R., Dorta-Gonzalez P. The leader — follower location model // Netw. Spat. Econ. 2007. V. 7. P. 45–61. DOI: 10. 1007/s11067-006-9007-2.
     
  5. Береснев В. Л., Мельников А. А. Дополнительные ограничения для динамической задачи конкурентного размещения // Дискрет. анализ и исслед. операций. 2023. Т. 30, № 3. С. 43–56. DOI: 10.33048/daio.2023.30.774.
     
  6. 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. DOI: 10.1016/S0377-2217(97)00303-2.
     
  7. Dempe S. Bilevel optimization: Theory, algorithms, applications and a bibliography // Bilevel optimization: Advances and next challenges. Cham: Springer, 2020. P. 581–672. DOI: 10.1007/978-3-030-52119-6_20.
     
  8. Beresnev V. L., Melnikov A. A. Approximation of the competitive facility location problem with MIPs // Comput. Oper. Res. 2019. V. 104. P. 139–148. DOI: 10.1016/j.cor.2018.12.010.

Исследование выполнено при финансовой поддержке Российского научного фонда (проект № 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

Статья поступила 18 октября 2024 г
После доработки — 25 октября 2024 г.
Принята к публикации 1 ноября 2024 г.

Abstract:

We consider a dynamic competitive facility location problem modeling an interaction of two competing parties (Leader and Follower) who place their facilities within a planning horizon split into several time periods. The Leader is assumed to open his/her facilities at the beginning of the planning horizon and does not change his/her decision later, while the Follower can modify his/her choice within each time period. We propose an algorithm that computes the best Leader’s decision and is built on the base of the branch-and-bound computational scheme. To compute upper bounds, a special relaxation of the initial bilevel problem strengthened with additional constraints (cuts) is used. The paper describes the construction of these constraints while utilizing auxiliary optimization problems; this provides the strongest cuts. On an instance of a dynamic competitive facility location on a network with three vertices, we demonstrate that the model is capable to take into account information regarding the changes of problem’s parameters along the time period. An implementation of the branch-and-bound algorithm shows a significant benefit from using the cuts specially designed for dynamic competitive models: it improves the upper bound’s quality and reduces the number of nodes in the branching tree. 
Illustr. 2, bibliogr. 8.

References:
  1. H. Stackelberg, The Theory of the Market Economy (Oxford Univ. Press, Oxford, 1952).
     
  2. 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), DOI: 10.1108/BIJ-11-2021-0638.
     
  3. H. A. Eiselt and Z. Drezner, Competitive location models: A review, Eur. J. Oper. Res. 316 (1), 5–18 (2024), DOI: 10.1016/j.ejor.2023.10.030.
     
  4. D. R. Santos-Penate, R. Suarez-Vega, and P. Dorta-Gonzalez, The leader — follower location model, Netw. Spat. Econ. 7, 45–61 (2007), DOI: 10.1007/ s11067-006-9007-2.
     
  5. V. L. Beresnev and A. A. Melnikov, Additional constraints for dynamic competitive facility location problem, Diskretn. Anal. Issled. Oper. 30 (3), 43–56 (2023), DOI: 10.33048/daio.2023.30.774 [Russian] [J. Appl. Ind. Math. 17 (3), 483–490 (2023), DOI: 10.1134/S199047892303002X].
     
  6. 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), DOI: 10.1016/S0377-2217(97)00303-2.
     
  7. S. Dempe, Bilevel optimization: Theory, algorithms, applications and a bibliography, in Bilevel Optimization: Advances and Next Challenges (Springer, Cham, 2020), pp. 581–672, DOI: 10.1007/978-3-030-52119-6_20.
     
  8. V. L. Beresnev and A. A. Melnikov, Approximation of the competitive facility location problem with MIPs, Comput. Oper. Res. 104, 139–148 (2019), DOI: 10.1016/j.cor.2018.12.010.