Optimal Direct and Indirect Covering Trees

Justin Williams ()

Annals of Operations Research, 2003, vol. 123, issue 1, 265-284

Abstract: The maximal covering subtree problem has applications in transportation network design and extensive facility location. A subtree of a network is a tree that is not a full spanning tree. Finding an optimal subtree may involve the two objectives, minimizing the total arc cost or distance of the subtree, and maximizing the subtree's coverage of population or demand at nodes. Coverage may be defined as direct or indirect: indirect coverage requires that a node be within a distance threshold s>0 of the subtree, and direct coverage requires that a node be connected to the subtree (s=0). Previous approaches to this problem have sought to identify optimal subtrees of a “parent” network that is itself a tree (e.g., a minimum spanning tree). In this paper four new bi-objective zero–one programming models are presented. The first two are models for the problem of finding optimal subtrees on a single spanning tree parent under conditions of (1) direct and (2) indirect coverage. These problems have been addressed previously in the literature. In the third and fourth models, the subtree can be selected from among multiple candidate parent spanning trees simultaneously. The latter models address a new generalization of the first problem and offer both increased flexibility and the potential for a more diverse array of solutions. The models have “integer-friendly” solution properties and are relatively small in terms of the number of decision variables and constraints. Computational experience is reported for a demonstration problem and results are compared to the results of previous models. Copyright Kluwer Academic Publishers 2003

Keywords: location; covering tree; transportation network; extensive facility (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1026187616229 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:123:y:2003:i:1:p:265-284:10.1023/a:1026187616229

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1026187616229

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().