An note on spanning trees for network location problems

An note on spanning trees for network location problems

0.00 Avg rating0 Votes
Article ID: iaor19982379
Country: Serbia
Volume: 8
Issue: 1
Start Page Number: 129
End Page Number: 135
Publication Date: Jan 1998
Journal: Yugoslav Journal of Operations Research
Authors: , ,
Keywords: location
Abstract:

A p-facility location problem on a network N consists of locating p new facilities on N such that some function of the distances from them to the vertices of N is minimized. We consider a class of such problems where the objective function is nondecreasing in distance. Median, center and centdian problems belong to this class. We prove that the optimal solutions on the network and on the corresponding spanning trees are equal. Since location problems on a tree network are easier to solve than on a general one, we propose a descent local search heuristic that optimally solves the problem on a spanning tree at each iteration.

Reviews

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