•A GRASP-based constructive algorithm is proposed to solve combinatorial dynamic optimization problems.•Tests are conducted on time-varying multi-dimensional knapsack problem with dimensional changes.•Improved evolutionary algorithms, employing hyper-heuristic based local search procedure are developed.•A hyper-heuristic algorithm, using other metaheuristics as low-level heuristics is developed.•Results of extensive statistical analyses point out the competiveness of the proposed algorithms. Optimization in dynamic environments is a hot research area that has attracted a notable attention in the past decade. It is clear from the dynamic optimization literature that most of the effort is devoted to continuous dynamic optimization problems although majority of the real-life problems are combinatorial. Additionally, in comparison to evolutionary or population-based approaches, constructive search strategy, which is shown to be successful in stationary combinatorial optimization problems, is commonly ignored by the dynamic optimization community. In the present work, a constructive and multi-start search strategy is proposed to solve dynamic multi-dimensional knapsack problem, which has numerous applications in real world. Making use of constructive and multi-start features, the aim here is to test the performance of such a strategy and to observe its behavior in dynamically changing environments. In this regard, this strategy is compared to the well-known evolutionary and population-based approaches, including a Genetic Algorithm-based memetic algorithm, Differential Evolution algorithm, Firefly Algorithm and a hyper-heuristic, which employs these population-based algorithms as low-level heuristics in accordance with their individual contributions. Furthermore, in order to improve their performances in dynamic environments, the mentioned evolutionary algorithms are enhanced by using triggered random immigrants and adaptive hill climbing strategies. As one can see from the comprehensive experimental analysis, while the proposed approach outperforms most of the evolutionary-based approaches, it is outperformed by firefly and hyper-heuristic algorithms in some of the instances. This points out competiveness of the proposed approaches. Finally, according to the statistical results of non-parametric tests, one can conclude that the proposed approach can be considered as a promising and a competitive algorithm in dynamic environments.