A Cut Approach to the Rectilinear Distance Facility Location Problem

Jean-Claude Picard and H. Donald Ratliff
Additional contact information
Jean-Claude Picard: Ecole Polytechnique, Montreal, Quebec
H. Donald Ratliff: University of Florida, Gainesville, Florida

Operations Research, 1978, vol. 26, issue 3, 422-433

Abstract: This paper is concerned with the problem of locating n new facilities in the plane when there are m facilities already located. The objective is to minimize the weighted sum of rectilinear distances. Necessary and sufficient conditions for optimality are established. We show that the optimum locations of the new facilities are dependent on the relative orderings of old facilities along the two coordinate axes but not on the distances between them. Based on these results an algorithm is presented that requires the solution of at most m − 1 minimum cut problems on networks with at most n + 2 vertices. All of these results are easily extended to the same location problem on a tree graph.

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

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.3.422 (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:3:p:422-433

Access Statistics for this article

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