Capacitated ring arborescence problems with profits

Alessandro Hill (), Roberto Baldacci () and Edna Ayako Hoshino ()
Additional contact information
Alessandro Hill: California Polytechnic State University
Roberto Baldacci: University of Bologna
Edna Ayako Hoshino: University of Mato Grosso do Sul

OR Spectrum: Quantitative Approaches in Management, 2019, vol. 41, issue 2, No 2, 357-389

Abstract: Abstract In this work, we introduce profit-oriented capacitated ring arborescence problems and present exact and heuristic algorithms. These combinatorial network design problems ask for optimized bi-level networks taking into account arc costs and node profits. Solutions combine circuits on the inner level with arborescences on the outer level of the networks. We consider the prize-collecting, the budget-constrained and the target-profit models and develop corresponding exact branch-and-cut algorithms based on mixed-integer formulations and valid inequalities. Iterated local search heuristics based on the exploration of problem-specific neighborhoods are elaborated to strengthen the upper bounds. For a set of hard literature derived instances with up to 51 nodes, we provide computational results which give evidence for the efficiency of the proposed approaches. Furthermore, we extensively analyze the performance of our methods, the obtained solution networks and the impact of the cutting planes on the obtained lower bounds.

Keywords: Network design; Ring arborescence problem; Vehicle routing problem; Orienteering problem; Prize-collecting Steiner tree problem; Mathematical programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-018-0539-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:orspec:v:41:y:2019:i:2:d:10.1007_s00291-018-0539-x

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-018-0539-x

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().