Optimized Search Heuristics

In recent years, much attention and many papers have been devoted to general heuristics techniques, known as metaheuristics, that are applicable, in particular, to solve hard combinatorial optimization problems. There are a huge amount of combinatorial optimization problems in all sectors of management, as for example sequencing and scheduling, routing and transportation and plant location. These metaheuristics use neighborhood function to explore the set of feasible solutions. Recently a new class of metaheuristics have been developed that present some additional innovation features related with the mathematical structure of the problems, that we denominate as Optimized Search Heuristics (OSH). The inclusion of these new features has the objective of improving the search by guiding it efficiently towards a good solution, and can be seen as intensification/diversification strategies based on classical optimization and hybrid methods. Some of these new features include new crossover operators as the perfect offspring by Louren\c{c}o [1998] and optimized crossover by Aggrawal, Orlin \& Tai [1997] in genetic algorithms, or optimized intensification strategies in tabu search. These operators consider a set parents and try to obtain the best offspring of these parents by solving exactly a relaxation of the problem, or make a large optimized step to a optimal solution of a subproblem, taking advantage that an exact method can solve efficiently and in short time the relaxation problems and subproblems of the main one. We will present a survey and contributions from several authors in the use of these optimized features in metaheuristics, and also, we will introduce new ideas how to apply the OSH methods to several well-known combinatorial optimization problems, as the job-shop scheduling problem and the crew scheduling problem.