Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

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.     

Algorithms for central-median paths with bounded length on trees

The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. In the literature, there is just one paper that considers the problem of finding an optimal location of a path on a tree using combinations of the two above criteria, and efficient algorithms are provided. In particular, the cases where one criterion is optimized subject to a restriction on the value of the other are considered and linear time algorithms are presented. However, these problems do not consider any bound on the length or cost of the facility. In this paper we consider the two following problems: find a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; find a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. From an application point of view the constraint on the length of the path may refer to a budget constraint for establishing the facility. The restriction on the length of the path complicates the two problems but for both of them we give O(n log² n) divide-and-conquer algorithms.     

A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments

In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A _i ,A _j ) is called covered if the time to access the network from A _i plus the time for traveling along the network plus the time for reaching A _j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.     

Sequential competitive location on networks

We present a survey of recent developments in the field of sequential competitive location problems, including the closely related class of voting location problems, i.e. problems of locating resources as the result of a collective election. Our focus is on models where possible locations are not a priori restricted to a finite set of points. Furthermore, we restrict our attention to problems defined on networks. Since a line, i.e. an interval of one-dimensional real space, may be interpreted as a special type of network and because models defined on lines might contain ideas worth adopting in more general network models, we include these models as well, yet without describing them in detail for the sake of brevity.     

On the Minimum Average Distance Spanning Tree of the Hypercube

Given an undirected and connected graph G, with a non-negative weight on each edge, the Minimum Average Distance (MAD) spanning tree problem is to find a spanning tree of G which minimizes the average distance between pairs of vertices. This network design problem is known to be NP-hard even when the edge-weights are equal. In this paper we make a step towards the proof of a conjecture stated by A.A. Dobrynin, R. Entringer and I. Gutman in 2001, and which says that the binomial tree B _n is a MAD spanning tree of the hypercube H _n . More precisely, we show that the binomial tree B _n is a local optimum with respect to the 1-move heuristic which, starting from a spanning tree T of the hypercube H _n , attempts to improve the average distance between pairs of vertices, by adding an edge e of H _n -T and removing an edge e′ from the unique cycle created by e. We also present a greedy algorithm which produces good solutions for the MAD spanning tree problem on regular graphs such as the hypercube and the torus.     

The least element property of center location on tree networks with applications to distance and precedence constrained problems

In the classicalp-center location model on a network there is a set of customers, and the primary objective is to selectp service centers that will minimize the maximum distance of a customer to a closest center. Suppose that thep centers receive their supplies from an existing central depot on the network, e.g. a warehouse. Thus, a secondary objective is to locate the centers that optimize the primary objective as close as possible to the central depot. We consider tree networks and twop-center models. We show that the set of optimal solutions to the primary objective has a semilattice structure with respect to some natural ordering. Using this property we prove that there is ap-center solution to the primary objective that simultaneously minimizes every secondary objective function which is monotone nondecreasing in the distances of thep centers from the existing central depot.Restricting the location models to a rooted path network (real line) we prove that the above results hold for the respective classicalp-median problems as well.     

Sorting weighted distances with applications to objective function evaluations in single facility location problems

We consider single facility location problems defined on rectilinear spaces and spaces induced by tree networks. We focus on discrete cases, where the facility is restricted to be in a prespecified finite set S, and the goal is to evaluate the objective at each point in S. We present efficient improved algorithms to perform this task for several classes of objective functions.     

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.     

Locating the two-median of a tree network with continuous link demands

Typical formulations of thep-median problem on a network assume discrete nodal demands. However, for many problems, demands are better represented by continuous functions along the links, in addition to nodal demands. For such problems, optimal server locations need not occur at nodes, so that algorithms of the kind developed for the discrete demand case can not be used. In this paper we show how the 2-median of a tree network with continuous link demands can be found using an algorithm based on sequential location and allocation. We show that the algorithm will converge to a local minimum and then present a procedure for finding the global minimum solution.     

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.     

Center location problems on tree graphs with subtree-shaped customers

We consider the p-center problem on tree graphs where the customers are modeled as continua subtrees. We address unweighted and weighted models as well as distances with and without addends. We prove that a relatively simple modification of Handler’s classical linear time algorithms for unweighted 1- and 2-center problems with respect to point customers, linearly solves the unweighted 1- and 2-center problems with addends of the above subtree customer model. We also develop polynomial time algorithms for the p-center problems based on solving covering problems and searching over special domains.     

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.     

Norm statistics and the complexity of clustering problems

In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of ?_p-statistics and ?_q norms. We discuss a real world application in which the case p=2 and q=1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the ‘pure’ ?₂-statistic and ?₂ norm are known to satisfy a ‘string property’ and can be solved in polynomial time. We generalize the string property for the case p=q. The string property need not hold when q≤p−1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

Location problems

Recent developments for several location problems are surveyed. These include: graph theoretic and combinatorial formulations of the simple plant location problem, the NP-hardness of some p-center problems, worst-case bounds for several polynomial-time heuristics for some p-center problems, and a general solution to a class of one facility network problems with convex cost functions.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.