A Cut Approach to the Rectilinear Distance Facility Location Problem.
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 distance. Necessary and sufficient conditions for optimality are established. It is shown that the optimum locations of the new facilities is dependent on the relative positions of old facilities but not on the distances between them. Based on these results an algorithm is presented which requires the solution of at most 2(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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1975
- Accession Number
- ADA020387
Entities
People
- H. Donald Ratliff
- Jean-claude Picard
Organizations
- University of Florida