×

Extensive facility location problems on networks: an updated review. (English) Zbl 1397.90081

Summary: Location problems with extensive facilities represent a challenging field of research. According to the specialized literature, a facility is called extensive if, for purposes of location, it is too large in relation to its environment to be considered a point. There are many examples of this type of structures that appear in real-world applications both in the continuous space (straight lines, circles, strips) and in networks (paths, cycles, trees). There exists a recent literature review on the location of dimensional facilities on continuous space [J. M. Díaz-Báñez et al., Eur. J. Oper. Res. 152, No. 1, 22–44 (2004; Zbl 1040.90021); A. Schöbel, “Location of dimensional facilities in a continuous space”, in: Location Science. Heidelberg New York Dordrecht London: Springer Cham. 135–175 (2015; doi:10.1007/978-3-319-13111-5_7)] that does not cover similar problems on networks. The goal of this paper is to review the location of dimensional facilities in networks. We mainly concentrate on the location of paths and trees considering the most common objective functions in the location literature, namely median and center. However, we also consider some other alternative criteria generalizing them, as the ordered median objective function, or related to equity, reliability, and robustness. We include the basic tools and techniques that are applicable to develop algorithms for this kind of problems. Moreover, we present the best known complexity results for each of the considered problems. Finally, some suggestions are also made for possible directions of future research.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1040.90021
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alstrup, S; Holm, J; Lichtenberg, KD; Thorup, M, Maintaining information in fully dynamic trees with top trees, ACM Trans Algorithms, 1, 243-264, (2005) · Zbl 1321.68211 · doi:10.1145/1103963.1103966
[2] Alstrup S, Lauridsen PW, Sommerlund P, Thorup M (1997) Finding cores of limited length. In: Proceedings of 5th international workshop on algorithms and data structures (WADS), lecture notes in computer science, vol 1272. Springer, Berlin, pp 45-54 · Zbl 1321.90075
[3] Alstrup S, Lauridsen PW, Sommerlund P, Thorup M (2001) Finding cores of limited length, IT-C Technical Report Series 2000-4, University of Copenhagen
[4] Averbakh, I; Berman, O, Algorithms for path medi-centers of a tree, Comput Oper Res, 26, 1395-1409, (1999) · Zbl 0967.90064 · doi:10.1016/S0305-0548(99)00042-8
[5] Balasubramanian S, Harini S, Rangan CP (2009) Core and conditional core path of specified length in special classes of graphs. In: Das S, Uehara R (eds) WALCOM: algorithms and computation. WALCOM 2009. Lecture notes in computer science, vol 5431, Springer, Berlin, Heidelberg, pp 262-273 · Zbl 1211.05159
[6] Becker, RI; Perl, Y, Finding the two-core of a tree, Discrete Appl Math, 11, 103-113, (1985) · Zbl 0608.05026 · doi:10.1016/S0166-218X(85)80002-0
[7] Becker, RI; Lari, I; Scozzari, A; Storchi, G, Efficient algorithms for finding the \((k,ℓ )\)-core of tree networks, Networks, 40, 208-215, (2002) · Zbl 1026.90052 · doi:10.1002/net.10051
[8] Becker, RI; Chang, YI; Lari, I; Scozzari, A; Storchi, G, Finding the \(ℓ \)-core of a tree, Discrete Appl Math, 118, 25-42, (2002) · Zbl 1004.68123 · doi:10.1016/S0166-218X(01)00254-2
[9] Becker, RI; Lari, I; Scozzari, A, Algorithms for central-Median paths with bounded length on trees, Eur J Oper Res, 179, 1208-1220, (2007) · Zbl 1127.90043 · doi:10.1016/j.ejor.2005.09.049
[10] Becker, RI; Lari, I; Scozzari, A; Storchi, G, The location of Median paths on grid graphs, Ann Oper Res, 150, 65-78, (2007) · Zbl 1144.90497 · doi:10.1007/s10479-006-0162-0
[11] Benkoczi, R; Bhattacharya, B; Tamir, A, Collection depots facility location problems in trees, Networks, 53, 40-62, (2009) · Zbl 1168.90534 · doi:10.1002/net.20258
[12] Bhattacharya, B; Shi, Q; Tamir, A, Optimal algorithms for the path/tree-shaped facility location problems in trees, Algorithmica, 55, 601-618, (2009) · Zbl 1185.68461 · doi:10.1007/s00453-007-9157-8
[13] Bhattacharya B, Hu Y, Shi Q, Tamir A (2006) Optimal algorithms for the path, tree-shaped facility location problems in trees, ISAAC, lecture notes in computer science, vol 4288. Springer, Berlin, pp 379-388 · Zbl 1135.90357
[14] Bhattacharyya, B; Dehne, F, Using spine decomposition to efficiently solve the length-constrained heaviest path problem for trees, Inf Process Lett, 108, 293-297, (2008) · Zbl 1191.68202 · doi:10.1016/j.ipl.2008.05.023
[15] Boffey, B, Efficient solution methods for covering tree problems, TOP, 6, 205-221, (1998) · Zbl 0916.90175 · doi:10.1007/BF02564788
[16] Caceres, T; López-de-los-Mozos, MC; Mesa, JA, The path-variance problem on tree networks, Discrete Appl Math, 145, 72-79, (2004) · Zbl 1058.90032 · doi:10.1016/j.dam.2003.09.008
[17] Díaz-Báñez, JM; Mesa, JA; Schöbel, A, Continuous location of dimensional structures, TOP, 154, 22-44, (2004) · Zbl 1040.90021
[18] Dvir A, Segal M (2008) The \((k,ℓ )\) coredian tree for ad hoc networks. In: IEEE the 28th international conference on distributed computing systems workshops. https://doi.org/10.1109/ICDCS · Zbl 0485.68055
[19] Frederickson, GN; Johnson, DB, Finding the k-th paths and p-centers by generating and searching good data structures, J Algorithms, 4, 61-80, (1983) · Zbl 0509.68057 · doi:10.1016/0196-6774(83)90035-4
[20] George, JW; Revelle, CS, Bi-objective Median subtree location problems, Ann Oper Res, 122, 219-232, (2003) · Zbl 1053.90079 · doi:10.1023/A:1026154708960
[21] Hakimi, SL; Schmeichel, EF; Labbé, M, On locating path-or tree-shaped facilities on networks, Networks, 23, 543-555, (1993) · Zbl 0806.90074 · doi:10.1002/net.3230230605
[22] Halpern, J, The location of a center-Median convex combination on an undirected tree, J Reg Sci, 16, 237-245, (1976) · doi:10.1111/j.1467-9787.1976.tb00966.x
[23] Halpern, J, Finding minimal center-median convex combination (cent-Dian) of a graph, Manag Sci, 24, 534-544, (1978) · Zbl 0371.90120 · doi:10.1287/mnsc.24.5.535
[24] Hassin, R; Tamir, A, Efficient algorithms for optimization and selection on series-parallel graphs, SIAM J Algebraic Discrete Methods, 7, 379-389, (1986) · Zbl 0617.90083 · doi:10.1137/0607043
[25] Hedetniemi, SM; Cockaine, EJ; Hedetniemi, ST, Linear algorithms for finding the Jordan centre and path centre of a tree, Transp Sci, 15, 98-114, (1981) · doi:10.1287/trsc.15.2.98
[26] Itai, A; Papadimitriou, CH; Szwarcfiter, JL, Hamilton paths in grid graphs, SIAM J Comput, 4, 676-686, (1982) · Zbl 0506.05043 · doi:10.1137/0211056
[27] Kalcsics, J; Nickel, S; Puerto, J, Multifacility ordered Median problems on networks: a further analysis, Networks, 41, 1-12, (2003) · Zbl 1026.90056 · doi:10.1002/net.10053
[28] Kim, TU; Lowe, TJ; Tamir, A; Ward, JE, On the location of a tree-shaped facility, Networks, 28, 167-175, (1996) · Zbl 0865.90088 · doi:10.1002/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L
[29] Labbé, M; Laporte, G; Martín, IR; González, JJS, Locating Median cycles in networks, Eur J Oper Res, 160, 457-470, (2005) · Zbl 1067.90109 · doi:10.1016/j.ejor.2003.07.010
[30] Laporte, G; Martín, IR, Locating a cycle in a transportation or a telecommunications network, Networks, 50, 92-108, (2007) · Zbl 1118.90030 · doi:10.1002/net.20170
[31] Laporte G, Nickel S, Saldanha da Gama F (2015) Location science. Springer International Publishing, Switzerland · Zbl 1329.90003 · doi:10.1007/978-3-319-13111-5
[32] Lari, I; Ricca, F; Scozzari, A, Comparing different metaheuristic approaches for the Median path problem with bounded length, Eur J Oper Res, 190, 587-597, (2008) · Zbl 1146.90456 · doi:10.1016/j.ejor.2007.07.001
[33] Lari, I; Ricca, F; Scozzari, A; Becker, RI, Locating Median paths on connected outerplanar graphs, Networks, 57, 294-307, (2011) · Zbl 1219.05079 · doi:10.1002/net.20426
[34] Megiddo, N, Linear-time algorithms for linear programming in \(R^3\) and related problems, SIAM J Comput, 12, 759-776, (1983) · Zbl 0521.68034 · doi:10.1137/0212052
[35] Mesa, JA; Boffey, TB, A review of extensive facility location in networks, Eur J Oper Res, 95, 592-603, (1996) · Zbl 0926.90057 · doi:10.1016/0377-2217(95)00321-5
[36] Mesa, JA; Puerto, J; Tamir, A, Improved algorithms for several network location problems with equality measures, Discrete Appl Math, 130, 437-448, (2003) · Zbl 1033.90011 · doi:10.1016/S0166-218X(02)00599-1
[37] Minieka, E, The optimal location of a path or tree in a tree network, Networks, 15, 309-321, (1985) · Zbl 0579.90027 · doi:10.1002/net.3230150304
[38] Morgan, CA; Slater, JP, A linear algorithm for a core of a tree, J Algorithms, 1, 247-258, (1980) · Zbl 0454.68067 · doi:10.1016/0196-6774(80)90012-7
[39] Nickel, S; Puerto, J, A unified approach to network location, Networks, 34, 283-290, (1999) · Zbl 0948.90086 · doi:10.1002/(SICI)1097-0037(199912)34:4<283::AID-NET8>3.0.CO;2-2
[40] Nickel S, Puerto J (2005) Location theory: a unified approach. Springer, Berlin · Zbl 1229.90001
[41] Novik A (1996) Improved algorithms for locating tree or path shaped facilities on a tree network, M.S. Thesis, School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel · Zbl 0926.90057
[42] Peng, S; Lo, W-T, Efficient algorithms for finding a core of a tree with a specified length, J Algorithms, 20, 445-458, (1996) · Zbl 0845.68053 · doi:10.1006/jagm.1996.0022
[43] Peng, S; Stephens, AB; Yesha, Y, Algorithms for a core and \(k\)-tree core of a tree, J Algorithms, 15, 143-159, (1993) · Zbl 0782.68092 · doi:10.1006/jagm.1993.1034
[44] Puerto, J; Tamir, A, Locating tree-shaped facilities using the ordered Median objective, Math Programm, 102, 313-338, (2005) · Zbl 1079.90081 · doi:10.1007/s10107-004-0547-2
[45] Puerto, J; Rodríguez-Chía, AM; Tamir, A; Perez-Brito, D, The bi-criteria doubly weighted center-Median path problem on a tree, Networks, 47, 237-247, (2006) · Zbl 1103.90021 · doi:10.1002/net.20112
[46] Puerto, J; Ricca, F; Scozzari, A, Extensive facility location problems on networks with equity measures, Discrete Appl Math, 157, 1069-1085, (2009) · Zbl 1163.90039 · doi:10.1016/j.dam.2008.03.035
[47] Puerto, J; Ricca, F; Scozzari, A, The continuous and discrete path-variance problems on trees, Networks, 53, 221-228, (2009) · Zbl 1178.90218 · doi:10.1002/net.20284
[48] Puerto, J; Ricca, F; Scozzari, A, Minimax regret path location on trees, Networks, 58, 147-158, (2011) · Zbl 1236.90137
[49] Puerto, J; Ricca, F; Scozzari, A, Range minimization problems in path-facility location on trees, Discrete Appl Math, 160, 2294-2305, (2012) · Zbl 1250.90103 · doi:10.1016/j.dam.2012.05.020
[50] Puerto, J; Ricca, F; Scozzari, A, Reliability problems in multiple path-shaped facility location on networks, Discrete Optim, 12, 61-72, (2014) · Zbl 1308.90091 · doi:10.1016/j.disopt.2014.01.003
[51] Puerto, J; Rodríguez-Chía, AM; Tamir, A, Revisiting \(k\)-sum optimization, Math Program, 165, 579-604, (2017) · Zbl 1373.90068 · doi:10.1007/s10107-016-1096-1
[52] Richey, MB, Optimal location of a path or tree on a network with cycles, Networks, 20, 391-407, (1990) · Zbl 0715.90071 · doi:10.1002/net.3230200404
[53] Rozanov M (2015) The nestedness property of the convex ordered median location problem on a tree. MSc thesis, Tel-Aviv University. http://primage.tau.ac.il/libraries/theses/exeng/free/3257656.pdf · Zbl 0371.90120
[54] Rozanov M, Tamir A (2018) The nestedness property of location problems on the line. TOP. https://doi.org/10.1007/s11750-018-0471-x · Zbl 1394.90463
[55] Schöbel, A; Laporte, G (ed.); etal., Location of dimensional facilities in a continuous space, (2015), Cham
[56] Shioura, A; Shigeno, M, The tree center problems and the relationship with the bottleneck knapsack problem, Networks, 29, 107-110, (1997) · Zbl 0888.90147 · doi:10.1002/(SICI)1097-0037(199703)29:2<107::AID-NET4>3.0.CO;2-N
[57] Shioura, A; Uno, T, A linear time algorithm for finding a \(k\)-tree core, J Algorithms, 23, 281-290, (1997) · Zbl 0873.68166 · doi:10.1006/jagm.1996.0838
[58] Slater, PJ, Locating central paths in a graph, Transp Sci, 15, 1-18, (1982) · doi:10.1287/trsc.16.1.1
[59] Takamizawa, K; Nishizeki, T; Saito, N, Linear-time computability of combinatorial problems on series-parallel graphs, J ACM, 29, 623-641, (1982) · Zbl 0485.68055 · doi:10.1145/322326.322328
[60] Tamir, A, An \(O(pn^2)\) algorithm for the \(p\)-Median and related problems on tree graphs, Oper Res Lett, 19, 59-64, (1996) · Zbl 0865.90089 · doi:10.1016/0167-6377(96)00021-1
[61] Tamir, A, Fully polynomial approximation schemes for locating a tree-shaped facility: a generalization of the knapsack problem, Discrete Appl Math, 87, 229-243, (1998) · Zbl 0910.90241 · doi:10.1016/S0166-218X(98)00059-6
[62] Tamir, A, Sorting weighted distances with applications to objective function evaluations in single facility location problems, Oper Res Lett, 32, 249-257, (2004) · Zbl 1043.90044 · doi:10.1016/j.orl.2003.10.004
[63] Tamir, A; Lowe, TJ, The generalized \(p\)-forest problem on a tree network, Networks, 22, 217-230, (1992) · Zbl 0772.90057 · doi:10.1002/net.3230220302
[64] Tamir, A; Puerto, J; Pèrez-Brito, D, The Centdian subtree on the tree networks, Discrete Appl Math, 118, 263-278, (2002) · Zbl 1016.68063 · doi:10.1016/S0166-218X(01)00199-8
[65] Tamir, A; Puerto, J; Mesa, JA; Rodriguez-Chia, AM, Conditional location of path and tree shaped facilities on trees, J Algorithms, 56, 50-75, (2005) · Zbl 1101.68738 · doi:10.1016/j.jalgor.2005.01.005
[66] Tang, H; Cheng, TCE; Ng, CT, A note on the subtree ordered Median problem in networks based on nestedness property, J Ind Manag Optim, 8, 41-49, (2012) · Zbl 1364.90196 · doi:10.3934/jimo.2012.8.41
[67] Wang B-F, Lin J-J (2000) Finding a Two-Core of a tree in linear time, ISAAC, lecture notes in computer science, vol 1969. Springer, Berlin, pp 467-478 · Zbl 1127.90043
[68] Wang, B-F, Finding a k-tree core and a k-tree center of a tree network in parallel, IEEE Trans Parallel Distrib Syst, 9, 186-191, (1998) · doi:10.1109/71.663884
[69] Wang, B-F, Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network, J Algorithms, 34, 90-108, (2000) · Zbl 0949.68177 · doi:10.1006/jagm.1999.1020
[70] Wang, B-F, A 2-core of a tree in linear time, SIAM J Discrete Math, 15, 193-210, (2002) · Zbl 0991.05096 · doi:10.1137/S0895480100374242
[71] Wang, B-F; Ku, S-C; Shi, K-H, Cost-optimal parallel algorithms for the tree bisector and related problems, IEEE Trans Parallel Distrib Syst, 12, 888-898, (2001) · doi:10.1109/71.954619
[72] Wang, B-F; Peng, S; Yu, H-Y; Ku, S-C, Efficient algorithms for a constrained \(k\)-tree core problem in a tree network, J Algorithms, 59, 107-124, (2006) · Zbl 1103.68135 · doi:10.1016/j.jalgor.2004.12.002
[73] Wang, B-F; Lin, T-C; Lin, C-H; Ku, S-C, Finding the conditional location of a Median path on a tree, Inf Comput, 206, 828-839, (2008) · Zbl 1153.90020 · doi:10.1016/j.ic.2008.04.004
[74] Ye J-H (2017) Improved algorithms for minmax regret path location problems on trees, Ph.D. Dissertation, Department of Computer Science, Nation Tsing Hua University
[75] Ye, J-H; Wang, B-F, On the minmax regret path Median problem on trees, J Comput Syst Sci, 81, 1159-1170, (2015) · Zbl 1321.90075 · doi:10.1016/j.jcss.2015.01.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.