metodologia grasp

CAPITULO 3
METODOLOGIA GRASP

3.1

Descripción General de la Metodología GRASP

La metodología GRASP consiste en combinar dos heurísticas:
1. Una heurística constructiva.
2. Una heurística de mejora.

3.2

Modelo básico de routing. VRP
1.

Construir la ruta.

2.

Asignación de los clientes a las rutas, sin exceso de capacidad.

3.

Circuito hamiltoneano de costo mínimo.4.

Dos niveles de decisión: Asignación

y Orden de visitas o

recorrido.
Se opera con datos reales no euclidianos para que el resultado sea real.

3.2.1 Metodología de las técnicas Metaheurísticas

Meta Heurísticos en Optimización Combinatoria
En los últimos años ha habido un crecimiento espectacular en el
desarrollo de procedimientos heurísticos para resolver problemascombinatorios. Este hecho puede ser constatado examinando el gran
número de artículos en revistas de Investigación Operativa en los que

se proponen y estudian métodos heurísticos como las publicaciones
específicas para el estudio y divulgación de dichos procedimientos
tales como “Journal of Heuristics”.
El auge que experimentan los procedimientos heurísticos se debe sin
duda a la necesidad dedisponer de herramientas que permitan
ofrecer soluciones rápidas a problemas reales. Es importante destacar
el hecho de que los algoritmos heurísticos (por sí solos) no garantizan
la optimalidad de la solución encontrada, aunque su propósito es
encontrar una solución cercana al óptimo en un tiempo razonable. Sin
embargo, la gran cantidad de publicaciones en donde problemas de
gran dificultad sonresueltos con gran rapidez, avalan estos métodos.
Dentro de las técnicas heurísticas existen diversos métodos, como:
Métodos

constructivos,

de

descomposición,

de

reducción,

de

manipulación del modelo y de búsqueda local. Tradicionalmente, para
resolver un problema dado se diseñaba un algoritmo específico que
pertenecía a algunos de los métodos enumerativos. El interésprimordial de los investigadores del área es diseñar métodos
generales que sirvan para resolver clases o categorías de problemas.
Dado que estos métodos generales sirven para construir o guiar el
diseño de métodos que resuelvan problemas específicos se les ha
dado el nombre de Metaheurísticos. Los profesores Osman y Kelly
(1995) introducen la siguiente definición:

"Los procedimientosMetaheurísticos son una clase de métodos
aproximados que están diseñados para resolver problemas difíciles de
optimización combinatoria, en los que los heurísticos clásicos no son
eficientes”. Los Metaheurísticos proporcionan un marco general para
crear nuevos algoritmos híbridos combinando diferentes conceptos
derivados de: inteligencia artificial, evolución biológica y mecanismos
estadísticos" .Los

cuatro

reconocidos

procedimientos
en

la

Metaheurísticos

Optimización

más

Combinatoria

utilizados

son:

y

Simulated

Annealing, Tabú Search, GRASP y Algoritmos Genéticos. Si se está
interesado en profundizar en estas técnicas y desea consultar más
información , se recomienda la siguiente bibliografía: "Optimización
Heurística y Redes Neuronales"1 y"Heurísticas en Optimización"

2

3.2.2 Procedimientos Meta-Heurísticos:
A) Búsqueda Tabú
B) Templado Simulado
C) Algoritmos Genéticos
D) GRASP
1

"Optimización Heurística y Redes Neuronales". Edit Adenso Díaz. Editorial
Paraninfo. 1996
2

"Heurísticas en Optimización". J. Marcos Moreno y José A. Moreno. Edita:
Dirección General Universidades, Gobierno de Canarias (1999).

- Simulatedannealing (primeros trabajos 1953, 1983)
-

Redes neuronales (primeras ideas en los 60, resurgieron en los
80)

-

Algoritmos genéticos (primeras ideas en los 60, mayormente
aplicaciones a problemas de IA).
Algoritmos evolutivos

-

Tabú Search

(primeras aplicaciones a optimización combinatoria

en 1986, basado en algunas ideas de los 70)
-

Búsqueda con umbral (Threshold...