The location of n new facilities on a network when the objective function is a sum of weighted distances between new and existing facilities, plus a sum of weighted distances between new facilities is studied. Interdistance constraints which impose upper bounds on distances between facilities have been included. A linear programming approach has been developed which solves the problem exactly on any spanning tree of the network, and which yields a lower bounding problem when the network is cyclic. The gap between the best spanning tree solution and the lower bound averages about 4% in the computational studies.
Get full access to this article
View all access options for this article.
References
1.
DantzigG, 1963Linear Programming and Extensions (Princeton University Press, Princeton, NJ)
2.
DijkstraE W, 1959, “A note on two problems in connexion with graphs”Numerische Mathematik1269–271
3.
EatonD JDaskinM SSimmonsDBullochBJansmaG, 1985, “Determining emergency medical service vehicle deployment in Austin, Texas”Interfaces1596–108
4.
EMSS (Emergency Medical Services Systems) Act, 1973, US Public Law, US Statutes at Large, Volume 87, 93–154, 93rd Congress, 1st Session
5.
ErkutEFrancisR LLoweT JTamirA, 1986, “Equivalent mathematical programming formulations of monotonic tree network location problems”, RR-86-3, Industrial and Systems Engineering Department, University of Florida, Gainesville, FL
6.
ErkutE, 1986Distance Constrained Multi-facility Tree Network Location Problems with Extensions to Planar Networks PhD dissertation, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL
7.
FloydR W, 1962, “Algorithm 97, shortest path”Communications of the ACM5345
