DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
an introduction to trajectory-based heuristics, with an application to

Since the very early beginnings of operations research, heuristics have been used to tackle problems that could not be solved using exact solution techniques, in particular, difficult combinatorial problems.  Classical heuristics are usually classified into two broad groups: construction heuristics, which construct a solution from scratch, and improvement methods, which improve step by step feasible initial solutions, often obtained by construction heuristics.  The most common, by far, of the improvement approaches is Local Search (LS), an iterative search procedure that progressively improves an initial feasible solution by applying a series of local modifications (or moves).  At each iteration, the search moves to an improving feasible solution that differs only slightly from the current one (in fact, the difference between the previous and the new solutions amounts to one of the local modifications mentioned above) and thus follows a trajectory in the search space.  The search terminates when it encounters a local optimum with respect to the transformations that it considers, an important limitation of the method: unless one is extremely lucky, this local optimum will, more often than not, be a somewhat mediocre solution.  This realization has led to the progressive development of more sophisticated solution approaches that retain the basic principles of LS, but also complement them with others to achieve a much better performance.

In the first part of the talk, we will provide an introduction to trajectory-based heuristic, namely, the definition of the search space and the neighborhod structure, we will examine several trajectory-based (meta-) heuristics, which have become quite popular over proved very effective for solving difficult combinatorial problems: Simutated Annealing, Tabu Search, Variable Neigborhood Descent, etc.

In the second part of the talk, we wiil describe how trajectory-based heuristics have been applied to variety of problems in the field of vehicle routing.