IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v63y2015i2p394-411.html
   My bibliography  Save this article

Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand

Author

Listed:
  • Igor Averbakh

    (Department of Management, University of Toronto Scarborough, Toronto, Ontario M1C 1A4, Canada)

  • Oded Berman

    (Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

  • Jörg Kalcsics

    (Institute of Operations Research, Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany)

  • Dmitry Krass

    (Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

Abstract

We consider facility location problems where the demand is continuously and uniformly distributed over a convex polygon with m vertices in the rectilinear plane, n facilities are already present, and the goal is to find an optimal location for an additional facility. Based on an analysis of structural properties of incremental Voronoi diagrams, we develop polynomial exact algorithms for five conditional location problems. The developed methodology is applicable to a variety of other facility location problems with continuous demand. Moreover, we briefly discuss the Euclidean case.

Suggested Citation

  • Igor Averbakh & Oded Berman & Jörg Kalcsics & Dmitry Krass, 2015. "Structural Properties of Voronoi Diagrams in Facility Location Problems with Continuous Demand," Operations Research, INFORMS, vol. 63(2), pages 394-411, April.
    • Handle: RePEc:inm:oropre:v:63:y:2015:i:2:p:394-411
    DOI: 10.1287/opre.2015.1354
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2015.1354
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2015.1354?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. B. Curtis Eaton & Richard G. Lipsey, 1975. "The Principle of Minimum Differentiation Reconsidered: Some New Developments in the Theory of Spatial Competition," Review of Economic Studies, Oxford University Press, vol. 42(1), pages 27-49.
    2. A. Jourani & C. Michelot & M. Ndiaye, 2009. "Efficiency for continuous facility location problems with attraction and repulsion," Annals of Operations Research, Springer, vol. 167(1), pages 43-60, March.
    3. Sándor P. Fekete & Joseph S. B. Mitchell & Karin Beurer, 2005. "On the Continuous Fermat-Weber Problem," Operations Research, INFORMS, vol. 53(1), pages 61-76, February.
    4. Tom M. Cavalier & Hanif D. Sherali, 1986. "Euclidean Distance Location-Allocation Problems with Uniform Demands over Convex Polygons," Transportation Science, INFORMS, vol. 20(2), pages 107-116, May.
    5. Aoyagi, Masaki & Okabe, Atsuyuki, 1993. "Spatial competition of firms in a two-dimensional bounded market," Regional Science and Urban Economics, Elsevier, vol. 23(2), pages 259-289, April.
    6. Atsuyuki Okabe & Masaki Aoyagi, 1991. "Existence of equilibrium configurations of competitive firms on an infinite two-dimensional space," Journal of Urban Economics, Elsevier, vol. 29(3), pages 349-370, May.
    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. Bouchery, Yann & Woxenius, Johan & Fransoo, Jan C., 2020. "Identifying the market areas of port-centric logistics and hinterland intermodal transportation," European Journal of Operational Research, Elsevier, vol. 285(2), pages 599-611.
    2. Thomas Byrne, 2022. "The Stackelberg Game: responses to regular strategies," Papers 2211.06472, arXiv.org.
    3. Thomas Byrne & Sándor P. Fekete & Jörg Kalcsics & Linda Kleist, 2023. "Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game," Annals of Operations Research, Springer, vol. 321(1), pages 79-101, February.
    4. Byrne, Thomas & Kalcsics, Jörg, 2022. "Conditional facility location problems with continuous demand and a polygonal barrier," European Journal of Operational Research, Elsevier, vol. 296(1), pages 22-43.

    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. Thomas Byrne & Sándor P. Fekete & Jörg Kalcsics & Linda Kleist, 2023. "Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game," Annals of Operations Research, Springer, vol. 321(1), pages 79-101, February.
    2. Huck, Steffen & Knoblauch, Vicki & Muller, Wieland, 2003. "On the profitability of collusion in location games," Journal of Urban Economics, Elsevier, vol. 54(3), pages 499-510, November.
    3. Knoblauch, Vicki, 2002. "An Easy Proof That a Square Lattice Is an Equilibrium for Spatial Competition in the Plane," Journal of Urban Economics, Elsevier, vol. 51(1), pages 46-53, January.
    4. Byrne, Thomas & Kalcsics, Jörg, 2022. "Conditional facility location problems with continuous demand and a polygonal barrier," European Journal of Operational Research, Elsevier, vol. 296(1), pages 22-43.
    5. Daniel Strobach, 2006. "Competition between airports with an application to the state of Baden-Württemberg," Diskussionspapiere aus dem Institut für Volkswirtschaftslehre der Universität Hohenheim 272/2006, Department of Economics, University of Hohenheim, Germany.
    6. Dodge Cahan & Hongjia H. Chen & Louis Christie & Arkadii Slinko, 2021. "Spatial competition on 2-dimensional markets and networks when consumers don’t always go to the closest firm," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(4), pages 945-970, December.
    7. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    8. Dominic Keehan & Dodge Cahan & John McCabe-Dansted & Arkadii Slinko, 2022. "Equilibria on a circular market when consumers do not always buy from the closest firm," Review of Economic Design, Springer;Society for Economic Design, vol. 26(3), pages 285-306, September.
    9. Benček, David, 2016. "Opportunistic candidates and knowledgeable voters: A recipe for extreme views," Kiel Working Papers 2047, Kiel Institute for the World Economy (IfW Kiel).
    10. Bertrand Ottino-Loffler & Forrest Stonedahl & Vipin Veetil & Uri Wilensky, 2017. "Spatial Competition with Interacting Agents," International Journal of Microsimulation, International Microsimulation Association, vol. 10(3), pages 75-91.
    11. Abdullah Dasci & Gilbert Laporte, 2005. "A Continuous Model for Multistore Competitive Location," Operations Research, INFORMS, vol. 53(2), pages 263-280, April.
    12. Kocenda, Evzen & Hanousek, Jan & Engelmann, Dirk, 2008. "Currencies, competition, and clans," Journal of Policy Modeling, Elsevier, vol. 30(6), pages 1115-1132.
    13. Borenstein, Severin & Netz, Janet, 1999. "Why do all the flights leave at 8 am?: Competition and departure-time differentiation in airline markets," International Journal of Industrial Organization, Elsevier, vol. 17(5), pages 611-640, July.
    14. H Kohsaka, 1989. "An Analysis of Competitive Oscillations between Japanese Twin Cities," Environment and Planning A, , vol. 21(6), pages 803-816, June.
    15. Mohajan, Devajit & Mohajan, Haradhan, 2023. "The Responses of an Organization for the Increase in Wage Rates: Profit Maximization Cases," MPRA Paper 118238, University Library of Munich, Germany, revised 10 Jun 2023.
    16. Daoqin Tong & Alan T. Murray, 2009. "Maximising coverage of spatial demand for service," Papers in Regional Science, Wiley Blackwell, vol. 88(1), pages 85-97, March.
    17. Dimitrios Xefteris, 2018. "Candidate valence in a spatial model with entry," Public Choice, Springer, vol. 176(3), pages 341-359, September.
    18. Shino, Junnosuke & Kawasaki, Ryo, 2012. "Farsighted stable sets in Hotelling’s location games," Mathematical Social Sciences, Elsevier, vol. 63(1), pages 23-30.
    19. Peter Chinloy & James Musumeci, 1994. "Shopping Center Financing: Pricing Loan Default Risk," Journal of Real Estate Research, American Real Estate Society, vol. 9(1), pages 49-64.
    20. Salvanes, Kjell G. & Steen, Frode & Sorgard, Lars, 2005. "Hotelling in the air? Flight departures in Norway," Regional Science and Urban Economics, Elsevier, vol. 35(2), pages 193-213, March.

    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:inm:oropre:v:63:y:2015:i:2:p:394-411. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.