ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» №4, 2012

Об одном подходе к робастности решения в задаче о 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.