A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

Modelling lost demand in competitive facility location

In this paper, we propose a simple new approach to model lost demand (also referred to as elastic demand) in competitive facility location. A ‘dummy’ competing facility that attracts the lost demand is added to the list of competing facilities. All competitive facility location models, regardless of their complexity or assumptions, can be modified to include lost demand and be solved by the same algorithms designed for standard models once the dummy facility is added to the data as an additional competitor.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Optimal location and design of a competitive facility

A single facility has to be located in competition with fixed existing facilities of similar type. Demand is supposed to be concentrated at a finite number of points, and consumers patronise the facility to which they are attracted most. Attraction is expressed by some function of the quality of the facility and its distance to demand. For existing facilities quality is fixed, while quality of the new facility may be freely chosen at known costs. The total demand captured by the new facility generates income. The question is to find that location and quality for the new facility which maximises the resulting profits.It is shown that this problem is well posed as soon as consumers are novelty oriented, i.e. attraction ties are resolved in favour of the new facility. Solution of the problem then may be reduced to a bicriterion maxcovering-minquantile problem for which solution methods are known. In the planar case with Euclidean distances and a variety of attraction functions this leads to a finite algorithm polynomial in the number of consumers, whereas, for more general instances, the search of a maximal profit solution is reduced to solving a series of small-scale nonlinear optimisation problems. Alternative tie-resolution rules are finally shown to result in problems in which optimal solutions might not exist.Mathematics Subject Classification (2000):90B85, 90C30, 90C29, 91B42Partially supported by Grant PB96-1416-C02-02 of the D.G.E.S. and Grant BFM2002-04525-C02-02 of Ministerio de Ciencia y Tecnología, Spain     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.     

Approximate algorithms for the competitive facility location problem

We consider the competitive facility location problem in which two competing sides (the Leader and the Follower) open in succession their facilities, and each consumer chooses one of the open facilities basing on its own preferences. The problem amounts to choosing the Leader’s facility locations so that to obtain maximal profit taking into account the subsequent facility location by the Follower who also aims to obtain maximal profit. We state the problem as a two-level integer programming problem. A method is proposed for calculating an upper bound for the maximal profit of the Leader. The corresponding algorithm amounts to constructing the classical maximum facility location problem and finding an optimal solution to it. Simultaneously with calculating an upper bound we construct an initial approximate solution to the competitive facility location problem. We propose some local search algorithms for improving the initial approximate solutions. We include the results of some simulations with the proposed algorithms, which enable us to estimate the precision of the resulting approximate solutions and give a comparative estimate for the quality of the algorithms under consideration for constructing the approximate solutions to the problem.     

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.     

Existence theory for spatially competitive network facility location models

Models for locating a firm's production facilities while simultaneously determining production levels at these facilities and shipping patterns so as to maximize the firm's profits are presented. In these models, existing firms, are assumed to act in accordance with an appropriate model of spatial equilibrium. A proof of existence of a solution to the combined location-equilibrium problem is provided.     

Recent insights in Huff-like competitive facility location and design

Recently, several articles appeared on the location–design problem that firms face when entering a competing market. All use a Huff-like attraction model. We discuss the formulation of the base model, the different settings studied in the papers and summarise their findings.     

Upper bounds for objective functions of discrete competitive facility location problems

Under study is the problem of locating facilities when two competing companies successively open their facilities. Each client chooses an open facility according to his own preferences and return interests to the leader firm or to the follower firm. The problem is to locate the leader firm so as to realize the maximum profit (gain) subject to the responses of the follower company and the available preferences of clients. We give some formulations of the problems under consideration in the form of two-level integer linear programming problems and, equivalently, as pseudo-Boolean two-level programming problems. We suggest a method of constructing some upper bounds for the objective functions of the competitive facility location problems. Our algorithm consists in constructing an auxiliary pseudo-Boolean function, which we call an estimation function, and finding the minimum value of this function. For the special case of the competitive facility location problems on paths, we give polynomial-time algorithms for finding optimal solutions. Some results of computational experiments allow us to estimate the accuracy of calculating the upper bounds for the competitive location problems on paths.     

Heuristic algorithms for delivered price spatially competitive network facility location problems

We review previous formulations of models for locating a firm's production facilities while simultaneously determining production levels at those facilities so as to maximize the firm's profit. We enhance these formulations by adding explicit variables to represent the firm's shipping activities and discuss the implications of this revised approach. In these formulations, existing firms, as well as new entrants, are assumed to act in accordance with an appropriate model of spatial equilibrium. The firm locating new production facilities is assumed to be a large manufacturer entering an industry composed of a large number of small firms. Our previously reported proof of existence of a solution to the combined location-equilibrium problem is briefly reviewed. A heuristic algorithm based on sensitivity analysis methods which presume the existence of a solution and which locally approximate price changes as linear functions of production perturbations resulting from newly established facilities is presented. We provide several numerical tests to illustrate the contrasting locational solutions which this paper's revised delivered price formulation generates relative to those of previous formulations. An exact, although computationally burdensome, method is also presented and employed to check the reliability of the heuristic algorithm.     

Strategic facility location: A review

Facility location decisions are a critical element in strategic planning for a wide range of private and public firms. The ramifications of siting facilities are broadly based and long-lasting, impacting numerous operational and logistical decisions. High costs associated with property acquisition and facility construction make facility location or relocation projects long-term investments. To make such undertakings profitable, firms plan for new facilities to remain in place and in operation for an extended time period. Thus, decision makers must select sites that will not simply perform well according to the current system state, but that will continue to be profitable for the facility's lifetime, even as environmental factors change, populations shift, and market trends evolve. Finding robust facility locations is thus a difficult task, demanding that decision makers account for uncertain future events. The complexity of this problem has limited much of the facility location literature to simplified static and deterministic models. Although a few researchers initiated the study of stochastic and dynamic aspects of facility location many years ago, most of the research dedicated to these issues has been published in recent years. In this review, we report on literature which explicitly addresses the strategic nature of facility location problems by considering either stochastic or dynamic problem characteristics. Dynamic formulations focus on the difficult timing issues involved in locating a facility (or facilities) over an extended horizon. Stochastic formulations attempt to capture the uncertainty in problem input parameters such as forecast demand or distance values. The stochastic literature is divided into two classes: that which explicitly considers the probability distribution of uncertain parameters, and that which captures uncertainty through scenario planning. A wide range of model formulations and solution approaches are discussed, with applications ranging across numerous industries.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

The branch-and-bound algorithm for a competitive facility location problem with the prescribed choice of suppliers

In the mathematical model under study, the two competing sides consecutively place their facilities aiming to capture consumers and maximize profits. The model amounts to a bilevel integer programming problem. We take the optimal noncooperative solutions as optimal to this problem. To find approximate and optimal solutions, we propose a branch-and-bound algorithm. Simulations show that the algorithm can be applied to solve the individual problems of low and medium dimension.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

An exact cooperative method for the uncapacitated facility location problem

In this paper, we present a cooperative primal-dual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a known and effective tabu search procedure, and a dual process, which performs a lagrangian branch-and-bound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branch-and-bound nodes: decision-variable bound tightening rules applied at each node, and a subgradient caching strategy to improve the bundle method applied at each node.     

Multiple criteria facility location problems: A survey

This paper provides a review on recent efforts and development in multi-criteria location problems in three categories including bi-objective, multi-objective and multi-attribute problems and their solution methods. Also, it provides an overview on various criteria used. While there are a few chapters or sections in different location books related to this topic, we have not seen any comprehensive review papers or book chapter that can cover it. We believe this paper can be used as a complementary and updated version.     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题. 研究中首先利用原始对偶技巧得到 9-近似算法, 然后利用贪婪增广技巧将近似比改进到2.606, 最后讨论了该问题的相应变形问题.     

An improved per-scenario bound for the two-stage stochastic facility location problem

We study the two-stage stochastic facility location problem(2-SFLP)by proposing an LP(location problem)-rounding approximation algorithm with 2.3613 per-scenario bound for this problem,improving the previously best per-scenario bound of 2.4957.