Optimal capacitated ring trees
Alessandro Hill and
Stefan VOß
Working Papers from University of Antwerp, Faculty of Business and Economics
Abstract:
We study a new network design model combining ring and tree structures under capacity constraints. The solution topology of this capacitated ring tree problem (CRTP) is based on ring trees which are the union of trees and 1-trees. The objective is the minimization of edge costs but could also incorporate other types of measures. This overall problem generalizes prominent capacitated vehicle routing and Steiner tree problem variants. Two customer types have to be connected to a distributor ensuring single and double node connectivity, respectively, while installing optional Steiner nodes. The number of ring trees and the number of customers supplied by such a single structure are bounded. After embedding this combinatorial optimization model in existing network design concepts, we develop a mathematical formulation and introduce several valid inequalities for the CRTP that are separated in our exact algorithm. Additionally, we use local search techniques to tighten the obtained upper bounds. For a set of literature-derived instances we consider various reliability scenarios and present computational results.
Keywords: Capacitated ring tree problem; Steiner tree; Ring tree; Vehicle routing; Survivable network design; Integer programming (search for similar items in EconPapers)
Pages: 32 pages
Date: 2014-07
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)
Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/d9597f/145286.pdf (application/pdf)
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:ant:wpaper:2014012
Access Statistics for this paper
More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().