A novel iterative improvement pivoting rule for local search heuristics
Saad Bougrine, Mohamed Amine El Majdouli, Abdelhakim Ameur El Imrani · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2017
This paper proposes a new pivoting rule named Oriented iterative improvement "OI" for local search heuristics extensively used in metaheuristics solving NP-Hard combinatorial optimization problems. Actually, OI consists in dividing the neighborhood of a solution into many subsets and orients the walk in the search space using information gathered from another reference solution. In this study, the proposed improvement strategy is compared to the well-known first improvement strategy which is known to give good solutions in a relatively short time in comparison to the other strategies. the Single Machine Total Weighted Tardiness problem SMTWTP is used to evaluate the performance of the proposed pivoting rule. the experiments show that OI is comparable with Random first iterative improvement in terms of solutions quality but more importantly, OI scores a largely better time complexity.