Об одном подходе к робастности решения в задаче о p-медиане
| Авторы: | И. Л. Васильев, А. В. Ушаков |
| Аннотация: | В работе исследуется один из подходов к определению робастности решения в дискретных задачах размещения на примере задачи о p-медиане. Рассматривается бикритериальная задача размещения p предприятий таким образом, чтобы суммарные затраты на обслуживание всех клиентов были минимальны и к тому же полученное решение имело максимально возможную робастность. Для такой задачи предложен алгоритм на основе метода ε-ограничений, позволяющий найти аппроксимацию множества точек оптимальных по Слейтеру. |
| Ключевые слова: | задача о p-медиане; бикритериальная комбинаторная оптимизация; робастностьв дискретных задачах размещения; метод ε-ограничений |
| УДК: | 519.854.2 |
| Литература: |
1. B´erub´e J. F. An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits / J. F. B´erub´e, M. Gendreau, J. Y. Potvin // EJOR. – 2009. – Vol. 194, N 1. – P. 39–50. 2. Blanquero R. Locating a competitive facility in the plane with a robustness criterion / R. Blanquero, E. Carrizosa, E. M. T. Hendrix // EJOR. – 2011. – Vol. 215, N 1. – P. 21–24. 3. Carrizosa E. Robust facility location / E. Carrizosa, S. Nickel // Math. Methods Oper. Res. – 2003. – Vol. 58, N 2. – P. 331–349. 4. Ehrgott M. Bicriteria robustness versus cost optimisation in tour of duty planning at Air New Zealand / M. Ehrgott, D. M. Ryan // Proceedings of the 35th Annual Conference of the Operational Research Society of New Zealand. – 2000. – P. 31–39. 5. Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys / eds.M. Ehrgott, X. Gandibleux. – Dordrecht : Kluwer Academic Publishers, 2003. – 520 p. – (International Series in Operations Research & Management Science). 6. Hakimi S. L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems / S. L. Hakimi // Operations Research. – 1965. – Vol. 13, № 3. – P. 462–475. 7. Mavrotas G. Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems / G. Mavrotas // Applied Mathematics and Computation. – 2009. – Vol. 213, N 2. – P. 455–465. 8. Melamed I. I. A computational investigation of linear parametrization of criteria in multicriteria discrete programming / I. I. Melamed, I. K. Sigal // Computational Mathematics and Mathematical Physics. – 1996. – Vol. 36, N 10. – P. 1341–1343. 9. Melamed I. I. The linear convolution of criteria in the bicriteria traveling salesman problem / I. I. Melamed, I. K. Sigal // Computational Mathematics and Mathematical Physics. – 1997. – Vol. 37, N 8. – P. 902–905. 10. Melamed I. I. Numerical analysis of tricriteria tree and assignment problems / I. I. Melamed, I. K. Sigal // Computational Mathematics and Mathematical Physics. – 1998. – Vol. 38, N 10. – P. 1704–1707. 11. Melamed I. I. Combinatorial optimization problems with two and three criteria / I. I. Melamed, I. K. Sigal // Doklady Mathematics. – 1999. – Vol. 59, N 3. – P. 490–493. 12. The p-median problem: A survey of metaheuristic approaches / N. Mladenovi´c, J. Brimberg, P. Hansen, J .A. Moreno-P´erez // EJOR. – 2007. – Vol. 179, N 3. – P. 927–939. 13. Reese J. Solution Methods for the p-Median Problem: An Annotated Bibliography / J. Reese // Networks. – 2006. – Vol. 28, N 3. – P. 125–142. |