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.     

竞争环境下截流设施选址问题

研究企业新建设施时,市场上已有设施存在的情况下,使本企业总体利润最大的截流设施选址问题。在一般截留设施选址模型的基础上引入引力模型,消费者到某个设施接受服务的概率与偏离距离及设施的吸引力相关,同时设施的建设费用与设施吸引力正相关,建立非线性整数规划模型并使用贪婪算法进行求解。数值分析表明,该算法求解速度快,模型计算精度较高。     

竞争环境下截流问题的选址-价格模型

研究了竞争环境下考虑产品定价的截流设施选址问题。连锁企业在市场上新建设施时,市场上已有属于竞争对手的设施存在,在连锁企业新建设施位置确定之后,两个企业关于产品定价进行双寡头完全信息非合作博弈。定义了效用函数,引入Huff模型,以企业利润最大为目标,建立双层规划模型,证明了模型纳什均衡价格的存在性,并构造启发式算法对模型进行求解。算例分析表明,该算法求解结果较为理想,可用于大中型网络的规划选址问题。     

Heuristics for the facility location and design (1|1)-centroid problem on the plane

A chain (the leader) wants to set up a single new facility in a planar market where similar facilities of a competitor (the follower), and possibly of its own chain, are already present. The follower will react by locating another single facility after the leader locates its own facility. Fixed demand points split their demand probabilistically over all facilities in the market in proportion to their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational model. Both the location and the quality (design) of the new leader’s facility are to be found. The aim is to maximize the profit obtained by the leader following the follower’s entry. Four heuristics are proposed for this hard-to-solve global optimization problem, namely, a grid search procedure, an alternating method and two evolutionary algorithms. Computational experiments show that the evolutionary algorithm called UEGO_cent.SASS provides the best results.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

A two-level evolutionary algorithm for solving the facility location and design (1|1)-centroid problem on the plane with variable demand

In this work, the problem of a company or chain (the leader) that considers the reaction of a competitor chain (the follower) is studied. In particular, the leader wants to set up a single new facility in a planar market where similar facilities of the follower, and possibly of its own chain, are already present. The follower will react by locating another single facility after the leader locates its own facility. Both the location and the quality (representing design, quality of products, prices, etc.) of the new leader’s facility have to be found. The aim is to maximize the profit obtained by the leader considering the future follower’s entry. The demand is supposed to be concentrated at n demand points. Each demand point splits its buying power among the facilities proportionally to the attraction it feels for them. The attraction of a demand point for a facility depends on both the location and the quality of the facility. Usually, the demand is considered in the literature to be fixed or constant regardless the conditions of the market. In this paper, the demand varies depending on the attraction for the facilities. Taking variable demand into consideration makes the model more realistic. However, it increases the complexity of the problem and, therefore, the computational effort needed to solve it. Three heuristic methods are proposed to cope with this hard-to-solve global optimization problem, namely, a grid search procedure, a multistart algorithm and a two-level evolutionary algorithm. The computational studies show that the evolutionary algorithm is both the most robust algorithm and the one that provides the best results.     

Competitive facility location and design with reactions of competitors already in the market

A new retail facility is to locate and its service quality is to determine where similar facilities of competitors offering the same goods are already present. The market share captured by each facility depends on its distance to customers and its quality, which is described by a probabilistic Huff-like model. In order to maximize the profit of the new facility, a two-stage method is developed, which takes into account the reactions of the competitors. In the quality decision stage, the competitive decision process occurring among facilities is modelled as a game, whose solution is given by its Nash equilibrium. The solution, which can be represented as functions of the location of the new facility, is obtained by analytical resolution of a system of equations in the case of one facility in the market or by polynomial approximation in the case of multiple facilities. In the location decision stage, an interval based global optimization method is used to determine the best location of the new facility. Numerical experiments on randomly generated instances demonstrate the effectiveness of the method.     

A robust model for a leader–follower competitive facility location problem in a discrete space

This paper aims at determining the optimal locations for the leader’s new facilities under the condition that the number of the follower’s new facilities is unknown for the leader. The leader and the follower have some facilities in advance. The first competitor, the leader, opens p new facilities in order to increase her own market share. On the other hand, she knows that her competitor, the follower, will react to her action and locate his new facilities as well. The number of the follower’s new facilities is unknown for the leader but it is assumed that the leader knows the probability of opening different numbers of the follower’s new facilities. The leader aims at maximizing her own market share after the follower’s new facilities entry. The follower’s objective is also to maximize his own market share. Since the number of the follower’s new facilities is unknown for leader, “Robust Optimization” is used for maximizing the leader’s market share and making the obtained results “robust” in various scenarios in terms of different numbers of the follower’s new facilities. The optimal locations for new facilities of both the leader and the follower are chosen among pre-determined potential locations. It is assumed that the demand is inelastic. The customers probabilistically meet their demands from all different facilities and the demand level which is met by each facility is computed by Huff rule. The computational experiments have been applied to evaluate the efficiency of the proposed model.     

Customer Allocation in Maximum Capture Problems

The maximum capture (MAXCAP) model and its variants have been widely used to find the maximum capture that a firm can get as it enters a spatial market where there are already existing (competitor??s) facilities. While the model obtains the optimal demand capture, it however allows the customers to be assigned to the non-closest facility which may incur additional operating costs. A two stage method can be used that overcomes the drawback of the original model while requiring a negligible extra computational effort. To make the original model mathematically self contained and more concise two revised formulations of the problem RMAXCAP-1 and RMAXCAP-2 are proposed which assure that the customers patronize only their closest entering facilities. These models are tested on different sizes of datasets and their performances are compared.     

Environmentally friendly facility location with market competition

Many traditional facility location models assume spatial monopoly where market competition is ignored. Since facility locations affect the firm’s market exposure and subsequently its profit, accounting for the impact of the location decisions on customers while anticipating the reaction of competitor firms is essential. In this paper, we introduce a competitive facility location problem where market prices and production costs are determined through the economic equilibrium while explicitly considering competition from other firms. In order to accommodate for the growing efforts on limiting carbon emissions, the presented model includes constraints on the amount of carbon emissions that are due to transportation, while allowing carbon trading. The problem is formulated as a mixed integer non-linear model. Through numerical examples, we illustrate the effect of market competition on the location decisions and discuss the impact of emission limits and carbon trading on customers.     

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.     

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.     

A location–allocation problem for a web services provider in a competitive market

Web Services have become a viable component technology in distributed e-commerce platforms. Due to the move to high-speed Internet communication and tremendous increases in computing power, network latency has begun to play a more important role in determining service response time. Hence, the locations of a Web Services provider’s facilities, customer allocation, and the number of servers at each facility have a significant impact on its performance and customer satisfaction. In this paper we introduce a location–allocation model for a Web Services provider in a duopoly competitive market. Demands for services of these servers are available at each node of a network, and a subset of nodes is to be chosen to locate one or more servers in each. The objective is to maximize the provider’s profit. The problem is formulated and analyzed. An exact solution approach is developed and the results of its efficiency are reported.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

Global facility network design in the presence of competition

We study the facility network design problem for a global firm that is a monopolist seller in its domestic market but faces local competition in its foreign market. The global firm produces in the face of demand and exchange rate uncertainty but can postpone localization and distribution of the output until after uncertainties are resolved. The competitor in the foreign market, however, enjoys the flexibility of postponing all production activities until after uncertainties are resolved. The two firms engage in an ex-post Cournot competition in the foreign market. We consider three potential network configurations for the global firm. Under a linear demand function, we provide the necessary and sufficient condition that one of the three networks is the global firm’s optimal choice, and explore how the presence of foreign competition affects the sensitivity of the global firm’s design to various cost parameters and market uncertainties.     

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     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

Solving a Huff-like competitive location and design model for profit maximization in the plane

A chain wants to set up a single new facility in a planar market where similar facilities of competitors, and possibly of its own chain, are already present. Fixed demand points split their demand probabilistically over all facilities in the market proportionally with their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational or logit type model. Both the location and the quality (design) of the new facility are to be found so as to maximise the profit obtained for the chain. Several types of constraints and costs are considered.     

Optimal pricing and quantity of products with two offerings

This paper analyzes the decision of a firm offering two versions of a product, a deluxe and a regular. While both products satisfy the same market, the deluxe version is sold at a high price relative to its cost and is aimed at the high end of the demand curve. The regular version is sold at a low price relative to its cost and is targeted to customers at the low end of the demand curve. This two-offering strategy is especially popular with book publishers where a paperback book is introduced some time after the hardbound version is introduced. The time between the introduction of the two versions of the product is accompanied by a downward shift in the demand curve due to customers losing interest in the product or satisfying their demand from a secondary used market. We solve a profit maximization model for a firm using a two-offering strategy. The model is solved for linear and exponential deterioration in demand, which is assumed to be deterministic. Also, a model with linear deterioration in demand, which is assumed to be stochastic, is solved. The results indicate that substantial improvements in profit can be obtained by using the two-offering strategy. Numerical sensitivity analysis and examples are used to illustrate the results.