On solving unreliable planar location problems

In this paper, we generalize conventional P-median location problems by considering the unreliability of facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. We proposed efficient solution methods to determine locations of these facilities in the unreliable location model. Space-filling curve-based algorithms are developed to determine initial locations of these facilities. The unreliable P-median location problem is then decomposed to P 1-median location problems; each problem is solved to the optimum. A bounding procedure is used to monitor the iterative search, and to provide a consistent basis for termination. Extensive computational tests have indicated that the heuristics are efficient and effective for solving unreliable location problems.Scope and purposeThis paper addresses an important class of location problems, where p unreliable facilities are to be located on the plane, so as to minimize the expected travel distance or related transportation cost between the customers and their nearest available facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. Potential application of the unreliable location problem is found in numerous areas. The facilities to be located can be fire station or emergency shelter, where it fails to provide service during some time window, due to the capacity or resource constraints. Alternatively, the facilities can be telecommunication posts or logistic/distribution centers, where the service is unavailable due to breakdown, repair, shutdown of unknown causes. In this paper, we prescribed heuristic procedures to determine the location of new facilities in the unreliable location problems. The numerical study of 2800 randomly generated instances has shown that these solution procedures are both efficient and effective, in terms of computational time and solution quality.     

Dynamic facility location: The progressive p-median problem

A dynamic p-median problem is considered. Demand is changing over a given time horizon and the facilities are built one at a time at given times. Once a new facility is built, some of the customers will use its services and some of the customers will patronize an existing facility. At any given time, customers patronize the closest facility. The problem is to find the best locations for the new facilities. The problem is formulated and the two facilities case is solved by a special algorithm. The general problem is solved using the standard mathematical programming code AMPL.     

Lagrangean relaxation heuristics for the p-cable-trench problem

We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.     

GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering

In this study, a maximal covering location problem is investigated. In this problem, we want to maximize the demand of a set of customers covered by a set of p facilities located among a set of potential sites. It is assumed that a set of facilities that belong to other firms exists and that customers freely choose allocation to the facilities within a coverage radius. The problem can be formulated as a bilevel mathematical programming problem, in which the leader locates facilities in order to maximize the demand covered and the follower allocates customers to the most preferred facility among those selected by the leader and facilities from other firms. We propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic to find near optimal solutions. Results of the heuristic approaches are compared to solutions obtained with a single-level reformulation of the problem. Computational experiments demonstrate that the proposed algorithms can find very good quality solutions with a small computational burden. The most important feature of the proposed heuristics is that, despite their simplicity, optimal or near-optimal solutions can be determined very efficiently.     

A decomposition approach for the p-median problem on disconnected graphs

The p-median problem seeks for the location of p facilities on the vertices (customers) of a graph to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities. In many real applications of the p-median problem the underlying graph is disconnected. That is the case of p-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem. In such cases the problem can be decomposed into smaller p-median problems which are solved in each component k for different feasible values of p_k, and the global solution is obtained by finding the best combination of p_k medians. This approach has the advantage that it permits to solve larger instances since only the sizes of the connected components are important and not the size of the whole graph. However, since the optimal number of facilities to select from each component is not known, it is necessary to solve p-median problems for every feasible number of facilities on each component. In this paper we give a decomposition algorithm that uses a procedure to reduce the number of subproblems to solve. Computational tests on real instances of the optimal diversity management problem and on simulated instances are reported showing that the reduction of subproblems is significant, and that optimal solutions were found within reasonable time.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

GeD spline estimation of multivariate Archimedean copulas

A new multivariate Archimedean copula estimation method is proposed in a non-parametric setting. The method uses the so-called Geometrically Designed splines (GeD splines) to represent the cdf of a random variable W_θ, obtained through the probability integral transform of an Archimedean copula with parameter θ. Sufficient conditions for the GeD spline estimator to possess the properties of the underlying theoretical cdf, K(θ,t), of W_θ, are given. The latter conditions allow for defining a three-step estimation procedure for solving the resulting non-linear regression problem with linear inequality constraints. In the proposed procedure, finding the number and location of the knots and the coefficients of the unconstrained GeD spline estimator and solving the constraint least-squares optimisation problem are separated. Thus, the resulting spline estimator is used to recover the generator and the related Archimedean copula by solving an ordinary differential equation. The proposed method is truly multivariate, it brings about numerical efficiency and as a result can be applied with large volumes of data and for dimensions d≥2, as illustrated by the numerical examples presented.     

Fast metaheuristics for the discrete (r|p)-centroid problem

Two players, the leader and his competitor, open facilities, striving to capture the largest market share. The leader opens p facilities, then the follower opens r facilities. Each client chooses the nearest facility as his supplier. We need to choose p facilities of the leader in such a way as to maximize his market share. This problem can be represented as a bilevel programming problem. Based on this representation, in this work we propose two numerical approaches: local search with variable neighborhoods and stochastic tabu search. We pay the most attention to improving the methods’ efficiency at no loss to the quality of the resulting solutions. Results of numerical experiments support the possibility to quickly find an exact solution for the problem and solutions with small error.     

An aggregation heuristic for large scale p-median problem

The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity.In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a “core” heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.     

A Lagrangian relaxation approach for a large scale new variant of capacitated clustering problem

This paper studies a new variant of capacitated clustering problem (VCCP). In the VCCP, p facilities which procure a raw material from a set of suppliers are to be located among n potential sites (n > p) such that the total cost of assigning suppliers to the facilities and opening such facilities is minimized. Each supplier has a limited supply volume and each facility has a minimum supply requirement that must be satisfied by assigning enough suppliers to the facility. Each supplier can be assigned to at most one facility. When a supplier is assigned to a facility, the former will supply its all available volume to the latter. In order to solve the VCCP, a Lagrangian relaxation approach (LR) with two phases of dual optimization, the subgradient deflection in the first phase and the standard subgradient method in the second phase, is proposed. In the approach, the assignment constraints are relaxed. The resulting Lagrangian relaxed problem can be decomposed into a set of independent knapsack problems, which can be solved to optimality efficiently. At each Lagrangian iteration, a feasible solution is constructed from that of the Lagrangian relaxed problem by applying a greedy algorithm. Finally, the best feasible solution found so far is improved by a simple tabu search algorithm. Numerical tests on random instances show that the proposed LR can produce a tight lower bound and a high quality feasible solution for all instances with up to 4000 suppliers, 200 potential sites, and 100 plants to locate.     

Exact optimal solutions of the minisum facility and transfer points location problems on a network

We consider hierarchical facility location problems on a network called Multiple Location of Transfer Points (MLTP) and Facility and Transfer Points Location Problem (FTPLP), where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p‐median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration‐based approach to solve the problems with a single facility.     

Improved Algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs

We consider a common scenario in competitive location, where two competitors (providers) place their facilities (servers) on a network, and the users, which are modeled by the nodes of the network, can choose between the providers. We assume that each user has an inelastic demand, specified by a positive real weight. A user is fully served by a closest facility. The benefit (gain) of a competitor is his market share, i.e., the total weight (demand) of the users served at his facilities. In our scenario the two providers, called the leader and the follower, sequentially place p and r servers, respectively. After the leader selects the locations for his p servers, the follower will determine the optimal locations for his r servers, that maximize his benefit. An (r,p)-centroid is a set of locations for the p servers of the leader, that will minimize the maximum gain of the follower who can establish r servers. In this paper we focus mainly on the cases where either the leader or the follower can establish only one facility, i.e., either p=1, or r=1. We consider two versions of the model. In the discrete case the facilities can be established only at the nodes, while in the absolute case they can be established anywhere on the network. For the (r,1)-centroid problem, we show that it is strongly NP-hard for a general graph, but can be approximated within a factor e/(e?1). On the other hand, when the graph is a tree, we provide strongly polynomial algorithms for the (r,p)-centroid model, whenever p is fixed. For the (1,1)-centroid problem on a general graph, we improve upon known results, and give the first strongly polynomial algorithm. The discrete (1,p)-centroid problem has been known to be NP-hard even for a subclass of series-parallel graphs with pathwidth bounded by 6. In view of this result, we consider the discrete and absolute (1,p) centroid models on a tree, and present the first strongly polynomial algorithms. Further improvements are shown when the tree is a path.     

Variable neighborhood search for the p-median

Consider a set L of potential locations for p facilities and a set U of locations of given users. The p-median problem is to locate simultaneously the p facilities at locations of L in order to minimize the total transportation cost for satisfying the demand of the users, each supplied from its closest facility. This model is a basic one in location theory and can also be interpreted in terms of cluster analysis where locations of users are then replaced by points in a given space. We propose several new Variable Neighborhood Search heuristics for the p-median problem and compare them with Greedy plus Interchange, and two Tabu Search heuristics.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.     

Tabu based heuristics for the generalized hierarchical covering location problem

The classical Hierarchical Covering Location Problem (HCLP) is the problem to find locations maximizing the number of covered customers, where the customers are assumed to be covered if they are located within a specific distance from the facility, and not covered otherwise. In the generalized HCLP (G-HCLP), customers asking a certain level of services can be served by the facility whose level is equal or the higher. The service coverage is also generalized in a way that the partial coverage is allowed if the distance from the facility is larger than the specified range although it is located in the covered distance. The locations and the levels of the facilities are to be determined, and their set of customers to serve is to be decided as well. Mixed integer programming formulation and the solution procedure using meta-heuristics is developed, and it is shown that suggested heuristic yields high quality solution in a reasonable computation time.     

A simple approach to the problem of 3-D reconstruction

A relatively simple mathematical procedure for the reconstruction of the 3-dimensional (3D) image of the left ventricle (LV) of the heart is presented. The method is based on the assumption that every ray whoch emanates from the midpoint of the long axis of the 3D body crosses the surface boundary of the ventricle at one and only one point. The coordinates r_i, φ_i, θ_i of the data points on, say, the outer boundary, (i.e., the epicardium) are calculated in a spherical coordinate system having its origin in the midpoint of the long axis. The problem of defining the coordinates of a prescribed grid point on the boundary is treated as an interpolation problem for the function r = r(φ, θ), defined in the rectangle 0 ≤ φ ≤ 2π; 0 ≤ θ ≤ π with r_i given in the points (φ_i, θ_i).     

A quadtree-based allocation method for a class of large discrete Euclidean location problems

A special data compression approach using a quadtree-based method is proposed for allocating very large demand points to their nearest facilities while eliminating aggregation error. This allocation procedure is shown to be extremely effective when solving very large facility location problems in the Euclidian space. Our method basically aggregates demand points where it eliminates aggregation-based allocation error, and disaggregates them if necessary. The method is assessed first on the allocation problems and then embedded into the search for solving a class of discrete facility location problems namely the p-median and the vertex p-center problems. We use randomly generated and TSP datasets for testing our method. The results of the experiments show that the quadtree-based approach is very effective in reducing the computing time for this class of location problems.     

A bilevel fixed charge location model for facilities under imminent attack

We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which m ranges from 10 to 30, and r varies between 1 and 3. The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender's facility opening plan is sensitive to the protection and distance costs.     

A new directed branching heuristic for the pq-median problem

The pq-median problem, of Serra and ReVelle seeks to locate hierarchical facilities at two levels so as to obtain a coherent structure. Coherence requires that the entire area assigned to a facility at the inferior level be assigned to one and the same facility at the next higher level of the hierarchy. Although optimal solutions can be obtained by means of solving biobjective integer linear programs, large problems are likely to require heuristics. Here we present a new heuristic that combines the generation of points, by means of a “directed” branching procedure with the final selection of points, using the FDH-technique. We further compare our new heuristic with the two most relevant heuristics proposed by Serra and ReVelle.