New models for locating a moving service facility

In this paper we analyze a new location problem which is a generalization of the well-known single facility location model. This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single facility location problem on L ^p spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial step function belong to a subspace of L ^p called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm does not have to converge to an optimal solution of the considered problem while the proposed algorithm does.     

The single facility location problem with average-distances

This paper considers a location problem in ℝ ⁿ , where the demand is not necessarily concentrated at points but it is distributed in hypercubes following a Uniform probability distribution. The goal is to locate a service facility minimizing the weighted sum of average distances (measured with ℓ _p norms) to these demand hypercubes. In order to do that, we present an iterative scheme that provides a sequence converging to an optimal solution of the problem for p∈[1,2]. For the planar case, analytical expressions of this iterative procedure are obtained for p=2 and p=1, where two different approaches are proposed. The paper ends with a computational analysis of the proposed methodology, comparing its efficiency with a standard minimizer.      

On the convergence of the generalized Weiszfeld algorithm

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.     

On the point for which the sum of the distances to <Emphasis Type="Italic">n</Emphasis> given points is minimum

Translation with annotations of E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tôhoku Mathematical Journal (first series), 43 (1937) pp. 355–386.A short introduction about the translation is found in Appendix A. Appendix B lists particular notations used by Weiszfeld and their now more conventional equivalents. Numbered footnotes are those of the original paper of Weiszfeld. Boxed numerals are references to observations about the translation and comments of the translator, all to be found in Appendix C.     

A projected Weiszfeld algorithm for the box-constrained Weber location problem

The Weber problem consists of finding a point in Rⁿ that minimizes the weighted sum of distances from m points in Rⁿ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed-point iteration.In this work we generalize the Weber location problem considering box constraints. We propose a fixed-point iteration with projections on the constraints and demonstrate descending properties. It is also proved that the limit of the sequence generated by the method is a feasible point and satisfies the KKT optimality conditions. Numerical experiments are presented to validate the theoretical results.     

On an extension of Weber problem with Euclidean distance

The paper is an extension of the authors previous work [5] in which an approximate discrete technique is proposed to solve the Weber problem with the Euclidean distance. Now, it is assumed that the cost of connection (the cost associated with two points in the plane) depends upon the distance stronger than linearly. A model is formulated and an approximate discrete technique analogous to that in [5] is proposed. Its validity is proved. Both the numerical complexity and the practical efficiency of the algorithm are considered. An example is given     

Accelerating the convergence in the single-source and multi-source Weber problems

The modified Weiszfeld method [Y. Vardi, C.H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

The Fermat—Weber location problem revisited

The Fermat—Weber location problem requires finding a point in ^N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ^N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives

This paper considers the problem of locating a single semi-obnoxious facility on a general network, so as to minimize the total transportation cost between the new facility and the demand points (minisum), and at the same time to minimize the undesirable effects of the new facility by maximizing its distance from the closest population center (maximin). The two objectives employ different distance metrics to reflect reality. Since vehicles move on the transportation network, the shortest path distance is suitable for the minisum objective. For the maximin objective, however, the elliptic distance metric is used to reflect the impact of wind in the distribution of pollution. An efficient algorithm is developed to find the nondominated set of the bi-objective model and is implemented on a numerical example. A simulation experiment is provided to find the average computational complexity of the algorithm.     

Open questions concerning Weiszfeld's algorithm for the Fermat-Weber location problem

The Fermat—Weber location problem is to find a point in ⁿ that minimizes the sum of the weighted Euclidean distances fromm given points in ⁿ . A popular iterative solution method for this problem was first introduced by Weiszfeld in 1937. In 1973 Kuhn claimed that if them given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld's scheme converges to the unique optimal solution. We demonstrate that Kuhn's convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points.     

The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.     

Solving a continuous local access network design problem with a stabilized central column generation approach

In this paper, we focus on a variant of the multi-source Weber problem. In the multi-source Weber problem, the location of a fixed number of concentrators, and the allocation of terminals to them, must be chosen to minimize the total cost of links between terminals and concentrators. In our variant, we have a third hierarchical level, two categories of link costs, and the number of concentrators is unknown. To solve this difficult problem, we propose several heuristics, and use a new stabilized column generation approach, based on a central cutting plane method, to provide lower bounds.     

Uncertain models for single facility location problems on networks

In practical location problems on networks, the vertex demand is usually non-deterministic. This paper employs uncertainty theory to deal with this non-deterministic factor in single facility location problems. We first propose the concepts of satisfaction degree for both vertices and the whole network, which are used to evaluate products assignment. Based on different network satisfaction degree, two models are constructed. The solution to these models is based on Hakimi’s results, and some examples are given to illustrate these models.     

Minmax p-Traveling Salesmen Location Problems on a Tree

Suppose that p traveling salesmen must visit together all points of a tree, and the objective is to minimize the maximum of the lengths of their tours. The location–allocation version of the problem (where both optimal home locations of the salesmen and their optimal tours must be found) is known to be NP-hard for any p2. We present exact polynomial algorithms with a linear order of complexity for location versions of the problem (where only optimal home locations must be found, without the corresponding tours) for the cases p=2 and p=3.     

Public facility location using dispersion,population, and equity criteria

From a practical perspective, the paper demonstrates that the appropriate use of dispersion, population, and equity criteria can lead to fairly good solutions with respect to the p-median objective. The only stipulation is that the decision maker verifies (through simple constraint checks) that the chosen locations meet the dispersion, population, and equity criteria. An empirical investigation is conducted to obtain appropriate values for these parameters. From a location science perspective, a new location model that accounts for equity and efficiency simultaneously is studied and analyzed. Specifically, the p-maxian problem with side constraints on dispersion, population, and equity is developed, its NP-completeness established, and valid inequalities and bounds derived. Computational tests show encouraging results.     

Convergence of a SOR-Weiszfeld Type Algorithm for Incomplete Data Sets

We consider a generalization of the Weiszfeld algorithm with successive overrelaxation for data sets where some data point fields may be missing and prove its global convergence. A counterexample is also provided to the convergence of an alternative generalization.