The probabilistic gradual covering location problem on a network with discrete random demand weights

We study the gradual covering location problem on a network with uncertain demand. A single facility is to be located on the network. Two coverage radii are defined for each node. The demand originating from a node is considered fully covered if the shortest distance from the node to the facility does not exceed the smaller radius, and not covered at all if the shortest distance is beyond the larger radius. For a distance between these two radii, the coverage level is specified by a coverage decay function. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand weight is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

Facility location and scale decision problem with customer preference

This paper addresses the facility location problem that aims to optimize the location and scale of a new facility in consideration of customer restrictions, including customer preference and the minimum number of customers required to open the facility. In a classic covering problem, the customer is assumed to be covered if he/she is located within the critical distance zone around the facility and is otherwise not covered. This problem is caused by customer facility selection, which differs from the classic covering problem in which services are determined only by proximity. This paper proposes a mixed integer programming formulation based on customer restrictions and also develops a heuristic solution procedure using Lagrangian relaxation. The suggested solution procedure is shown to yield acceptable results in a reasonable computation time.     

Transmitter location for maximum coverage and constructive-destructive interference management

Covering location models consider a demand “covered” if there is at least one facility sited within a preset threshold distance. If more than one facility satisfies this criterion, it is implicitly assumed that one of these facilities - usually the closest - will serve the customer, while the remaining ones will have no relation to the demand. However, there are cases in which this multiple coverage has either synergetic or undesired effects. In digital television broadcast networks using Single Frequency Network transmissions, if a customer receives transmissions from more than one transmitter, the strongest transmitter is the main signal source, while the second and following transmitters can either contribute to a good reception or act as sources of interference, depending on the technology and their relative locations. In this case, facilities should be located so as to avoid overlapping coverage if there is interference, or enhancing overlapping coverage if signals are combined constructively. We propose models that are solved using a commercial software, that address this problem. One of these models is used to compare different alternatives of network design for a region in Chile, and to find the best coverage situations.     

The generalized maximal covering location problem

We consider a generalization of the maximal cover location problem which allows for partial coverage of customers, with the degree of coverage being a non-increasing step function of the distance to the nearest facility. Potential application areas for this generalized model to locating retail facilities are discussed.We show that, in general, our problem is equivalent to the uncapacitated facility location problem. We develop several integer programming formulations that capitalize on the special structure of our problem. Extensive computational analysis of the solvability of our model under a variety of conditions is presented.     

Optimizing the Location of a Production Firm

A facility needs to be located in the plane to sell goods to a set of demand points. The cost for producing an item and the actual transportation cost per unit distance are given. The planner needs to determine the best location for the facility, the price charged at the source (mill price) and the transportation rate per unit distance to be charged to customers. Demand by customers is elastic and assumed declining linearly with the total charge. For each customer two parameters are given: the demand at charge zero and the decline of demand per unit charge. The objective is to find a location for the facility in the plane, the mill price charged to customers and the unit transportation rate charged to customers such that the company’s profit is maximized. The problem is formulated and an algorithm that finds the optimal solution is designed and tested on randomly generated problems.     

New MAXCAP related problems: Formulation and model solutions

In this paper three related problems of the maximum capture (MAXCAP) model are proposed. These include the case where facilities provide a certain amount of service level for the customers, the possibility where customers do not allocate their demand completely to one facility but prorate their demand based on the service level, and finally we explore the situation where customers will not opt for sharing their demand irrespective of the service level if the next attractive facility is too far way which we express by a distance threshold. These models are put forward to mimic realistic situations related to customer behavior when it comes to selecting a facility. Their respective mathematical formulations are put forward and tested on a case study and also over a range of larger data sets.     

Fuzzy logic based algorithms for maximum covering location problems

This paper concerns a class of maximum covering location problems in networks in uncertain environments. It is assumed that (a) relative weights of demand nodes are either deterministic or imprecise, described by linguistic expressions and (b) potential facility site locations are limited to network nodes. The concept of coverage is extended to include a degree of node coverage which means that the borders between the subset of covered demand nodes and the subset of uncovered demand nodes are inexact. The acceptable service distance/travelling times from a facility site to demand nodes are modelled by fuzzy sets. Three new algorithms for choosing the best facility locations are developed which assume that (1) demands at all nodes are equally important, (2) relative weights of demand at nodes are deterministic and (3) weights of demand at nodes are imprecise and described by linguistic terms, respectively. The algorithms are based on searching among potential facility nodes by applying comparison operations on discrete fuzzy sets. It is shown how to extend the proposed algorithms from one-site to multi-site covering problems. Illustrative examples of selecting locations for logistics centres in a distribution company are given.     

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.     

The generalized covering traveling salesman problem

In this paper we develop a problem with potential applications in humanitarian relief transportation and telecommunication networks. Given a set of vertices including the depot, facility and customer vertices, the goal is to construct a minimum length cycle over a subset of facilities while covering a given number of customers. Essentially, a customer is covered when it is located within a pre-specified distance of a visited facility on the tour. We propose two node-based and flow-based mathematical models and two metaheuristic algorithms including memetic algorithm and a variable neighborhood search for the problem. Computational tests on a set of randomly generated instances and on set of benchmark data indicate the effectiveness of the proposed algorithms.     

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.     

Generalized coverage: New developments in covering location models

The goal of the paper is to provide an overview of the following classes of models:Gradual cover models: These models seek to relax the “all or nothing” assumption by replacing it with a general coverage function which represents the proportion of demand covered at a certain distance from the facility.The cooperative cover model: This recently developed generalization is designed to replace the “individual coverage” assumption with a mechanism where all facilities contribute to the coverage of each demand point. This is accomplished by viewing coverage as the transmission of a “signal” by the facilities. The signal transmitted by each facility dissipates with distance. However, the signal received by each demand point is the aggregation of the transmissions from all the facilities. If the signal strength at the demand point exceeds a certain threshold, the point is covered, otherwise it is not.Variable radius model: This model is primarily designed to relax the “fixed coverage radius” assumption, making the coverage radius an endogenously determined function of the facility cost. Thus, instead of having to locate a certain pre-determined number of facilities, the decision-maker has a certain budget that can be used to construct facilities of different types, with the more expensive facilities having larger coverage radius.     

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.     

The Capacitated p-facility Location Problem on the Real Line

The problem we address involves locating p new facilities to service a set of customers or fixed points on the real line such that a measure of total cost will be minimized. A basic form of this problem was investigated by Love (1976), who observed that the fixed points must be allocated in sequence to the new facilities in an optimal solution, and thus, the problem can be solved by a dynamic programming algorithm. Since then, other forms of the model have been investigated; however, in all cases it is assumed that the new facilities have unlimited capacity so that customer flows are always allocated to the nearest facility. The objective of this paper is to analyze the effect of capacity constraints on the optimal locations of the new facilities. A general fixed-cost function is also included to account for practical considerations such as zoning regulations, and to permit the facilities to be located anywhere on the line instead of only at the fixed vertices. A dynamic programming method is formulated to solve the problem when the variable cost components are increasing convex functions of travel distance. The problem is shown to be NP-hard under more general cost structures.     

Solving a class of facility location problems using genetic algorithms

Locating p facilities to serve a number of customers is a problem in many areas of business. The problem is to determine p facility locations such that the weighted average distance traveled from all the demand points to their nearest facility sites is minimized. A variant of the p-median problem is one in which a maximum distance constraint is imposed between the demand point and its nearest facility location, also known as the p-median problem with maximum distance constraint. In this paper, we apply a fairly new methodology known as genetic algorithms to solve a relatively large sized constrained version of the p -median problem. We present our computational experience on the use of genetic algorithms for solving the constrained version of the p-median problem using two different data sets. Our comparative experimental experience shows that this solution procedure performs quite well compared with the results obtained from existing techniques.     

Heuristics for the single source capacitated multi-facility Weber problem

The Single Source Capacitated Multi-facility Weber Problem (SSCMWP) is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity such that each customer satisfies all its demand from exactly one facility. The SSCMWP is a non-convex optimization problem and difficult to solve. In the SSCMWP, customer locations, customer demands and facility capacities are known a priori. The transportation costs are proportional to the distance between customers and facilities. We consider both the Euclidean and rectilinear distance cases of the SSCMWP. We first present an Alternate Location and Allocation type heuristic and its extension by embedding a Very Large Scale Neighborhood search procedure. Then we apply a Discrete Approximation approach and propose both lower and upper bounding procedures for the SSCWMP using a Lagrangean Relaxation scheme. The proposed heuristics are compared with the solution approaches from the literature. According to extensive computational experiments on standard and randomly generated test sets, we can say that they yield promising performance.     

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.     

New heuristic algorithms for discrete competitive location problems with binary and partially binary customer behavior

We consider discrete location problems for an entering firm which competes with other established firms in a market where customers are spatially separated. In these problems, a given number of facility locations must be selected among a finite set of potential locations. The formulation and resolution of this type of problem depend on customers' behavior. The attraction for a facility depends on its characteristics and the distance between the facility and the customer. In this paper we study the location problem for the so-called Binary and Partially Binary Rules, in which the full demand of a customer is served by the most attractive facility, or by all the competing firms but patronizing only one facility of each firm, the one with the maximum attraction in the firm. Two new heuristic algorithms based on ranking of potential locations are proposed to deal with this sort of location problems. The proposed algorithms are compared with a classical genetic algorithm for a set of real geographical coordinates and population data of municipalities in Spain.     

A fuzzy clustering-based hybrid method for a multi-facility location problem

A fuzzy clustering-based hybrid method for a multi-facility location problem is presented in this study. It is assumed that capacity of each facility is unlimited. The method uses different approaches sequentially. Initially, customers are grouped by spherical and elliptical fuzzy cluster analysis methods in respect to their geographical locations. Different numbers of clusters are experimented. Then facilities are located at the proposed cluster centers. Finally each cluster is solved as a single facility location problem. The center of gravity method, which optimizes transportation costs is employed to fine tune the facility location. In order to compare logistical performance of the method, a real world data is gathered. Results of existing and proposed locations are reported.     

A fuzzy multi-objective covering-based vehicle location model for emergency services

Timeliness is one of the most important objectives that reflect the quality of emergency services such as ambulance and firefighting systems. To provide timeliness, system administrators may increase the number of service vehicles available. Unfortunately, increasing the number of vehicles is generally impossible due to capital constraints. In such a case, the efficient deployment of emergency service vehicles becomes a crucial issue. In this paper, a multi-objective covering-based emergency vehicle location model is proposed. The objectives considered in the model are maximization of the population covered by one vehicle, maximization of the population with backup coverage and increasing the service level by minimizing the total travel distance from locations at a distance bigger than a prespecified distance standard for all zones. Model applications with different solution approaches such as lexicographic linear programming and fuzzy goal programming (FGP) are provided through numerical illustrations to demonstrate the applicability of the model. Numerical results indicate that the model generates satisfactory solutions at an acceptable achievement level of desired goals.     

Constrained particle swarm algorithms for optimizing coverage of large-scale camera networks with mobile nodes

Proper sensor placement is crucial for maximizing the usability of large-scale sensor networks. Specially, the total sensible area covered by a sensor network can be maximized if we optimally arrange all sensors. To address this coverage optimization problem, this paper studies a typical sensor network—camera network. In this network, both locations and orientations of the cameras can be adjusted. An interesting constraint is the moving distance limitation. It transforms the optimization into a constrained problem. To tackle this problem, we investigate as possible solutions three variations of the particle swarm optimization (PSO) algorithm, namely the absorbing PSO, the penalty PSO, and the reflecting PSO. They are tested against several benchmarks. The experiments show that the PSO can be effectively applied on optimizing the coverage of the constrained camera network. And it can be easily adapted for coverage optimization of general sensor networks. The statistical analysis shows that the performances of the above three algorithms are in descending order. The results further prove that the absorbing PSO is an optimal choice for improving the coverage of the aforementioned sensor network.