Location equilibria for a continuous competitive facility location problem under delivered pricing

The problem of finding location equilibria of a location-price game where firms first select their locations and then set delivered prices in order to maximise their profits is investigated. Assuming that firms set the equilibrium prices in the second stage, the game can be reduced to a location game for which a global minimiser of the social cost is a location equilibrium, provided that the demand is completely inelastic and the marginal production cost is constant. When the set of feasible locations is a region of the plane the minimisation of the social cost becomes a hard-to-solve global optimisation problem. We propose an exact interval branch-and-bound algorithm suitable for small and medium size problems and an alternating Weiszfeld-like heuristic for larger instances. The latter approach is based on a new iterative formula for which the validity of the descent property is proved. The proposed heuristic performs extremely well against the exact method when tested on small to medium size instances while requiring a tiny fraction of its computational time.     

Models and algorithms for competitive facility location problems with different customer behavior

Competitive facility location problems arise in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. We assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. For this bi-level optimization problem we consider six different customer behavior scenarios from the literature: binary, proportional and partially binary, each combined with essential and unessential demand. The decision making for the leader and the follower depends on these scenarios. In this work we present mixed integer linear programming models for the follower problem of each scenario and use them in combination with an evolutionary algorithm to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them efficiently into similar, not yet considered ones. We present numerical results of our algorithm and compare them to so far state-of-the-art approaches from the literature. Our method shows good performance in all customer behavior scenarios and is able to outperform previous solution procedures on many occasions.     

A leader-follower game in competitive facility location

We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits 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. We propose heuristics that combine tabu search with exact solution methods.     

Branch-and-bound algorithm for a competitive facility location problem

We study a mathematical model generalizing the well-known facility location problem. In this model we consider two competing sides successively placing their facilities and aiming to “capture” consumers, in order to make maximal profit. We state the problem as a bilevel integer programming problem, regarding optimal noncooperative solutions as optimal solutions. We propose a branch-and-bound algorithm for finding the optimal noncooperative solution. While constructing the algorithm, we represent our problem as the problem of maximizing a pseudo-Boolean function. An important ingredient of the algorithm is a method for calculating an upper bound for the values of the pseudo-Boolean function on subsets of solutions. We present the results of a simulation demonstrating the computational capabilities of the proposed algorithm.     

A simple and deterministic competitive algorithm for online facility location

This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is O (log n)-competitive under these various models, where n is the total number of customers. It also shows that the algorithm is O (1)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.     

An integrated approach to facility location problems

An integrated analysis approach to facility location problems is described. The approach is based on integrating analytical location models and a multicriteria decision model.     

Randomized local search for the discrete competitive facility location problem

Consider a finite set of consumers that two competing companies are willing to service. The companies open facilities one by one. The set of locations available to open facilities is finite. The problem is to find a facility location for the first company that maximizes its profit given that the second company also makes its decision by maximizing the profit. We propose a randomized local search scheme that employs an internal local search procedure to estimate the solutions being enumerated. Numerical experiments with random input data show that the scheme is able to find high quality approximate solutions for examples with dimension that has not been amenable to previously known algorithms.     

Applied p-median and p-center algorithms for facility location problems

Facility location problems with the objective to minimize the sum of the setup cost and transportation cost are studied in this paper. The setup and transportation costs are considered as a function of the number of opened facilities. Three methods are introduced to solve the problem. The facility location model with bounds for the number of opened facility is constructed in this work. The relationship between setup cost and transportation cost is studied and used to build these methods based on greedy algorithm, p-median algorithm and p-center algorithm. The performance of the constructed methods is tested using 100 random data sets. In addition, the networks representing the road transportation system of Chiang Mai city and 5 provinces in Northern Thailand are illustrated and tested using all presented methods. Simulation results show that the method developed from greedy algorithm is suitable for solving problems when the setup cost is higher than transportation cost while the opposite cases are more efficiently solved with the method developed by the p-median problem.     

Covering problems in facility location: A review

In this study, we review the covering problems in facility location. Here, besides a number of reviews on covering problems, a comprehensive review of models, solutions and applications related to the covering problem is presented after Schilling, Jayaraman, and Barkhi (1993). This survey tries to review all aspects of the covering problems by stressing the works after Schilling, Jayaraman, and Barkhi (1993). We first present the covering problems and then investigate solutions and applications. A summary and future works conclude the paper.     

基于竞争环境的截流设施选址与车辆路径问题

研究竞争环境下截流设施选址与带时间窗的多中心车辆路径问题。首先,在考虑设施覆盖范围衰退的情况下,利用阶梯型效用函数和偏离距离描述消费者的选择行为,并确定截流设施的需求量;然后,采用基于聚集度的启发式算法对门店进行分类,借助双层规划法,建立门店选址与车辆路径安排的多目标整数规划模型;最后,采用改进的蚁群算法进行求解。通过分析对比实验结果,验证了模型的有效性和可行性。     

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

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

Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem

A bi-objective competitive facility location and design problem is considered. The problem of obtaining a complete representation of the efficient set and its corresponding Pareto-front has been previously tackled through exact general methods, but they require high computational effort. In this work, we propose a new evolutionary multi-objective optimization algorithm, named FEMOEA, which deals with the problem at hand in a fast and efficient way. It combines ideas from different multi-objective and single-objective optimization evolutionary algorithms, although it also incorporates new devices which help to reduce the computational requirements, and also to improve the quality of the provided solutions. The performance of the algorithm is analyzed by comparing it to other (meta)heuristics previously proposed in the literature. In particular, the reference algorithms MOEA/D, SPEA2 and NSGA-II have been considered. A comprehensive computational study shows that the new heuristic method outperforms, on average, the three heuristic algorithms. Additionally, it reduces, on average, the computing time of the exact methods by approximately 99%, and this offering high-quality discrete approximations of the true Pareto-front.     

A simultaneous facility location,vehicle routing and dynamic pricing in a distribution network

This paper incorporates location, pricing and routing decisions by the goal of maximizing profit in a distribution network. In this problem, multiple consecutive time periods are considered in the decision of depot locations at the beginning of the planning horizon, pricing, and routing during each period. According to the varying willingness to pay (w.t.p) of the consumers across different regions and time periods, dynamic regional pricing techniques were incorporated into this problem. In this study, a non-linear mixed integer model is proposed for solving the problem. This model is then converted into a mixed integer quadratic constrained problem that can be solved with the CPLEX solver. Due to the inability of the exact algorithm to solve certain medium and all large instances, and in order to improve the obtained upper bounds for medium test problems, lagrangian relaxation (LR) was introduced. Two pure and hybrid heuristic algorithms are proposed for tackling this problem. The heuristic algorithm includes price optimization and location-routing steps. In the hybrid heuristics, these steps are embedded in the particle swarm optimization (PSO) and self-learning PSO (SLPSO) algorithms framework. Computational experiments illustrate the efficiency of the proposed algorithms. Sensitivity analysis indicates the necessity of switching from the pure heuristic to the hybrid version for scarce capacity settings.     

On the competitive facility location problem with a free choice of suppliers

We consider a mathematical model from the class of competitive sequential facility location problems. In these problems, the competitors sequentially open their facilities, and each side aims to “capture” the consumers and maximize its profits. In the proposed model, we consider a situation of a “free” choice by each side of an open facility to service a customer. The model is formulated as a bilevel integer programming problem. We show that the problem of finding an optimal noncooperative solution can be represented as a maximization problem for a pseudo-Boolean function. We propose an algorithm for constructing an admissible noncooperative solution for fixed values of the variables in this pseudo-Boolean function. We also propose a method for constructing an upper bound on the maximal value of the pseudo-Boolean function on subsets of solutions defined by partial (0, 1)-vectors.     

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.     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

A dual RAMP algorithm for single source capacitated facility location problems

Annals of Mathematics and Artificial Intelligence - In this paper, we address the Single Source Capacitated Facility Location Problem (SSCFLP) which considers a set of possible locations for...     

The big cube small cube solution method for multidimensional facility location problems

In this paper we propose a general solution method for (non-differentiable) facility location problems with more than two variables as an extension of the Big Square Small Square technique (BSSS). We develop a general framework based on lower bounds and discarding tests for every location problem. We demonstrate our approach on three problems: the Fermat–Weber problem with positive and negative weights, the median circle problem, and the p-median problem. For each of these problems we show how to calculate lower bounds and discarding tests. Computational experiences are given which show that the proposed solution method is fast and exact.     

Connected facility location via random facility sampling and core detouring

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems.