A self-adaptive and stagnation-aware breakout local search algorithm on the grid for the Steiner tree problem with revenue, budget and hop constraints

Dokeroglu T., Mengusoglu E.

SOFT COMPUTING, vol.22, no.12, pp.4133-4151, 2018 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 22 Issue: 12
  • Publication Date: 2018
  • Doi Number: 10.1007/s00500-017-2630-7
  • Journal Name: SOFT COMPUTING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.4133-4151
  • Hacettepe University Affiliated: Yes


The Steiner tree problem (STP) is a challenging NP-Hard combinatorial optimization problem. The STP with revenue, budget and hop constraints (STPRBH) determines a subtree of a given undirected graph with the defined constraints. In this study, we propose a novel self-adaptive and stagnation-aware breakout local search (BLS) algorithm (Grid-BLS) for the solution of the STPRBH. The proposed Grid-BLS is a parallel algorithm and keeps the parameters of the BLS heuristic in a population at the master node and tunes/updates them with the best performing parameters sent by the slave nodes. The parameter tuning of the BLS heuristic is considered as another optimization job and processed by a genetic algorithm that runs on the master node. The slave nodes perform BLS search and use a multistarting technique that prevents them to get stuck in a local optima by restarting the search processes. A master and slave communication topology is used for communicating with the slave processors. In order to evaluate the performance of the Grid-BLS algorithm, experiments are carried out on 240 benchmark problem instances. The solutions for 226 of these problems are reported to be optimal or the best solutions. The Grid-BLS achieves 21 new best solutions (graphs) that have never been found by any heuristic algorithm so far and performs better than the state-of-the-art heuristic algorithms Greedy, Destroy&Repair, Tabu Search, and Dynamic Memetic.