Breakout local search for the Steiner tree problem with revenue, budget and hop constraints

Zhang-Hua Fu and Jin-Kao Hao

European Journal of Operational Research, 2014, vol. 232, issue 1, 209-220

Abstract: The Steiner tree problem (STP) is one of the most popular combinatorial optimization problems with various practical applications. In this paper, we propose a Breakout Local Search (BLS) algorithm for an important generalization of the STP: the Steiner tree problem with revenue, budget and hop constraints (STPRBH), which consists of determining a subtree of a given undirected graph which maximizes the collected revenues, subject to both budget and hop constraints. Starting from a probabilistically constructed initial solution, BLS uses a Neighborhood Search (NS) procedure based on several specifically designed move operators for local optimization, and employs an adaptive diversification strategy to escape from local optima. The diversification mechanism is implemented by adaptive perturbations, guided by dedicated information of discovered high-quality solutions. Computational results based on 240 benchmarks show that BLS produces competitive results with respect to several previous approaches. For the 56 most challenging instances with unknown optimal results, BLS succeeds in improving 49 and matching one best known results within reasonable time. For the 184 instances which have been solved to optimality, BLS can also match 167 optimal results.

Keywords: Steiner tree problems; Network design; Constrained combinatorial optimization; Heuristic search; Adaptive perturbation (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221713005559
Full text for ScienceDirect subscribers only

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:eee:ejores:v:232:y:2014:i:1:p:209-220

DOI: 10.1016/j.ejor.2013.06.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().