On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.     

A correction to the definition of local center

It is known that in order to solve the minimax facility location problem on a graph with a finite set of demand points, only a finite set of possible location points, called ‘local centers’ must be considered.It has been shown that the continuous m-center problem on a graph can be solved by using a series of set covering problems in which each local center covers the demand points at a distance not greater than a corresponding number called ‘the range’ of the local center.However, all points which are at the same distance from more than two demand points, and from which there is no direction where all these distances are decreasing, must also be considered as local centers. This paper proves that, in some special cases, it is not sufficient to consider only the points where this occurs with respect to pairs of demand points. The definition of local center is corrected and the corresponding results and algorithms are revised.     

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.     

The probabilistic 1-maximal covering problem on a network with discrete demand weights

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. 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 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.     

Restart strategies for GRASP with path-relinking heuristics

GRASP with path-relinking is a hybrid metaheuristic, or stochastic local search (Monte Carlo) method, for combinatorial optimization. A restart strategy in GRASP with path-relinking heuristics is a set of iterations {i ₁, i ₂, …} on which the heuristic is restarted from scratch using a new seed for the random number generator. Restart strategies have been shown to speed up stochastic local search algorithms. In this paper, we propose a new restart strategy for GRASP with path-relinking heuristics. We illustrate the speedup obtained with our restart strategy on GRASP with path-relinking heuristics for the maximum cut problem, the maximum weighted satisfiability problem, and the private virtual circuit routing problem.     

Discrete cooperative covering problems

A family of discrete cooperative covering problems is analysed in this paper. Each facility emits a signal that decays by the distance and each demand point observes the total signal emitted by all facilities. A demand point is covered if its cumulative signal exceeds a given threshold. We wish to maximize coverage by selecting locations for p facilities from a given set of potential sites. Two other problems that can be solved by the max-cover approach are the equivalents to set covering and p-centre problems. The problems are formulated, analysed and solved on networks. Optimal and heuristic algorithms are proposed and extensive computational experiments reported.     

A Procedure for Locating Emergency-Service Facilities for All Possible Response Distances

The problem of locating emergency-service facilities involves the assignment of a set of demand points to a set of facilities. One way to formulate the problem is to minimize the number of required facilities, given that the maximum distance between the demand points and their nearest facility does not exceed some specified value. We present a procedure for determining the numbers of such facilities for all possible values of the maximum distance. Computational results are presented for a microcomputer implementation.     

Multi-objective competitive location problem with distance-based attractiveness and its best non-dominated solution

The multi-objective competitive location problem (MOCLP) with distance-based attractiveness is introduced. There are m potential competitive facilities and n demand points on the same plane. All potential facilities can provide attractiveness to the demand point which the facility attractiveness is represented as distance-based coverage of a facility, which is “full coverage” within the maximum full coverage radius, “no coverage” outside the maximum partial coverage radius, and “partial coverage” between those two radii. Each demand point covered by one of m potential facilities is determined by the greatest accumulated attractiveness provided the selected facilities and least accumulated distances between each demand point and selected facility, simultaneously. The tradeoff of maximum accumulated attractiveness and minimum accumulated distances is represented as a multi-objective optimization model. A proposed solution procedure to find the best non-dominated solution set for MOCLP is introduced. Several numerical examples and instances comparing with introduced and exhaustive method demonstrates the good performance and efficiency for the proposed solution procedure.     

Experiments with LAGRASP heuristic for set k-covering

The set k-covering problem (SC _k P) is a variant of the classical set covering problem, in which each object is required to be covered at least k times. We describe a hybrid Lagrangean heuristic, named LAGRASP, which combines subgradient optimization and GRASP with path-relinking to solve the SC _k P. Computational experiments carried out on 135 test instances show experimentally that by properly tuning the parameters of LAGRASP, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, LAGRASP makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, whereas other strategies fail to find new improving solutions.     

An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

On a robustness property in single-facility location in continuous space

We consider a single-facility location problem in continuous space—here the problem of minimizing a sum or the maximum of the possibly weighted distances from a facility to a set of points of demand. The main result of this paper shows that every solution (optimal facility location) of this problem has an interesting robustness property. Any optimal facility location is the most robust in the following sense: given a suitable highest admissible cost, it allows the greatest perturbation of the locations of the demand without exceeding this highest admissible chosen cost.     

The variable radius covering problem

In this paper we propose a covering problem where the covering radius of a facility is controlled by the decision-maker; the cost of achieving a certain covering distance is assumed to be a monotonically increasing function of the distance (i.e., it costs more to establish a facility with a greater covering radius). The problem is to cover all demand points at a minimum cost by finding optimal number, locations and coverage radii for the facilities. Both, the planar and discrete versions of the model are considered. Heuristic approaches are suggested for solving large problems in the plane. These methods were tested on a set of planar problems. Mathematical programming formulations are proposed for the discrete problem, and a solution approach is suggested and tested.     

Demand Point Aggregation for Planar Covering Location Models

The covering location problem seeks the minimum number of facilities such that each demand point is within some given radius of its nearest facility. Such a model finds application mostly in locating emergency types of facilities. Since the problem is NP-hard in the plane, a common practice is to aggregate the demand points in order to reduce the computational burden. Aggregation makes the size of the problem more manageable but also introduces error. Identifying and controlling the magnitude of the error is the subject of this study. We suggest several aggregation methods with a priori error bounds, and conduct experiments to compare their performance. We find that the manner by which infeasibility is measured greatly affects the best choice of an aggregation method.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

A discrete competitive facility location model with variable attractiveness

We consider the discrete version of the competitive facility location problem in which new facilities have to be located by a new market entrant firm to compete against already existing facilities that may belong to one or more competitors. The demand is assumed to be aggregated at certain points in the plane and the new facilities can be located at predetermined candidate sites. We employ Huff's gravity-based rule in modelling the behaviour of the customers where the probability that customers at a demand point patronize a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. The objective of the firm is to determine the locations of the new facilities and their attractiveness levels so as to maximize the profit, which is calculated as the revenue from the customers less the fixed cost of opening the facilities and variable cost of setting their attractiveness levels. We formulate a mixed-integer nonlinear programming model for this problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and another branch-and-bound method with nonlinear programming relaxation. Computational results obtained on a set of randomly generated instances show that the last method outperforms the others in terms of accuracy and efficiency and can provide an optimal solution in a reasonable amount of time.     

Covering continuous demand in the plane

Continuous demand is generated in a convex polygon. A facility located in the area covers demand within a given radius. The objective is to find the locations for p facilities that cover the maximum demand in the area. A procedure that calculates the total area covered by a set of facilities is developed. A multi start heuristic approach for solving this problem is proposed by applying a gradient search from a randomly generated set of p locations for the facilities. Computational experiments for covering a square area illustrate the effectiveness of the proposed algorithm.     

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 Quintile Share Ratio in location analysis

The inequality measure “Quintile Share Ratio” (QSR or sometimes S80/S20) is the primary income inequality measure in the European Union’s set of indicators on social cohesion. An important reason for its adoption as a leading indicator is its simplicity. The Quintile Share Ratio is “The ratio of total income received by the 20% of the population with the highest income (top quintile) to that received by the 20% of the population with the lowest income (lowest quintile)”. The QSR concept is used in this paper in the context of obnoxious facility location where the inequality is in distances to the obnoxious facility. The single facility location problem minimizing the QSR is investigated. The problem is investigated for continuous uniform demand in an area such as a disk, a rectangle, and a line; when demand is generated at a finite set of demand points; and when the facility can be located anywhere on a network. Optimal solution algorithms are devised for demand originating at a finite set of demand points and at nodes of the network. Computational experiments demonstrate the effectiveness of the algorithms.     

Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution

We are concerned with a problem in which a firm or franchise enters a market by locating new facilities where there are existing facilities belonging to a competitor. The firm aims at finding the location and attractiveness of each facility to be opened so as to maximize its profit. The competitor, on the other hand, can react by adjusting the attractiveness of its existing facilities with the objective of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the facilities of the firm can be located at predetermined candidate sites. We employ Huff’s gravity-based rule in modeling the behavior of the customers where the fraction of customers at a demand point that visit a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. In order to find the optimal solution of this model, we convert it into an equivalent one-level mixed-integer nonlinear program so that it can be solved by global optimization methods. Apart from reporting computational results obtained on a set of randomly generated instances, we also compute the benefit the leader firm derives from anticipating the competitor’s reaction of adjusting the attractiveness levels of its facilities. The results on the test instances indicate that the benefit is 58.33% on the average.     

Spherical minimax location problem using the Euclidean norm: Formulation and optimization

The minimax spherical location problem is formulated in the Cartesian coordinate system using the Euclidean norm, instead of the spherical coordinate system using spherical arc distance measures. It is shown that minimizing the maximum of the spherical arc distances between the facility point and the demand points on a sphere is equivalent to minimizing the maximum of the corresponding Euclidean distances. The problem formulation in this manner helps to reduce Karush-Kuhn-Tucker necessary optimality conditions into the form of a set of coupled nonlinear equations, which is solved numerically by using a method of factored secant update with a finite difference approximation to the Jacobian. For a special case when the set of demand points is on a hemisphere and one or more point-antipodal point pair(s) are included in the demand points, a simplified approach gives a minimax point in a closed form.