Distance Constraints for Tree Network Multifacility Location Problems

Richard L. Francis, Timothy J. Lowe and H. Donald Ratliff
Additional contact information
Richard L. Francis: University of Florida, Gainesville, Florida
Timothy J. Lowe: University of Florida, Gainesville, Florida
H. Donald Ratliff: University of Florida, Gainesville, Florida

Operations Research, 1978, vol. 26, issue 4, 570-596

Abstract: We consider the problem of finding locations for new facilities in an imbedded tree network with respect to existing facilities, with upper bounds imposed on distances between all pairs of facilities. We obtain necessary and sufficient conditions, termed separation conditions, for the distance constraints to be consistent. We find string models useful in obtaining insight into the conditions. These separation conditions involve shortest paths through an associated network that has as arc lengths the upper bounds on pair-wise facility distances. Also, we give an algorithm that constructs a feasible solution to the distance constraints if one exists. As an application of the separation conditions, we solve a multifacility minimax location problem. Most of the results obtained in this paper are also true when distances are Tchebyshev between facilities in R p , p ≥ 1, or are rectilinear between facilities in R 2 . Further, the results of this paper should be useful in addressing “nonlinear” minimax location problems and multiobjective, multifacility location problems.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.4.570 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:4:p:570-596

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().