On the location of a tree-shaped facility

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 genaral 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 servicing 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.