Journal article
On the location of a tree-shaped facility
Networks, Vol.28(3), pp.167-175
10/1996
DOI: 10.1002/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.3.CO;2-T
Abstract
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
Details
- Title: Subtitle
- On the location of a tree-shaped facility
- Creators
- Tae Ung Kim - Sungkyunkwan UniversityTimothy J. Lowe - University of IowaArie Tamir - Tel Aviv UniversityJames E. Ward - Purdue University West Lafayette
- Resource Type
- Journal article
- Publication Details
- Networks, Vol.28(3), pp.167-175
- DOI
- 10.1002/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.3.CO;2-T
- ISSN
- 0028-3045
- Language
- English
- Date published
- 10/1996
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963106402771
Metrics
1 Record Views