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.     

Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming model and its solution

We are concerned with a problem in which a firm or franchise enters a market by locating new facilities where there are existing facilities belonging to a competitor. The firm aims at finding the location and attractiveness of each facility to be opened so as to maximize its profit. The competitor, on the other hand, can react by adjusting the attractiveness of its existing facilities with the objective of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the facilities of the firm can be located at predetermined candidate sites. We employ Huff’s gravity-based rule in modeling the behavior of the customers where the fraction of customers at a demand point that visit 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. In order to find the optimal solution of this model, we convert it into an equivalent one-level mixed-integer nonlinear program so that it can be solved by global optimization methods. Apart from reporting computational results obtained on a set of randomly generated instances, we also compute the benefit the leader firm derives from anticipating the competitor’s reaction of adjusting the attractiveness levels of its facilities. The results on the test instances indicate that the benefit is 58.33% on the average.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

The equitable location problem on the plane

This paper considers the problem of locating M facilities on the unit square so as to minimize the maximal demand faced by each facility subject to closest assignments and coverage constraints. Focusing on uniform demand over the unit square, we develop upper and lower bounds on feasibility of the problem for a given number of facilities and coverage radius. Based on these bounds and numerical experiments we suggest a heuristic to solve the problem. Our computational results show that the heuristic is very efficient, as the average gap between its solutions and the lower bound is 4.34%.     

Parallel algorithms for continuous multifacility competitive location problems

We consider a continuous location problem in which a firm wants to set up two or more new facilities in a competitive environment. Both the locations and the qualities of the new facilities are to be found so as to maximize the profit obtained by the firm. This hard-to-solve global optimization problem has been addressed in Redondo et al. (Evol. Comput.17(1), 21–53, 2009) using several heuristic approaches. Through a comprehensive computational study, it was shown that the evolutionary algorithm uego is the heuristic which provides the best solutions. In this work, uego is parallelized in order to reduce the computational time of the sequential version, while preserving its capability at finding the optimal solutions. The parallelization follows a coarse-grain model, where each processing element executes the uego algorithm independently of the others during most of the time. Nevertheless, some genetic information can migrate from a processor to another occasionally, according to a migratory policy. Two migration processes, named Ring-Opt and Ring-Fusion2, have been adapted to cope the multiple facilities location problem, and a superlinear speedup has been obtained.     

Location of Multiple-Server Congestible Facilities for Maximizing Expected Demand, when Services are Non-Essential

We formulate a model for locating multiple-server, congestible facilities. Locations of these facilities maximize total expected demand attended over the region. The effective demand at each node is elastic to the travel time to the facility, and to the congestion at that facility. The facilities to be located are fixed, so customers travel to them in order to receive service or goods, and the demand curves at each demand node (which depend on the travel time and the queue length at the facility), are known. We propose a heuristic for the resulting integer, nonlinear formulation, and provide computational experience.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

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.     

Covering continuous demand in the plane

Continuous demand is generated in a convex polygon. A facility located in the area covers demand within a given radius. The objective is to find the locations for p facilities that cover the maximum demand in the area. A procedure that calculates the total area covered by a set of facilities is developed. A multi start heuristic approach for solving this problem is proposed by applying a gradient search from a randomly generated set of p locations for the facilities. Computational experiments for covering a square area illustrate the effectiveness of the proposed algorithm.     

Discrete cooperative covering problems

A family of discrete cooperative covering problems is analysed in this paper. Each facility emits a signal that decays by the distance and each demand point observes the total signal emitted by all facilities. A demand point is covered if its cumulative signal exceeds a given threshold. We wish to maximize coverage by selecting locations for p facilities from a given set of potential sites. Two other problems that can be solved by the max-cover approach are the equivalents to set covering and p-centre problems. The problems are formulated, analysed and solved on networks. Optimal and heuristic algorithms are proposed and extensive computational experiments reported.     

The stochastic economic lot sizing problem for non-stop multi-grade production with sequence-restricted setup changeovers

We study a variant of the stochastic economic lot scheduling problem (SELSP) encountered in process industries, in which a single production facility must produce several different grades of a family of products to meet random stationary demand for each grade from a common finished-goods (FG) inventory buffer that has limited storage capacity. When the facility is set up to produce a particular grade, the only allowable changeovers are from that grade to the next lower or higher grade. Raw material is always available, and the production facility produces continuously at a constant rate even during changeover transitions. All changeover times are constant and equal to each other, and demand that cannot be satisfied directly from inventory is lost. There is a changeover cost per changeover occasion, a spill-over cost per unit of product in excess whenever there is not enough space in the FG buffer to store the produced grade, and a lost-sales cost per unit short whenever there is not enough FG inventory to satisfy the demand. We model the SELSP as a discrete-time Markov decision process (MDP), where in each time period the decision is whether to initiate a changeover to a neighboring grade or keep the set up of the production facility unchanged, based on the current state of the system, which is defined by the current set up of the facility and the FG inventory levels of all the grades. The goal is to minimize the (long-run) expected average cost per period. For problems with more than three grades, we develop a heuristic solution procedure which is based on decomposing the original multi-grade problem into several 3-grade MDP sub-problems, numerically solving each sub-problem using value iteration, and constructing the final policy for the original problem by combining parts of the optimal policies of the sub-problems. We present numerical results for problem examples with 2–5 grades. For the 2- and 3-grade examples, we numerically solve the exact MDP problem using value iteration to obtain insights into the structure of the optimal changeover policy. For the 4- and 5-grade examples, we compare the performance of the decomposition-based heuristic (DBH) solution procedure against that obtained by numerically solving the exact problem. We also compare the performance of the DBH method against the performance of three simpler parameterized heuristics. Finally, we compare the performance of the DBH and the exact solution procedures for the case where the FG inventory storage consists of a number of separate general-purpose silos capable of storing any grade as long as it is not mixed with any other grade.     

γ-Robust facility relocation problem

In this paper, we consider relocating facilities, where we have demand changes in the network. Relocations are performed by closing some of the existing facilities from low demand areas and opening new ones in newly emerging areas. However, the actual changes of demand are not known in advance. Therefore, different scenarios with known probabilities are used to capture such demand changes. We develop a mixed integer programming model for facility relocation that minimizes the expected weighted distance while making sure that relative regret for each scenario is no greater than γ. We analyzed the problem structure and developed a Lagrangian Decomposition Algorithm (LDA) to expedite the solution process. Numerical experiments are carried out to show the performance of LDA against the exact solution method.     

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.     

Solving the Passive Optical Network with Fiber Duct Sharing Planning Problem Using Discrete Techniques

Similar to the constrained facility location problem, the passive optical network (PON) planning problem necessitates the search for a subset of deployed facilities (splitters) and their allocated demand points (optical network units) to minimize the overall deployment cost. In this paper we use a mixed integer linear programming formulation stemming from network flow optimization to construct a heuristic based on limiting the total number of interconnecting paths when implementing fiber duct sharing. Then, a disintegration heuristic involving the construction of valid clusters from the output of a k means algorithm, reduce the time complexity while ensuring close to optimal results. The proposed heuristics are then evaluated using a real-world dataset, showing favourable performance.     

The obnoxious p facility network location problem with facility interaction

Three heuristics are proposed to solve the maximin formulation for siting p facilities on a network considering a pollution dispersion equation and facility interaction. Initially, the single facility problem is approached by building up polygons which model pollution spread about the nodes of the network. This is extended in the first heuristic to the p facility problem. The second combines both the p-maximin and p-maxisum objectives in a lexicographic manner. The third is based on recent developments of Simulated Annealing. The proposed heuristics are evaluated for up to six facilities on a set of randomly generated networks having 20 to 40 nodes and low or medium arc density.     

Optimizing capacity,pricing and location decisions on a congested network with balking

In this paper, we consider the problem of making simultaneous decisions on the location, service rate (capacity) and the price of providing service for facilities on a network. We assume that the demand for service from each node of the network follows a Poisson process. The demand is assumed to depend on both price and distance. All facilities are assumed to charge the same price and customers wishing to obtain service choose a facility according to a Multinomial Logit function. Upon arrival to a facility, customers may join the system after observing the number of people in the queue. Service time at each facility is assumed to be exponentially distributed. We first present several structural results. Then, we propose an algorithm to obtain the optimal service rate and an approximate optimal price at each facility. We also develop a heuristic algorithm to find the locations of the facilities based on the tabu search method. We demonstrate the efficiency of the algorithms numerically.     

Inventory Control for Supply Chains with Service Level Constraints: A Synergy between Large Deviations and Perturbation Analysis

We consider a model of a supply chain consisting of n production facilities in tandem and producing a single product class. External demand is met from the finished goods inventory maintained in front of the most downstream facility (stage 1); unsatisfied demand is backlogged. We adopt a base-stock production policy at each stage of the supply chain, according to which the facility at stage i produces if inventory falls below a certain level w _i and idles otherwise. We seek to optimize the hedging vector w=(w ₁,...,w _n ) to minimize expected inventory costs at all stages subject to maintaining the stockout probability at stage 1 below a prescribed level (service level constraint). We make rather general modeling assumptions on demand and production processes that include autocorrelated stochastic processes. We solve this stochastic optimization problem by combining analytical (large deviations) and sample path-based (perturbation analysis) techniques. We demonstrate that there is a natural synergy between these two approaches.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

Optimal algorithms for the α-neighbor p-center problem

Assigning multiple service facilities to demand points is important when demand points are required to withstand service facility failures. Such failures may result from a multitude of causes, ranging from technical difficulties to natural disasters. The α-neighbor p-center problem deals with locating p service facilities. Each demand point is assigned to its nearest α service facilities, thus it is able to withstand up to α − 1 service facility failures. The objective is to minimize the maximum distance between a demand point and its αth nearest service facility. We present two optimal algorithms for both the continuous and discrete α-neighbor p-center problem. We present experimental results comparing the performance of the two optimal algorithms for α = 2. We also present experimental results showing the performance of the relaxation algorithm for α = 1, 2, 3.     

Multi-objective competitive location problem with distance-based attractiveness and its best non-dominated solution

The multi-objective competitive location problem (MOCLP) with distance-based attractiveness is introduced. There are m potential competitive facilities and n demand points on the same plane. All potential facilities can provide attractiveness to the demand point which the facility attractiveness is represented as distance-based coverage of a facility, which is “full coverage” within the maximum full coverage radius, “no coverage” outside the maximum partial coverage radius, and “partial coverage” between those two radii. Each demand point covered by one of m potential facilities is determined by the greatest accumulated attractiveness provided the selected facilities and least accumulated distances between each demand point and selected facility, simultaneously. The tradeoff of maximum accumulated attractiveness and minimum accumulated distances is represented as a multi-objective optimization model. A proposed solution procedure to find the best non-dominated solution set for MOCLP is introduced. Several numerical examples and instances comparing with introduced and exhaustive method demonstrates the good performance and efficiency for the proposed solution procedure.