Asymmetric distances,semidirected networks and majority in Fermat–Weber problems

The Fermat–Weber problem is considered with distance defined by a quasimetric, an asymmetric and possibly nondefinite generalisation of a metric. In such a situation a distinction has to be made between sources and destinations. We show how the classical result of optimality at a destination or a source with majority weight, valid in a metric space, may be generalized to certain quasimetric spaces. The notion of majority has however to be strengthened to supermajority, defined by way of a measure of the asymmetry of the distance, which should be finite. This extended majority theorem applies to most asymmetric distance measures previously studied in literature, since these have finite asymmetry measure. Perhaps the most important application of quasimetrics arises in semidirected networks, which may contain edges of different (possibly zero) length according to direction, or directed edges. Distance in a semidirected network does not necessarily have finite asymmetry measure. But it is shown that an adapted majority result holds nevertheless in this important context, thanks to an extension of the classical node-optimality result to semidirected networks with constraints. Finally the majority theorem is further extended to Fermat–Weber problems with mixed asymmetric distances.     

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.     

Fast approximations for sums of distances, clustering and the Fermat–Weber problem

We describe two data structures that preprocess a set S of n points in (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of . This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(nlogn) time deterministic and O(n) time randomized -approximation algorithm for the so called Fermat–Weber problem in any fixed dimension.     

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.     

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.     

On the use of the Varignon frame for single facility Weber problems in the presence of convex barriers

This paper presents a new experimental approach to the Weber problem in the presence of convex barriers by using the Varignon frame. The Varignon frame is a mechanical system of strings, weights and a board with holes that has been used to identify an optimal location for the classical Weber problem. We show through analytical results that the same analog can also be used for some of the Weber problems in the presence of barriers. Some examples from the literature are revisited through experiments. Findings are compared to those found in the literature. Practical use of the analog is discussed as it provides rapid solutions, allows for flexibility, and enables one to visualize the problem.     

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     

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.     

Well-posedness of mixed variational inequalities, inclusion problems and fixed point problems

We generalize the concept of well-posedness to a mixed variational inequality and give some characterizations of its well-posedness. Under suitable conditions, we prove that the well-posedness of a mixed variational inequality is equivalent to the well-posedness of a corresponding inclusion problem. We also discuss the relations between the well- posedness of a mixed variational inequality and the well-posedness of a fixed point problem. Finally, we derive some conditions under which a mixed variational inequality is well-posed. This work was supported by the National Natural Science Foundation of China (10671135) and Specialized Research Fund for the Doctoral Program of Higher Education (20060610005). The research of the third author was partially support by NSC 95-2221-E-110-078.     

A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables

Geometric branch-and-bound techniques are well-known solution algorithms for non-convex continuous global optimization problems with box constraints. Several approaches can be found in the literature differing mainly in the bounds used.     

Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty

In this paper, we consider the two-stage minimax robust uncapacitated lot-sizing problem with interval uncertain demands. A mixed integer programming formulation is proposed. Even though the robust uncapacitated lot-sizing problem with discrete scenarios is an NP-hard problem, we show that it is polynomial solvable under the interval uncertain demand set.     

Existence and algorithm of solutions for mixed equilibrium problems and bilevel mixed equilibrium problems in Banach spaces

Some classes of mixed equilibrium problems and bilevel mixed equilibrium problems are introduced and studied in reflexive Banach spaces. First, by using a minimax inequality, some new existence results of solutions and the behavior of solution set for the mixed equilibrium problems and the bilevel mixed equilibrium problems are proved under suitable assumptions without the coercive conditions. Next, by using auxiliary principle technique, some new iterative algorithms for solving the mixed equilibrium problems and the bilevel mixed equilibrium problems are suggested and analyzed. The strong convergence of the iterative sequences generated by the proposed algorithms is proved under suitable assumptions without the coercive conditions. These results are new and generalize some recent results in this field.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

A location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations

The capacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane, and allocating their capacities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where the customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation, which is even more difficult than its deterministic version. We then propose an alternate location–allocation local search heuristic generalizing the ideas used originally for the deterministic problem. In its original form, the applicability of the heuristic depends on the calculation of the expected distances between the facilities and customers, which can be done for only very few distance and probability density function combinations. We therefore propose approximation methods which make the method applicable for any distance function and bivariate location distribution.     

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.      

Minisum location problem with farthest Euclidean distances

The paper formulates an extended model of Weber problem in which the customers are represented by convex demand regions. The objective is to generate a site in R ² that minimizes the sum of weighted Euclidean distances between the new facility and the farthest points of demand regions. This location problem is decomposed into a polynomial number of subproblems: constrained Weber problems (CWPs). A projection contraction method is suggested to solve these CWPs. An algorithm and the complexity analysis are presented. Three techniques of bound test, greedy choice and choice of starting point are adopted to reduce the computational time. The restricted case of the facility is also considered. Preliminary computational results are reported, which shows that with the above three techniques adopted the algorithm is efficient.The authors were supported by the dissertation fund of Nari-Relays Corporation.     

Sorting weighted distances with applications to objective function evaluations in single facility location problems

We consider single facility location problems defined on rectilinear spaces and spaces induced by tree networks. We focus on discrete cases, where the facility is restricted to be in a prespecified finite set S, and the goal is to evaluate the objective at each point in S. We present efficient improved algorithms to perform this task for several classes of objective functions.     

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C₁,…,C_k} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width.     

On the solution of bounded and unbounded mixed complementarity problems

A reformulation of the bounded mixed complementarity problem is introduced. It is proved that the level sets of the objective function are bounded and, under reasonableassumptions, stationary points coincide with solutions of the original variationalinequality problem. Therefore, standard minimization algorithms applied to the new reformulation must succeed. This result is applied to the compactification of unboundedmixed complementarity problems     

Combined location-routing problems—a neural network approach

While in location planning it is often assumed that deliveries are made on a direct-trip basis, in fact deliveries, e.g., to the different supermarkets belonging to a specific chain or to retail outlets of any kind, usually are performed as round-trips. Therefore, it is often necessary to combine the two issues of locating a depot and of planning tours in one problem formulation.In this paper, a neural network approach based on a self-organizing map is proposed for solving such single-depot location-routing problems in the plane. The results derived by this approach are compared with those which can be found by different well-known heuristics, and it is shown that the self-organising map approach competes well with these concepts. Moreover, some modifications which rely on ideas from Tabu Search can be shown to be especially useful for increasing the number of feasible solutions found by the self-organising map approach. Finally, the implementation of the Weiszfeld procedure for a final improvement of the optimal depot location proves to be a useful device.