Conditional facility location problems with continuous demand and a polygonal barrier

Thomas Byrne*, Jörg Kalcsics

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
61 Downloads (Pure)

Abstract

We consider facility location problems where n facilities are present in a convex polygon in the rectilinear plane, over which continuous and uniform demand is distributed and within which a convex polygonal barrier is located (removing all demand and preventing all travel within the barrier), and the optimal location for an additional facility is sought. We start with an in-depth analysis of the representation of the bisectors of two facilities affected by the barrier and how it is affected by the position of the additional facility. Following this, a detailed investigation into the changes in the structure of the Voronoi diagram caused by the movement of this additional facility, which governs the form of the objective function for numerous facility location problems, yields a set of linear constraints for a general convex barrier that partitions the market space into a finite number of regions within which the exact solution can be found in polynomial time. This allows us to formulate a polynomial exact algorithm that makes use of a triangular decomposition of the incremental Voronoi diagram and the first order optimality conditions.

Original languageEnglish
Pages (from-to)22-43
Number of pages22
JournalEuropean Journal of Operational Research
Volume296
Issue number1
Early online date16 Feb 2021
DOIs
Publication statusPublished - 1 Jan 2022

Keywords

  • barriers
  • location
  • planar facility location
  • spatial demand
  • Voronoi diagrams

Fingerprint

Dive into the research topics of 'Conditional facility location problems with continuous demand and a polygonal barrier'. Together they form a unique fingerprint.

Cite this