Iterated local search with two strategies in the acceptance criterion for the tree t $t$ ‐spanner problem

Abstract The tree t $t$ ‐spanner problem ( T r _ t $Tr\_t$ ‐SP), for a given edge‐weighted, undirected, and connected graph, is an NP $$ ‐hard problem with practical applications that aims to find a spanning tree with minimum t $t$ , called the stretch factor. Due to its computational intractability, metaheuristic techniques have attracted much attention in the literature for finding good solutions within an acceptable computational time. In this article, we make the first attempt to propose a single solution‐based iterated local search (ILS) for theT r _ t $Tr\_t$ ‐SP. To ensure high search efficiency and efficacy, the proposed ILS framework relies on the perturbation strategy, a problem‐specific local search, and the use of two strategies in the acceptance criterion of ILS. On a set of available 48 benchmark instances, experimental results indicate that the proposed ILS consistently outperforms the existing best‐so‐far approach, particularly with the increase in instance sizes. The results yield new improved values on 32 instances out of 48 instances. We investigate the effectiveness of using two strategies in the acceptance criterion of ILS. Moreover, a statistical analysis is conducted to demonstrate its significance.