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. 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.
    2. 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.
    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. Alan T. Murray, 2016. "Maximal Coverage Location Problem," International Regional Science Review, , vol. 39(1), pages 5-27, January.
    3. 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.
    4. Alan T. Murray & Ran Wei & Richard L. Church & Matthew R. Niblett, 2019. "Addressing risks and uncertainty in forest land use modeling," Journal of Geographical Systems, Springer, vol. 21(3), pages 319-338, September.
    5. 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.
    6. Lorenz M. Roebers & Aras Selvi & Juan C. Vera, 2018. "Using Column Generation to Solve Extensions to the Markowitz Model," Papers 1812.00093, arXiv.org, revised Jun 2019.
    7. 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.
    8. Ana Iannoni & Reinaldo Morabito & Cem Saydam, 2008. "A hypercube queueing model embedded into a genetic algorithm for ambulance deployment on highways," Annals of Operations Research, Springer, vol. 157(1), pages 207-224, January.
    9. 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.
    10. 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.
    11. 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.
    12. Attila Bernáth & Tamás Király & Erika Kovács & Gergely Mádi-Nagy & Gyula Pap & Júlia Pap & Jácint Szabó & László Végh, 2013. "Algorithms for multiplayer multicommodity flow problems," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(4), pages 699-712, December.
    13. Wajid, Shayesta & Nezamuddin, N., 2023. "Capturing delays in response of emergency services in Delhi," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    14. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    15. 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.
    16. Cihan Çetinkaya & Samer Haffar, 2018. "A Risk-Based Location-Allocation Approach for Weapon Logistics," Logistics, MDPI, vol. 2(2), pages 1-15, May.
    17. Yaw Asiedu & Mark Rempel, 2011. "A multiobjective coverage‐based model for Civilian search and rescue," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(3), pages 167-179, April.
    18. Alan T Murray & Ran Wei & Tony H Grubesic, 2014. "An Approach for Examining Alternatives Attributable to Locational Uncertainty," Environment and Planning B, , vol. 41(1), pages 93-109, February.
    19. 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.
    20. Wajid, Shayesta & Nezamuddin, N., 2022. "A robust survival model for emergency medical services in Delhi, India," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).

    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.