Premium
On the location of a tree‐shaped facility
Author(s) -
Kim Tae Ung,
Lowe Timothy J.,
Tamir Arie,
Ward James E.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199610)28:3<167::aid-net5>3.0.co;2-l
Subject(s) - facility location problem , computer science , tree (set theory) , focus (optics) , mathematical optimization , total cost , function (biology) , 1 center problem , service (business) , operations research , mathematics , mathematical analysis , physics , economy , evolutionary biology , optics , economics , biology , microeconomics
This paper considers the problem of locating a central facility on a tree network. The central facility takes the form of a subtree of the network and provides service to several demand points located at the nodes of the network. Two types of costs are involved in evaluating a given facility selection. The setup cost represents the costs of establishing the facility and is taken to be directly proportional to the total length of the facility. The transportation cost is the cost associated with the travel of customers to the central facility. The objective function is to select a tree‐shaped facility that will minimize the sum of the setup cost and the total transportation cost. We introduce a general model and a simple “bottom‐up” dynamic programming algorithm for its solution. We then focus on the important class of covering problems, where the transportation cost of a customer to the serving facility is zero if the distance between the two is below a certain threshold and it is equal to some penalty term otherwise. We improve upon the performance of existing methods, and present algorithms with subquadratic complexity. © 1996 John Wiley & Sons, Inc.