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.     

Applied p-median and p-center algorithms for facility location problems

Facility location problems with the objective to minimize the sum of the setup cost and transportation cost are studied in this paper. The setup and transportation costs are considered as a function of the number of opened facilities. Three methods are introduced to solve the problem. The facility location model with bounds for the number of opened facility is constructed in this work. The relationship between setup cost and transportation cost is studied and used to build these methods based on greedy algorithm, p-median algorithm and p-center algorithm. The performance of the constructed methods is tested using 100 random data sets. In addition, the networks representing the road transportation system of Chiang Mai city and 5 provinces in Northern Thailand are illustrated and tested using all presented methods. Simulation results show that the method developed from greedy algorithm is suitable for solving problems when the setup cost is higher than transportation cost while the opposite cases are more efficiently solved with the method developed by the p-median problem.     

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.     

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.     

Lagrangean relaxation and decomposition in an uncapacitated 2-hierarchal location-allocation problem

We consider an uncapacitated 2-hierarchal location-allocation problem where p₁ level 1 facilities and p₂ level 2 facilities are to be located among n(?p₁ + p₂) potential locations so as to minimize the total weighted travel distance to the facilities when θ, (0 ? θ ? 1) fraction of the demand from a level 1 facility is referred to a level 2 facility. At most one facility may be located at any location. In this model, a level 2 facility provides services in addition to services provided by a level 1 facility.The problem is formulated as a mathematical programming problem, relaxed and solved by a subgradient optimization procedure. The proposed procedure is illustrated with an example.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

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.     

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.     

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 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.     

A heuristic method for large-scale multi-facility location problems

A heuristic method for solving large-scale multi-facility location problems is presented. The method is analogous to Cooper's method (SIAM Rev. 6 (1964) 37), using the authors’ single facility location method (Comput. Optim. Appl. 21 (2002) 213) as a parallel subroutine, and reassigning customers to facilities using the heuristic of nearest center reclassification. Numerical results are reported. Scope and purpose We study the multiple facility location problem (MFLP). The objective in MFLP is to locate facilities to serve optimally a given set of customers. MFLPs have many applications in Operations Research, and a rich literature, see Drezner (Location Sci. 3(4) (1995) 275) for a recent survey.MFLPs involve, in addition to the location decision, also the assignment of customers to facilities. The MFLP is therefore a special clustering problem, the clusters here are the sets of customers assigned to the same facility.We propose a parallel heuristic method for solving MFLPs, using ideas from cluster analysis (nearest mean reclassification (Cluster Analysis, 3rd Edition, Edward Arnold, London, 1993)), and the authors’ Newton bracketing method for convex minimization (Comput. Optim. Appl. 21 (2002) 213) as a subroutine. The method is suitable for large-scale problems, as illustrated by numerical examples.     

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.     

A dynamic multi-objective approach for the reconfigurable multi-facility layout problem

The multi-facility layout problem involves the physical organization of departments inside several facilities, to allow flexible and efficient operations. This work studies the facility layout problem in a new perspective, considering a group of facilities, and two different concerns: the location of departments within a group of facilities, and the location of departments inside each facility itself. The problem is formulated as a Quadratic Programming Problem with multiple objectives and unequal areas, allowing layout reconfigurations in each planning period. The objectives of the model are: the minimization of costs (material handling inside facilities and between facilities, and re-layout); the maximization of adjacency between departments; and the minimization of the “unsuitability” of department positions and locations. This unsuitability measure is a new objective proposed in this work, to combine the characteristics of existing locations with the requirements of departments. The model was tested with data from the literature as well as with a problem inspired in a first tier supplier in the automotive industry. Preliminary results show that this work can be viewed as an innovative and promising integrated approach for tackling real, complex facility layout problems.     

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.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances.     

Solution approaches for facility location of medical supplies for large-scale emergencies

In this paper, we propose models and solution approaches for determining the facility locations of medical supplies in response to large-scale emergencies. We address the demand uncertainty and medical supply insufficiency by providing each demand point with services from a multiple quantity of facilities that are located at different quality levels (distances). The problem is formulated as a maximal covering problem with multiple facility quantity-of-coverage and quality-of-coverage requirements. Three heuristics are developed to solve the location problem: a genetic algorithm heuristic, a locate–allocate heuristic, and a Lagrangean relaxation heuristic. We evaluate the performance of the model and the heuristics by using illustrative emergency examples. We show that the model provides an effective method to address uncertainties with little added cost in demand point coverage. We also show that the heuristics are able to generate good facility location solutions in an efficient manner. Moreover, we give suggestions on how to select the most appropriate heuristic to solve different location problem instances.     

Solving the constrained coverage problem

Coverage problem which is one of the challenging problems in facility location studies, is NP-hard. In this paper, we focus on a constrained version of coverage problem in which a set of demand points and some constrained regions are given and the goal is to find a minimum number of sensors which covers all demand points. A heuristic approach is presented to solve this problem by using the Voronoi diagram and p-center problem's solution. The proposed algorithm is relatively time-saving and is compared with alternative solutions. The results are discussed, and concluding remarks and future work are given.     

Risk management in uncapacitated facility location models with random demands

In this paper we consider a location-optimization problem where the classical uncapacitated facility location model is recast in a stochastic environment with several risk factors that make demand at each customer site probabilistic and correlated with demands at the other customer sites. Our primary contribution is to introduce a new solution methodology that adopts the mean–variance approach, borrowed from the finance literature, to optimize the “Value-at-Risk” (VaR) measure in a location problem. Specifically, the objective of locating the facilities is to maximize the lower limit of future earnings based on a stated confidence level. We derive a nonlinear integer program whose solution gives the optimal locations for the p facilities under the new objective. We design a branch-and-bound algorithm that utilizes a second-order cone program (SOCP) solver as a subroutine. We also provide computational results that show excellent solution times on small to medium sized problems.     

基于混合需求的设施选址问题研究

研究网络中设施的需求一部分来自于网络节点, 一部分来自于过往流量的基于混合需求的设施选址问题。引入引力模型, 以新建设施获得总利润最大为目标建立非线性整数规划模型, 并构造启发式算法, 通过MATLAB进行仿真实验, 将求解结果与GPAH算法及精确算法的结果进行比较。比较结果表明, 提出的算法求解质量高、运行速度快, 可用于大中型网络设施的选址问题。