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

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

Водян М. Е., Панин А. А., Плясунов А. В.
Дискретный анализ и исследование операций, 32, 3, 43-70 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.821

Аннотация:

Исследуется пороговая устойчивость задачи с медианным размещением предприятий и фабричным ценообразованием. Задача пороговой устойчивости имеет следующие отличия от исходной двухуровневой постановки: в задаче верхнего уровня максимизируется отклонение бюджетов потребителей от ожидаемых значений при условии, что доход производителя не меньше заданного порога. Главное отличие исследуемой постановки от задач, чья пороговая устойчивость изучалась ранее, заключается в том, что при фиксированном размещении предприятий задача фабричного ценообразования NP-трудна в сильном смысле. 

Для решения задачи пороговой устойчивости предлагается алгоритм на основе спуска с чередующимися окрестностями (VND). Численное исследование алгоритма проводится на известных примерах и случайно сгенерированных данных. Эксперимент показал, что идея итеративного вычитания радиуса пороговой устойчивости из бюджетов потребителей, впервые реализованная в данной работе, сильно снижает время работы алгоритма. На примерах, для которых был найден оптимум, алгоритм ошибся в среднем на 0,63%. На всех примерах алгоритм находит решение в среднем на 2,97% лучше, чем решатель Gurobi. 

Табл. 4, ил. 2, библиогр. 33.

Литература:
  1. Panin A. A., Plyasunov A. V. Stability analysis for pricing // Mathematical optimization theory and operations research. Rev. Sel. Pap. 19th Int. Conf. MOTOR 2020 (Novosibirsk, Russia, July 6–10, 2020). Cham: Springer, 2020. P. 57–69. (Commun. Comput. Inf. Sci.; V. 1275).
     
  2. 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.
     
  3. 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.
     
  4. Водян М. Е., Панин А. А., Плясунов А. В. Исследование пороговой устойчивости двухуровневой задачи размещения производства и дискриминационного ценообразования // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 3. С. 79–104.
     
  5. Dyer M., Stougie L. Computational complexity of stochastic programming problems // Math. Program. Ser. A. 2006. V. 106, No. 3. P. 423–432. DOI: 10.1007/s10107-005-0597-0.
     
  6. Кибзун А. И., Кан Ю. С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009. 372 с.
     
  7. Ben-Tal A., Nemirovski A. Robust optimization — Methodology and applications // Math. Program. Ser. B. 2002. V. 92, No. 3. P. 453–480. DOI: 10.1007/s101070100286.
     
  8. Snyder L. V. Facility location under uncertainty: A review // IIE Trans. 2006. V. 38. P. 537–554. DOI: 10.1080/07408170500216480.
     
  9. Greenberg H. J. An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization // Advances in computational and stochastic optimization, logic programming, and heuristic search. New York: Springer, 1998. P. 97–147.
     
  10. Correia I., da Gama F. S. Facility location under uncertainty // Location science. Cham: Springer, 2015. P. 177–203.
     
  11. Ben-Tal A., Nemirovski A. Robust solutions of uncertain linear programs // Oper. Res. Lett. 1999. V. 25, No. 1. P. 1–13.
     
  12. Yu G., Yang J. On the shortest path problem // Comput. Oper. Res. 1988. V. 25, No. 6. P. 457–68.
     
  13. Kouvelis P., Yu G. Robust discrete optimization and its applications. Dordrecht: Kluwer Acad. Publ., 1997. 358 p. 
     
  14. Averbakh I., Lebedev V. Interval data minmax regret network optimization problems // Discrete Appl. Math. 2004. V. 138. P. 289–301.
     
  15. Aissi H., Bazgan C., Vanderpooten D. Complexity of the min-max and min-max regret assignment problems // Oper. Res. Lett. 2005. V. 33, No. 6. P. 634–640.
     
  16. Carrizosa E., Nickel S. Robust facility location // Math. Methods Oper. Res. 2003. V. 58, No. 2. P. 331–349.
     
  17. 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.
     
  18. Леонтьев В. К. Устойчивость задачи коммивояжера // Журн. вычисл. математики и мат. физики. 1975. Т. 15, № 5. С. 1298–1309.
     
  19. Rossi A., Gurevsky E., Battaia O., Dolgui A. Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations // Discrete Appl. Math. 2016. V. 208. P. 123–136.
     
  20. Gurevsky E., Rasamimanana A., Pirogov A., Dolgui A., Rossi A. Stability factor for robust balancing of simple assembly lines under uncertainty // Discrete Appl. Math. 2022. V. 318. P. 113–132.
     
  21. Pirogov A., Gurevsky E., Rossi A., Dolgui A. Robust balancing of transfer lines with blocks of uncertain parallel tasks under fixed cycle time and space restrictions // Eur. J. Oper. Res. 2021. V. 290. P. 946–955.
     
  22. Sotskov Yu. N. Assembly and production line designing, balancing and scheduling with inaccurate data: A survey and perspectives // Algorithms. 2023. V. 16, No. 2. Article ID 100. 43 p.
     
  23. Леонтьев В. К., Гордеев Э. Н. Качественное исследование траекторных задач // Кибернетика. 1986. № 5. С. 82–89.
     
  24. Sotskov Yu. N., Leontiev V. K., Gordeev E. N. Some concepts of stability analysis in combinatorial optimization // Discrete Appl. Math. 1995. V. 58, No. 2. P. 169–190.
     
  25. Кузьмин К. Г. Единый подход к нахождению радиусов устойчивости в многокритериальной задаче о максимальном разрезе графа // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 30–51.
     
  26. Dempe S., Zemkoho A. Bilevel optimization. Advances and next challenges. Cham: Springer, 2020. 672 p. (Springer Optim. Its Appl.; V. 161). DOI: 10. 1007/978-3-030-52119-6.
     
  27. Talbi E.-G. Metaheuristics: From design to implementation. Berlin: Wiley, 2009. 624 p.
     
  28. Mladenovic N., Hansen P. Variable neighbourhood search // Comput. Oper. Res. 1997. V. 24. P. 1097–1100.
     
  29. Кочетов Ю. А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет. анализ и исслед. операций. 2003. Т. 10, № 1. С. 11–43.
     
  30. 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.
     
  31. Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. С. 36–54.
     
  32. 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.
     
  33. Панин А. А., Пащенко М. Г., Плясунов А. В. Двухуровневые модели конкурентного размещения производства и ценообразования // Автоматика и телемеханика. 2014. № 4. С. 153–169.

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

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

E-mail: m.vodyan@g.nsu.ru

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

E-mail: aapanin1988@gmail.com 

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

E-mail: apljas@math.nsc.ru 

Статья поступила 29 ноября 2024 г.
После доработки — 2 февраля 2025 г.
Принята к публикации 22 июня 2025 г.

Abstract:

We study the threshold stability of the problem with the median location of facilities and mill pricing. The problem of threshold stability has the following differences from the original two-level formulation: in the top-level problem, the deviation of consumer budgets from expected values is maximized provided that the producer’s income is not less than a given threshold. The problem statement considered in this paper differs from those previously studied in that the pricing problem is NP-hard in the strong sense when the location of facilities is fixed. 

A variable neighborhoods descent based algorithm (VND) to solve the threshold stability problem is proposed. Numerical investigation of the algorithm is carried out on known examples and randomly generated data. The experiment shows that iteratively subtracting the threshold stability radius from the consumer budgets, which is first implemented in this paper, strongly reduces the running time of the algorithm. On the examples with the optimum known, the algorithm was wrong on average by 0.63%. In all the examples, the algorithm finds a solution on average 2.97% better than the Gurobi solver. 

Tab. 4, illustr. 2, bibliogr. 33.

References:
  1. A. A. Panin and A. V. Plyasunov, Stability analysis for pricing, in Mathematical Optimization Theory and Operations Research, Rev. Sel. Pap. 19th Int. Conf. MOTOR 2020 (Novosibirsk, Russia, July 6–10, 2020) (Springer, Cham, 2020), pp. 57–69 (Commun. Comput. Inf. Sci., Vol. 1275).
     
  2. 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. 
     
  3. 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.
     
  4. M. E. Vodyan, A. A. Panin, and A. V. Plyasunov, A study of the threshold stability of the bilevel problem of facility location and discriminatory pricing, Diskretn. Anal. Issled. Oper. 31 (3), 79–104 (2024) [Russian] [J. Appl. Ind. Math. 18 (3) 558–574 (2024), DOI: 10.1134/S1990478924030165].
     
  5. M. Dyer and L. Stougie, Computational complexity of stochastic programming problems, Math. Program, Ser. A, 106 (3), 423–432 (2006), DOI: 10. 1007/s10107-005-0597-0.
     
  6. A. I. Kibzun and Yu. S. Kan, Stochastic Programming Problems with Probability Criteria (Fizmatlit, Moscow, 2009) [Russian].
     
  7. A. Ben-Tal and A. Nemirovski, Robust optimization — Methodology and applications, Math. Program, Ser. B, 92 (3), 453–480 (2002), DOI: 10.1007/ s101070100286.
     
  8. L. V. Snyder, Facility location under uncertainty: A review, IIE Trans. 38, 537–554 (2006), DOI: 10.1080/07408170500216480.
     
  9. H. J. Greenberg, An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, in Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search (Springer, New York, 1998), pp. 97–147, DOI: 10.1007/ 978-1-4757-2807-1_4.
     
  10. I. Correia, F. S. da Gama, Facility location under uncertainty, in Location Science (Springer, Cham, 2015), pp. 177–203.
     
  11. A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett. 25 (1), 1–13 (1999).
     
  12. G. Yu and J. Yang, On the shortest path problem, Comput. Oper. Res. 25 (6), 457–68 (1988).
     
  13. P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications (Kluwer Acad. Publ., Dordrecht, 1997). 
     
  14. I. Averbakh and V. Lebedev, Interval data minmax regret network optimization problems, Discrete Appl. Math. 138, 289–301 (2004).
     
  15. H. Aissi, C. Bazgan, and D. Vanderpooten, Complexity of the min-max and min-max regret assignment problems, Oper. Res. Lett. 33 (6), 634–640 (2005).
     
  16. E. Carrizosa and S. Nickel, Robust facility location, Math. Methods Oper. Res. 58 (2), 331–349 (2003).
     
  17. 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).
     
  18. V. K. Leontiev, Stability of the travelling salesman problem, Zh. Vychisl. Mat. Mat. Fiz. 15 (5), 1298–1309 (1975) [Russian] [USSR Comput. Math. Math. Phys. 15 (5), 199–213 (1975), 10.1016/0041-5553(75)90116-0].
     
  19. A. Rossi, E. Gurevsky, O. Battaia, and A. Dolgui, Maximizing the robustness for simple assembly lines with fixed cycle time and limited number of workstations, Discrete Appl. Math. 208, 123–136 (2016).
     
  20. E. Gurevsky, A. Rasamimanana, A. Pirogov, A. Dolgui, and A. Rossi, Stability factor for robust balancing of simple assembly lines under uncertainty, Discrete Appl. Math. 318, 113–132 (2022).
     
  21. A. Pirogov, E. Gurevsky, A. Rossi, and A. Dolgui, Robust balancing of transfer lines with blocks of uncertain parallel tasks under fixed cycle time and space restrictions, Eur. J. Oper. Res. 290, 946–955 (2021).
     
  22. Yu. N. Sotskov, Assembly and production line designing, balancing and scheduling with inaccurate data: A survey and perspectives, Algorithms 16 (2), ID 100 (2023).
     
  23. V. K. Leontiev and È. N. Gordeev, Qualitative investigation of path problems, Kibernetika, No. 5, 82–89 (1986) [Russian] [Cybernetics 22 (5) 636–646 (1986), DOI: 10.1007/BF01068361].
     
  24. Yu. N. Sotskov, V. K. Leontiev, and É. N. Gordeev, Some concepts of stability analysis in combinatorial optimization, Discrete Appl. Math. 58 (2), 169–190 (1995).
     
  25. K. G. Kuzmin, A general approach to the calculation of stability radii for the max-cut problem with multiple criteria, Diskretn. Anal. Issled. Oper. 22 (5), 30–51 (2015) [Russian] [J. Appl. Ind. Math. 9 (4) 527–539 (2015), DOI: 10. 1134/S1990478915040092].
     
  26. S. Dempe and A. Zemkoho, Bilevel Optimization: Advances and Next Challenges (Springer, Cham, 2020) (Springer Optim. Its Appl., Vol. 161), DOI: 10.1007/978-3-030-52119-6.
     
  27. E.-G. Talbi, Metaheuristics: From Design to Implementation (Wiley, Berlin, 2009).
     
  28. N. Mladenović and P. Hansen, Variable neighbourhood search, Comput. Oper. Res. 24, 1097–1100 (1997).
     
  29. Yu. A. Kochetov, N. Mladenović, and P. Hansen, Local variable neighbourhood search, Diskretn. Anal. Issled. Oper., Ser. 2, 10 (1), 11–43 (2003) [Russian].
     
  30. 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.
     
  31. 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), DOI: 10.1134/S1990478915030102].
     
  32. P. Hanjoul, P. Hansen, D. Peeters, and J.-F. Thisse, Uncapacitated plant location under alternative spatial price policies, Manag. Sci. 36 (1), 41–57 (1990), DOI: 10.1287/mnsc.36.1.41.
     
  33. A. A. Panin, M. G. Pashchenko, and A. V. Plyasunov, Bilevel competitive facility location and pricing problems, Avtom. Telemekh., No. 4, 153–169 (2014) [Russian] [Autom. Remote Control 75 (4), 715–727 (2014), DOI: 10. 1134/S0005117914040110].