Rectilinear distance to a facility in the presence of a square barrier

This paper derives analytical expressions for the rectilinear distance to a facility in the presence of a square barrier. The distribution of the barrier distance is derived for two regular patterns of facilities: square and diamond lattices. This distribution, which provides all the information about the barrier distance, will be useful for facility location problems with barriers and reliability analysis of facility location. The distribution of the barrier distance demonstrates how the location and the size of the barrier affect the barrier distance. A?numerical example shows that the total barrier distance increases as the barrier gets closer to a facility, whereas the maximum barrier distance increases as the barrier becomes greater in size.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

Efficient Location for a Semi-Obnoxious Facility

This paper deals with a location model for the placement of a semi-obnoxious facility in a continuous plane with the twin objectives of maximizing the distance to the nearest inhabitant and minimizing the sum of distances to all the users (or the distance to the farthest user) in a unified manner. For special cases, this formulation includes (1) elliptic maximin and rectangular minisum criteria problem, and (2) rectangular maximin and minimax criteria problem. Polynomial-time algorithms for finding the efficient set and the tradeoff curve are presented.     

Planar weber location problems with line barriers

The Weber problem for a given finite set of existing facilities in the plane is to find the location of a new facility such that the weithted sum of distances to the existing facilities is minimized.

A variation of this problem is obtained if the existing facilities are situated on two sides of a linear barrier. Such barriers like rivers, highways, borders or mountain ranges are frequently encountered in practice.

Structural results as well as algorithms for this non-convex optimization problem depending on the distance function and on the number and location of passages through the barrier are presented.     

Locating an axis-parallel rectangle on a Manhattan plane

In this paper we consider the problem of locating an axis-parallel rectangle in the plane such that the sum of distances between the rectangle and a finite point set is minimized, where the distance is measured by the Manhattan norm ? ₁. In this way we solve an extension of the Weber problem to extensive facility location. As a model, our problem is appropriate for position sensing of rectangular objects.     

On the Weber facility location problem with limited distances and side constraints

The objective in the continuous facility location problem with limited distances is to minimize the sum of distance functions from the facility to the customers, but with a limit on each of the distances, after which the corresponding function becomes constant. The problem has applications in situations where the service provided by the facility is insensitive after a given threshold distance. In this paper, we propose a global optimization algorithm for the case in which there are in addition lower and upper bounds on the numbers of customers served.     

The expropriation location problem

In this paper, we consider the location of a new obnoxious facility that serves only a certain proportion of the demand. Each demand point can be bought by the developer at a given price. An expropriation budget is given. Demand points closest to the facility are expropriated within the given budget. The objective is to maximize the distance to the closest point not expropriated. The problem is formulated and polynomial algorithms are proposed for its solution both on the plane and on a network.     

A multi-objective integrated facility location-hardening model: Analyzing the pre- and post-disruption tradeoff

Two methods of reducing the risk of disruptions to distribution systems are (1) strategically locating facilities to mitigate against disruptions and (2) hardening facilities. These two activities have been treated separately in most of the academic literature. This article integrates facility location and facility hardening decisions by studying the minimax facility location and hardening problem (MFLHP), which seeks to minimize the maximum distance from a demand point to its closest located facility after facility disruptions. The formulation assumes that the decision maker is risk averse and thus interested in mitigating against the facility disruption scenario with the largest consequence, an objective that is appropriate for modeling facility interdiction. By taking advantage of the MFLHP’s structure, a natural three-stage formulation is reformulated as a single-stage mixed-integer program (MIP). Rather than solving the MIP directly, the MFLHP can be decomposed into sub-problems and solved using a binary search algorithm. This binary search algorithm is the basis for a multi-objective algorithm, which computes the Pareto-efficient set for the pre- and post-disruption maximum distance. The multi-objective algorithm is illustrated in a numerical example, and experimental results are presented that analyze the tradeoff between objectives.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

Continuous covering and cooperative covering problems with a general decay function on networks

A cooperative covering location problem anywhere on the networks is analysed. Each facility emits a signal that decays by the distance along the arcs of the network and each node observes the total signal emitted by all facilities. A node is covered if its cumulative signal exceeds a given threshold. The cooperative approach differs from traditional covering models where the signal from the closest facility determines whether or not a point is covered. The objective is to maximize coverage by the best location of facilities anywhere on the network. The problems are formulated and analysed. Optimal algorithms for one or two facilities are proposed. Heuristic algorithms are proposed for location of more than two facilities. Extensive computational experiments are reported.     

Fixed Point Optimality Criteria for the Location Problem with Arbitrary Norms

The single-facility location problem in continuous space is considered, with distances given by arbitrary norms. When distances are Euclidean, for many practical problems the optimal location of the new facility coincides with one of the existing facilities. This property carries over to problems with generalized distances. In this paper a necessary and sufficient condition for the location of an existing facility to be the optimal location of the new facility is developed. Some computational examples using the condition are given.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.     

The minimum equitable radius location problem with continuous demand

We analyze the location of p facilities satisfying continuous area demand. Three objectives are considered: (i) the p-center objective (to minimize the maximum distance between all points in the area and their closest facility), (ii) equalizing the load service by the facilities, and (iii) the minimum equitable radius – minimizing the maximum radius from each point to its closest facility subject to the constraint that each facility services the same load. The paper offers three contributions: (i) a new problem – the minimum equitable radius is presented and solved by an efficient algorithm, (ii) an improved and efficient algorithm is developed for the solution of the p-center problem, and (iii) an improved algorithm for the equitable load problem is developed. Extensive computational experiments demonstrated the superiority of the new solution algorithms.     

Using a Facility Location Algorithm to Determine Optimum Cast Bloom Lengths

The dimensions of a bloom, which is a rectangular piece of steel, are critical for efficiently and effectively rolling the bloom into a finished structural shape (I-beam) for sale to the customer. To achieve maximum productivity and yield, the bloom size (thickness, width and length) to be rolled on a finishing mill into a structural shape must be determined by steel deformation experts. Suppose, for a particular finishing mill, these ‘rolled' blooms are all produced from a ‘cast' bloom of the same cross-section but with many different lengths. It is necessary to consolidate the many ‘cast' bloom length-metallurgical grade combinations to a number that can be managed by the casting operation and bloom stockyard without significantly impacting productivity and yield. An uncapacitated facility location problem formulation and algorithm were used to solve this problem. The way in which this approach was used to solve a real-world application is discussed.     

Algorithms for central-median paths with bounded length on trees

The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. In the literature, there is just one paper that considers the problem of finding an optimal location of a path on a tree using combinations of the two above criteria, and efficient algorithms are provided. In particular, the cases where one criterion is optimized subject to a restriction on the value of the other are considered and linear time algorithms are presented. However, these problems do not consider any bound on the length or cost of the facility. In this paper we consider the two following problems: find a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; find a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. From an application point of view the constraint on the length of the path may refer to a budget constraint for establishing the facility. The restriction on the length of the path complicates the two problems but for both of them we give O(n log² n) divide-and-conquer algorithms.     

Placing a finite size facility with a center objective on a rectangular plane with barriers

This paper addresses the finite size 1-center placement problem on a rectangular plane in the presence of barriers. Barriers are regions in which both facility location and travel through are prohibited. The feasible region for facility placement is subdivided into cells along the lines of Larson and Sadiq [R.C. Larson, G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research 31 (4) (1983) 652–669]. To overcome complications induced by the center (minimax) objective, we analyze the resultant cells based on the cell corners. We study the problem when the facility orientation is known a priori. We obtain domination results when the facility is fully contained inside 1, 2 and 3-cornered cells. For full containment in a 4-cornered cell, we formulate the problem as a linear program. However, when the facility intersects gridlines, analytical representation of the distance functions becomes challenging. We study the difficulties of this case and formulate our problem as a linear or nonlinear program, depending on whether the feasible region is convex or nonconvex. An analysis of the solution complexity is presented along with an illustrative numerical example.     

A BSSS algorithm for the single facility location problem in two regions with different norms

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.     

Location of Preventive Health Care Facilities

This paper is focused on the problem of locating preventive health care facilities. The aim is to maximize participation to prevention programs. We assume that distance is a major determinant of participation and people would go to the closest facility for preventive health care. Each facility is required to have more than a predetermined number of clients because of the direct relationship between volume and quality of preventive services. We provide a mathematical formulation and present alternative solution approaches for this new location problem. We report on computational performance of the proposed methods in locating public health centers in Fulton County, Georgia and mammography screening centers in Montreal, Quebec.     

A hierarchical location-allocation model with travel based on expected referral distances

The hierarchical p-median location-allocation model assumes that patrons always travel to the closest facility of appropriate level and that their interests are best served when the distances they must travel to do this are minimized. This assumption about travel behavior is unrealistic, patrons in the real world are known, for instance, to bypass lower level facilities that can serve their needs to attend higher level facilities. We introduce the concept of “expected distance under referral” to deal with such irrationality and incorporate it into a location-allocation model that minimizes the negative effects of such irrational behavior. We demonstrate the model with several types of non-optimal travel behavior.     

Location and shape of a rectangular facility in ℝn. Convexity properties. Convexity properties

In this paper we address a generalization of the Weber problem, in which we seek for the center and the shape of a rectangle (the facility) minimizing the average distance to a given set (the demand-set) which is not assumed to be finite. Some theoretical properties of the average distance are studied, and an expression for its gradient, involving solely expected distances to rectangles, is obtained. This enables the resolution of the problem by standard optimization techniques. The research of the authors is partially supported by Spanish DGICYT grant PB93-0927.