We consider the problem of the optimal location of facilities on an undirected weighted network located on a plane. The vertices are assigned positive weights and the edges are segments. The weight of a vertex reflects the requirement to locate the facilities as far away from it as possible. Constraints are given on the minimum admissible distances from vertices to the facilities. It is necessary to find such points on the edges of the network to locate the facilities that the minimum weighted distance from the vertices to the facilities is maximum. An algorithm for solving the problem with a given accuracy for two facilities is proposed.
Download file
Counter downloads: 4
- Title Approximate solution of the maximin problem of locating facilities on a network with constraints on minimum distances
- Headline Approximate solution of the maximin problem of locating facilities on a network with constraints on minimum distances
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/8
Keywords
convex hull, location problem, maximin criterion, obnoxious facility, networkAuthors
References
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.
Drezner Z. Facility Location. A Survey of Applications and Methods. N.Y.: Springer, 1995. 571 p.
Nickel S. Location Theory. A Unified Approach. Berlin: Springer Verlag, 2005. 437 p.
Farani R. Z. and Flekmatfar M. Facility Location: Concepts, Models, Algorithms and Case Studies. Berlin: Springer Verlag, 2009. 549 p.
Eiselt H. A. and Marianov V. Foundations of Location Analysis. N.Y.: Springer, 2011. 509 p.
Church R. L. and Garfinkel R. S. Locating an obnoxious facility on a network // Trans. Sci. 1978. V. 12. No. 2. P.107-118.
Забудский Г. Г. Решение макси-суммной задачи размещения на сети с ограничениями на транспортные затраты // Прикладная дискретная математика. 2023. №60. С. 120-127.
Melachrinoudis Е. and Zhang G. An O(mn) algorithm for the 1-maximin problem on a network // Comput. & Oper. Res. 1999. V.26. No.9. P.849-869.
Heydari R. and Melachrinoudis E. Location of a semi-obnoxious facility with elliptic maxmin and network minisum objectives // Eur. J. Oper. Res. 2012. V.223. No. 2. P.452-460.
Zabudsky G. and Lisina M. Approximately algorithm for maximin location problem on network // Proc. XII Intern. Conf. "Dynamics of Systems, Mechanisms and Machines". 13-15 November 2018, Omsk, Russia. P. 1-6.
Tamir A. Obnoxious facility location on graphs // SIAM J. Discrete Math. 1991. V. 4. No. 4. P. 550-567.
Welch S. В. and Wesolowsky S. The obnoxious p facility network location problem with facility interaction // Eur. J. Oper. Res. 1997. V. 102. No.2. P.302-319.
Tamir A. Locating two obnoxious facilities using the weighted maximin criterion // Oper. Res. Let. 2006. V.34. No.l. P.97-105.
Яглом И. M., Болтянский И. М. Выпуклые фигуры. М.: Технике-теоретическая литература, 1951. 344 с.
Shamos М. I.Computational Geometry. PhD Thesis. New Haven, Yele University, 1978. 236 p.
Пpepapama Ф., Шеймос M. Вычислительная геометрия: Введение. M.: Мир, 1989. 478 с.
Approximate solution of the maximin problem of locating facilities on a network with constraints on minimum distances | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/8
Download full-text version
Counter downloads: 68