Network location problems with continuous link demands: p-medians on a chain and 2-medians on a tree

This paper is concerned with minisum location-allocation problems on undirected networks in which demands can occur on links with uniform probability distributions. Two types of networks are considered. The first type considered is simply a chain graph. It is shown that except for the 1-median case, the problem is generally non-convex. However, for the p-median case, a discrete set of potential optimal facility locations may be identified, and hence it is shown that all local and global minima to the problem may be discovered by solving a series of trivial linear programming problems. This analysis is then extended to prescribe an algorithm for the 2-median location-allocation problem on a tree network involving uniform continuous demands on links. Some localization theorems are presented in the spirit of the work done on discrete nodal demand problems.     

Heuristic Procedures for Solving the Discrete Ordered Median Problem

We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median and p-center. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega (1996) for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen and Mladenović (1997) for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.     

Extensive facility location problems on networks with equity measures

This paper deals with the problem of locating path-shaped facilities of unrestricted length on networks. We consider as objective functions measures conceptually related to the variability of the distribution of the distances from the demand points to a facility. We study the following problems: locating a path which minimizes the range, that is, the difference between the maximum and the minimum distance from the vertices of the network to a facility, and locating a path which minimizes a convex combination of the maximum and the minimum distance from the vertices of the network to a facility, also known in decision theory as the Hurwicz criterion. We show that these problems are NP-hard on general networks. For the discrete versions of these problems on trees, we provide a linear time algorithm for each objective function, and we show how our analysis can be extended also to the continuous case.     

Developments in network location with mobile and congested facilities

We review four facility location problems which are motivated by urban service applications and which can be thought of as extensions of the classic Q-median problem on networks. In problems P1 and P2 it is assumed that travel times on network links change over time in a probabilistic way. In P2 it is further assumed that the facilities (servers) are movable so that they can be relocated in response to new network travel times. Problems P3 and P4 examine the Q-median problem for the case when the service capacity of the facilities is finite and, consequently, some or all of the facilities can be unavailable part of the time. In P3 the facilities have stationary home locations but in P4 they have movable locations and thus can be relocated to compensate for the unavailability of the busy facilities. We summarize our main results to date on these problems.     

Inverse median location problems with variable coordinates

Given n points in \mathbbR^d{\mathbb{R}^d} with nonnegative weights, the inverse 1-median problem with variable coordinates consists in changing the coordinates of the given points at minimum cost such that a prespecified point in \mathbbR^d{\mathbb{R}^d} becomes the 1-median. The cost is proportional to the increase or decrease of the corresponding point coordinate. If the distances between points are measured by the rectilinear norm, the inverse 1-median problem is NP{\mathcal{NP}}-hard, but it can be solved in pseudo-polynomial time. Moreover, a fully polynomial time approximation scheme exists in this case. If the point weights are assumed to be equal, the corresponding inverse problem can be reduced to d continuous knapsack problems and is therefore solvable in O(nd) time. In case that the squared Euclidean norm is used, we derive another efficient combinatorial algorithm which solves the problem in O(nd) time. It is also shown that the inverse 1-median problem endowed with the Chebyshev norm in the plane is NP{\mathcal{NP}}-hard. Another pseudo-polynomial algorithm is developed for this case, but it is shown that no fully polynomial time approximation scheme does exist.     

A flexible model and efficient solution strategies for discrete location problems

Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported.     

The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

The Ordered Gradual Covering Location Problem on a Network

In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like p-median or p-center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

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.     

Sequential Discrete p-Facility Models for Competitive Location Planning

Two new models for duopolistic competitive discrete location planning with sequential acting and variable delivered prices are introduced. If locations and prices are assumed to be set once and for all by the players, the resulting bilevel program is nonlinear. Under the assumption that further price adjustments are possible, i.e., that a Nash equilibrium in prices is reached, the model can be simplified to a linear discrete bilevel formulation. It is shown that in either situation players should not share any locations or markets if they strive for profit-maximization.For the situation with price adjustments, a heuristic solution procedure is suggested. In addition, the bilevel models are shown to serve as a basis from which different well-known location models – as, for example, the p-median problem, the preemptive location problem and the maximum covering problem – can be derived as special cases.     

Discrete space location-allocation solutions from genetic algorithms

Genetic algorithms are adaptive sampling strategies based on information processing models from population genetics. Because they are able to sample a population broadly, they have the potential to out-perform existing heuristics for certain difficult classes of location problems. This paper describes reproductive plans in the context of adaptive optimization methods, and details the three genetic operators which are the core of the reproductive design. An algorithm is presented to illustrate applications to discrete-space location problems, particularly thep-median. The algorithm is unlikely to compete in terms of efficiency with existingp-median heuristics. However, it is highly general and can be fine-tuned to maximize computational efficiency for any specific problem class.     

Probability chains: A general linearization technique for modeling reliability in facility location and related problems

In this paper, we propose an efficient technique for linearizing facility location problems with site-dependent failure probabilities, focusing on the unreliable p-median problem. Our approach is based on the use of a specialized flow network, which we refer to as a probability chain, to evaluate compound probability terms. The resulting linear model is compact in size. The method can be employed in a straightforward way to linearize similarly structured problems, such as the maximum expected covering problem. We further discuss how probability chains can be extended to problems with co-location and other, more general problem classes. Additional lower bounds as well as valid inequalities for use within a branch and cut algorithm are introduced to significantly speed up overall solution time. Computational results are presented for several test problems showing the efficiency of our linear model in comparison to existing problem formulations.     

Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

The linking set problem: a polynomial special case of the multiple-choice knapsack problem

We consider the linking set problem, which can be seen as a particular case of the multiple-choice knapsack problem. This problem occurs as a subproblem in a decomposition procedure for solving large-scale p-median problems such as the optimal diversity management problem. We show that if a non-increasing diference property of the costs in the linking set problem holds, then the problem can be solved by a greedy algorithm and the corresponding linear gap is null.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

A note on solving large p-median problems

In a previous paper we presented a tree search algorithm for the p-median problem, the problem of locating p facilities (medians) on a network, which was based upon La grangean relaxation and subgradient optimisation. That algorithm solved (optimally) problems with an arbitrary number of medians and having up to 200 vertices.In this note we show that it is possible to enhance that algorithm to solve (optimally) problems having up to 900 vertices using the Cray-1S computer.