IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v63y2015i2p394-411.html

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. 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.
    2. 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.
    3. 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.
    4. B. Curtis Eaton & Richard G. Lipsey, 1975. "The Principle of Minimum Differentiation Reconsidered: Some New Developments in the Theory of Spatial Competition," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 42(1), pages 27-49.
    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. 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. 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.
    3. 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.
    4. Thomas Byrne, 2022. "The Stackelberg Game: responses to regular strategies," Papers 2211.06472, arXiv.org.

    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. 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.
    3. 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.
    4. 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.
    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. Drezner, Zvi & Eiselt, H.A., 2024. "Competitive location models: A review," European Journal of Operational Research, Elsevier, vol. 316(1), pages 5-18.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Benček, David, 2016. "Opportunistic candidates and knowledgeable voters: A recipe for extreme views," Kiel Working Papers 2047, Kiel Institute for the World Economy.
    12. Abdullah Dasci & Gilbert Laporte, 2005. "A Continuous Model for Multistore Competitive Location," Operations Research, INFORMS, vol. 53(2), pages 263-280, April.
    13. Ricardo Biscaia & Isabel Mota, 2013. "Models of spatial competition: A critical review," Papers in Regional Science, Wiley Blackwell, vol. 92(4), pages 851-871, November.
    14. Hanaki, Nobuyuki & Tanimura, Emily & Vriend, Nicolaas J., 2019. "The Principle of Minimum Differentiation revisited: Return of the median voter," Journal of Economic Behavior & Organization, Elsevier, vol. 157(C), pages 145-170.
    15. Tsakas, Nikolas & Xefteris, Dimitrios, 2018. "Electoral competition with third party entry in the lab," Journal of Economic Behavior & Organization, Elsevier, vol. 148(C), pages 121-134.
    16. Kocenda, Evzen & Hanousek, Jan & Engelmann, Dirk, 2008. "Currencies, competition, and clans," Journal of Policy Modeling, Elsevier, vol. 30(6), pages 1115-1132.
    17. Sengupta, Abhijit & Sengupta, Kunal, 2008. "A Hotelling-Downs model of electoral competition with the option to quit," Games and Economic Behavior, Elsevier, vol. 62(2), pages 661-674, March.
    18. Berno Buechel, 2014. "Condorcet winners on median spaces," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 735-750, March.
    19. Jason G. Cummins & Ingmar Nyman, 2005. "The Dark Side of Competitive Pressure," RAND Journal of Economics, The RAND Corporation, vol. 36(2), pages 361-397, Summer.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    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: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.