Abstract
In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems—the Maximal Direct and Indirect Covering Tree problems—were introduced by Hutson and ReVelle. Previous solution techniques are extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered is attenuated by distance. It is also shown that the corresponding problem is NP-hard when the underlying network is not a tree.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Church, R. L. and J. R. Current (1993). Maximal covering tree problems.Naval Research Logistics 40, 129–142.
Cohon, J. L. (1978).Multiobjective Programming and Planning. Academic Press, New York.
Current, J. R., C. S. ReVelle and J. L. Cohon (1986). The hierarchical network design problem.European Journal of Operational Research 21, 188–197.
Garey, M. J. and D. S. Johnson (1979).Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco.
Hutson, V. A. and C. S. ReVelle (1989). Maximal direct covering tree problems.Transportation Science 23, 288–299.
Hutson, V. A. and C. S. ReVelle (1993). Indirect covering tree problems on spanning tree networks.European Journal of Operational Research 65, 20–32.
Kim, T. U., T. J. Lowe, J. E. Ward and R. L. Francis (1989). A minimum length covering subgraph of a network.Annals of Operations Research 18, 245–260.
Kim, T. U., T. J. Lowe, J. E. Ward and R. L. Francis (1990). A minimum length covering subtree of a tree.Naval Research Logistics Quarterly 37, 309–326.
Kincaid, R. K., T. J. Lowe and T. L. Morin (1988). The location of central structures in trees.Computers & Operations Research 15, 103–113.
Mesa, J. A. and T. B. Boffey (1996). Location of extensive facilities in networks.European Journal of Operational Research 95, 592–603.