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

• 成果类型: Article
• 署名作者: Averbakh, Igor; Berman, Oded; Kalcsics, Joerg; Krass, Dmitry
• 署名单位: University of Toronto; University Toronto Scarborough; University of Toronto; Helmholtz Association; Karlsruhe Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1354
• 发表日期: 2015
• 页码: 394-411
• 关键词: Allocation problem; algorithm; SPACE; FIRMS

摘要

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.