A planar single-facility competitive location and design problem under the multi-deterministic choice rule

A new customer choice rule, which may model in some cases the actual patronising behaviour of customers towards the facilities closer to reality than other existing rules, is proposed. According to the new rule, customers split their demand among the firms in the market by patronising only one facility from each firm, the one with the highest utility, and the demand is split among those facilities proportionally to their attraction. The influence of the choice rule in the location of facilities is investigated. In particular, a new continuous competitive single-facility location and design problem using this new rule is proposed. Both exact and heuristic methods are proposed to solve it. A comparison with the classical proportional (or Huff) choice rule when solving the location model reveals that both the location and the quality of the new facility to be located may be quite different depending on the patronising behaviour of customers. Most importantly, the profit that the locating chain may lose if a wrong choice is made can be quite high in some instances.     

Constrained location of competitive facilities in the plane

This paper examines a competitive facility location problem occurring in the plane. A new gravity-based utility model is developed, in which the capacity of a facility serves as its measure of attractiveness. A new problem formulation is given, having elastic gravity-based demand, along with capacity, forbidden region, and budget constraints. Two solution algorithms are presented, one based on the big square small square method, and the second based on a penalty function formulation using fixed-point iteration. Computational testing is presented, comparing these two algorithms along with a general-purpose nonlinear solver.Scope and purposeIn a competitive business environment where products are not distinguishable, facility location plays an important role in an organization's success. This paper examines a firm's problem of selecting the locations in the plane for a set of new facilities such that market capture is maximized across all of the firm's facilities (both new and pre-existing). Customers are assumed to divide their demand among all competing facilities according to a utility function that considers facility attractiveness (measured by facility capacity for satisfying demand) and customer-facility distance. The level of customer demand is assumed to be a function of the facility configuration. Three types of constraints are introduced, involving facility capacity, forbidden regions for new facility location, and a budget function. Two solution algorithms are devised, one based on branch-and-bound methods and the other based on penalty functions. Computational testing is presented, comparing these two algorithms along with a general-purpose nonlinear solver.     

Discrete models for competitive location with foresight

We adapt the competitive location model based on maximal covering to include the knowledge that a competitor will enter the market later with a single new facility. The objective is to locate facilities under a budget constraint in order to maximise the remaining market share after the competitor's later entry.     

Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models

Companies frequently decide on the location and design for new facilities in a sequential way. However, for a fixed number of new facilities, the company might be able to improve its profit by taking its decisions for all the facilities simultaneously. In this paper we compare three different strategies: simultaneous location and independent design of two facilities in the plane, the same with equal designs, and the sequential approach of determining each facility in turn. The basic model is profit maximization for the chain, taking market share, location costs and design costs into account. The market share captured by each facility depends on the distance to the customers (location) and its quality (design), through a probabilistic Huff-like model. Recent research on this type of models was aimed at finding global optima for a single new facility, holding quality fixed or variable, but no exact algorithm has been proposed to find optimal solutions for more than one facility. We develop such an exact interval branch-and-bound algorithm to solve both simultaneous location and design two-facility problems. Then, we present computational results and exhibit the differences in locations and qualities of the optimal solutions one may obtain by the sequential and simultaneous approaches.     

Planar Location and Design of a New Facility with Inner and Outer Competition: An Interval Lexicographical-like Solution Procedure

A chain has to decide the location and design for a single new facility in a region where a set of facilities already exists offering the same type of product. Some of the existing facilities belong to the chain and the others are competitors. Since competition comes from outside the chain, the maximization of the profit is the main objective of the chain’s owner. Customers are supposed to patronize all the facilities, the old and the new, proportionally to the attraction they feel for them. The entrance of the new facility may thus also have a detrimental effect on the market shares of the existing chain-owned facilities, and this cannibalization should be minimized as a secondary objective. This problem is formulated as a biobjective optimization problem, and a variant of the lexicographic method is proposed to generate certain efficient solutions. This requires solving two related optimization problems, both neither convex nor concave, for which a unified interval branch and bound method is developed. Computational experiments on randomly generated problems show the feasibility of the approach, while an application of the model with real data demonstrates its use for economical analysis. This paper has been supported by the Ministry of Education and Science of Spain under the research project SEJ2005-06273/ECON, in part financed by the European Regional Development Fund (ERDF). Boglárka Tóth, on leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary.     

Two level General variable neighborhood search for Attractive traveling salesman problem

Attractive traveling salesman problem (AtTSP) consists of finding maximal profit tour starting and ending at a given depot after visiting some of the facilities. Total length of the tour must not exceed the given maximum distance. Each facility achieves profit from the customers, based on the distance between the facility and customers as well as on the attractiveness of that facility. Total profit of a tour is equal to a sum of profits of all visited facilities. In this paper, we develop a new variant of Variable neighborhood search, called 2-level General variable neighborhood search (2-GVNS) for solving AtTSP. At the second level, we use General variable neighborhood search in the local search lor building neighboring solution and checking its feasibility. Our 2-GVNS heuristic outperforms tabu search heuristic, the only one proposed in the literature so far, in terms of precision and running times. In addition, 2-GVNS finds all optimal known solutions obtained by Branch and cut algorithm and offers several new best known solutions.     

On minimax-regret Huff location models

We address the following single-facility location problem: a firm is entering into a market by locating one facility in a region of the plane. The demand captured from each user by the facility will be proportional to the users buying power and inversely proportional to a function of the user-facility distance. Uncertainty exists on the buying power (weight) of the users. This is modeled by assuming that a set of scenarios exists, each scenario corresponding to a weight realization. The objective is to locate the facility following the Savage criterion, i.e., the minimax-regret location is sought. The problem is formulated as a global optimization problem with objective written as difference of two convex monotonic functions. The numerical results obtained show that a branch and bound using this new method for obtaining bounds clearly outperforms benchmark procedures.     

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.     

竞争市场新进企业的容量设施选址研究

合理的设施选址方案对于企业进入新市场时占领市场份额具有重要的战略意义.竞争设施选址是考虑竞争者运行现有设施时如何在市场中启动新设施的问题.在实现特定市场份额条件下,以最小化新进企业成本为目标提出一种容量设施选址模型;设计一种双向选择机制,以确定设施与消费者之间的服务关系,并基于模拟退火框架,结合双向选择机制给出求解模型的算法;应用数值算例,分析企业市场份额、成本与预期市场份额指标之间的关系,并对原有企业的3种防御性选址策略进行有效性比较.     

A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem

In a dynamic market setting, firms need to quickly respond to shifting demographics and economic conditions. In this paper, we investigate the problem of determining the optimum set of locations for a firm, which operates a chain of facilities under competition. We consider the objective of maximizing profit, defined as gross profit margin minus logistics costs. We propose a location-routing model where revenue is realized according to probabilistic patronization of customers and routing costs are incurred due to vehicles serving the open facilities from a central depot. We propose a hybrid heuristic optimization methodology for solving this model. The optimal locations are searched for by a Genetic Algorithm while an integrated Tabu Search algorithm is employed for solving the underlying vehicle routing problem. The solution approach is tested on a real dataset of a supermarket chain. The results show that the location decisions made by the proposed methodology lead to increased market share and profit margin, while keeping logistics costs virtually unchanged. Finally, we present a GIS-based framework that can be used to store, analyze and visualize all data as well as model solutions in geographic format.     

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.     

Facility location in anticipation of future competition

In this paper, we consider locating a new facility in a competitive environment. A future competitor is expected to enter the market and locate his facility at its best site. The best location for one's own facility is to be found such that the market share captured following the competitor's entry is maximized. The problem is complicated because the best location for the competitor depends on the selected location for one's own facility. The problem is formulated using the gravity model for the estimation of market share. Three heuristic solution procedures are proposed. Computational experiments with these heuristics are presented.     

Incorporating competitors' reactions in facility location decisions: A market equilibrium approach

When a firm locates a new plant, and begins producing and shipping product to markets, this typically stimulates reactions by other firms supplying those markets. This suggests that to truly make a profit maximizing location decision, a firm must anticipate the market's reaction in the location decision-making process. In this paper, we review the development of a class of models designed to determine the profit maximizing location decision for a firm seeking to establish a manufacturing facility (or facilities) on a network characterized by either competitive or oligopolistic economic competition. One particular model from this class is presented, and the importance of anticipating the reaction to a location decision is illustrated through numerical examples of the model.     

Super facilities versus chaining in mitigating disruptions impacts

Dealing disruptions has increasingly attracted researchers’ attention in the last decades due to recent events: weather deregulation, natural disasters, financial crisis, etc. Researchers often dealt with the strategic aspect of the problem while making facility location decisions to build a robust supply chain. In this paper we address the flexibility aspect. We consider the problem of allocating demand arising from a set of products to a set of dedicated facilities. The facilities are subject to disruption and the demand is then lost. To mitigate disruption impacts, we consider the use of a super facility that can hold the demand of products when the dedicated facilities are under failure. In systems with identical products and facilities, we propose an algorithm that can be used to determine the optimal capacity of the super facility so as to minimize the sum of capacity investment, demand allocation and lost sales cost. Finally we compare the performance of the super facility configuration to that of the single chain configuration. The single chain refers to a facility configuration where each facility is configured to fulfill only two products and each product can be assigned to only two facilities and the whole system forms a closed chain.     

Semi-obnoxious single facility location in Euclidean space

This paper deals with the problem of determining within a bounded region the location for a new facility that serves certain demand points. For that purpose, the facility planners have two objectives. First, they attempt to minimize the undesirable effects introduced by the new facility by maximizing its minimum Euclidean distance with respect to all demand points (maximin). Secondly, they want to minimize the total transportation cost from the new facility to the demand points (minisum). Typical examples for such “semi-obnoxious” facilities are power plants that, as polluting agents, are undesirable and should be located far away from demand points, while cost considerations force planners to have the facility in close proximity to the customers. We describe the set of efficient solutions of this bi-criterion problem and propose an efficient algorithm for its solution.

Scope and purpose

It is becoming increasingly difficult to site necessary but potentially polluting (semi-obnoxious) facilities such as power plants, chemical plants, waste dumps, airports or train stations. More systematic decision-aid tools are needed to generate several options that balance the public's concerns with the interests of the developer or location planner. In this paper, a model is presented that generates the best possible sites (efficient solutions) with respect to two conflicting criteria: maximize distance from population centers and minimize total transportation costs. Having all efficient solutions at hand, the two sides can select one that best compromises their criteria. A very interesting property found is that most of these efficient solutions are on edges of a Voronoi diagram. An algorithm is developed that constructs the complete trajectory of efficient solutions.     

Fast metaheuristics for the discrete (r|p)-centroid problem

Two players, the leader and his competitor, open facilities, striving to capture the largest market share. The leader opens p facilities, then the follower opens r facilities. Each client chooses the nearest facility as his supplier. We need to choose p facilities of the leader in such a way as to maximize his market share. This problem can be represented as a bilevel programming problem. Based on this representation, in this work we propose two numerical approaches: local search with variable neighborhoods and stochastic tabu search. We pay the most attention to improving the methods’ efficiency at no loss to the quality of the resulting solutions. Results of numerical experiments support the possibility to quickly find an exact solution for the problem and solutions with small error.     

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.     

To innovate or not to innovate?

In this paper, we analyze the evolution of output decisions of adaptive firms in an environment of oligopolistic competition. The firm might either choose to produce one of several existing product variants or try to establish a new product variant on the market. The demand for each individual product variant is subject to a life cycle, but aggregate demand for product variants is constant over time. Every period each firm has to decide whether to produce the product again, introduce a new product variant itself (which generates an initial advantage on that market), or follow another firm and change to the production of an already established product. Different firms have heterogeneous abilities to develop products and imitate existing designs; therefore, the effects of the decision whether to imitate existing designs or to innovate differ between firms. We examine the evolution of behavior in this market using an agent-based simulation model. The firms are endowed with simple rules to estimate market potentials and market founding potentials of all firms, including themselves, and make their decisions using a stochastic learning rule. Furthermore, the characteristics of the firms change dynamically due to “learning by doing” effects. The main questions discussed are how the success and the optimal strategy of a firm depend on the interplay between characteristics of the industry and properties of the firm     

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.     

Computation of Multi-facility Location Nash Equilibria on a Network Under Quantity Competition

We deal with the location-quantity problem for competing firms when they locate multiple facilities and offer the same type of product. Competition is performed under delivered quantities that are sent from the facilities to the customers. This problem is reduced to a location game when the competing firms deliver the Cournot equilibrium quantities. While existence conditions for a Nash equilibrium of the location game have been discussed in many contributions in the literature, computing an equilibrium on a network when multiple facilities are to be located by each firm is a problem not previously addressed. We propose an integer linear programming formulation to fill this gap. The formulation solves the profit maximization problem for a firm, assuming that the other firms have fixed their facility locations. This allows us to compute location Nash equilibria by the best response procedure. A study with data of Spanish municipalities under different scenarios is presented and conclusions are drawn from a sensitivity analysis.