Discrete stochastic location models

In this paper, we study how the two classical location models, the simple plant location problem and thep-median problem, are transformed in a two-stage stochastic program with recourse when uncertainty on demands, variable production and transportation costs, and selling prices is introduced. We also discuss the relation between the stochastic version of the SPLP and the stochastic version of thep-median.     

Comparative error bound theory for three location models: continuous demand versus discrete demand

We develop a unified error bound theory to compare a given p-median, p-center or covering location model with continuously distributed demand points in R ⁿ to a corresponding given original model of the same type having a finite collection of demand points in R ⁿ . We give ways to construct either a continuous or finite demand point model from the other model and also control the error bound. Our work uses Voronoi tilings extensively, and is related to earlier error bound theory for aggregating finitely many demand points.     

The multiple location of transfer points

In this paper, we investigate the location of several transfer points to serve as collector points for customers who need the services of a facility. For example, demand for emergency services by patients is generated at a set of demand points that need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of multiple transfer points and one facility. Locating one transfer point when the set of demand points and the location of the facility are known was investigated in a previous paper by the authors. In this paper, we apply the results of that paper to solve the problem when the location of the facility is known. Both minisum and minimax versions of the models are investigated both in the plane and on the network.     

Extreme points of discrete location polyhedra

The problem of characterizing extreme points of a family of polyhedra is considered. This family embraces a variety of linear relaxations of feasible regions of discrete location problems. After characterizing the extreme points by means of a homogeneous system of linear equations, we obtain, as particular cases, four problems which have already been treated from a polyhedral point of view in the literature. Finally, we show that our characterization improves the one known for the Simple Plant Location Problem and corrects the one established for the Two-Level Uncapacitated Facility Location Problem. The first and third authors were supported by Fundación Séneca, project PB/11/FS/97     

Modelling lost demand in competitive facility location

In this paper, we propose a simple new approach to model lost demand (also referred to as elastic demand) in competitive facility location. A ‘dummy’ competing facility that attracts the lost demand is added to the list of competing facilities. All competitive facility location models, regardless of their complexity or assumptions, can be modified to include lost demand and be solved by the same algorithms designed for standard models once the dummy facility is added to the data as an additional competitor.     

Competitive facility location model with concave demand

We consider a spatial interaction model for locating a set of new facilities that compete for customer demand with each other, as well as with some pre-existing facilities to capture the “market expansion” and the “market cannibalization” effects. Customer demand is assumed to be a concave non-decreasing function of the total utility derived by each customer from the service offered by the facilities. The problem is formulated as a non-linear Knapsack problem, for which we develop a novel solution approach based on constructing an efficient piecewise linear approximation scheme for the objective function. This allows us to develop exact and α-optimal solution approaches capable of dealing with relatively large-scale instances of the model. We also develop a fast Heuristic Algorithm for which a tight worst-case error bound is established.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

A multi-objective heuristic approach for the casualty collection points location problem

In this paper, we formulate the casualty collection points (CCPs) location problem as a multi-objective model. We propose a minimax regret multi-objective (MRMO) formulation that follows the idea of the minimax regret concept in decision analysis. The proposed multi-objective model is to minimize the maximum per cent deviation of individual objectives from their best possible objective function value. This new multi-objective formulation can be used in other multi-objective models as well. Our specific CCP model consists of five objectives. A descent heuristic and a tabu search procedure are proposed for its solution. The procedure is illustrated on Orange County, California.     

On the location of critical points of polynomials

Given a polynomial of degree and with at least two distinct roots let . For a fixed root we define the quantities and . We also define and to be the corresponding minima of and as runs over . Our main results show that the ratios and are bounded above and below by constants that only depend on the degree of . In particular, we prove that , for any polynomial of degree .

     

Discrete facility location with nonlinear diseconomies in fixed costs

A discrete facility location problem is formulated where the total fixed cost for establishing the facilities includes a component that is a nonlinear function of the number of facilities being established. Some theoretical properties of the solution are derived when this fixed cost is a convex nondecreasing function of the number of facilities. Based on these properties an efficient bisection heuristic is developed where at each iteration, the classical uncapacitated facility location and/or m-median subproblems are solved using available efficient heuristics.     

Capacitated location allocation problem with stochastic location and fuzzy demand: A hybrid algorithm

In this article, a capacitated location allocation problem is considered in which the demands and the locations of the customers are uncertain. The demands are assumed fuzzy, the locations follow a normal probability distribution, and the distances between the locations and the customers are taken Euclidean and squared Euclidean. The fuzzy expected cost programming, the fuzzy β-cost minimization model, and the credibility maximization model are three types of fuzzy programming that are developed to model the problem. Moreover, two closed-form Euclidean and squared Euclidean expressions are used to evaluate the expected distance between customers and facilities. In order to solve the problem at hand, a hybrid intelligent algorithm is applied in which the simplex algorithm, fuzzy simulation, and a modified genetic algorithm are integrated. Finally, in order to illustrate the efficiency of the proposed hybrid algorithm, some numerical examples are presented.     

Production and location on a network under demand uncertainty

The Hakimi theorem is fundamental in location theory. It says that the set of nodes and market-places necessarily contains a profit-maximizing location when the transportation costs are concave in distance. The purpose of this letter is to discuss the validity of this theorem in the context of a two-stage stochastic model of the location of a firm on a network. In the first stage, the firm chooses its location and production level before knowing the exact demands. In the second stage, it observes the realization of the random variables representing the demands and decides upon the distribution of its production. It is shown that the Hakimi theorem still holds in this model when the firm is risk-neutral. On the other hand, in the case of a risk-averse firm, it ceases to be true in that all the points of the network must be considered to obtain an optimal location.     

The minimum equitable radius location problem with continuous demand

We analyze the location of p facilities satisfying continuous area demand. Three objectives are considered: (i) the p-center objective (to minimize the maximum distance between all points in the area and their closest facility), (ii) equalizing the load service by the facilities, and (iii) the minimum equitable radius – minimizing the maximum radius from each point to its closest facility subject to the constraint that each facility services the same load. The paper offers three contributions: (i) a new problem – the minimum equitable radius is presented and solved by an efficient algorithm, (ii) an improved and efficient algorithm is developed for the solution of the p-center problem, and (iii) an improved algorithm for the equitable load problem is developed. Extensive computational experiments demonstrated the superiority of the new solution algorithms.     

An approach for solving competitive location problems with variable demand using multicore systems

A planar competitive location and design problem with variable demand is considered. The assumption that the demand may vary depending on the conditions of the market makes the problem more realistic, but it also increases its complexity, and therefore, the computational effort needed to solve it. In this paper, a modification of a heuristic recently proposed to cope with the problem is presented, which allows, on the one hand, to obtain the same solutions as the original heuristic more quickly and, on the other hand, to handle larger size problems. Furthermore, a parallel version of the algorithm, suitable for being run in most of today’s personal computers, has also been proposed. The parallel algorithm has been implemented using the OpenMP library and the results show an ideal efficiency up to at least eight processors (the largest number of available processing elements). The effectiveness of the parallel algorithm has also been measured. From the computational results, it can be inferred that the proposed parallelization is robust.     

Stability of equilibrium points of demand-inventory model with stock-dependent demand

A model of demand and inventory of a product in one echelon of supply chain is considered. The model is formulated as a system of difference equations, in which every equilibrium point is nonhyperbolic. A positive invariant set of the system is constructed. An analysis of properties of equilibrium points of the system is based on the Lyapunov method or reducing it to the family of systems of difference equations with hyperbolic equilibrium points.     

Optimal lateral transshipment policies for a two location inventory problem with multiple demand classes

We consider an inventory model for spare parts with two stockpoints, providing repairable parts for a critical component of advanced technical systems. As downtime costs for these systems are expensive, ready–for–use spare parts are kept in stock to be able to quickly respond to a breakdown of a system. We allow for lateral transshipments of parts between the stockpoints upon a demand arrival. Each stockpoint faces demands from multiple demand classes. We are interested in the optimal lateral transshipment policy. There are three ways in which a demand can by satisfied: from own stock, via a lateral transshipment, or via an emergency procedure. Using stochastic dynamic programming, we characterize and prove the structure of the optimal policy, that is, the policy for satisfying the demands which minimizes the average operating costs of the system. This optimal policy is a threshold type policy, with state-dependent thresholds at each stockpoint for every demand class. We show a partial ordering in these thresholds in the demand classes. In addition, we derive conditions under which the so-called hold back and complete pooling policies are optimal, two policies that are often assumed in the literature. Furthermore, we study several model extensions which fit in the same modeling framework.     

On the location of fixed points on pairs of spaces

Let f: (X, A)→(X, A) be an admissible selfmap of a pair of metrizable ANR's. A Nielsen number of the complement Ñ(f; X, A) and a Nielsen number of the boundary ñ(f; X, A) are defined. Ñ(f; X, A) is a lower bound for the number of fixed points on C1(X - A) for all maps in the homotopy class of f. It is usually possible to homotope f to a map which is fixed point free on Bd A, but maps in the homotopy class of f which have a minimal fixed point set on X must have at least ñ(f; X, A) fixed points on Bd A. It is shown that for many pairs of compact polyhedra these lower bounds are the best possible ones, as there exists a map homotopic to f with a minimal fixed point set on X which has exactly Ñ(f; X - A) fixed points on C1(X−A) and ñ(f; X, A) fixed points on Bd A. These results, which make the location of fixed points on pairs of spaces more precise, sharpen previous ones which show that the relative Nielsen number N(f; X, A) is the minimum number of fixed points on all of X for selfmaps of (X, A), as well as results which use Lefschetz fixed point theory to find sufficient conditions for the existence of one fixed point on C1(X−A).     

An upper bound for the competitive location and capacity choice problem with multiple demand scenarios

A new mathematical model is considered related to competitive location problems where two competing parties, the Leader and the Follower, successively open their facilities and try to win customers. In the model, we consider a situation of several alternative demand scenarios which differ by the composition of customers and their preferences.We assume that the costs of opening a facility depend on its capacity; therefore, the Leader, making decisions on the placement of facilities, must determine their capacities taking into account all possible demand scenarios and the response of the Follower. For the bilevel model suggested, a problem of finding an optimistic optimal solution is formulated. We show that this problem can be represented as a problem of maximizing a pseudo- Boolean function with the number of variables equal to the number of possible locations of the Leader’s facilities.We propose a novel systemof estimating the subsets that allows us to supplement the estimating problems, used to calculate the upper bounds for the constructed pseudo-Boolean function, with additional constraints which improve the upper bounds.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.