Single-facility location problems with barriers

Publication date 20 January 2003

barriers continuous location single facility location

Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Continuous location (90B85)

Review text

The book almost exclusively deals with continuous location problems, where only one new facility is to be located such that an objective function considering distances from the located facility to some existing facilities be minimal. This problem is studied here with many modifications and under a broad spectrum of constraints. The modifications are represented by various gauges and the associated ways, how to measure the distance between two facilities. The constraints include various forms of obstacles, which can occur on the way from a facility to other one. Arbitrary shaped regions, which cannot be throughpassed and in which no facility can be placed, may represent the obstacles. These obstacles are referred as barriers on the contrary to forbidden regions, which can be traversed but not used for location. The book is divided into four parts and eleven chapters. The first chapter introduces general terms, definitions and lemmas concerning block norms and polyhedral distance functions with stress on polyhedral gauges in a two-dimensional Euclidean space. The second chapter deals with the visibility in the space with various types of gauges. Then optimality conditions for the shortest path in the space with smooth barriers are stated. These conditions are based on Euler-Lagrange differential equations. At the end of the chapter, the special barrier touching property for polyhedral barriers in a plane is derived. The next chapter provides an overview of the location problems with and without barriers, forbidden and congested regions. Furthermore, location problem classification is introduced here and the visibility graph defined, including discussion on computational complexity of the associated algorithms. In the fourth chapter, the main principles of lower and upper bound computation are explained. To obtain a lower bound of the location problem with barrier regions, simple relaxation consisting in barrier discarding is used. To get an upper bound for the location problem with forbidden regions, the restriction of the problem to a problem with barrier regions is used. When an upper bound of the problem with barriers is sought for, the optimal solution of a location problem defined on visibility graph may be used. The fifth chapter contains an approach to solving the location problem with polyhedral barriers. The approach makes use of a visibility grid, segments of which are given by linear borders of all shadow regions formed for each existing facility and each extreme point of barriers. This grid decomposes a plane into a number of cells. An optimality condition for points from a cell interior is derived and it is shown that the location problem in a cell can be reformulated as an unconstrained location problem. Then an algorithm for optimal solution is suggested, which comprises search over grid segments and over cell interiors. It is shown that the algorithm can be simplified by introducing a finite set of sample points. The optimalization problem for one cell is formulated as a mixed integer problem and possible simplification of the algorithm is derived for Weber objective function. Some features of multifacility Weber problems are discussed at the end of this chapter. In the sixth chapter the continuous location problem with one circle barrier is solved. It is proved that the Euclidean distance function remains convex on any cell of the visibility grid and an exact algorithm is derived there, which searches for the optimal location of a facility over each cell of the visibility grid. This algorithm solves a convex optimisation problem on each cell. In addition a heuristic algorithm is suggested here. In the seventh chapter, the author solves the line barrier problem with a finite number of passages. She explains the associated principle on the cases with one, two and \(N\) passages gradually. The principle is based on generating a set of unconstrained location problems, which are solved for existing facilities from one of the half-planes and for surrogate facilities corresponding to passages, in the weights of which contributions of facilities from the other half-pane are included. The best solution of the unconstrained problems is declared to be the resulting solution of the original problem. The eighth chapter is focused on Weber problems with block norm and polyhedral barriers. It is proved that it is possible to construct in polynomial time such a grid that an optimal location must be contained in the set of intersection points of the grid. Furthermore, it is shown that the problem could be considerably reduced, if only points from the convex hull of the existing facilities and extreme points of barriers are considered. In chapter nine the centre problem with Manhattan metric is studied. Comparing this problem with the Weber problem with block norms, many issues concerning a dominating set do not hold here. Nevertheless, it is proved that even in this case, there exists a dominating set of feasible solutions and the optimal solution can be found in an intersection of a weighted bisector of two facilities and the grid or in an intersection of two weighted bisectors determined by a triple of the existing facilities. This issue allows to construct polynomial algorithm for the problem. At the end of this chapter a generalization of the approach to a broader class of metrics is suggested. The tenth chapter deals with the multiobjective location problem, when an efficient (Pareto) solution is sought for a set of objective functions. For each of these objectives a different metric can be used. The suggested approach is based on the decomposition of the plane into a set of cells into accordance to visibility taking into consideration all used metrics. This way the original problem can be substituted by a set of convex subproblems, which can be solved for an individual objective function. This process yields a set of nondominated points in the objective space for each subproblem. This approach is improved for bicriteria problems, where the reduction of the dominated set is employed. The last chapter reports on a problem from practice, where the theoretical issues from the previous chapters are demonstrated. The problem consists in placing a playground location into a developing residential area, where existing facilities are represented by eighteen building blocks and their weights are proportional to the numbers of children living in them. There is a transport obstacle formed by a highway intersecting the area. The problem is solved as bicriterial Weber problem for a first case, when the playground location is restricted only by the barrier and by one forbidden area and for a second case, when the location is restricted to a rectangular area owned by the city. At the end of the chapter, the problem is also studied as a centre problem and all results obtained are compared. In conclusion, this book gives a broad and excellent overview on the continuous location problems with barriers and their solution algorithms.

Recommendations

Cited in

(43)

This page was built for publication: Single-facility location problems with barriers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4788111)