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.     

On a Constrained Optimal Location Algorithm

In problems of optimal location, one seeks a position or location that optimizes a particular objective function; this objective function typically relates location and distances to a fixed point set. When one's search is restricted to a given set, we refer to this as a constrained optimal location problem. For a finite point set A, there exist numerous finite algorithms to solve optimal location problems. In this paper we demonstrate how an algorithm, solving optimal location problems in inner-product spaces, can be modified to solve certain constrained optimal location problems. We then apply this modification to a particularly simple (and easily implemented) algorithm and investigate the complexity of the result. In particular we improve a known estimate from exponential to polynomial.     

平面上的min-max型点-线选址问题

本文研究两类平面选址问题：(1)求一直线到n个给定点的最大加权距离为最小；(2)求一点到n条给定直线的最大加权距离为最小．对这两个非线性优化问题，我们给出最优解的刻划及迭代次数为多项式的算法．     

平面上的点-线选址问题

本文研究两类平面选址问题：（1）求一直线到n个给定点的加权距离和为最小；（2）求一点到n条给定直线的加权距离和为最小，对这两个非线性最优化问题，欠给出迭代次数为多项式的算法。     

Approximate formulas of average distances associated with regions and their applications to location problems

This study is concerned with the problem of measuring average distances between two points in two different coplanar regions. The objectives are: (1) to derive the approximated average distances associated with circular regions and to check their accuracy; and (2) to apply these approximated distances to location problems. Results show that the simple approximate formulas are accurate and useful. The approximated average distances can be applied to the analyses of varied kinds of movement phenomena in cities.     

Minimal curves with limited curvature in cases of cost depending on location

Find a connection of two points in the plane with minimal cost, the cost per length unit depending on the location, and the curvature of the curve being limited. For simple cases, as a necessary condition, the known optical law of refraction is supplemented by a “circular law of refraction”.

For the general case, a practicable numerical procedure is developed on the foundation of graph theory. This procedure is able to additionally take into consideration the given directions of the curve in the end points. Several examples demonstrate fundamental solution structures for classical basic problems and also solutions for routing problems in planning traffic ways.     

On the feasible set for the squared Euclidean Weber problem and applications

In this paper we find the set of feasible solution points to the Weber location problem with squared Euclidean distances when the weights can be at any point in a given set of intervals. We prove that this set is a convex polygon. The result is then used to solve the minimax regret objective when individual scenarios can be any set of weights in a given set of intervals.     

Numerical solution of an integral equation with a logarithmic kernel

When formulating boundary value problems within different branches of mathematical physics, one encounters an integral equation whose kernel is equal to the logarithm of the distance between two points on a plane, closed, smooth, and simple curve. This equation can be replaced by a system of linear algebraic equations which can be solved numerically.In the present paper we investigate two methods by which this replacement can be performed. Several examples are given in the literature where one of the methods is used. In contrast to this we here put forward a second method, which gives a higher accuracy without requiring more computational effort.     

On a lower and upper bound for the curvature of ellipses with more than two foci

Let a set of points in the Euclidean plane be given. We are going to investigate the levels of the function measuring the sum of distances from the elements of the pointset which are called foci. Levels with only one focus are circles. In case of two different points as foci they are ellipses in the usual sense. If the set of the foci consists of more than two points then we have the so-called polyellipses. In this paper we investigate them from the viewpoint of differential geometry. We give a lower and upper bound for the curvature involving explicit constants. They depend on the number of the foci, the rate of the level and the global minimum of the function measuring the sum of the distances. The minimizer will be characterized by a theorem due to E. Weiszfeld together with a new proof. Explicit examples will also be given. As an application we present a new proof for a theorem due to P. Erd?s and I. Vincze. The result states that the approximation of a regular triangle by circumscribed polyellipses has an absolute error in the sense that there is no way to exceed it even if the number of the foci are arbitrary large.     

An efficient solution method for Weber problems with barriers based on genetic algorithms

In this paper we consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.     

A D.C. biobjective location model

In this paper we address the biobjective problem of locating a semiobnoxious facility, that must provide service to a given set of demand points and, at the same time, has some negative effect on given regions in the plane. In the model considered, the location of the new facility is selected in such a way that it gives answer to these contradicting aims: minimize the service cost (given by a quite general function of the distances to the demand points) and maximize the distance to the nearest affected region, in order to reduce the negative impact. Instead of addressing the problem following the traditional trend in the literature (i.e., by aggregation of the two objectives into a single one), we will focus our attention in the construction of a finite -dominating set, that is, a finite feasible subset that approximates the Pareto-optimal outcome for the biobjective problem. This approach involves the resolution of univariate d.c. optimization problems, for each of which we show that a d.c. decomposition of its objective can be obtained, allowing us to use standard d.c. optimization techniques.     

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.     

On a robustness property in single-facility location in continuous space

We consider a single-facility location problem in continuous space—here the problem of minimizing a sum or the maximum of the possibly weighted distances from a facility to a set of points of demand. The main result of this paper shows that every solution (optimal facility location) of this problem has an interesting robustness property. Any optimal facility location is the most robust in the following sense: given a suitable highest admissible cost, it allows the greatest perturbation of the locations of the demand without exceeding this highest admissible chosen cost.     

Generalized median solutions,strategy-proofness and strictly convex norms

Generalized location problems withn agents are considered, who each report a point inm-dimensional Euclidean space. A solution assigns a compromise point to thesen points, and the individual utilities for this compromise point are equal to the negatives of the distances to the individual positions. These distances are measured by a given strictly convex norm, common to all agents. Form=2, it is shown that if a Pareto optimal, strategy-proof and anonymous solution exists, thenn must be odd, and the solution is obtained by taking the median coordinatewise, where the coordinates refer to a basis that is orthogonal with respect to the given norm. Furthermore, in that case (m=2) such a solution always exists. Form > 2, existence of a solution depends on the norm.Supported by a grant from the Cooperation Centre Tilburg and Eindhoven University.     

<Emphasis Type="Italic">k</Emphasis>-Elliptic Optimization for Locational Problems Under Constraints

A solution is presented to a problem of finding a location with a minimum sum of weighted distances from a given set of fixed points. This is obtained by controlling the distance parameter of a multi-focal ellipse with the fixed points as foci. The control is performed with the aid of thread, pins and rings. Later the technique is extended to constrained locational problems.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

A global optimization procedure for the location of a median line in the three-dimensional space

A global optimization procedure is proposed to find a line in the Euclidean three-dimensional space which minimizes the sum of distances to a given finite set of three-dimensional data points.Although we are using similar techniques as for location problems in two dimensions, it is shown that the problem becomes much harder to solve. However, a problem parameterization as well as lower bounds are suggested whereby we succeeded in solving medium-size instances in a reasonable amount of computing time.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Price Expectations and Cobwebs Under Uncertainty

Classical approaches to location problems are based on the minimization of the average distance (the median concept) or the minimization of the maximum distance (the center concept) to the service facilities. The median solution concept is primarily concerned with the spatial efficiency while the center concept is focused on the spatial equity. The k-centrum model unifies both the concepts by minimization of the sum of the k largest distances. In this paper we investigate a solution concept of the conditional median which is a generalization of the k-centrum concept taking into account the portion of demand related to the largest distances. Namely, for a specified portion (quantile) of demand we take into account the entire group of the corresponding largest distances and we minimize their average. It is shown that such an objective, similar to the standard minimax, may be modeled with a number of simple linear inequalities. Equitable properties of the solution concept are examined.     

Confined location of facilities on a graph

Location problems on a graph are usually classified according to the form that the set of located facilities takes, the specification of the demand location set and the objective function of distances between facilities and demand points. In this paper we suppose that a given number of located facilities is confined to the same number of edges. We consider eight types of optimality criteria: minirnizing(or maximizing) the minimum (or maximum) distance from a demand to its nearest (farthest) facility.