A heuristic for large-sizep-median location problems with application to school location

This paper initially proposes a heuristic algorithm for thep-median problem designed for large weighted graphs. The problem is approached through the construction ofp trees whose shapes are progressively modified according to successive tests over the stability of their roots and vertices. The algorithm seems promising because: (i) on a regular PC it can handle problems of the order of 500 vertices, while the mainframe version goes indefinitely further, (ii) contrary to what normally would be expected, execution times seem to be inversely proportional top, and even for large problems, they may be reasonable, especially ifp is large relative to the number of vertices, and (iii) it produces solutions of good quality and in most of the cases studied, it outperforms the traditional heuristic of Teitz and Bart. A real application of the algorithm embedded in a methodology to evaluate the location of 85 public schools, among 389 possible vertices, in the metropolitan area of Rio de Janeiro is reported. Results confirmed the conjecture of poor location and the procedure was able to identify several micro-regions simply void of schools. The methodology is being well received by the education authorities and its extension to the whole metropolitan area is being considered.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

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.     

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.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

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.     

Complete convergence for moving average processes associated to heavy-tailed distributions and applications

The complete convergence is obtained for the moving average processes associated to heavy-tailed distributions via integral test. As the applications, two versions of Chover's law of the iterated logarithm are deduced.     

Monotone iterates with quadratic convergence rate for solving weighted average approximations to semilinear parabolic problems

This paper deals with discrete monotone iterative methods for solving semilinear singularly perturbed parabolic problems. Monotone sequences, based on the accelerated monotone iterative method, are constructed for a nonlinear difference scheme which approximates the semilinear parabolic problem. This monotone convergence leads to the existence-uniqueness theorem. An analysis of convergence of the monotone iterative method to the solutions of the nonlinear difference scheme is given. Numerical experiments are presented.     

A comparative study of approaches to dynamic location problems

We compare the performance of seven approximate methods for locating new capacity over time to minimize the total discounted costs of meeting growing demands at several locations. Comparisons are based on results for two industrial planning problems from India, and are given for both discrete-time and continuous-time frameworks. We also discuss strategies for combining different methods into possibly more effective hybrid approaches.     

On the lexicographic minimax approach to location problems

When locating public facilities, the distribution of travel distances among the service recipients is an important issue. It is usually tackled with the minimax (center) solution concept. The minimax solution concept, despite the most commonly used in the public sector location models, is criticized as it does not comply with the major principles of the efficiency and equity modeling. In this paper we develop a concept of the lexicographic minimax solution (lexicographic center) being a refinement of the standard minimax approach to location problems. We show that the lexicographic minimax approach complies with both the Pareto-optimality (efficiency) principle (crucial in multiple criteria optimization) and the principle of transfers (essential for equity measures) whereas the standard minimax approach may violate both these principles. Computational algorithms are developed for the lexicographic minimax solution of discrete location problems.     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFL_β[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is c_ij. For iF, the cost of opening a facility at location i is f_i0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem.     

Outcomes of voting and planning in single facility location problems

For a given set of users located at the vertices of a network N, we consider the location of a single facility. Two different decision making procedures, voting among the users and minimizing total distance travelled by the users, are compared.Provided that a voting solution exists, it is shown that the two solutions sets coincide if N is a so-called cactus. For general networks, the outcomes of the two procedures are compared in terms of the cyclic structure of N and the number of users.     

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.     

A reduction result for location problems with polyhedral barriers

In this paper we consider the problem of locating one new facility in the plane with respect to a given set of existing facilities where a set of polyhedral barriers restricts traveling. This non-convex optimization problem can be reduced to a finite set of convex subproblems if the objective function is a convex function of the travel distances between the new and the existing facilities (like e.g. the median and center objective functions). An exact algorithm and a heuristic solution procedure based on this reduction result are developed.     

Ambulance location and relocation problems with time-dependent travel times

EMERGENCY SERVICE PROVIDERS ARE FACING THE FOLLOWING PROBLEM: how and where to locate vehicles in order to cover potential future demand effectively. Ambulances are supposed to be located at designated locations such that in case of an emergency the patients can be reached in a time-efficient manner. A patient is said to be covered by a vehicle if (s)he can be reached by an ambulance within a predefined time limit. Due to variations in speed and the resulting travel times it is not sufficient to solve the static ambulance location problem once using fixed average travel times, as the coverage areas themselves change throughout the day. Hence we developed a multi-period version, taking into account time-varying coverage areas, where we allow vehicles to be repositioned in order to maintain a certain coverage standard throughout the planning horizon. We have formulated a mixed integer program for the problem at hand, which tries to optimize coverage at various points in time simultaneously. The problem is solved metaheuristically using variable neighborhood search. We show that it is essential to consider time-dependent variations in travel times and coverage respectively. When ignoring them the resulting objective will be overestimated by more than 24%. By taking into account these variations explicitly the solution on average can be improved by more than 10%.     

Duality for location problems with unbounded unit balls

Given an optimization problem with a composite of a convex and componentwise increasing function with a convex vector function as objective function, by means of the conjugacy approach based on the perturbation theory, we determine a dual to it. Necessary and sufficient optimality conditions are derived using strong duality. Furthermore, as special case of this problem, we consider a location problem, where the “distances” are measured by gauges of closed convex sets. We prove that the geometric characterization of the set of optimal solutions for this location problem given by Hinojosa and Puerto in a recently published paper can be obtained via the presented dual problem. Finally, the Weber and the minmax location problems with gauges are given as applications.     

Approximate duality for vector quasi-equilibrium problems and applications

In this paper, we introduce new versions of ?-dual problems of a vector quasi-equilibrium problem with set-valued maps, and we give an ?-duality result between approximate solutions of the primal and dual problems. As the first application of the main result, we obtain an ?-duality for a vector quasi-equilibrium problem whose ?-solutions are understood in the sense of proper efficiency. The second application is devoted to an?-duality for a vector optimization problem with set-valued maps.