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

Igor Averbakh (), Oded Berman (), Jörg Kalcsics () and Dmitry Krass ()
Additional contact information
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

Operations Research, 2015, vol. 63, issue 2, 394-411

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.

Keywords: continuous facilities location; Voronoi diagrams; median problem; market share problem; covering problem (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1354 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:2:p:394-411

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().