Skip to main content
SpringerLink
Log in

Extensive facility location problems on networks: an updated review

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

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 (Díaz-Báñez et al. in TOP 154:22–44, 2004; Schöbel in Location of dimensional facilities in a continuous space, 2015) 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. This abbreviation stands for memory access models “Exclusive Read Exclusive Write Parallel Random Access Machine”.

References

  • Alstrup S, Holm J, Lichtenberg KD, Thorup M (2005) Maintaining information in fully dynamic trees with top trees. ACM Trans Algorithms 1:243–264

    Article  Google Scholar 

  • 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

  • Alstrup S, Lauridsen PW, Sommerlund P, Thorup M (2001) Finding cores of limited length, IT-C Technical Report Series 2000-4, University of Copenhagen

  • Averbakh I, Berman O (1999) Algorithms for path medi-centers of a tree. Comput Oper Res 26:1395–1409

    Article  Google Scholar 

  • 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

  • Becker RI, Perl Y (1985) Finding the two-core of a tree. Discrete Appl Math 11:103–113

    Article  Google Scholar 

  • Becker RI, Lari I, Scozzari A, Storchi G (2002) Efficient algorithms for finding the \((k,\ell )\)-core of tree networks. Networks 40:208–215

    Article  Google Scholar 

  • Becker RI, Chang YI, Lari I, Scozzari A, Storchi G (2002) Finding the \(\ell \)-core of a tree. Discrete Appl Math 118:25–42

    Article  Google Scholar 

  • Becker RI, Lari I, Scozzari A (2007) Algorithms for central-median paths with bounded length on trees. Eur J Oper Res 179:1208–1220

    Article  Google Scholar 

  • Becker RI, Lari I, Scozzari A, Storchi G (2007) The location of median paths on grid graphs. Ann Oper Res 150:65–78

    Article  Google Scholar 

  • Benkoczi R, Bhattacharya B, Tamir A (2009) Collection depots facility location problems in trees. Networks 53:40–62

    Article  Google Scholar 

  • Bhattacharya B, Shi Q, Tamir A (2009) Optimal algorithms for the path/tree-shaped facility location problems in trees. Algorithmica 55:601–618

    Article  Google Scholar 

  • 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

  • Bhattacharyya B, Dehne F (2008) Using spine decomposition to efficiently solve the length-constrained heaviest path problem for trees. Inf Process Lett 108:293–297

    Article  Google Scholar 

  • Boffey B (1998) Efficient solution methods for covering tree problems. TOP 6:205–221

    Article  Google Scholar 

  • Caceres T, López-de-los-Mozos MC, Mesa JA (2004) The path-variance problem on tree networks. Discrete Appl Math 145:72–79

    Article  Google Scholar 

  • Díaz-Báñez JM, Mesa JA, Schöbel A (2004) Continuous location of dimensional structures. TOP 154:22–44

    Google Scholar 

  • Dvir A, Segal M (2008) The \((k,\ell )\) coredian tree for ad hoc networks. In: IEEE the 28th international conference on distributed computing systems workshops. https://doi.org/10.1109/ICDCS

  • Frederickson GN, Johnson DB (1983) Finding the k-th paths and p-centers by generating and searching good data structures. J Algorithms 4:61–80

    Article  Google Scholar 

  • George JW, Revelle CS (2003) Bi-objective median subtree location problems. Ann Oper Res 122:219–232

    Article  Google Scholar 

  • Hakimi SL, Schmeichel EF, Labbé M (1993) On locating path-or tree-shaped facilities on networks. Networks 23:543–555

    Article  Google Scholar 

  • Halpern J (1976) The location of a center–median convex combination on an undirected tree. J Reg Sci 16:237–245

    Article  Google Scholar 

  • Halpern J (1978) Finding minimal center–median convex combination (cent-dian) of a graph. Manag Sci 24:534–544

    Article  Google Scholar 

  • Hassin R, Tamir A (1986) Efficient algorithms for optimization and selection on Series-parallel graphs. SIAM J Algebraic Discrete Methods 7:379–389

    Article  Google Scholar 

  • Hedetniemi SM, Cockaine EJ, Hedetniemi ST (1981) Linear algorithms for finding the Jordan centre and path centre of a tree. Transp Sci 15:98–114

    Article  Google Scholar 

  • Itai A, Papadimitriou CH, Szwarcfiter JL (1982) Hamilton paths in grid graphs. SIAM J Comput 4:676–686

    Article  Google Scholar 

  • Kalcsics J, Nickel S, Puerto J (2003) Multifacility ordered median problems on networks: a further analysis. Networks 41:1–12

    Article  Google Scholar 

  • Kim TU, Lowe TJ, Tamir A, Ward JE (1996) On the location of a tree-shaped facility. Networks 28:167–175

    Article  Google Scholar 

  • Labbé M, Laporte G, Martín IR, González JJS (2005) Locating median cycles in networks. Eur J Oper Res 160:457–470

    Article  Google Scholar 

  • Laporte G, Martín IR (2007) Locating a cycle in a transportation or a telecommunications network. Networks 50:92–108

    Article  Google Scholar 

  • Laporte G, Nickel S, Saldanha da Gama F (2015) Location science. Springer International Publishing, Switzerland

    Book  Google Scholar 

  • Lari I, Ricca F, Scozzari A (2008) Comparing different metaheuristic approaches for the median path problem with bounded length. Eur J Oper Res 190:587–597

    Article  Google Scholar 

  • Lari I, Ricca F, Scozzari A, Becker RI (2011) Locating median paths on connected outerplanar graphs. Networks 57:294–307

    Article  Google Scholar 

  • Megiddo N (1983) Linear-time algorithms for linear programming in \(R^3\) and related problems. SIAM J Comput 12:759–776

    Article  Google Scholar 

  • Mesa JA, Boffey TB (1996) A review of extensive facility location in networks. Eur J Oper Res 95:592–603

    Article  Google Scholar 

  • Mesa JA, Puerto J, Tamir A (2003) Improved algorithms for several network location problems with equality measures. Discrete Appl Math 130:437–448

    Article  Google Scholar 

  • Minieka E (1985) The optimal location of a path or tree in a tree network. Networks 15:309–321

    Article  Google Scholar 

  • Morgan CA, Slater JP (1980) A linear algorithm for a core of a tree. J Algorithms 1:247–258

    Article  Google Scholar 

  • Nickel S, Puerto J (1999) A unified approach to network location. Networks 34:283–290

    Article  Google Scholar 

  • Nickel S, Puerto J (2005) Location theory: a unified approach. Springer, Berlin

    Google Scholar 

  • 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

  • Peng S, Lo W-T (1996) Efficient algorithms for finding a core of a tree with a specified length. J Algorithms 20:445–458

    Article  Google Scholar 

  • Peng S, Stephens AB, Yesha Y (1993) Algorithms for a core and \(k\)-tree core of a tree. J Algorithms 15:143–159

    Article  Google Scholar 

  • Puerto J, Tamir A (2005) Locating tree-shaped facilities using the ordered median objective. Math Programm 102:313–338

    Article  Google Scholar 

  • Puerto J, Rodríguez-Chía AM, Tamir A, Perez-Brito D (2006) The bi-criteria doubly weighted center–median path problem on a tree. Networks 47:237–247

    Article  Google Scholar 

  • Puerto J, Ricca F, Scozzari A (2009) Extensive facility location problems on networks with equity measures. Discrete Appl Math 157:1069–1085

    Article  Google Scholar 

  • Puerto J, Ricca F, Scozzari A (2009) The continuous and discrete path-variance problems on trees. Networks 53:221–228

    Article  Google Scholar 

  • Puerto J, Ricca F, Scozzari A (2011) Minimax regret path location on trees. Networks 58:147–158

    Google Scholar 

  • Puerto J, Ricca F, Scozzari A (2012) Range minimization problems in path-facility location on trees. Discrete Appl Math 160:2294–2305

    Article  Google Scholar 

  • Puerto J, Ricca F, Scozzari A (2014) Reliability problems in multiple path-shaped facility location on networks. Discrete Optim 12:61–72

    Article  Google Scholar 

  • Puerto J, Rodríguez-Chía AM, Tamir A (2017) Revisiting \(k\)-sum optimization. Math Program 165:579–604

    Article  Google Scholar 

  • Richey MB (1990) Optimal location of a path or tree on a network with cycles. Networks 20:391–407

    Article  Google Scholar 

  • 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

  • Rozanov M, Tamir A (2018) The nestedness property of location problems on the line. TOP. https://doi.org/10.1007/s11750-018-0471-x

  • Schöbel A (2015) Location of dimensional facilities in a continuous space. In: Laporte G et al (eds) Location science. Springer International Publishing, Cham

    Google Scholar 

  • Shioura A, Shigeno M (1997) The tree center problems and the relationship with the bottleneck knapsack Problem. Networks 29:107–110

    Article  Google Scholar 

  • Shioura A, Uno T (1997) A linear time algorithm for finding a \(k\)-tree core. J Algorithms 23:281–290

    Article  Google Scholar 

  • Slater PJ (1982) Locating central paths in a graph. Transp Sci 15:1–18

    Article  Google Scholar 

  • Takamizawa K, Nishizeki T, Saito N (1982) Linear-time computability of combinatorial problems on series-parallel graphs. J ACM 29:623–641

    Article  Google Scholar 

  • Tamir A (1996) An \(O(pn^2)\) algorithm for the \(p\)-median and related problems on tree graphs. Oper Res Lett 19:59–64

    Article  Google Scholar 

  • Tamir A (1998) Fully polynomial approximation schemes for locating a tree-shaped facility: a generalization of the knapsack problem. Discrete Appl Math 87:229–243

    Article  Google Scholar 

  • Tamir A (2004) Sorting weighted distances with applications to objective function evaluations in single facility location problems. Oper Res Lett 32:249–257

    Article  Google Scholar 

  • Tamir A, Lowe TJ (1992) The generalized \(p\)-forest problem on a tree network. Networks 22:217–230

    Article  Google Scholar 

  • Tamir A, Puerto J, Pèrez-Brito D (2002) The centdian subtree on the tree networks. Discrete Appl Math 118:263–278

    Article  Google Scholar 

  • Tamir A, Puerto J, Mesa JA, Rodriguez-Chia AM (2005) Conditional location of path and tree shaped facilities on trees. J Algorithms 56:50–75

    Article  Google Scholar 

  • Tang H, Cheng TCE, Ng CT (2012) A note on the subtree ordered median problem in networks based on nestedness property. J Ind Manag Optim 8:41–49

    Article  Google Scholar 

  • 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

  • Wang B-F (1998) Finding a k-tree core and a k-tree center of a tree network in parallel. IEEE Trans Parallel Distrib Syst 9:186–191

    Article  Google Scholar 

  • Wang B-F (2000) 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

    Article  Google Scholar 

  • Wang B-F (2002) A 2-Core of a tree in Linear time. SIAM J Discrete Math 15:193–210

    Article  Google Scholar 

  • Wang B-F, Ku S-C, Shi K-H (2001) Cost-optimal parallel algorithms for the tree bisector and related problems. IEEE Trans Parallel Distrib Syst 12:888–898

    Article  Google Scholar 

  • Wang B-F, Peng S, Yu H-Y, Ku S-C (2006) Efficient algorithms for a constrained \(k\)-tree core problem in a tree network. J Algorithms 59:107–124

    Article  Google Scholar 

  • Wang B-F, Lin T-C, Lin C-H, Ku S-C (2008) Finding the conditional location of a median path on a tree. Inf Comput 206:828–839

    Article  Google Scholar 

  • 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

  • Ye J-H, Wang B-F (2015) On the minmax regret path median problem on trees. J Comput Syst Sci 81:1159–1170

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IMUS and Dept. Estadística e Investigación Operativa, Universidad de Sevilla, Seville, Spain

    Justo Puerto

  2. Università di Roma, La Sapienza, Rome, Italy

    Federica Ricca

  3. Università degli Studi Niccolò Cusano, Rome, Italy

    Andrea Scozzari

Authors
  1. Justo Puerto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Federica Ricca
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrea Scozzari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Justo Puerto.

Additional information

This research has been partially supported by Spanish Ministry of Economía and Competitividad/FEDER grant number MTM2016-74983-C02-01.

This invited paper is discussed in the comments available at https://doi.org/10.1007/s11750-018-0473-8, https://doi.org/10.1007/s11750-018-0474-7, and https://doi.org/10.1007/s11750-018-0475-6

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Puerto, J., Ricca, F. & Scozzari, A. Extensive facility location problems on networks: an updated review. TOP 26, 187–226 (2018). https://doi.org/10.1007/s11750-018-0476-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-018-0476-5

Keywords

Mathematics Subject Classification

Search

Navigation