We consider the problem of the optimal location of a facility on an undirected weighted network. A positive weight is assigned to each edge. Two positive parameters are assigned to the vertices. The first parameter reflects the requirement to place the facility as close to the vertex as possible, and the second - as far as possible. There is a limit on the total weighted distance from the facility to the vertices, taking into account the first parameter. It is necessary to find acceptable locations of the facility on the edges of the network with the maximum sum of weighted distances from them to the vertices, taking into account the second parameter (local extremes). A polynomial algorithm is proposed to find all local extremums at the edges of the network.
Download file
Counter downloads: 5
- Title Solving of the maxisum location problem on network with a restriction on transport costs
- Headline Solving of the maxisum location problem on network with a restriction on transport costs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 60
- Date:
- DOI 10.17223/20710410/60/11
Keywords
location problem, maxisum criterion, undesirable facility, networkAuthors
References
Tamir A. Obnoxious facility location on graphs // SIAM J. Discrete Math. 1991. V. 4. No.4. P. 550-567.
Drezner Z. Facility Location. A Survey of Applications and Methods. N.Y.: Springer, 1995. 571 p.
Eiselt H. A. and Marianov V. Foundations of Location Analysis. N.Y.: Springer, 2011. 509 p.
Zabudsky G. G. and Lisina M. S. Approximately algorithm for maximin location problem on network // Dynamics of Systems, Mechanisms and Machines. XII Intern. Conf. Omsk, Russia, 13-15 November 2018. https://ieeexplore.ieee.org/document/8601502.
Church R. L. and Garfinkel R. S. Locating an obnoxious facility on a network // Trans. Sci. 1978. V. 12. No. 2. P. 107-118.
Hakimi S. L. Optimal location of switching centers and the absolute centers and medians of a graph // Oper. Res. 1964. V. 12. No.3. P.450-459.
Berman O. and Drezner Z. A note on the location of an obnoxious facility on a network // Eur. J. Oper. Res. 2000. V. 120. No. 1. P.215-217.
Забудский Г. Г. Размещение опасного объекта на сети с ограничением на транспортные затраты // Проблемы машиноведения. VI Междунар. науч.-техн. конф. Омск, 22-23 марта 2022. С. 162-165.
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.
Ху T. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 519 с.
Solving of the maxisum location problem on network with a restriction on transport costs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/11
Download full-text version
Counter downloads: 126