TABU SEARCH WITH ASPIRATION CRITERION FOR THE TIMETABLING PROBLEM

Abstract

The aspiration criterion is an imperative element in the Tabu Search, with aspiration-by-default and the aspiration-by-objective the mainly used criteria in the literature. In this paper a new aspiration criterion is proposed in order to implement a probabilistic function when evaluating an element classified as tabu which improves the current solution, the proposal is called Tabu Search with Probabilistic Aspiration Criterion (BT- CAP). The test case used to evaluate the performance of the Probabilistic Aspiration Criterion proposed consists on the 20 instances of the problem described in the First International Timetabling Competition. The results are compared with 2 additional variants of the Tabu Search Algorithm: Tabu Search with Default Aspiration Criterion (BT-CAD) and Tabu Search with Objective Aspiration Criterion (BT-CAO). Wilcoxon test was applied to the generated results, and it was proved with 99 % confidence that BT-CAP algorithm gets better solutions than the two other variants of the Tabu Search algorithm.

Keywords

• búsqueda tabú
• criterio de aspiración
• programación de horarios
• metaheurística