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

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

Водян М. Е., Панин А. А., Плясунов А. В.
Дискретный анализ и исследование операций, 31, 3, 79–104 (2024)
Скачать статью

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

Аннотация:

Рассматривается задача пороговой устойчивости для двухуровневой задачи с медианным типом размещения предприятий и дискриминационным ценообразованием. При решении такой задачи необходимо найти радиус пороговой устойчивости и такое полудопустимое решение исходной двухуровневой задачи, для которого выручка лидера не меньше заранее заданного значения (порога) при любом отклонении бюджетов, не превышающем порогового радиуса устойчивости, и которое сохраняет свою полудопустимость. Таким образом, пороговый радиус устойчивости определяет предел возмущений бюджетов потребителей, при котором выполняются эти условия.

Разработаны два приближённых алгоритма решения задачи пороговой устойчивости на основе эвристики спуска с чередующимися окрестностями. Эти алгоритмы основываются на поиске хорошего приближённого размещения предприятий, а также на вычислении оптимального набора цен для найденного размещения предприятий. Алгоритмы отличаются способом сравнения различных размещений предприятий, что в конечном итоге приводит к различным оценкам радиуса пороговой устойчивости. Численный эксперимент показал эффективность выбранного подхода как с точки зрения времени работы алгоритмов, так и качества получаемых решений. Табл. 4, ил. 2, библиогр. 24.

Литература:
  1. 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. DOI: 10.1007/ 978-1-4757-2807-1_4.
     
  2. Ben-Tal A., Nemirovski A. Robust optimization: Methodology and applications // Math. Program. 2002. V. 92. P. 453–480.
     
  3. Snyder L. V. Facility location under uncertainty: A review // IIE Trans. 2006. V. 38. P. 537–554. DOI: 10.1080/07408170500216480.
     
  4. Dyer M., Stougie L. Computational complexity of stochastic programming problems // Math. Program. Ser. A. 2006. V. 106. P. 423–432. DOI: 10.1007/ s10107-005-0597-0.
     
  5. Кибзун А. И., Кан Ю. С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009. 371 с.
     
  6. Correia I., da Gama F. S. Facility location under uncertainty // Location science. Cham: Springer, 2015. P. 177–203.
     
  7. Charitopoulos V. M., Papageorgiou L. G., Dua V. Multiparametric mixed integer linear programming under global uncertainty // Comput. Chem. Eng. 2018. V. 116. P. 279–295.
     
  8. Carrizosa E., Nickel S. Robust facility location // Math. Methods Oper. Res. 2003. V. 58. P. 331–349.
     
  9. Carrizosa E., Ushakov A., Vasilyev I. Threshold robustness in discrete facility location problems: A bi-objective approach // Optim. Lett. 2015. V. 9. P. 1297–1314.
     
  10. Rossi A., Gurevsky E., Battaïa 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.
     
  11. 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.
     
  12. Sotskov Yu. N. Assembly and production line designing, balancing and scheduling with inaccurate data: A survey and perspectives // Algorithms. 2023. V. 16, No. 2. Paper ID 100. 43 p.
     
  13. Леонтьев В. К. Устойчивость задачи коммивояжера // Вычисл. математика и мат. физика. 1975. Т. 15, № 5. С. 1298–1309.
     
  14. Леонтьев В. К., Гордеев Э. Н. Качественное исследование траекторных задач // Кибернетика. 1986. № 5. С. 82–89.
     
  15. Sotskov Yu. N., Leontiev V. K., Gordeev Eh. N. Some concepts of stability analysis in combinatorial optimization // Discrete Appl. Math. 1995. V. 58, No. 2. P. 169–190.
     
  16. Кузьмин К. Г. Единый подход к нахождению радиусов устойчивости в многокритериальной задаче о максимальном разрезе графа // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 30–51.
     
  17. 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.
     
  18. 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. P. 1295–1315.
     
  19. 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.
     
  20. Kochetov Yu. A., Plyasunov A. V., Panin A. A. Bilevel discrete optimisation: Computational complexity and applications // The Palgrave handbook of operations research. Cham: Palgrave Macmillan, 2022. P. 3–42. DOI: 10.1007/978-3-030-96935-6_1.
     
  21. Talbi E.-G. Metaheuristics: From design to implementation. Berlin: Wiley, 2009. 624 p.
     
  22. Mladenovic N., Hansen P. Variable neighbourhood search // Comput. Oper. Res. 1997. V. 24. P. 1097–1100.
     
  23. Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. С. 36–54.
     
  24. Vodyan M. E., Panin A. A., Plyasunov A. V. Metaheuristics for finding the stability radius in the bilevel facility location and uniform pricing problem // 2023 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.

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

Водян Максим Евгеньевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 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

Статья поступила 10 ноября 2023 г.
После доработки — 23 января 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

The problem of threshold stability for a bilevel problem with a median type of facility location and discriminatory pricing is considered. When solving such a problem, it is necessary to find the threshold stability radius and a semifeasible solution of the original bilevel problem such that the leader’s revenue is not less than a predetermined value (threshold) for any deviation of budgets that does not exceed the threshold stability radius and which preserves its semifeasibility. Thus, the threshold stability radius determines the limit of disturbances of consumer budgets with which these conditions are satisfied. 

Two approximate algorithms for solving the threshold stability problem based on the heuristic of descent with alternating neighborhoods are developed. These algorithms are based on finding a good approximate location of facilities as well as on calculating the optimal set of prices for the found location of facilities. The algorithms differ in the way they compare various locations of facilities; this ultimately leads to different estimates of threshold stability radius. A numerical experiment has shown the efficiency of the chosen approach both in terms of the running time of the algorithms and the quality of the solutions obtained. 
Tab. 4, illustr. 2, bibliogr. 24.

References:
  1. 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.
     
  2. A. Ben-Tal and A. Nemirovski, Robust optimization: Methodology and applications, Math. Program. 92, 453–480 (2002).
     
  3. L. V. Snyder, Facility location under uncertainty: A review, IIE Trans. 38, 537–554 (2006), DOI: 10.1080/07408170500216480.
     
  4. M. Dyer and L. Stougie, Computational complexity of stochastic programming problems, Math. Program., Ser. A, 106, 423–432 (2006), DOI: 10.1007/ s10107-005-0597-0.
     
  5. A. I. Kibzun and Yu. S. Kan, Stochastic Programming Problems with Probabilistic Criteria (Fizmatlit, Moscow, 2009) [Russian].
     
  6. I. Correia and F. S. da Gama, Facility location under uncertainty, in Location Science (Springer, Cham, 2015), pp. 177–203.
     
  7. V. M. Charitopoulos, L. G. Papageorgiou, and V. Dua, Multiparametric mixed integer linear programming under global uncertainty, Comput. Chem. Eng. 116, 279–295 (2018).
     
  8. E. Carrizosa and S. Nickel, Robust facility location, Math. Methods Oper. Res. 58, 331–349 (2003).
     
  9. E. Carrizosa, A. Ushakov, and I. Vasilyev, Threshold robustness in discrete facility location problems: A bi-objective approach, Optim. Lett. 9, 1297–1314 (2015).
     
  10. A. Rossi, E. Gurevsky, O. Battaïa, 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).
     
  11. 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).
     
  12. Yu. N. Sotskov, Assembly and production line designing, balancing and scheduling with inaccurate data: A survey and perspectives, Algorithms 16 (2), ID 100 (2023).
     
  13. V. K. Leontiev, Stability of the travelling salesman problem, Vychisl. Mat. Mat. Fiz. 15 (5), 1298–1309 (1975) [Russian] [USSR Comput. Math. Math. Phys. 15 (5), 199–213 (1975)].
     
  14. V. K. Leontiev and Eh. N. Gordeev, Qualitative investigation of path problems, Kibern., No. 5, 82–89 (1986) [Russian] [Cybern. 22, 636–646 (1986)].
     
  15. Yu. N. Sotskov, V. K. Leontiev, and Eh. N. Gordeev, Some concepts of stability analysis in combinatorial optimization, Discrete Appl. Math. 58 (2), 169–190 (1995).
     
  16. K. G. Kuz’min, 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)].
     
  17. 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_7.
     
  18. A. A. Panin and A. V. Plyasunov, The multilevel facility location and pricing problems: the computational complexity and the stability analysis, Optim. Lett. 17, 1295–1315 (2023).
     
  19. 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.
     
  20. Yu. A. Kochetov, A. V. Plyasunov, and A. A. Panin, Bilevel discrete optimisation: Computational complexity and applications, in The Palgrave Handbook of Operations Research (Palgrave Macmillan, Cham, 2022), pp. 3–42, DOI: 10.1007/978-3-030-96935-6_1.
     
  21. E.-G. Talbi, Metaheuristics: From Design to Implementation (Wiley, Berlin, 2009).
     
  22. N. Mladenovic and P. Hansen, Variable neighbourhood search, Comput. Oper. Res. 24, 1097–1100 (1997).
     
  23. 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)].
     
  24. 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 2023 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.