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

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

Драчeв Р. Р., Панин А. А., Плясунов А. В.
Дискретный анализ и исследование операций, 33, 2, 19-45 (2026)
Скачать статью

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

Аннотация:

Рассматривается трёхуровневая задача конкурентного ценообразования. Две компании, производящие однородный продукт, конкурируют за потребительский спрос. На первом уровне компания-лидер, а на втором уровне компания-последователь устанавливают цены на каждом из своих предприятий с целью максимизировать собственный доход. На третьем уровне каждый потребитель выбирает предприятие с наименьшими общими расходами на покупку и транспортировку товара и совершает покупку в том случае, если расходы не превышают его бюджета. Цель игры — найти такие цены лидера, при которых его доход максимален. Известно, что проблема $\Sigma^p_2$ -трудна. Предложены нижние и верхние границы оптимума, и разработаны приближённые алгоритмы решения, основанные на спуске с чередующимися окрестностями. Проведён вычислительный эксперимент с использованием примеров различной размерности и сложности. 

Табл. 7, ил. 2, библиогр. 20.

Литература:
  1. Панин А. А., Плясунов А. В. Задача ценообразования. Часть 1. Точные и приближённые алгоритмы решения // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 5. С. 83–100.
     
  2. Плясунов А. В., Панин А. А. Задача ценообразования. Часть 2. Вычислительная сложность // Дискрет. анализ и исслед. операций. 2013. Т. 19, № 6. С. 56–71.
     
  3. Дементьев В. Т., Шамардин Ю. В. Задача о выборе цен на продукцию при условии обязательного удовлетворения спроса // Дискрет. анализ и исслед. операций. Cер. 2. 2002. Т. 9, № 2. С. 31–40.
     
  4. Lederes Ph. J., Thisse J.-F. Competitive location on network under delivered pricing // Oper. Res. Lett. 1990. V. 9, No. 3. P. 147–154. DOI: 10.1016/0167-6377(90)90012-T.
     
  5. Aboolian R., Berman O., Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // J. Oper. Res. Soc. 2008. V. 59, No. 11. P. 1506–1519. DOI: 10.1057/palgrave.jors. 2602493.
     
  6. Luer-Villagra A., Marianov V. A competitive hub location and pricing problem // Eur. J. Oper. Res. 2013. V. 231, No. 3. P. 734–744. DOI: 10.1016/j.ejor.2013.06.006.
     
  7. Serra D., ReVelle Ch. Competitive locations and pricing on networks // Geogr. Anal. 1999. V. 31, No. 2. P. 109–129. DOI: 10.1111/gean.1999.31.1.109.
     
  8. Aboolian R., Berman O., Krass D. Competitive facility location model with concave demand // Eur. J. Oper. Res. 2007. V. 181, No. 2. P. 598–619. DOI: 10.1016/j.ejor.2005.10.075.
     
  9. Bouhtou M., Grigoriev A., van Hoesel S., van der Kraaij A. F., Spieksma F. C. R., Uetz M. Pricing bridges to cross a river // Nav. Res. Logist. 2007. V. 54, No. 4. P. 411–420. DOI: 10.1002/nav.20216.
     
  10. Diakova Z. S., Kochetov Yu. A. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. V. 39, No. 4. P. 29–34. DOI: 10.1016/j.endm.2012.10.005.
     
  11. Ahmadi-Javid A., Amire E., Meskar M. A profit-maximization locationrouting-pricing problem: A branch-and-price algorithm // Eur. J. Oper. Res. 2018. V. 271, No. 3. P. 866-881. DOI: 10.1016/j.ejor.2018.02.020.
     
  12. Lin Y. H., Tian Q. Facility location and pricing problem: Discretized mill price and exact algorithms // Eur. J. Oper. Res. 2023. V. 308, No. 2. P. 568–580. DOI: 10.1016/j.ejor.2022.11.052.
     
  13. Hansen P., Hanjoul P., Thisse J.-F., Peeters D. Uncapacitated plant location under alternative spatial price policies // Manag. Sci. 1990. V. 36, No. 1. P. 41–57. DOI: 10.1287/mnsc.36.1.41.
     
  14. Garcia-Herreros P., Florensa C., Pratik M. Capacity planning with competitive decision-makers: Trilevel milp formulation, degeneracy and solution approaches // Eur. J. Oper. Res. 2017. V. 262, No. 2. P. 449–463. DOI: 10.1016/j.ejor.2017.04.013.
     
  15. Plyasunov A. V., Panin A. A. The multilevel facility location and pricing problems: the computational complexity and the stability analysis // Optim. Lett. 2022. V. 17, No. 6. P. 1295–1315. DOI: 10.1007/s11590-022-01924-3. 
     
  16. Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. C. 36–54. DOI: 10.17377/daio.2015.22.480.
     
  17. Sinnl M., Fischetti M., Ljubić I., Monaci M. Intersection cuts for bilevel optimization // Integer programming and combinatorial optimization. Proc. 18th Int. Conf. (Liège, Belgium, June 1–3, 2016). Cham: Springer, 2016. P. 77–88. (Lect. Notes Comput. Sci.; V. 9682.) DOI: 10.1007/ 978-3-319-33461-5_7.
     
  18. Hansen P. N., Mladenović N. Variable neighborhood search // Eur. J. Oper. Res. 2001. V. 130, No. 3. P. 449–467. DOI: 10.1016/S0305-0548(97) 00031-2.
     
  19. Mladenović N., Hansen P. First vs. best improvement: An empirical study // Discrete Appl. Math. 2006. V. 154, No. 5. P. 802–817. DOI: 10.1016/j.dam.2005.05.020.
     
  20. Задача размещения и ценообразования // Дискретные задачи размещения. Новосибирск: ИМ СО РАН, 2025. URL: https://old.math.nsc.ru/AP/benchmarks/Pricing/price.html (accessed: 20.10.2025).

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2026–0021). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

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

E-mail: rrdrachev@gmail.com 

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

E-mail: aapanin1988@gmail.com 

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

E-mail: apljas@math.nsc.ru 

Статья поступила 24 декабря 2025 г.
После доработки — 12 февраля 2026 г.
Принята к публикации 23 марта 2026 г.

Abstract:

This article considers a three-level competitive pricing problem. Two companies producing a homogeneous product compete for consumer demand. At the first level, the leader and the follower set prices at each of their facilities to maximize their own revenue. At the third level, each client chooses the facility with the lowest total purchasing and transportation costs and makes a purchase if these costs do not exceed their budget. The goal of the game is to find the leader’s prices that maximize their revenue. The problem is known to be $\Sigma^p_2$-hard. Lower and upper bounds for the optimum are proposed, and approximate solution algorithms based on descent with alternating neighborhoods are developed. A computational experiment is conducted using examples of varying dimensions and complexity. 

Tab. 7, illustr. 2, bibliogr. 20.

References:
  1. A. V. Plyasunov and A. A. Panin, The pricing problem. Part I: Exact and approximate algorithms, Diskretn. Anal. Issled. Oper. 19 (5), 83–100 (2012) [Russian] [J. Appl. Ind. Math. 7 (2), 241–251 (2013), DOI: 10.1134/ S1990478913020142].
     
  2. A. V. Plyasunov and A. A. Panin, The pricing problem. Part II: Computational complexity, Diskretn. Anal. Issled. Oper. 19 (6), 56–71 (2013) [Russian] [J. Appl. Ind. Math. 7 (3), 420–430 (2013), DOI: 10.1134/S1990478913030150].
     
  3. V. T. Dementyev and Yu. V. Shamardin, The problem of price selection for production under the condition of obligatory satisfaction of demand, Diskretn. Anal. Issled. Oper., Ser. 2, 9 (2), 31–40 (2002) [Russian].
     
  4. Ph. J. Lederes and J.-F. Thisse, Competitive location on network under delivered pricing, Oper. Res. Lett. 9 (3), 147–154 (1990), DOI: 10.1016/ 0167-6377(90)90012-T.
     
  5. R. Aboolian, O. Berman, and D. Krass, Optimizing pricing and location decisions for competitive service facilities charging uniform price, J. Oper. Res. Soc. 59 (11), 1506–1519 (2008), DOI: 10.1057/palgrave.jors.2602493.
     
  6. A. Luer-Villagra, and V. Marianov, A competitive hub location and pricing problem, Eur. J. Oper. Res. 231 (3), 734–744 (2013), DOI: 10.1016/j. ejor.2013.06.006.
     
  7. D. Serra and Ch. ReVelle, Competitive locations and pricing on networks, Geogr. Anal. 31 (2), 109–129 (1999), DOI: 10.1111/gean.1999.31.1.109.
     
  8. R. Aboolian, O. Berman, and D. Krass, Competitive facility location model with concave demand, Eur. J. Oper. Res. 181 (2), 598–619 (2007), DOI: 10.1016/j.ejor.2005.10.075.
     
  9. M. Bouhtou, A. Grigoriev, S. van Hoesel, A. F. van der Kraaij, F. C. R. Spieksma, and M. Uetz, Pricing bridges to cross a river, Nav. Res. Logist. 54 (4), 411–420 (2007), DOI: 10.1002/nav.20216.
     
  10. Z. S. Diakova and Yu. A. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron. Notes Discrete Math. 39 (4), 29–34 (2012), DOI: 10.1016/j.endm.2012.10.005.
     
  11. A. Ahmadi-Javid, E. Amire, and M. Meskar, A profit-maximization location-routing-pricing problem: A branch-and-price algorithm, Eur. J. Oper. Res. 271 (3), 866-881 (2018), DOI: 10.1016/j.ejor.2018.02.020.
     
  12. Y. H. Lin and Q. Tian, Facility location and pricing problem: Discretized mill price and exact algorithms, Eur. J. Oper. Res. 308 (2), 568–580 (2023), DOI: 10.1016/j.ejor.2022.11.052.
     
  13. P. Hansen, P. Hanjoul, J.-F. Thisse, and D. Peeters, Uncapacitated plant location under alternative spatial price policies, Manag. Sci. 36 (1), 41–57 (1990), DOI: 10.1287/mnsc.36.1.41.
     
  14. P. Garcia-Herreros, C. Florensa, and M. Pratik, Capacity planning with competitive decision-makers: Trilevel milp formulation, degeneracy and solution approaches, Eur. J. Oper. Res. 262 (2), 449–463 (2017), DOI: 10.1016/j. ejor.2017.04.013.
     
  15. A. V. Plyasunov and A. A. Panin, The multilevel facility location and pricing problems: the computational complexity and the stability analysis, Optim. Lett. 17 (6), 1295–1315 (2022), DOI: 10.1007/s11590-022-01924-3. 
     
  16. Yu. A. Kochetov, A. A. Panin, and A. V. Plyasunov, Comparison of metaheuristics for the bilevel facility location and mill pricing problem, Diskretn. Anal. Issled. Oper. 22 (3), 36–54 (2015), DOI: 10.17377/daio. 2015.22.480 [Russian] [J. Appl. Ind. Math. 9 (3), 392–401 (2015), DOI: 10.1134/S1990478915030102].
     
  17. M. Sinnl, M. Fischetti, I. Ljubić, and M. Monaci, Intersection cuts for bilevel optimization, in Integer Programming and Combinatorial Optimization, Proc. 18th Int. Conf. (Liège, Belgium, June 1–3, 2016) (Springer, Cham, 2016), pp. 77–88 (Lect. Notes Comput. Sci., Vol. 9682.) DOI: 10.1007/ 978-3-319-33461-5_7
     
  18. P. N. Hansen and N. Mladenović, Variable neighborhood search, Eur. J. Oper. Res. 130 (3), 449–467 (2001), DOI: 10.1016/S0305-0548(97) 00031-2.
     
  19. N. Mladenović and P. Hansen, First vs. best improvement: An empirical study, Discrete Appl. Math. 154 (5), 802–817 (2006), DOI: 10.1016/j.dam. 2005.05.020.
     
  20. Facility location and pricing problem, in Discrete Location Problems (IM SO RAN, Novosibirsk, 2025) [Russian], URL: https://old.math.nsc.ru/AP/benchmarks/Pricing/price.html (accessed: 20.10.2025).