Bounding methods for facilities location algorithms

Single- and multi-facility location problems are often solved with iterative computational procedures. Although these procedures have proven to converage, in practice it is desirable to be able to compute a lower bound on the objective function at each iteration. This enables the user to stop the iterative process when the objective function is within a prespecified tolerance of the optimum value. In this article we generalize a new bounding method to include multi-facility problems with l_p distances. A proof is given that for Euclidean distance problems the new bounding procedure is superior to two other known methods. Numerical results are given for the three methods.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

One-facility location with rectilinear tour distances

This article concerns the location of a facility among n points where the points are serviced by “tours” taken from the facility. Tours include m points at a time and each group of m points may become active (may need a tour) with some known probability. Distances are assumed to be rectilinear. For m ≤ 3, it is proved that the objective function is separable in each dimension and an exact solution method is given that involves finding the median of numbers appropriately generated from the problem data. It is shown that the objective function becomes multimodal when some tours pass through four or more points. A bounded heuristic procedure is suggested for this latter case. This heuristic involves solving an auxiliary three-point tour location problem.     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

The conditional p-center problem in the plane

An algorithm is given for the conditional p-center problem, namely, the optimal location of one or more additional facilities in a region with given demand points and one or more preexisting facilities. The solution dealt with here involves the minimax criterion and Euclidean distances in two-dimensional space. The method used is a generalization to the present conditional case of a relaxation method previously developed for the unconditional p-center problems. Interestingly, its worst-case complexity is identical to that of the unconditional version, and in practice, the conditional algorithm is more efficient. Some test problems with up to 200 demand points have been solved. © 1993 John Wiley & Sons, Inc.     

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

On the rectangular p-center problem

The p-center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or l₁) distances are considered. An O(n) algorithm for the 1-center problem, an O(n) algorithm for the 2-center problem, and an O(n logn) algorithm for the 3-center problem are given. Generalizations to general p-center problems are also discussed.     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

Estimating travel distances by the weighted lp norm

Empirical distance functions are used to estimate actual travel distances in a transportation network, to verify the accuracy of road mileage data, and to formulate continuous location models. In this article we consider the problem of fitting the weighted l_p norm to a given network. Mathematical properties are derived for two fitting criteria found in the literature. These properties are used to develop an accurate and efficient methodology to solve for the best-fitting parameter values. The directional bias of the l_p norm is analyzed for its effect on the range of search for the optimal p value. Concepts and methodology are applied to a case study of the road system in Southern Ontario. In conclusion, a general framework for other types of distance functions is briefly discussed.     

Estimates of circular error probabilities

The general problem we are concerned with here is the estimation of P_θ(C) where C is some fixed event and P_θ is unknown in some class. The various available estimation procedures seem to involve the choice of some random probability measure. In particular we consider this problem when C is a disk in R² centered at o and P_θ is restricted to be bivariate normal. Details concerning the implementation of the estimation procedures and a Monte Carlo study are discussed for this case. This particular problem arises when we are concerned with assessing the accuracy of a targeting procedure.     

The optimal linear combination of control variates in the presence of asymptotically negligible bias

The optimal linear combination of control variates is well known when the controls are assumed to be unbiased. We derive here the optimal linear combination of controls in the situation where asymptotically negligible bias is present. The small-sample linear control which minimizes the mean square error (MSE) is derived. When the optimal asymptotic linear control is used rather than the optimal small-sample control, the degradation in MSE is c/n³, where n is the sample size and c is a known constant. This analysis is particulary relevant to the small-sample theory for control variates as applied to the steady-state estimation problem. Results for the method of multiple estimates are also given.     

A vertex-closing approach to the p-center problem

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and lower bounds, to establish refined lower bounds, and to verify the optimality of solutions. These subgraphs form the foundation of two polynomial algorithms of complexity O(|E| log |E|) and O(|E|²). The algorithms are proven to converge to an optimum for special cases, and computational evidence is provided which suggests that they produce very good solutions more generally. Both algorithms perform very well on problems where p is large relative to the number of vertices n, specifically, when p/n ≥ 0.30. One of the algorithms is especially efficient for solving a sequence of problems on the same graph.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.     

An iterative algorithm for the multifacility minimax location problem with euclidean distances

An iterative solution method is presented for solving the multifacility location problem with Euclidean distances under the minimax criterion. The iterative procedure is based on the transformation of the multifacility minimax problem into a sequence of squared Euclidean minisum problems which have analytical solutions. Computational experience with the new method is also presented.     

Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

A note on equity across groups in facility location

An equity model between groups of demand points is proposed. The set of demand points is divided into two or more groups. For example, rich and poor neighborhoods and urban and rural neighborhoods. We wish to provide equal service to the different groups by minimizing the deviation from equality among groups. The distance to the closest facility is a measure of the quality of service. Once the facilities are located, each demand point has a service distance. The objective function, to be minimized, is the sum of squares of differences between all pairs of service distances between demand points in different groups. The problem is analyzed and solution techniques are proposed for the location of a single facility in the plane. Computational experiments for problems with up to 10,000 demand points and rectilinear, Euclidean, or general ?_p distances illustrate the efficiency of the proposed algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

On a rational stopping rule for facilities location algorithms

In the multifacility location problem, a number of new facilities are to be located so as to minimize a sum of weighted distances. Recently, a lower bound on the optimal value was developed, for use in deciding when to stop an iterative solution procedure. We develop a stronger bound that allows some computational savings.     

Estimating moments of the minimum order statistic from normal populations—a bayesian approach

Let Yⁱ ∽ N(θⁱ, σ), i = 1, …, p, be independently distributed, where θⁱ and σ are unknown. A Bayesian approach is used to estimate the first two moments of the minimum order statistic, W = min (Y¹, …, Y^p). In order to compute the Bayes estimates, one has to evaluate the predictive densities of the Yⁱ's conditional on past data. Although the required predictive densities are complicated in form, an efficient algorithm to calculate them has been developed and given in the article. An application of the Bayesian method in a continuous-review control model with multiple suppliers is discussed. © 1994 John Wiley & Sons, Inc.     

Relaxation method for the solution of the minimax location-allocation problem in euclidean space

A method previously devised for the solution of the p-center problem on a network has now been extended to solve the analogous minimax location-allocation problem in continuous space. The essence of the method is that we choose a subset of the n points to be served and consider the circles based on one, two, or three points. Using a set-covering algorithm we find a set of p such circles which cover the points in the relaxed problem (the one with m < n points). If this is possible, we check whether the n original points are covered by the solution; if so, we have a feasible solution to the problem. We now delete the largest circle with radius r_p (which is currently an upper limit to the optimal solution) and try to find a better feasible solution. If we have a feasible solution to the relaxed problem which is not feasible to the original, we augment the relaxed problem by adding a point, preferably the one which is farthest from its nearest center. If we have a feasible solution to the original problem and we delete the largest circle and find that the relaxed problem cannot be covered by p circles, we conclude that the latest feasible solution to the original problem is optimal. An example of the solution of a problem with ten demand points and two and three service points is given in some detail. Computational data for problems of 30 demand points and 1–30 service points, and 100, 200, and 300 demand points and 1–3 service points are reported.