IDEAS home Printed from https://ideas.repec.org/a/sae/envirb/v15y1988i2p181-190.html
   My bibliography  Save this article

A Multimedian Problem with Interdistance Constraints

Author

Listed:
  • E Erkut

    (Department of Finance and Management Science, Faculty of Business, University of Alberta, Edmonton, Canada T6G 2R6)

  • R L Francis

    (Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA)

  • T J Lowe

    (Krannert Graduate School of Management, Purdue University, West Lafayette, IN 47907, USA)

Abstract

The location of n new facilities on a network when the objective function is a sum of weighted distances between new and existing facilities, plus a sum of weighted distances between new facilities is studied. Interdistance constraints which impose upper bounds on distances between facilities have been included. A linear programming approach has been developed which solves the problem exactly on any spanning tree of the network, and which yields a lower bounding problem when the network is cyclic. The gap between the best spanning tree solution and the lower bound averages about 4% in the computational studies.

Suggested Citation

  • E Erkut & R L Francis & T J Lowe, 1988. "A Multimedian Problem with Interdistance Constraints," Environment and Planning B, , vol. 15(2), pages 181-190, June.
    • Handle: RePEc:sae:envirb:v:15:y:1988:i:2:p:181-190
    DOI: 10.1068/b150181
    as

    Download full text from publisher

    File URL: https://journals.sagepub.com/doi/10.1068/b150181
    Download Restriction: no
    File URL: https://libkey.io/10.1068/b150181?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. I. Douglas Moon & Sohail S. Chaudhry, 1984. "An Analysis of Network Location Problems with Distance Constraints," Management Science, INFORMS, vol. 30(3), pages 290-307, March.
    2. L. R. Ford, Jr. & D. R. Fulkerson, 1958. "A Suggested Computation for Maximal Multi-Commodity Network Flows," Management Science, INFORMS, vol. 5(1), pages 97-101, October.
    3. David J. Eaton & Mark S. Daskin & Dennis Simmons & Bill Bulloch & Glen Jansma, 1985. "Determining Emergency Medical Service Vehicle Deployment in Austin, Texas," Interfaces, INFORMS, vol. 15(1), pages 96-108, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Batta, Rajan & Lejeune, Miguel & Prasad, Srinivas, 2014. "Public facility location using dispersion, population, and equity criteria," European Journal of Operational Research, Elsevier, vol. 234(3), pages 819-829.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Batta, Rajan & Lejeune, Miguel & Prasad, Srinivas, 2014. "Public facility location using dispersion, population, and equity criteria," European Journal of Operational Research, Elsevier, vol. 234(3), pages 819-829.
    2. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    3. P. Daniel Wright & Matthew J. Liberatore & Robert L. Nydick, 2006. "A Survey of Operations Research Models and Applications in Homeland Security," Interfaces, INFORMS, vol. 36(6), pages 514-529, December.
    4. Lagergren, Marten, 1998. "What is the role and contribution of models to management and research in the health services? A view from Europe," European Journal of Operational Research, Elsevier, vol. 105(2), pages 257-266, March.
    5. Averbakh, Igor & Berman, Oded, 1996. "Locating flow-capturing units on a network with multi-counting and diminishing returns to scale," European Journal of Operational Research, Elsevier, vol. 91(3), pages 495-506, June.
    6. Huizhu Wang & Jianqin Zhou & Ling Zhou, 2024. "A Lattice Boltzmann Method-like Algorithm for the Maximal Covering Location Problem on the Complex Network: Application to Location of Railway Emergency-Rescue Spot," Mathematics, MDPI, vol. 12(2), pages 1-20, January.
    7. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    8. Wajid, Shayesta & Nezamuddin, N., 2023. "Capturing delays in response of emergency services in Delhi," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    9. Juan Villegas & Fernando Palacios & Andrés Medaglia, 2006. "Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example," Annals of Operations Research, Springer, vol. 147(1), pages 109-141, October.
    10. Cihan Çetinkaya & Samer Haffar, 2018. "A Risk-Based Location-Allocation Approach for Weapon Logistics," Logistics, MDPI, vol. 2(2), pages 1-15, May.
    11. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    12. Wajid, Shayesta & Nezamuddin, N., 2022. "A robust survival model for emergency medical services in Delhi, India," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    13. Pablo Adasme & Ali Dehghan Firoozabadi, 2019. "Facility Location with Tree Topology and Radial Distance Constraints," Complexity, Hindawi, vol. 2019, pages 1-29, November.
    14. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    15. Fabio Vitor & Todd Easton, 2018. "The double pivot simplex method," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 109-137, February.
    16. Jing Yao & Alan T. Murray, 2014. "Locational Effectiveness of Clinics Providing Sexual and Reproductive Health Services to Women in Rural Mozambique," International Regional Science Review, , vol. 37(2), pages 172-193, April.
    17. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    18. Desaulniers, G. & Desrosiers, J. & Dumas, Y. & Marc, S. & Rioux, B. & Solomon, M. M. & Soumis, F., 1997. "Crew pairing at Air France," European Journal of Operational Research, Elsevier, vol. 97(2), pages 245-259, March.
    19. Erkut, E. & ReVelle, C. & Ulkusal, Y., 1996. "Integer-friendly formulations for the r-separation problem," European Journal of Operational Research, Elsevier, vol. 92(2), pages 342-351, July.
    20. Downs, Joni A. & Gates, Robert J. & Murray, Alan T., 2008. "Estimating carrying capacity for sandhill cranes using habitat suitability and spatial optimization models," Ecological Modelling, Elsevier, vol. 214(2), pages 284-292.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:sae:envirb:v:15:y:1988:i:2:p:181-190. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: SAGE Publications (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.