The general facility location problem with connectivity on trees

In this note we study the general facility location problem with connectivity. We present an O(np ²)-time algorithm for the general facility location problem with connectivity on trees. Furthermore, we present an O(np)-time algorithm for the general facility location problem with connectivity on equivalent binary trees.     

The 1-median and 1-highway problem

In this paper we study a facility location problem in the plane in which a single point (median) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the L₁ or Manhattan metric. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. We represent the highway by a line segment with fixed length and arbitrary orientation. This problem was introduced in [Computers & Operations Research 38(2) (2011) 525–538]. They gave both a characterization of the optimal solutions and an algorithm running in O(n³logn) time, where n represents the number of clients. In this paper we show that the previous characterization does not work in general. Moreover, we provide a complete characterization of the solutions and give an algorithm solving the problem in O(n³) time.     

Optimal M/G/1 Server Location on a Network Having a Fixed Facility

This paper considers the problem of locating a single mobile service unit on a network G where the servicing of a demand includes travel time to a permanent facility which is located at a predetermined point on G. Demands for service, which occur solely on the nodes of the network, arrive in a homogeneous Poisson manner. The server, when free, can be immediately dispatched to a demand: the service unit travels to the demand, performs some on-scene service, continues to the permanent facility, where off-scene service is rendered, and then it returns to its ‘home’ location, where possibly additional off-scene service is given. Previous research has examined the same problem, however without the presence of a permanent facility. The paper discusses methods of solving two cases when the server is unable to be immediately dispatched to service a demand: (1) the zero-capacity queueing system; (2) the infinite-capacity queueing system. For the first case we prove that the optimal location is included in a small set of points in the network, and we show how to find this set. For the second case, we present an 0(n³) algorithm (n is the number of nodes) to obtain the optimal location.     

The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic

The p/q-active uncapacitated facility location problem is the problem of locating p facilities on n possible sites each serving at least q of the m clients at the minimum cost. The problem is an extension of the uncapacitated facility location problem (UFL) where constraints on the number of facilities and their minimum activity have been added. A use of this formulation could be the opening of p new schools where each must have at least q pupils. p/q-active is NP-hard like the UFL.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

LP-based approximation algorithms for capacitated facility location

In the capacitated facility location problem with hard capacities, we are given a set of facilities, ${\mathcal{F}}$ , and a set of clients ${\mathcal{D}}$ in a common metric space. Each facility i has a facility opening cost f _i and capacity u _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal{F}}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

A generalized Weiszfeld method for the multi-facility location problem

An iterative method is proposed for the K facilities location problem. The problem is relaxed using probabilistic assignments, depending on the distances to the facilities. The probabilities, that decompose the problem into K single-facility location problems, are updated at each iteration together with the facility locations. The proposed method is a natural generalization of the Weiszfeld method to several facilities.     

Undesirable facility location with minimal covering objectives

An undesirable facility is to be located within some feasible region of any shape in the plane or on a planar network. Population is supposed to be concentrated at a finite number n of points. Two criteria are taken into account: a radius of influence to be maximised, indicating within which distance from the facility population disturbance is taken into consideration, and the total covered population, i.e. lying within the influence radius from the facility, which should be minimised. Low complexity polynomial algorithms are derived to determine all nondominated solutions, of which there are only O(n³) for a fixed feasible region or O(n²) when locating on a planar network. Once obtained, this information allows almost instant answers and a trade-off sensitivity analysis to questions such as minimising the population within a given radius (minimal covering problem) or finding the largest circle not covering more than a given total population.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

Approximating the two-level facility location problem via a quasi-greedy approach

We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new approach enables us to approximate the metric 2-LFLP in polynomial time with a ratio of 1.77, a significant improvement on the previously known approximation ratios. Moreover, our approach results in a local improvement procedure for the 2-LFLP, which is useful in improving the approximation guarantees for several other multi-level facility location problems. An additional result of our approach is an O(ln (n))-approximation algorithm for the non-metric 2-LFLP, where n is the number of clients. This is the first non-trivial approximation for a non-metric multi-level facility location problem. An extended abstract of this paper appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2004.     

A cooperative location game based on the 1-center location problem

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG).We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ?_p metric spaces defined over R^d.     

A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints

Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems.     

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.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.