Facility location problems and games

Abstract

We concern ourselves with facility location problems and games wherein we must decide upon the optimal locating of facilities. A facility is considered to be any physical location to which customers travel to obtain a service, or from which an agent of the facility travels to customers to deliver a service. We model facilities by points without a capacity limit and assume that customers obtain (or are provided with) their service from the closest facility. Throughout this thesis we consider distance to be measured exclusively using the Manhattan metric, a natural choice in urban settings and also in scenarios arising from clustering for data analysis with heterogeneous dimensions. Additionally we always model the demand for the facility as continuously and uniformly distributed over some convex polygonal demand region P and it is only within P that we consider locating our facilities.We first consider five 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 begin 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 an exact polynomial-time algorithm that makes use of a triangular decomposition of the incremental Voronoi diagram and the first order optimality conditions.Following this we study competitive location problems in a continuous setting, in which the first player (''White'') places a set of n points in a rectangular domain P of width p and height q, followed by the second player (''Black''), who places the same number of points. Players cannot place points atop one another, nor can they move a point once it has been placed, and after all 2n points have been played each player wins the fraction of the board for which one of their points is closest. The goal for each player in the One-Round Voronoi Game is to score more than half of the area of P, and that of the One-Round Stackelberg Game is to maximise one's total area. Even in the more diverse setting of Manhattan distances, we determine a complete characterisation for the One-Round Voronoi Game wherein White can win only if p/q >= n, otherwise Black wins, and we show each player's winning strategies. For the One-Round Stackelberg Game we explore arrangements of White's points in which the Voronoi cells of individual facilities are equalised with respect to a number of attractive geometric properties such as fairness (equally-sized Voronoi cells) and local optimality (symmetrically balanced Voronoi cell areas), and explore each player's best strategy under certain conditions.