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.     

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.     

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.     

A bilevel fixed charge location model for facilities under imminent attack

We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which m ranges from 10 to 30, and r varies between 1 and 3. The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender's facility opening plan is sensitive to the protection and distance costs.     

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

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

Optimal location policy for three competitive facilities

Competitive facility location problems have been investigated in many papers. In most, authors have applied location models with two competitors. In this paper three companies, which are mutually competitive, intend to locate their facilities in a linear market. It is well-known that Nash equilibrium solution for location problem does not include three competitive facilities. In this paper we present the optimal location strategies for three facilities. In our model we assume that the demands are continuously distributed in a linear market and the facilities are locating according to a specific order of sequence, A, B and C. We apply the Stackelberg equilibrium solutions for competitive location problems with three facilities. In our model, we consider the decision problems in three stages. In the first stage, we decide the optimal location of facility A, which is located optimally in respect to the remaining two facilities B and C. In the second stage, we determine the optimal location of facility B which is optimally located in respect to facility C, by utilizing the information on the location of facility A. Finally in the third stage problem we decide the location of facility C, optimally located by utilizing the information on the location of A and B. In the first stage, we need the optimal solutions of the second and third stages. In the second stage we need the optimal solution of the third stage problem. Therefore, first we solve the third stage problem which is the simplest. After that, we solve the second stage problem utilizing the optimal solution strategy of the third stage problem. In this paper we present the optimal location strategies for three facilities.     

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 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.     

一个关于求解k-种产品选址问题的近似算法

对于k-种产品工厂选址问题,有如下描述：存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。     

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.     

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.     

A memetic algorithm for bi-objective integrated forward/reverse logistics network design

Logistics network design is a major strategic issue due to its impact on the efficiency and responsiveness of the supply chain. This paper proposes a model for integrated logistics network design to avoid the sub-optimality caused by a separate, sequential design of forward and reverse logistics networks. First, a bi-objective mixed integer programming formulation is developed to minimize the total costs and maximize the responsiveness of a logistics network. To find the set of non-dominated solutions, an efficient multi-objective memetic algorithm is developed. The proposed solution algorithm uses a new dynamic search strategy by employing three different local searches. To assess the quality of the novel solution approach, the quality of its Pareto-optimal solutions is compared to those generated by an existing powerful multi-objective genetic algorithm from the recent literature and to exact solutions obtained by a commercial solver.     

Capacitated facility location problem with general setup cost

This paper presents an extension of the capacitated facility location problem (CFLP), in which the general setup cost functions and multiple facilities in one site are considered. The setup costs consist of a fixed term (site setup cost) plus a second term (facility setup costs). The facility setup cost functions are generally non-linear functions of the size of the facility in the same site. Two equivalent mixed integer linear programming (MIP) models are formulated for the problem and solved by general MIP solver. A Lagrangian heuristic algorithm (LHA) is also developed to find approximate solutions for this NP-hard problem. Extensive computational experiments are taken on randomly generated data and also well-known existing data (with some necessary modifications). The detailed results are provided and the heuristic algorithm is shown to be efficient.     

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.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

Dynamic supply chain design with inventory

In this paper, we deal with a facility location problem where we build new facilities or close down already existing facilities at two different distribution levels over a given time horizon. In addition, we allow to carry over stock in warehouses between consecutive periods. Our model intends to minimize the total costs, including transportation and inventory holding costs for products as well as fixed and operating costs for facilities.     

Hybrid imperialist competitive algorithm,variable neighborhood search,and simulated annealing for dynamic facility layout problem

Today’s manufacturing plants tend to be more flexible due to rapid changes in product mix and market demand. Therefore, this paper investigates the problem of location and relocation (when there are changes incurred to the material flows between departments) manufacturing facilities such that the total cost of material flows and relocation costs are minimized. This problem is known as the dynamic facility layout problem (DFLP), which is a general case of static facility layout problem. This paper proposes a robust and simply structured hybrid technique based on integrating three meta-heuristics: imperialist competitive algorithms, variable neighborhood search, and simulated annealing, to efficiently solve the DFLP. The novel aspect of the proposed algorithm is taking advantage of features of all above three algorithms together. To test the efficiency of our algorithm, a data set from the literature is used for the experimental purpose. The results obtained are quite promising in terms of solution quality for most of the test problems.     

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.     

Robust capacitated facility location model for acquisitions under uncertainty

We study a new robust formulation for strategic location and capacity planning considering potential company acquisitions under uncertainty. Long-term logistics network planning is among the most difficult decisions for supply-chain managers. While costs, demands, etc. may be known or estimated well for the short-term, their future development is uncertain and difficult to predict.A new model formulation for the robust capacitated facility location problem is presented to cope with uncertainty in planning. Minimizing the expectation of the relative regrets across scenarios over multiple periods is the objective. It is achieved by dynamically assigning multi-level production allocations, locations and capacity adjustments for uncertain parameter development over time. Considering acquisitions for profit maximization and its supply-chain impact is new as well as the simultaneous decision of capacity adjustment and facility location over time. The solution of the novel robust formulation provides a single setup where good results can be achieved for any realized scenario. Hence, the solution may not be optimal for one particular scenario but may be good, i.e. the highest expected profit to gain, for any highly probable future realization. We show that robust mixed-integer linear programming model achieves superior results to the deterministic configurations in exhaustive computational tests. This dynamic robust formulation allows the supply-chain to favorably adapt to acquisitions and uncertain developments of revenue, demand and costs and hence reduces the potential negative impacts of uncertainty on supply-chain operations.     

Hybrid evolutionary algorithm with extreme machine learning fitness function evaluation for two-stage capacitated facility location problems

This paper considers the two-stage capacitated facility location problem (TSCFLP) in which products manufactured in plants are delivered to customers via storage depots. Customer demands are satisfied subject to limited plant production and limited depot storage capacity. The objective is to determine the locations of plants and depots in order to minimize the total cost including the fixed cost and transportation cost. However, the problem is known to be NP-hard. A practicable exact algorithm is impossible to be developed. In order to solve large-sized problems encountered in the practical decision process, an efficient alternative approximate method becomes more valuable. This paper aims to propose a hybrid evolutionary algorithm framework with machine learning fitness approximation for delivering better solutions in a reasonable amount of computational time. In our study, genetic operators are adopted to perform the search process and a local search strategy is used to refine the best solution found in the population. To avoid the expensive consumption of computational time during the fitness evaluating process, the framework uses extreme machine learning to approximate the fitness of most individuals. Moreover, two heuristics based on the characteristics of the problem is incorporated to generate a good initial population. Computational experiments are performed on two sets of test instances from the recent literature. The performance of the proposed algorithm is evaluated and analyzed. Compared with other algorithms in the literature, the proposed algorithm can find the optimal or near-optimal solutions in a reasonable amount of computational time. By employing the proposed algorithm, facilities can be positioned more efficiently, which means the fixed cost and the transportation cost can be decreased significantly, and organizations can enhance competitiveness by using the optimized facility location scheme.