Duality and Distance Constraints for the Nonlinear p-Center Problem on a Tree Network

A study was conducted on the problem of locating a given number (p) of service centers on a tree network constraining center locations and having customers, or demand points, located at network vertices. In the tree network, a unique shortest path exists between any 2 network points. Providing servi...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1982-07, Vol.30 (4), p.725
Main Authors: Tansel, B C, Francis, R L, Lowe, T J, Chen, M L
Format: Article
Language:English
Subjects:
Algorithms
Mathematical analysis
Networks
Operations research
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A study was conducted on the problem of locating a given number (p) of service centers on a tree network constraining center locations and having customers, or demand points, located at network vertices. In the tree network, a unique shortest path exists between any 2 network points. Providing service at a demand point will produce a cost that is a nonlinear function of the demand point distance from the nearest center. A dual to the distance-contrained location problem is presented, and both problems are solved with polynomial bounded procedures. A covering problem and its dual is also presented, and a covering algorithm is developed that provides proof of strong duality.
ISSN:0030-364X
1526-5463