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 multiple server location problem

In this paper, we introduce the Multiple Server location problem. A given number of servers are to be located at nodes of a network. Demand for these servers is generated at each node, and a subset of nodes need to be selected for locating one or more servers in each. There is no limit on the number of servers that can be established at each node. Each customer at a node selects the closest server (with demand divided equally when the closest distance is measured to more than one node). The objective is to minimize the sum of the travel time and the average time spent at the server, for all customers. The problem is formulated and analysed. Results using heuristic solution procedures: descent, simulated annealing, tabu search and a genetic algorithm are reported. The problem turns out to be a very difficult combinatorial problem when the total demand is very close to the total capacity of the servers.     

The central warehouse location problem revisited

This paper is concerned with the optimal location of a centralwarehouse, given a fixed number and the locations of the localwarehouses. We investigate whether the solution determined bythe traditional model that minimizes total transportation costdiffers from the one determined by a model that also takes intoaccount the inventory and service costs. We build simple modelsto address this question. Numerical results show that ignoringinventory costs in modelling location models may lead to inferiorlocation solutions.     

The multiple server center location problem

In this paper, we introduce the multiple server center location problem. p servers are to be located at nodes of a network. Demand for services of these servers is located at each node, and a subset of nodes are to be chosen to locate one or more servers in each. Each customer selects the closest server. The objective is to minimize the maximum time spent by any customer, including travel time and waiting time at the server sites. The problem is formulated and analyzed. Results for heuristic solution approaches are reported. Paper was partially supported by a College of Business Administration, California State University San Marcos summer grant of the first author. Paper was partially supported by an NSERC grant of the second author.     

The ordered capacitated facility location problem

In this paper, we analyze flexible models for capacitated discrete location problems with setup costs. We introduce a major extension with regards to standard models which consists of distinguishing three different points of view of a location problem in a logistics system. We develop mathematical programming formulations for these models using discrete ordered objective functions with some new features. We report on the computational behavior of these formulations tested on a randomly generated battery of instances.     

The maximum return-on-investment plant location problem

The standard plant location problem determines which plants to open from a set of potential sites in order to satisfy the demands at a set of customer vertices at a minimum total cost. However, the optimal solution may exceed a limit on investment costs imposed on the enterprise in a practical setting. This paper examines the plant location problem in an environment in which the investment in plant and equipment is also an objective to be minimised. The problem is posed as a bicriterion model which examines the tradeoff between the sum of operational and investment costs and investment cost (or total cost vs sunk cost). A weighting method is used to generate efficient solutions, one of which is shown to maximise the return on investment. The integer-friendliness of the LP relaxation is investigated.     

The maximum reliability location problem and α-reliablep-center problem: Derivatives of the probabilistic location set covering problem

In the last several years, the modeling of emergency vehicle location has focussed on the temporal availability of the vehicles. Vehicles are not available for service when they are engaged in earlier calls. To incorporate this dynamic aspect into facility location decisions, models have been developed which provide additional levels of coverage. In this paper, two new models are derived from the probabilistic location set covering problem. These models allow the examination of the relationships between the number of facilities being located, the reliability that a vehicle will be available, and a coverage standard. In addition, these models incorporate sectoral specific estimates of the availability of the vehicles. Solution of these models reveals that the use of sectoral estimates leads to facility locations which are distributed to a greater spatial extent over the region to be serviced.     

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

Algebraic optimization: The Fermat-Weber location problem

The Fermat-Weber location problem is to find a point in ⁿ that minimizes the sum of the (weighted) Euclidean distances fromm given points in ⁿ . In this work we discuss some relevant complexity and algorithmic issues. First, using Tarski's theory on solvability over real closed fields we argue that there is an infinite scheme to solve the problem, where the rate of convergence is equal to the rate of the best method to locate a real algebraic root of a one-dimensional polynomial. Secondly, we exhibit an explicit solution to the strong separation problem associated with the Fermat-Weber model. This separation result shows that an-approximation solution can be constructed in polynomial time using the standard Ellipsoid Method.     

The dual of a generalized minimax location problem

This paper develops the dual formulation of a generalized minimax problem which has distance and linear constraints.     

A non-triangular hub location problem

Hub location problems generally assume that the triangle inequality applies on the edges of a complete graph. Hence the flow between any pair of nodes requ     

The deterministic product location problem under a pick-by-order policy

This paper treats the product location problem in warehouses, i.e., stock keeping units (SKUs) are to be assigned to storage positions in order to minimize the resulting picking effort when retrieving SKUs in a pick-by-order environment. We restrict our view on warehouses having a single cross aisle and show that already very simple layouts consisting of only a single rack lead to NP-hard optimization problems. In addition to a complexity analysis for different layouts, elementary solution procedures are introduced and tested. Finally, we investigate the robustness of our deterministic problem when facing erroneous input data.     

The maximum return-on-investment plant location problem with market share

This paper examines the plant location problem under the objective of maximizing return-on-investment. However, in place of the standard assumption that all demands must be satisfied, we impose a minimum acceptable level on market share. The model presented takes the form of a linear fractional mixed integer program. Based on properties of the model, a local search procedure is developed to solve the problem heuristically. Variable neighbourhood search and tabu search heuristics are also developed and tested. Thus, a useful extension of the simple plant location problem is examined, and heuristics are developed for the first time to solve realistic instances of this problem.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

The multifacility maximin planar location problem with facility interaction

^** Email: s.salhi{at}kent.ac.uk Two branch-and-bound algorithms are proposed to optimally solvethe maximin formulation for locating p facilities in the plane.Tight upper and lower bounds are constructed and suitable methodsof guiding the search developed. To enhance the method, efficientmeasures for identifying specific squares for subdivision aresuggested. The proposed algorithms are evaluated on a set ofrandomly generated problems of up to five facilities and 120nodes.     

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.     

The capacitated maximal covering location problem with backup service

The maximal covering location problem has been shown to be a useful tool in siting emergency services. In this paper we expand the model along two dimensions — workload capacities on facilities and the allocation of multiple levels of backup or prioritized service for all demand points. In emergency service facility location decisions such as ambulance sitting, when all of a facility's resources are needed to meet each call for service and the demand cannot be queued, the need for a backup unit may be required. This need is especially significant in areas of high demand. These areas also will often result in excessive workload for some facilities. Effective siting decisions, therefore, must address both the need for a backup response facility for each demand point and a reasonable limit on each facility's workload. In this paper, we develop a model which captures these concerns as well as present an efficient solution procedure using Lagrangian relaxation. Results of extensive computational experiments are presented to demonstrate the viability of the approach.     

The simple plant location problem: Survey and synthesis

With emphasis on the simple plant location problem, (SPLP), we consider an important family of discrete, deterministic, single-criterion, NP-hard, and widely applicable optimization problems. The introductory discussion on problem formulation aspects is followed by the establishment of relationships between SPLP and set packing, set covering and set partitioning problems which all are among those structures in integer programming having the most wide-spread applications. An extensive discourse on solution properties and computational techniques, spanning from early heuristics to the presumably most novel exact methods is then provided. Other subjects of concern include a subfamily of SPLP's solvable in polynomial time, analyses of approximate algorithms, transformability of p-CENTER and p-MEDIAN to SPLP, and structural properties of the SPLP polytope. Along the way we attempt to synthesize these findings and relate them to other areas of integer programming.     

The planar hub location problem: a probabilistic clustering approach

Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs. We propose a probabilistic clustering method for the planar hub-location problem which is analogous to the method of Iyigun and Ben-Israel (in Operations Research Letters 38, 207–214, 2010; Computational Optmization and Applications, 2013) for the solution of the multi-facility location problem. The proposed method is an iterative probabilistic approach assuming that all trips can be taken with probabilities that depend on the travel costs based on the hub locations. Each hub location is the convex combination of all data points and other hubs. The probabilities are updated at each iteration together with the hub locations. Computations stop when the hub locations stop moving. Fermat-Weber problem and multi-facility location problem are the special cases of the proposed approach.