Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization

Resumen

We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of high-quality solutions throughout the search. After a fixed number of GRASP iterations, exterior path relinking is applied between all pairs of elite set solutions and the best solution found is returned. Exterior path relinking, or path separation, a variant of the more common interior path relinking, is first applied in this paper. In interior path relinking, paths in the neighborhood solution space connecting good solutions are explored between these solutions in the search for improvements. Exterior path relinking, as opposed to exploring paths between pairs of solutions, explores paths beyond those solutions. This is accomplished by considering an initiating solution and a guiding solution and introducing in the initiating solution attributes not present in the guiding solution. To complete the process, the roles of initiating and guiding solutions are exchanged. Extensive computational experiments on 190 instances from the literature demonstrate the competitiveness of this algorithm.

Abraham Duarte

Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.

Jesús Sánchez-Oro

Profesor Titular de Universidad

Profesor Titular del Departamento de Informática, siendo uno de los investigadores principales del Grupo de Investigación de Algoritmos para la Optimización GRAFO.