EconPapers    
Economics at your fingertips  
 

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 ().

 
Page updated 2024-11-05
Handle: RePEc:ant:wpaper:2014012