The problem of finding optimal locations for a set of service facilities is of strategic importance, and has generated a large body of research literature. In most models customer demand is assumed to be discrete and aggregated to a relatively small number of points. However, in many urban applications the number of potential customers can be in the millions and representing every customer residence as a separate demand point is usually infeasible. Thus, it may be more accurate to represent customer demand as continuously distributed over some region.
In this talk we consider two different location models. In the first, the demand is uniformly distributed over a convex polygon in the rectilinear plane, facilities can be located anywhere in the polygon, and customers obtain service from the closest open facility. We focus on conditional location problems where several facilities are already open and the goal is to choose optimally a location for an additional (new) facility. Assuming that customers obtain service from the closest open facility, the demand space can be partitioned into regions called "Voronoi cells"; the resulting partition is known as the "Voronoi diagram". The main difficulty is that it is generally impossible to represent the objective function in closed form. In fact, the representation of the objective function depends on the structure of the Voronoi diagram, i.e., the position and the geometry of the cell boundaries. Unfortunately, this structure can change drastically with the location of the "free" facility, making the underlying optimization problems quite difficult. To solve the problem, we derive structural properties of Voronoi diagrams for the rectilinear distances and show how to use them to identify sub-regions where the representation of the objective function is valid for any location in the region.
In the second model, the demand is continuously distributed along the edges of a network. Starting with the single facility problem, we first show that the finite dominating set for the node covering problem does not carry over to the case of edge demands. Afterwards, we present a solution approach for arbitrary demand functions and discuss some special cases. Next, we focus on the multi-facility problem under the assumption that the demand is constant on each edge. We present several discretization results for tree networks and show that these results do not carry over to general networks.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
