Multi-facility location problem with nonincreasing piecewise linear demand on a tree

Multi-facility location problem with nonincreasing piecewise linear demand on a tree

0.00 Avg rating0 Votes
Article ID: iaor20012026
Country: Japan
Volume: 43
Issue: 2
Start Page Number: 333
End Page Number: 340
Publication Date: Jun 2000
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: location, programming: dynamic
Abstract:

This paper deals with a multi-facility location problem on a tree. Given the number of facilities and the tree structure, the problem is to find the optimal locations of facilities so as to maximize the service provider's gain obtained from customers accessing the nearest facility. Customers are located only at vertices of the tree. For each vertex, customers' demand function is given, which is nonincreasing piecewise linear in the distance from the vertex to the nearest facility location. We modify the algorithm proposed by Megiddo–Zemel–Hakimi, and show that it yields the exact optimum within a polynomial time.

Reviews

Required fields are marked *. Your email address will not be published.