[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Locating facilities which interact: Some solvable cases

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The network version of them-median problem with mutual communication (MMMC) is to find the location ofm new facilities on a network withn nodes such that the sum of (a) the cost of interaction between the new facilities andn existing facilities on the network, and (b) the cost of interaction between pairs of new facilities is minimized. The existing facilities are located at nodes of the network and the interaction cost between a pair of facilities is a function of the network distance between the facilities. This problem is shown to be equivalent to a graph-theoretic Node Selection Problem (NSP). We show that many other problems can be formulated as an NSP. We then provide a polynomial time algorithm to solve NSP for the case when the flow graph is Halin. Extensions to other graph families are provided.

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

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. R.G. Askin and J.B. Goldberg, Economic optimization in product design, Eng. Opt. 14(1988)139–152.

    Article  Google Scholar 

  2. F. Barahona, A solvable case of quadratic 0–1 programming, Discr. Appl. Math. 13(1986)23–26.

    Article  Google Scholar 

  3. R.E. Bixby and D.K. Wagner, An almost linear-time algorithm for graph realization, Math. Oper. Res. 13(1988)99–123.

    Article  Google Scholar 

  4. D. Chhajed and T.J. Lowe, Solving structured multifacility location problems efficiently, Transp. Sci. (1993), to appear.

  5. D. Chhajed and T.J. Lowe,M-median andM-center problems with mutual communication: Solvable special cases, Oper. Res. 40(1992)S56-S66.

    Article  Google Scholar 

  6. D.G. Corneil and J.M. Keil, A dynamic programming approach to the dominating set problem onK-trees, SIAM J. Alg. Discr. Meth. 8(1987)535–543.

    Article  Google Scholar 

  7. P.M. Dearing, R.L. Francis and T.J. Lowe, Convex location problems on tree networks, Oper. Res. 24(1976)628–642.

    Article  Google Scholar 

  8. S.E. Eriksen and P.D. Berger, A quadratic programming model for product configuration optimization, Zeits. Oper. Res. 31(1987)B143-B159.

    Article  Google Scholar 

  9. E. Erkut, R.L. Francis and T.J. Lowe, A multimedian problem with interdistance constraints, Environ. Planning B: Planning and Design 15(1988)181–190

    Article  Google Scholar 

  10. E. Erkut, R.L. Francis, T.J. Lowe and A. Tamir, Equivalent mathematical programming formulations of monotonic tree network location problems, Oper. Res. 37(1989)447–461.

    Article  Google Scholar 

  11. R.L. Francis, T.J. Lowe and H.D. Ratliff, Distance constraints for tree network multifacility location problems, Oper. Res. 26(1978)570–596.

    Article  Google Scholar 

  12. J.E. Hopcroft and R.E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2(1973)135–158.

    Article  Google Scholar 

  13. A. Kolen, Location problems on trees and in the rectilinear plane, Stichting Mathematisch Centrum, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands (1982).

  14. R.L. Lipton and R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36(1979)177–189.

    Article  Google Scholar 

  15. R.J. Lipton and R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Comput. 9(1980)615–627.

    Article  Google Scholar 

  16. P.M. Pardalos and S. Jha, Graph separation techniques for quadratic zero-one programming (1990), Computer Science Department, The Pennsylvania State University, to appear in Comput. Math. Appl.

  17. J.-C. Picard and H.D. Ratliff, A cut approach to the rectilinear distance facility location problem, Oper. Res. 28(1978)422–433.

    Article  Google Scholar 

  18. T.V. Wimer, Linear algorithms onk-terminal graphs, Report No. URI-030, Clemson University (1987).

  19. Y. Xu, R.L. Francis and T.J. Lowe, The multimedian problem on a network: Exploiting block structure, Working Paper, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL (1988).

    Google Scholar 

  20. W. Domschke, Schedule synchronization for public transit networks, OR Spektrum 11(1989)17–24.

    Article  Google Scholar 

  21. M.B. Richey, Optimal location of a path or tree on a network with cycles, Working Paper, George Mason University, Fairfax, VA (1989).

    Google Scholar 

  22. G. Cornuejols, D. Naddef and W. Pulleyblank, The traveling salesman problem in graphs with 3-edge cutsets, J. ACM 32(1985)383–410.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chhajed, D., Lowe, T.J. Locating facilities which interact: Some solvable cases. Ann Oper Res 40, 101–124 (1992). https://doi.org/10.1007/BF02060472

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02060472

Keywords

Navigation