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 M/G/1 Server Location on a Network Having a Fixed Facility

This paper considers the problem of locating a single mobile service unit on a network G where the servicing of a demand includes travel time to a permanent facility which is located at a predetermined point on G. Demands for service, which occur solely on the nodes of the network, arrive in a homogeneous Poisson manner. The server, when free, can be immediately dispatched to a demand: the service unit travels to the demand, performs some on-scene service, continues to the permanent facility, where off-scene service is rendered, and then it returns to its ‘home’ location, where possibly additional off-scene service is given. Previous research has examined the same problem, however without the presence of a permanent facility. The paper discusses methods of solving two cases when the server is unable to be immediately dispatched to service a demand: (1) the zero-capacity queueing system; (2) the infinite-capacity queueing system. For the first case we prove that the optimal location is included in a small set of points in the network, and we show how to find this set. For the second case, we present an 0(n³) algorithm (n is the number of nodes) to obtain the optimal location.     

Weber‘s Problem with Attraction and Repulsion under Polyhedral Gauges

Given a finite set of points in the plane anda forbidden region , we want to find a point , such thatthe weighted sum to all given points is minimized.This location problem is a variant of the well-known Weber Problem, where wemeasure the distance by polyhedral gauges and alloweach of the weights to be positive ornegative. The unit ballof a polyhedral gauge may be any convex polyhedron containingthe origin. This large class of distance functions allows verygeneral (practical) settings – such as asymmetry – to be modeled. Each given point isallowed to have its own gaugeand the forbidden region enables us to include negative information in the model. Additionallythe use of negative and positive weights allows to include thelevel of attraction or dislikeness of a new facility.Polynomial algorithms and structural properties for this globaloptimization problem (d.c. objective function and anon-convex feasible set) based on combinatorial and geometrical methodsare presented.     

On the collection depots location problem

In this paper we investigate the problem of locating a new facility servicing a set of demand points. A given set of collection depots is also given. When service is required by a demand point, the server travels from the facility to the demand point, then from the demand point to one of the collection depots (which provides the shortest route back to the facility), and back to the facility. The problem is analyzed and properties of the solution point are formulated and proved. Computational results on randomly generated problems are reported.     

D.c. sets,d.c. functions and nonlinear equations

Ad.c. set is a set which is the difference of two convex sets. We show that any set can be viewed as the image of a d.c. set under an appropriate linear mapping. Using this universality we can convert any problem of finding an element of a given compact set in ⁿ into one of finding an element of a d.c. set. On the basis of this approach a method is developed for solving a system of nonlinear equations—inequations. Unlike Newton-type methods, our method does not require either convexity, differentiability assumptions or an initial approximate solution.The revision of this paper was produced during the author's stay supported by a Sophia lecturing-research grant at Sophia University (Tokyo, Japan).     

Determination of efficient solutions for point-objective locational decision problems

In this paper we study the point-objective problem of locating in ² a facility serving a finite number of customers to minimize the travel time, or the distance, to each customer.Travel times, or distances, are measured by going in the directions of some given vectors which means that, under some conditions, are evaluated by a norm function. An algorithm is proposed to find all the quasi-efficient points and all the efficient points (alternately or strictly), for any given set of travelling directions. Consequently, the problem of efficiency is addressed in a general framework.     

The probabilistic 1-maximal covering problem on a network with discrete demand weights

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making

Natural basic concepts in multiple-objective optimization lead to difficult multiextremal global optimization problems. Examples include detection of efficient points when nonconvexities occur, and optimization of a linear function over the efficient set in the convex (even linear) case. Assuming that a utility function exists allows one to replace in general the multiple-objective program by a single, nonconvex optimization problem, which amounts to a minimization over the efficient set when the utility function is increasing. A new algorithm is discussed for this utility function program which, under natural mild conditions, converges to an -approximate global solution in a finite number of iterations. Applications include linear, convex, indefinite quadratic, Lipschitz, and d.c. objectives and constraints.     

Optimizing pricing and location decisions for competitive service facilities charging uniform price

In this paper, we present the problem of optimizing the location and pricing for a set of new service facilities entering a competitive marketplace. We assume that the new facilities must charge the same (uniform) price and the objective is to optimize the overall profit for the new facilities. Demand for service is assumed to be concentrated at discrete demand points (customer markets); customers in each market patronize the facility providing the highest utility. Customer demand function is assumed to be elastic; the demand is affected by the price, facility attractiveness, and the travel cost for the highest-utility facility. We provide both structural and algorithmic results, as well as some managerial insights for this problem. We show that the optimal price can be selected from a certain finite set of values that can be computed in advance; this fact is used to develop an efficient mathematical programming formulation for our model.     

Computing Approximate Solutions of the Maximum Covering Problem with GRASP

We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

A production-transportation problem with stochastic demand and concave production costs

Well known extensions of the classical transportation problem are obtained by including fixed costs for the production of goods at the supply points (facility location) and/or by introducing stochastic demand, modeled by convex nonlinear costs, at the demand points (the stochastic transportation problem, [STP]). However, the simultaneous use of concave and convex costs is not very well treated in the literature. Economies of scale often yield concave cost functions other than fixed charges, so in this paper we consider a problem with general concave costs at the supply points, as well as convex costs at the demand points. The objective function can then be represented as the difference of two convex functions, and is therefore called a d.c. function. We propose a solution method which reduces the problem to a d.c. optimization problem in a much smaller space, then solves the latter by a branch and bound procedure in which bounding is based on solving subproblems of the form of [STP]. We prove convergence of the method and report computational tests that indicate that quite large problems can be solved efficiently. Problems up to the size of 100 supply points and 500 demand points are solved. Received October 11, 1993 / Revised version received July 31, 1995 Published online November 24, 1998     

Weber problems with high-speed lines

The Weber problem consists of finding a facility which minimizes the sum of weighted distances from itself to a finite set of given demand points.     

Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers

This paper studies a facility location problem with stochastic customer demand and immobile servers. Motivated by applications to locating bank automated teller machines (ATMs) or Internet mirror sites, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. Customers are assumed to visit the closest open facility. The objective of this problem is to minimize customers' total traveling cost and waiting cost. In addition, there is a restriction on the number of facilities that may be opened and an upper bound on the allowable expected waiting time at a facility. Three heuristic algorithms are developed, including a greedy-dropping procedure, a tabu search approach and an -optimal branch-and-bound method. These methods are compared computationally on a bank location data set from Amherst, New York.     

On the structure of the solution set for the single facility location problem with average distances

This paper analyzes continuous single facility location problems where the demand is randomly defined by a given probability distribution. For these types of problems that deal with the minimization of average distances, we obtain geometrical characterizations of the entire set of optimal solutions. For the important case of total polyhedrality on the plane we derive efficient algorithms with polynomially bounded complexity. We also develop a discretization scheme that provides ${\varepsilon}$ -approximate solutions of the original problem by solving simpler location problems with points as demand facilities.     

The expropriation location problem

In this paper, we consider the location of a new obnoxious facility that serves only a certain proportion of the demand. Each demand point can be bought by the developer at a given price. An expropriation budget is given. Demand points closest to the facility are expropriated within the given budget. The objective is to maximize the distance to the closest point not expropriated. The problem is formulated and polynomial algorithms are proposed for its solution both on the plane and on a network.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Minisum Location with Closest Euclidean Distances

This paper considers the problem of locating a facility not among demand points, as is usually the case, but among demand regions which could be market areas. The objective is to find the location that minimizes the sum of weighted Euclidean distances to the closest points of the demand regions. It is assumed that internal distribution within the areas is someone else's concern. A number of properties of the problem are derived and algorithms for solving the problem are suggested.     

The transfer point location problem

In this paper, we introduce the transfer point location problem. Demand for emergency service is generated at a set of demand points who 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 p helicopter pads and one facility. In this paper, we solve the special case where the location of the facility is known and the best location of one transfer point that serves a set of demand points is sought. Both minisum and minimax versions of the models are investigated. In follow up papers we investigate the general model using the results obtained in this paper.     

The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.