On locating path‐ or tree‐shaped facilities on networks

TLDR

The study of optimally locating a single path‑ or tree‑shaped facility of fixed length on a network was initiated by several authors. The authors aim to extend this work to locating p (≥1) such facilities, covering center, median, max eccentricity, and max distance sum problems on general and tree networks, with or without partial arcs. They analyze the 64 resulting problems, determining the algorithmic complexity for virtually all of them. They present a result generalizing the p‑Median theorem. © 1993 by John Wiley & Sons, Inc.

Abstract

Abstract The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of the p ‐Median theorem. © 1993 by John Wiley & Sons, Inc.