Спуск с чередующимися окрестностями для поиска радиуса пороговой устойчивости

Спуск с чередующимися окрестностями для поиска радиуса пороговой устойчивости в задаче размещения и дискриминационного ценообразования

Панин А. А., Пискеева Д. А., Плясунов А. В.
Дискретный анализ и исследование операций, 31, 4, 116-133 (2024)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2024.31.801

Аннотация:

Рассматривается новая проблема пороговой устойчивости при размещении предприятий и дискриминационном ценообразовании. В задаче размещения и ценообразования производитель принимает решение об открытии предприятий и назначении цен для каждого потребителя на каждом предприятии. Дискриминация в ценообразовании приводит к ситуации, когда каждый потребитель вынужден тратить максимум своих финансовых ресурсов, тем самым гарантируя максимальный доход производителю. В проблеме пороговой устойчивости финансовые ресурсы или бюджет каждого потребителя является параметром с известным ожидаемым значением. Цель — максимизировать отклонение параметров от ожидаемого значения при условии, что доход производителя не меньше заданного порога. 

Для решения проблемы пороговой устойчивости предлагается алгоритм, основанный на спуске с чередующимися окрестностями (VND). Численное исследование алгоритма проводится на известных примерах и случайно сгенерированных. Исследуются различные способы построения стартового размещения и различные критерии сравнения векторов размещения предприятий. 
Табл. 3, ил. 6, библиогр. 12.

Литература:
  1. Ben-Tal A., Nemirovski A. Robust optimization — Methodology and applications // Math. Program. Ser. B. 2002. V. 92, No. 3. P. 453–480.
     
  2. Carrizosa E., Nickel S. Robust facility location // Math. Methods Oper. Res. 2003. V. 58, No. 2. P. 331–349.
     
  3. Carrizosa E., Ushakov A., Vasilyev I. Threshold robustness in discrete facility location problems: A bi-objective approach // Optim. Lett. 2015. V. 9, No. 7. P. 1297–1314.
     
  4. Hanjoul P., Hansen P., Peeters D., Thisse J.-F. Uncapacitated plant location under alternative spatial price policies // Manage. Sci. 1990. V. 36, No. 1. P. 41–57. DOI: 10.1287/mnsc.36.1.41.
     
  5. Panin A. A., Plyasunov A. V. The multilevel facility location and pricing problems: The computational complexity and the stability analysis // Optim. Lett. 2023. V. 17, No. 6. P. 1295–1315. DOI: 10.1007/s11590-022-01924-3.
     
  6. Vodyan M. E., Panin A. A., Plyasunov A. V. Metaheuristics for finding the stability radius in the bilevel facility location and uniform pricing problem // Proc. 19th Int. Asian School-Seminar Optimization Problems of Complex Systems (Novosibirsk, Russia, Aug. 14–22, 2023). Piscataway: IEEE, 2023. P. 130–135. DOI: 10.1109/OPCS59592.2023.10275325.
     
  7. Panin A. A., Plyasunov A. V. Stability analysis for pricing // Mathematical optimization theory and operations research. Rev. Sel. Pap. 19th Int. Conf. (Novosibirsk, Russia, July 6–10, 2020). Cham: Springer, 2020. P. 57–69. (Commun. Comput. Inf. Sci.; V. 1275). DOI: 10.1007/978-3-030-58657-7_7.
     
  8. Diakova Z. S., Kochetov Yu. A. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. V. 39. P. 29–34. DOI: 10.1016/j.endm.2012.10.005.
     
  9. Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. С. 36–54.
     
  10. Кочетов Ю. А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет. анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 1. С. 11–43.
     
  11. Плясунов А. В., Панин А. А. Задача ценообразования. Часть 2. Вычислительная сложность // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 6. С. 56–71.
     
  12. Береснев В. Л., Кочетов Ю. А., Пащенко М. Г. [и др.]. Дискретные задачи размещения. Библиотека тестовых задач. Новосибирск: ИМ СО РАН, 2021. URL: math.nsc.ru/AP/benchmarks (дата обращения: 1.11.2024).

Исследование выполнено за счёт Российского научного фонда (проект № 23– 21–00424). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

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

E-mail: aapanin1988@gmail.com

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

E-mail: d.piskeeva@g.nsu.ru

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

E-mail: apljas@math.nsc.ru

Статья поступила 8 мая 2024 г.
После доработки — 15 мая 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

A new threshold stability problem in the context of facility location and discriminatory pricing is considered. In the statement of facility location and pricing problem, the company decides to open facilities and assign prices to each customer at each facility. The implementation of discriminatory pricing leads to a scenario where each customer is compelled to expend the maximum amount of their available financial resources, thereby ensuring the maximum revenue for the company. In the threshold stability problem, the available financial resources or budget of each consumer is a parameter with a known expected value. The objective is to maximize the deviation of the parameters from the expected value, provided that the company’s income remains above a given threshold. 

An algorithm based on variable neighborhood descent (VND) is proposed to solve the threshold stability problem. Numerical investigation of the algorithm is carried out on known instances and randomly generated ones. Various ways of constructing the starting facility location and different criteria for comparing the location vectors are analyzed. 
Tab. 3, illustr. 6, bibliogr. 12.

References:
  1. A. Ben-Tal and A. Nemirovski, Robust optimization — Methodology and applications, Math. Program., Ser. B, 92 (3), 453–480 (2002).
     
  2. E. Carrizosa and S. Nickel, Robust facility location, Math. Methods Oper. Res. 58 (2), 331–349 (2003).
     
  3. E. Carrizosa, A. Ushakov, and I. Vasilyev, Threshold robustness in discrete facility location problems: A bi-objective approach, Optim. Lett. 9 (7), 1297–1314 (2015).
     
  4. P. Hanjoul, P. Hansen, D. Peeters, and J.-F. Thisse, Uncapacitated plant location under alternative spatial price policies, Manage. Sci. 36 (1), 41–57 (1990), DOI: 10.1287/mnsc.36.1.41.
     
  5. A. A. Panin and A. V. Plyasunov, The multilevel facility location and pricing problems: The computational complexity and the stability analysis, Optim. Lett. 17 (6), 1295–1315 (2023), DOI: 10.1007/s11590-022-01924-3. 
     
  6. M. E. Vodyan, A. A. Panin, and A. V. Plyasunov, Metaheuristics for finding the stability radius in the bilevel facility location and uniform pricing problem, in Proc. 19th Int. Asian School-Seminar Optimization Problems of Complex Systems, Novosibirsk, Russia, Aug. 14–22, 2023 (IEEE, Piscataway, 2023), pp. 130–135, DOI: 10.1109/OPCS59592.2023.10275325.
     
  7. A. A. Panin and A. V. Plyasunov, Stability analysis for pricing, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 19th Int. Conf., Novosibirsk, Russia, July 6–10, 2020) (Springer, Cham, 2020), pp. 57–69 (Commun. Comput. Inf. Sci., Vol. 1275), DOI: 10.1007/978-3-030-58657-7.
     
  8. Z. S. Diakova and Yu. A. Kochetov, A double VNS heuristic for the facility location and pricing problem, Electron. Notes Discrete Math. 39, 29–34 (2012), DOI: 10.1016/j.endm.2012.10.005.
     
  9. 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) [Russian] [J. Appl. Ind. Math. 9 (3), 392–401 (2015)].
     
  10. Yu. A. Kochetov, N. Mladenović, and P. Hansen, Local search with alternating neighborhoods, Diskretn. Anal. Issled. Oper., Ser. 2, 10 (1), 11–43 (2003) [Russian].
     
  11. A. V. Plyasunov and A. A. Panin, The pricing problem. Part II: Computational complexity, Diskretn. Anal. Issled. Oper. 19 (6), 56–71 (2012) [Russian] [J. Appl. Ind. Math. 7 (3), 420–430 (2013), DOI: 10.1134/ S1990478913030150].
     
  12. V. L. Beresnev, Yu. A. Kochetov, M. G. Pashchenko, [et al.]. Discrete Location Problems. Benchmark Library (Inst. Mat. SO RAN, Novosibirsk, 2021), URL: math.nsc.ru/AP/benchmarks/english.html (accessed: Nov. 1, 2024).