Breakout local search for the Steiner tree problem with revenue, budget and hop constraints
Breakout local search for the Steiner tree problem with revenue, budget and hop constraints
复制标题
在收入、预算和跳跃限制下突破本地搜索斯坦纳树问题
DOI：
10.1016/j.ejor.2013.06.048
复制
发表时间：
2014
影响因子：
6.4
通讯作者：
Hao, Jin-Kao
中科院分区：
文献类型：
--
作者：
Fu, Zhang-Hua;Hao, Jin-Kao
斯坦纳树问题（STP）是最流行的组合优化问题之一，具有多种实际应用。在本文中，我们提出了一种突破局部搜索（BLS）算法，用于STP的一个重要推广：具有收入，预算和跳数约束的Steiner树问题（STPRBH），该问题包括确定给定无向图的子树，该子树在预算和跳数约束下使收集的收入最大化。从一个概率构造的初始解出发，BLS使用基于几个特别设计的移动算子的邻域搜索（NS）过程进行局部优化，并采用自适应多样化策略逃避局部最优。多样化机制通过自适应扰动实现，并以发现的高质量解的专用信息为指导。基于240个基准的计算结果表明，相对于之前的几种方法，BLS产生了具有竞争力的结果。对于56个具有未知最佳结果的最具挑战性的实例，BLS成功地改进了49个实例，并在合理的时间内匹配了一个最知名的结果。对于已求解到最优的184个实例，BLS还能匹配出167个最优结果。
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.
登录
查看更多内容
DOI：
10.1007/978-0-387-30165-5_18
发表时间：
2006
期刊：
--
影响因子：
--
作者：
S. Voß
通讯作者：
S. Voß
影响因子：
4
作者：
Benlic, Una;Hao, Jin-Kao
通讯作者：
Hao, Jin-Kao
DOI：
--
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Markus Sinnl;Verfassung der Arbeit
通讯作者：
Markus Sinnl;Verfassung der Arbeit
影响因子：
4.8
作者：
S. Voß
通讯作者：
S. Voß
DOI：
--
发表时间：
2000-02
期刊：
--
影响因子：
--
作者：
David S. Johnson;M. Minkoff;Steven J. Phillips
通讯作者：
David S. Johnson;M. Minkoff;Steven J. Phillips