Solving Chance-Constrained Programs combining Tabu Search and Simulation

Real world problems usually have to deal with some uncertainties. This is particularly true for the planning of services whose requests are unknown a priori. Several approaches for solving stochastic problems are reported in the literature. Metaheuristics seem to be a powerful tool for computing good and robust solutions. However, the efficiency of algorithms based on Local Search, such as Tabu Search, suffers from the complexity of evaluating the objective function after each move. In this paper, we propose alternative methods of dealing with uncertainties which are suitable to be implemented within a Tabu Search framework.