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.     

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.     

Pendant-medians

The median of a network is any point in the network that minimizes the sum of the shortest distances from it to each vertex. Let's omit from this sum the distance to any vertex that is intermediate on the shortest path from the median to another vertex. In other words, include in the sum only the pendant vertices of the shortest distance spanning free. A pendant-median is any point in the network that minimizes this revised sum of the shortest distances. A pendant-median models facility locations in which customers can be served without penalty along the route to other, more distant customers.This paper presents a simple algorithm to locate a pendant-median of a tree network and presents several results for general networks.     

Locating least-distant lines in the plane

In this paper we deal with locating a line in a plane. Given a set of existing facilities, represented by points in the plane, our objective is to find a straight line l minimizing the sum of weighted distances to the existing facilities, or minimizing the maximum weighted distance to the existing facilities, respectively. We show that for all distance measures derived from norms, one of the lines minimizing the sum objective contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.     

Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique

In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

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.     

Planar weber location problems with line barriers

The Weber problem for a given finite set of existing facilities in the plane is to find the location of a new facility such that the weithted sum of distances to the existing facilities is minimized.

A variation of this problem is obtained if the existing facilities are situated on two sides of a linear barrier. Such barriers like rivers, highways, borders or mountain ranges are frequently encountered in practice.

Structural results as well as algorithms for this non-convex optimization problem depending on the distance function and on the number and location of passages through the barrier are presented.     

Reliability problems in multiple path-shaped facility location on networks

In this paper we study a location problem on networks that combines three important issues: (1) it considers that facilities are extensive, (2) it handles simultaneously the location of more than one facility, and (3) it incorporates reliability aspects related to the fact that facilities may fail. The problem consists of locating two path-shaped facilities minimizing the expected service cost in the long run, assuming that paths may become unavailable and their failure probabilities are known in advance. We discuss several aspects of the computational complexity of problems of locating two or more reliable paths on graphs, showing that multifacility path location–with and without reliability issues–is a difficult problem even for 2 facilities and on very special classes of graphs. In view of this, we focus on trees and provide a polynomial time algorithm that solves the 2 unreliable path location problem on tree networks in $O\left(n^2\right)$ time, where $n$ is the number of vertices.     

Multicriteria tour planning for mobile healthcare facilities in a developing country

A multiobjective combinatorial optimization (MOCO) formulation for the following location-routing problem in healthcare management is given: For a mobile healthcare facility, a closed tour with stops selected from a given set of population nodes has to be found. Tours are evaluated according to three criteria: (i) An economic efficiency criterion related to the tour length, (ii) the criterion of average distances to the nearest tour stops corresponding to p-median location problem formulations, and (iii) a coverage criterion measuring the percentage of the population unable to reach a tour stop within a predefined maximum distance. Three algorithms to compute approximations to the set of Pareto-efficient solutions of the described MOCO problem are developed. The first uses the P-ACO technique, and the second and the third use the VEGA and the MOGA variant of multiobjective genetic algorithms, respectively. Computational experiments for the Thiès region in Senegal were carried out to evaluate the three approaches on real-world problem instances.     

A Linear Time Algorithm for Finding ak-Tree Core

Given a tree containingnvertices, consider the sum of the distance between all vertices and ak-leaf subtree (subtree which contains exactlykleaves). Ak-tree core is ak-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding ak-tree core for a givenk.     

Finding a core of a tree with pos/neg weight

Let T?=?(V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices?? weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247?C258, 1980) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems.     

Efficient Location for a Semi-Obnoxious Facility

This paper deals with a location model for the placement of a semi-obnoxious facility in a continuous plane with the twin objectives of maximizing the distance to the nearest inhabitant and minimizing the sum of distances to all the users (or the distance to the farthest user) in a unified manner. For special cases, this formulation includes (1) elliptic maximin and rectangular minisum criteria problem, and (2) rectangular maximin and minimax criteria problem. Polynomial-time algorithms for finding the efficient set and the tradeoff curve are presented.     

Minisum collection depots location problem with multiple facilities on a network

We investigate the problem of locating a set of service facilities that need to service customers on a network. To provide service, a server has to visit both the demand node and one of several collection depots. We employ the criterion of minimizing the weighted sum of round trip distances. We prove that there exists a dominating location set for the problem on a general network. The properties of the solution on a tree and on a cycle are discussed. The problem of locating service facilities and collection depots simultaneously is also studied. To solve the problem on a general network, we suggest a Lagrangian relaxation imbedded branch-and-bound algorithm. Computational results are reported.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

区间图上可带负权的2-中位选址问题（英文）

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.     

区间图上可带负权的2-中位选址问题

本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的$p-$中位选址问题($p\geq 2$)可分为两类：即 MWD 和 WMD 模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为$O(n^2)$的多项式时间算法.     

半讨厌型设施选址问题的模型与算法

研究了结合网络和平面模型的半讨厌型设施的选址问题.半讨厌型设施结合了讨厌型设施与喜爱型设施的性质,一方面由于这些设施对人们带来很多副作用,人们想要远离他们以避免遭到污染,但同时人们又希望距离设施不要过远,因此建立0-1整数模型,在保证所有人使用该设施的距离不超过既定距离的基础上,使污染范围最小.由于该问题是NP困难问题,本为给出了启发式算法,通过算例进行了比较分析,证明了算法的有效性.     

A polyhedral approach to the single row facility layout problem

The single row facility layout problem (SRFLP) is the NP-hard problem of arranging facilities on a line, while minimizing a weighted sum of the distances between facility pairs. In this paper, a detailed polyhedral study of the SRFLP is performed, and several huge classes of valid and facet-inducing inequalities are derived. Some separation heuristics are presented, along with a primal heuristic based on multi-dimensional scaling. Finally, a branch-and-cut algorithm is described and some encouraging computational results are given.