Post on 23-Jan-2016
Universidad de La Laguna | Experto en Logística y Transportes 1
Experto en Logística y TransportesMódulo 4: Transporte
José A. Moreno Pérez, J. Marcos Moreno Vega
Grupo de Computación Inteligente
Dpto. de E.I.O. y Computación
Escuela Técnica Superior de Ingeniería Informática
Universidad de La Laguna
jamoreno@ull.es, jmmoreno@ull.es
webpages.ull.es/users/jamoreno, webpages.ull.es/users/jmmoreno
Universidad de La Laguna | Experto en Logística y Transportes 2
Introducción
Heurísticas
Métodos constructivos
Búsquedas por entornos
GRASP
Optimización basada en Colonias de Hormigas
Universidad de La Laguna | Experto en Logística y Transportes 3
SITUACIÓN REAL
Hoy debes planificar la ruta de los 250 furgones de reparto de tu compañía desde
los 12 almacenes hasta las localizaciones de los 5000 vendedores finales. La
situación se complica debido a los posibles accidentes, cortes de carretera,
atascos, transporte de mercancías perecederas, horario en que puedes repartir la
mercancía, …
Además, no puedes usar la planificación de ayer, ya que la situación ha cambiado
significativamente: los pedidos no son los mismos, algunos de tus trabajadores
tienen el día libre, hay un desvío provisional debido a unas obras, se esperan
lluvias, ….
Universidad de La Laguna | Experto en Logística y Transportes 4
HERRAMIENTAS PARA LA GESTIÓN LOGÍSTICA
En el entorno Logístico y de Transportes actual, las empresas necesitan
herramientas computacionales que les permitan reducir costes, mejorar el servicio
y realizar sus operaciones de la forma más rápida posible.
Estas herramientas deben ser flexibles, permitir la incorporación del conocimiento
experto que poseen los gestores y facilitar su uso en nuevas situaciones.
Sistemas informáticos que resuelvan eficientemente las diversas tareas que aparecen en la Gestión Logística.
Universidad de La Laguna | Experto en Logística y Transportes 5
PROBLEMAS
OPTIMIZAR f(x)
s.a: x S
f(), función objetivo
S, región factible o espacio solución
OPTIMIZAR, minimizar, maximizar
Universidad de La Laguna | Experto en Logística y Transportes 6
PROBLEMAS | Ejemplo
x = ruta seguida por el viajante de comercio (permutación de las ciudades)
f(x) = suma de las distancias recorridas
S = todas las posibles rutas (todas las permutaciones de n-1 elementos)
Universidad de La Laguna | Experto en Logística y Transportes 7
SATISFACER EN LUGAR DE OPTIMIZAR
|S| = (n-1) 10! = 3 628 800
15! = 1 307 674 368 000
20! > 2 432 902 010 000 000 000
25! > 15 511 210 000 000 000 000 000 000
SATISFACER AL DECISOR
Encontrar una solución suficientemente buena con un uso razonable de recursos
OPTIMIZAR
HEURÍSTICAS
Universidad de La Laguna | Experto en Logística y Transportes 8
HEURÍSTICAS
Universidad de La Laguna | Experto en Logística y Transportes 9
HEURÍSTICAS | Origen
Heurística proviene del griego Heuriskein que puede traducirse por hallar,
descubrir, encontrar
Arquímedes salió corriendo desnudo por la calle gritando Eureka (lo
encontré), cuando descubrió el principio de flotación mientras estaba en el
baño
Definición: arte de inventar o descubrir hechos valiéndose de hipótesis o
principios que, aun no siendo verdaderos, estimulan la investigación
Universidad de La Laguna | Experto en Logística y Transportes 10
HEURÍSTICAS | Interpretaciones
Primera interpretación:
reglas con las que la gente gestiona el conocimiento común
Segunda interpretación:
procedimiento de resolución de problemas
Tercera interpretación:
función que permite evaluar la bondad de un movimiento, estado,
elemento o solución
Universidad de La Laguna | Experto en Logística y Transportes 11
HEURÍSTICAS | Primera Interpretación
Buscar un problema parecido que haya sido resuelto
Determinar cuáles fueron la técnica empleada para su resolución y la
solución obtenida.
Si es posible, usar la técnica y/o solución anteriores para resolver el
problema original.
Universidad de La Laguna | Experto en Logística y Transportes 12
HEURÍSTICAS | Primera Interpretación | Ejemplo
3x cosx dx = 3x sinx - sinx 3 dx = 3x sinx – 3 sinx dx =
3x sinx + 3 cosx + C
u dv = uv - v
du
4x sinx dx =
- 4x cosx + cosx 4 dx = - 4x cosx + 4 cosx dx =
- 4x cosx + 4 sinx + C
u dv = uv - v
du
Universidad de La Laguna | Experto en Logística y Transportes 13
HEURÍSTICAS | Segunda Interpretación
Un método heurístico (también llamado un algoritmo aproximado, un
procedimiento inexacto, o, simplemente, una heurística) es un conjunto bien
conocido de pasos para identificar rápidamente una solución de alta calidad
para un problema dado.
Barr, Golden, Kelly, Resende, Stewart
Universidad de La Laguna | Experto en Logística y Transportes 14
Heurística: desde el cliente actual nos movemos al cliente más cercano que no hayamos visitado
HEURÍSTICAS | Segunda Interpretación | Ejemplo
Universidad de La Laguna | Experto en Logística y Transportes 15
HEURÍSTICAS | Tercera Interpretación
Una función heurística es una correspondencia entre las descripciones de
estados del problema hacia alguna medida de deseabilidad, normalmente
representada por números. Los aspectos del problema que se consideran,
cómo se evalúan estos aspectos y los pesos que se dan a los aspectos
individuales, se eligen de forma que el valor que la función da a un nodo en el
proceso de búsqueda sea una estimación tan buena como sea posible para
ver si ese nodo pertenece a la ruta que conduce a la solución.
Elaine Rich, Kevin Knight
Universidad de La Laguna | Experto en Logística y Transportes 16
HEURÍSTICAS | Tercera Interpretación | Ejemplo
1 2 3
4 5 6
7 8 9
fx(1) = 3
fx(2) = 2
fx(3) = 3
fx(4) = 2
fx(5) = 4
fx(6) = 2
fx(7) = 3
fx(8) = 2
fx(9) = 3
X
fO(1) = 2
fO(2) = 1
fO(3) = 2
fO(4) = 1
fO(6) = 1
fO(7) = 2
fO(8) = 1
fO(9) = 2
O
fX(1) = 2
fX(2) = 1
fX(4) = 2
fX(6) = 1
fX(7) = 2
fX(8) = 2
fX(9) = 2
1 2 3
4 5 6
7 8 9
X
1 2 3
4 5 6
7 8 9
X
O
X
Función heurística: número de filas, columnas o diagonales en las que se puede ganar
Universidad de La Laguna | Experto en Logística y Transportes 17
HEURÍSTICAS
Algunos métodos de resolución de problemas emplean funciones
heurísticas, para evaluar determinados movimientos o elementos. Además,
las funciones heurísticas usadas intentan representar el conocimiento que
emplean los expertos para resolver los problemas.
Universidad de La Laguna | Experto en Logística y Transportes 18
¿POR QUÉ O CUÁNDO USAR HEURÍSTICAS?
No se dispone de un procedimiento exacto para resolver el problema planteado.
Se dispone de un procedimiento exacto, pero es ineficiente.
Se desea aumentar la eficiencia de un procedimiento exacto.
No se poseen conocimientos específicos sobre el problema que permitan abordarlo de forma exacta.
Se tiene que resolver repetidas veces un mismo problema, probablemente con datos distintos.
Se quiere disponer de un procedimiento de solución que el decisor pueda comprender.
Universidad de La Laguna | Experto en Logística y Transportes 19
PROPIEDADES DESEABLES DE UNA HEURÍSTICA
Simples: fáciles de comprender.
Robustas: buen comportamiento al variar el valor de algún parámetro.
Generales: aplicables a una gran variedad de problemas.
Efectivas: encontrar soluciones de alta calidad.
Eficientes: consumir poco recursos.
Producir múltiples soluciones.
Universidad de La Laguna | Experto en Logística y Transportes 20
EMPRESAS DE INVESTIGACIÓN Y DESARROLLO
Dirección web: www.antoptima.com
Descripción: AntOptima is a Swiss company based in Lugano which develops innovative optimisation methodologies to increase the efficiency of productive and logistic processes.
Productos:
Universidad de La Laguna | Experto en Logística y Transportes 21
Ant Route
Ant Route es un programa informático que permite la optimización dinámica a
gran escala de flotas y rutas de vehículos.
Es resultado de la colaboración entre AntOptima y un grupo de compañías
internacionales de distribución.
Ant Route consta de cuatro módulos: un módulo base, TOUR PLANNING
OPTIMISER, y tres módulos complementarios: GDO, SIMTOUR y TOUR-ONLINE.
El módulo principal de Ant Route es un algoritmo de optimización basado en
colonias de hormigas, que suministra eficientemente soluciones de alta calidad.
Universidad de La Laguna | Experto en Logística y Transportes 22
Ant Route
Dado un conjunto de órdenes, calcula las mejores rutas para la flota de vehículos. Tiene en cuenta, entre otras, las limitaciones sobre el máximo tiempo de viaje y los horarios de entrega y recogida.
TOUR PLANNING OPTIMISER
Resuelve problemas de rutas de vehículos con uno o varios almacenes, optimiza la asignación de conductores, gestiona varios tipos de transportes (camiones, furgonetas, …), …
GDO (Distribution optimiser)
Módulo que simula diferentes escenarios (lluvia, accidentes, congestiones, …) y suministra soluciones para cada uno de ellos.
SIM TOUR
A través de una conexión GSM/GPRS y usando un GPS, el gestor está constantemente en contacto con la flota de vehículos. Así, puede atender demandas no previstas inicialmente y resolver, conjuntamente con SIM TOUR, situaciones inesperadas.
TOUR ONLINE
Universidad de La Laguna | Experto en Logística y Transportes 23
CLASIFICACIÓN
Métodos constructivos
GRASP
Búsquedas por entornos
Búsquedas locales
Multiarranque
VNS (Búsqueda por entorno variable)
SA (Recocido simulado)
Búsqueda Local Guiada
Búsqueda Tabú
Métodos que imitan el comportamiento de sistemas biológicos
Optimización basada en colonias de hormigas
Algoritmos genéticos
Algoritmos Meméticos
Universidad de La Laguna | Experto en Logística y Transportes 24
MÉTODOS CONSTRUCTIVOS
Universidad de La Laguna | Experto en Logística y Transportes 25
MÉTODO CONSTRUCTIVO
Son las Heurísticas más simples y naturales.
Se basan en una estrategia muy usada para resolver problemas cotidianos:
construir, poco a poco, una solución del problema que se nos plantea.
En general, no suministran la mejor solución del problema.
Universidad de La Laguna | Experto en Logística y Transportes 26
MÉTODO CONSTRUCTIVO | Construyendo una solución
Coste = 300 um
1. Seleccionar un almacén.
2. Construir una ruta desde ese almacén.
3. Si todos los clientes han sido atendidos, parar. En caso contrario, repetir desde el paso 1.
Universidad de La Laguna | Experto en Logística y Transportes 27
MÉTODO CONSTRUCTIVO | Variantes
¿Cómo seleccionar los almacenes?
Al azar.
Ordenados por coste.
El primero al azar; los demás en función de la distancia a los realmente abiertos.
¿Cómo construir las rutas?
Al azar.
Desde un cliente al cliente más cercano.
Agrupar primero los clientes y luego abrir almacenes para ellos.
Universidad de La Laguna | Experto en Logística y Transportes 28
MÉTODO CONSTRUCTIVO |
Coste = 650 um
1. Seleccionar un almacén.
2. Construir una ruta desde ese almacén.
3. Si todos los clientes han sido atendidos, parar. En caso contrario, repetir desde el paso 1.
Universidad de La Laguna | Experto en Logística y Transportes 29
BÚSQUEDAS POR ENTORNOS
Universidad de La Laguna | Experto en Logística y Transportes 30
MOVIMIENTOS | Modificando una solución
Movimiento: modificación de una solución
Coste = 300 um
Coste = 280 um
2-intercambio de aristas
Universidad de La Laguna | Experto en Logística y Transportes 31
MOVIMIENTOS | Modificando una solución
Coste = 300 um
Coste = 295 um
intercambio de almacenes
Universidad de La Laguna | Experto en Logística y Transportes 32
MOVIMIENTOS | Modificando una solución
Coste = 300 um
Coste = 270 um
Reasignación de un cliente
Universidad de La Laguna | Experto en Logística y Transportes 33
MOVIMIENTOS | Modificando una solución
¿Qué almacenes intercambiar?
Dos al azar.
Dos próximos entre sí.
¿Qué cliente escoger para reasignar?
Uno al azar.
El más alejado de su correspondiente almacén.
¿A qué almacén reasignar el cliente escogido?
A uno al azar.
Al almacén cuya ruta esté más cerca del cliente.
Universidad de La Laguna | Experto en Logística y Transportes 34
3
3
3
6
7
1
9
1
4
3
5
3
1
6
9
3
4
5
2
5
4
1
5
1
7
3
1
3
4
3
2
5
3
6
4
8
7
3
7
5
9
2
2
8
3
4
4
1
Coste = 300 umCoste = 400 um
TOPOLOGIA DEL ESPACIO DE SOLUCIONES
Universidad de La Laguna | Experto en Logística y Transportes 35
5
3
5
6
7
5
9
1
4
3
5
3
4
6
9
2
4
5
6
5
4
7
5
4
7
3
1
3
4
2
6
5
3
2
4
8
7
3
7
5
9
9
9
8
3
4
4
8
ÓPTIMOS LOCALES Y GLOBALES (i)
Universidad de La Laguna | Experto en Logística y Transportes 36
ÓPTIMOS LOCALES Y GLOBALES (ii)
Un solución es un óptimo global para un problema si su valor objetivo es
mejor que el de cualquiera solución.
Una solución es un óptimo local para un problema si su valor objetivo es
mejor que el de cualquiera de sus vecinas.
Un óptimo global es también un óptimo local.
Universidad de La Laguna | Experto en Logística y Transportes 37
BÚSQUEDAS POR ENTORNOS
Búsquedas por entorno: después de fijar una apropiada estructura de entorno
sobre el espacio de soluciones, se escoge una solución del entorno de la
solución actual hasta que se satisfaga el criterio de parada. El proceso de
escoger una solución del entorno de la solución actual consta de dos fases:
seleccionar la solución y decidir si se acepta o no. Otro elemento importante
en tales búsquedas es el método por el cuál se determina la solución de
partida para iniciar el recorrido.
Universidad de La Laguna | Experto en Logística y Transportes 38
BÚSQUEDAS POR ENTORNOS
…
…
Universidad de La Laguna | Experto en Logística y Transportes 39
BÚSQUEDA LOCAL | Aplicando mejoras mientras sea posible
Aplican algún movimiento de mejora a la solución actual.
En general, estos movimientos se corresponden con ligeras modificaciones
de la solución que se tiene en cada iteración.
Cuando no existen movimientos de mejora, o se ha alcanzado una solución
satisfactoria para el usuario, se finaliza el método.
Esta Heurística se basa en la estrategia de mejora sucesiva que solemos usar
para dar solución a numerosos problemas cotidianos.
Universidad de La Laguna | Experto en Logística y Transportes 40
BÚSQUEDA LOCAL
Coste = 300 um Coste = 280 um
Coste = 250 um
Universidad de La Laguna | Experto en Logística y Transportes 41
BÚSQUEDA LOCAL
Definir qué tipo de modificación se va a realizar a las soluciones (cambiar los almacenes de lugar, cambiar las rutas, cambiar el almacén que sirve a un cliente, …).
Considerar una solución inicial (fijar almacenes y rutas de los vehículos).
Si ninguna de las posibles modificaciones mejora la solución actual, finalizar la búsqueda.
En caso contrario, aplicar una modificación de mejora a la solución actual.
Repetir desde el paso 3 con la nueva solución.
Universidad de La Laguna | Experto en Logística y Transportes 42
Posibles localizaciones:
Puntos de demanda:
Problema de la 2-mediana con distancia euclídea
INCONVENIENTE DE UNA BÚSQUEDA LOCAL (i)
Universidad de La Laguna | Experto en Logística y Transportes 43
Matriz de distanciasEstructura de entorno del 1-intercambio
Solución Objetivo Vecinas
Una Búsqueda Local sólo asegura optimalidad local. La solución que suministra puede estar muy alejada de la solución óptima global.
S3
S4
INCONVENIENTE DE UNA BÚSQUEDA LOCAL (ii)
Universidad de La Laguna | Experto en Logística y Transportes 44
5
3
5
6
7
5
9
1
4
3
5
3
4
6
9
2
4
5
6
5
4
7
5
4
7
3
1
3
4
2
6
5
3
2
4
8
7
3
7
5
9
9
9
8
3
4
4
8
INCONVENIENTE DE UNA BÚSQUEDA LOCAL (iii)
Universidad de La Laguna | Experto en Logística y Transportes 45
Coste = 450 umCoste = 300 um
BÚSQUEDA MULTIARRANQUE (Desarrollar búsquedas locales desde diferentes soluciones de inicio)
Coste = 460 um
Coste = 390 um Coste = 230 um
Universidad de La Laguna | Experto en Logística y Transportes 46
BÚSQUEDA MULTIARRANQUE
Generar varias soluciones iniciales.
Aplicar una Búsqueda Local desde cada una de las soluciones anteriores.
Devolver la mejor solución encontrada.
Universidad de La Laguna | Experto en Logística y Transportes 47
5
3
5
6
7
5
9
1
4
3
5
3
4
6
9
2
4
5
6
5
4
7
5
4
7
3
1
3
4
2
6
5
3
2
4
8
7
3
7
5
9
9
9
8
3
4
4
8
VENTAJA DE UNA BÚSQUEDA MULTIARRANQUE
Universidad de La Laguna | Experto en Logística y Transportes 48
GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
Métodos constructivos
Alternativa: GRASP
Fase constructiva
Fase de postprocesamiento
Empaquetando rectángulos con GRASP
Universidad de La Laguna | Experto en Logística y Transportes 49
Método constructivo: Añadir iterativamente elementos a una estructura,
inicialmente vacía, hasta obtener una solución del problema.
Evaluación heurística: mide la conveniencia de incluir este elemento como
parte de la solución
Adaptativo: la evaluación de un elemento depende de los elementos
previamente incluidos en la solución
Estrategia greedy: escoger el elemento que optimiza la función heurística
MÉTODOS CONSTRUCTIVOS | Descripción
Universidad de La Laguna | Experto en Logística y Transportes 50
Estructura: objeto en que han de empaquetarse las piezas
Evaluación heurística: ajuste de la pieza rectangular al nivel más profundo del objeto
Estrategia: greedy (escoger la pieza que mejor se ajusta al nivel más profundo del objeto)
Inconveniente: la estrategia greedy no suministra, en general, la solución óptima del problema
MÉTODOS CONSTRUCTIVOS | Ejemplo e inconveniente
Universidad de La Laguna | Experto en Logística y Transportes 51
Lista Restringida de Candidatos (LRC): conjunto de los mejores elementos
Estrategia alternativa: escoger, al azar, uno de los mejores elementos
LRC= { , }Iteración 1
GRASP | Una alternativa
LRC= { , }Iteración 2
LRC= { , }Iteración 3
Universidad de La Laguna | Experto en Logística y Transportes 52
Procedure GRASP
Begin
Preprocesamiento
Repeat
Fase Constructiva(Solución);
PostProcesamiento(Solución);
Actualizar(Solución, MejorSolución);
Until (Criterio de parada);
End.
GRASP | Descripción y elementos
Universidad de La Laguna | Experto en Logística y Transportes 53
OBJETIVOS DEL PREPROCESAMIENTO:
Incluir aquellos elementos que necesariamente forman parte de una
solución
Comenzar con una solución parcial que, al menos a priori, facilite la fase
constructiva posterior
GRASP | Preprocesamiento
Universidad de La Laguna | Experto en Logística y Transportes 54
Lista Restringida de Candidatos (LRC): conjunto de los mejores elementos
Por cardinalidad: está formada por los k (parámetro fijado por el usuario) elementos con mayor valor de la función heurística
Por rango: la lista está formada por los elementos cuya evaluación está a una distancia no superior a un umbral fijado por el usuario de la mayor evaluación. Esto es, dado un valor 0,1, la lista restringida de candidatos la forman los elementos cuya evaluación está en el intervalo [(1-)MAX, MAX], siendo MAX la evaluación del mejor elemento
Por intersección de las dos anteriores: en cada iteración del proceso constructivo, la lista la forman los elementos que pertenecen simultáneamente a los dos conjuntos anteriores
GRASP | Fase constructiva | Lista restringida de candidatos
Universidad de La Laguna | Experto en Logística y Transportes 55
El objetivo del postprocesamiento es mejorar las soluciones
obtenidas en la fase constructiva. Para ello, puede emplearsen desde
simples búsquedas locales, hasta procedimientos más sofisticados
como Búsqueda Tabú o Búsqueda por Entornos Variables.
GRASP | Postprocesamiento
Universidad de La Laguna | Experto en Logística y Transportes 56
Dado un objeto rectangular de amplitud fija w y altura infinita, y un conjunto,
R = {R(w1, h1), …, R(wn, hn)},
de rectángulos con al menos uno de sus lados, wi, hi, menor que w, se desea empaquetar el conjunto R en el objeto rectangular utilizando el
menor espacio posible.
w
GRASP | Un ejemplo | Definición del problema
w
Universidad de La Laguna | Experto en Logística y Transportes 57
C = {(y1, x11, x1
2), (y2, x21, x2
2), …, (yc, xc1, xc
2)}
yi altura del i-ésimo segmento
xi1 coordenada x inicial del i-ésimo
segmento
xi2 coordenada x final del i-ésimo segmento
GRASP | Contorno
Universidad de La Laguna | Experto en Logística y Transportes 58
Lista restringida de candidatos 1:
sea 1 [0,1] y supongamos que (yi, xi1, xi
2) es el segmento del contorno con menor altura. Entonces:
LRC1={R(wj, hj) R2: (0 xi2 - xi
1 - wj 1) (0 xi2 - xi
1 - hj 1)}
GRASP | Lista restringida de candidatos
Universidad de La Laguna | Experto en Logística y Transportes 59
Lista restringida de candidatos 2:
sea 2 [0,1] y supongamos que (yi, xi1, xi
2) es el segmento
del contorno con menor altura. Supongamos que los
segmentos anterior y posterior, respectivamente (yi-1, xi-11, xi-
12) y (yi+1, xi+1
1, xi+12), son tales que yi < yi+1 < yi-1. Entonces:
LRC2={R(wj, hj) LRC1 : (0 yi+1 - yi - wj 2) (0 yi+1
- yi - hj
2)}
Si LRC1 LRC2 = , tomar LRC2 = LRC1.
GRASP | Lista restringida de candidatos
Universidad de La Laguna | Experto en Logística y Transportes 60
Lista restringida de candidatos 3:
en las condiciones anteriores, si LRC1 LRC2 = , la lista
restringida de candidatos se construye como sigue:
LRC3={R(wj, hj) LRC1 : (0 yi-1 - yi - wj 3) (0 yi-1
- yi - hj 3)}
Si LRC1 LRC3 = , tomar LRC3 = LRC1.
GRASP | Lista restringida de candidatos
Universidad de La Laguna | Experto en Logística y Transportes 61
GRASP | Postprocesamiento | Idea
Universidad de La Laguna | Experto en Logística y Transportes 62
Procedimiento de mejora: extraer los últimos k rectángulos de la solución.
Supongamos, por simplicidad, que son {R1,R2, …, Rk}. Para cada
permutación, {Ri1,Ri2
, …, Rik}, de los rectángulos:
Paso 1: Hacer j = 1. Colocar el rectángulo Rij en la posición más
profunda del objeto y con la orientación que suponga una menor altura
relativa.
Paso 2: Hacer j = j+1. Tomar el rectángulo Rij de la permutación y
empaquetarlo siguiendo el proceso anterior.
Paso 3: Si j = k, parar; en caso contrario, repetir el paso 2.
Devolver la mejor de las soluciones obtenidas con el método anterior.
GRASP | Postprocesamiento | Idea
Universidad de La Laguna | Experto en Logística y Transportes 63
GRASP 1 = Repeticiones del método constructivo escogiendo, al
azar, un elemento de LRC1
GRASP 2 = Repeticiones del método constructivo escogiendo, al
azar, un elemento de LRC2
GRASP 3 = Repeticiones del método constructivo escogiendo, al
azar, un elemento de LRC3
GRASP 4 = GRASP 2 + Postprocesamiento
GRASP 5 = GRASP 3 + Postprocesamiento
GRASP | Variantes
Universidad de La Laguna | Experto en Logística y Transportes 64
Categoría n w hopt SA + BLF GRASP1 GRASP 2 GRASP 3 GRASP 4 GRASP 5 C1 16 ó 17 20 20 20.8 22.6 22 22 21.66 21.66 0.7 0.21 0.19
C2 25 40 15 15.9 17 17 16.33 16.33 16.33 2.4 0.20 0.20
C3 28 ó 29 60 30 31.5 33.66 35.33 33.66 33.66 33.33 4 0.31 0.34
C4 49 60 60 61.8 62.66 64.33 63 63.33 63 33 0.49 0.35
C5 72 ó 73 60 90 92.7 94.33 94 93 92.66 92.33 115 0.43 0.35
C6 97 80 120 123.6 125.33 124.33 124 123 123.33 382 0.47 0.63
C7 196 ó 197 160 240 249.6 247 245 246 244.66 245 4181 0.77 0.80
GRASP | Experiencia computacional
Universidad de La Laguna | Experto en Logística y Transportes 65
OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS
Hormigas reales
Explicamos su comportamiento
¿Cómo usar lo anterior?
Etapas del procedimiento
Universidad de La Laguna | Experto en Logística y Transportes 66
OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS
La estrategia empleada por las Colonias de Hormigas para descubrir fuentes de alimentación, establecer el camino más corto entre éstas y el hormiguero y transmitir esta información al resto de sus compañeras inspiró a los investigadores Marco Dorigo, Vittorio Maniezzo y Alberto Colorni. Éstos, emulando dicha estrategia, propusieron un nuevo procedimiento de resolución de problemas que supone actualmente uno de los tópicos en los que más se investiga.
Universidad de La Laguna | Experto en Logística y Transportes 67
HORMIGAS REALES
OBSTÁCULO
OBSTÁCULO
Universidad de La Laguna | Experto en Logística y Transportes 68
HORMIGAS REALES | Algunas observaciones
Si no encuentran un rastro de feromona, se mueven aleatoriamente.
Las hormigas construyen iterativamente soluciones al problema que se les plantea e intercambian información sobre éstas para construir mejores soluciones.
La atracción que sienten por un determinado camino es proporcional a la intensidad del rastro de feromona sobre el mismo.
Universidad de La Laguna | Experto en Logística y Transportes 69
EXPLICAMOS SU COMPORTAMIENTO | Características de las hormigas artificiales
Tendrán memoria
No serán completamente ciegas.
Vivirán en un entorno discreto.
Se moverán a razón de una unidad de espacio por unidad de tiempo.
Universidad de La Laguna | Experto en Logística y Transportes 70
EXPLICAMOS SU COMPORTAMIENTO | Simulación
A
E
D
B
A
A
1
1
0.5
0.5
Inicio
A
E
D
B
A
A
30
30
15
15
15
15
t = 0
A
E
D
B
A
A
30
30
20
20
10
10
= 30
= 15
t = 1
Universidad de La Laguna | Experto en Logística y Transportes 71
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio
Sistema Hormiga: Colocar una hormiga en cada ciudad.
Cada hormiga escoge la ciudad a la que ir con una probabilidad que depende de la distancia a dicha ciudad, y del rastro de feromona presente en la arista que conecta la ciudad de origen con la ciudad destino.
Empleando la memoria de que están dotadas, las hormigas construyen circuitos legales evitando repetir ciudades previamente visitadas.
Cuando se completa un circuito, las hormigas (todas o algunas) segregan feromona sobre las aristas que han sido atravesadas.
La feromona segregada, y la que estaba presente en las aristas, se usa para actualizar el rastro de feromona en la siguiente iteración.
Universidad de La Laguna | Experto en Logística y Transportes 72
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Elementos
dij distancia entre las ciudades i y j
ij = 1/ dij inversa de la distancia entre las ciudades i y j
Sk(i) conjunto de ciudades alcanzables por la k-ésima hormiga desde la ciudad i
ij intensidad del rastro de feromona de la arista (i,j)
ijk incremento de feromona de la arista (i,j) debido a la aportación de la k-ésima
hormiga
ij incremento de feromona de la arista (i,j) debido a la aportación de todas las hormigas
Lk longitud del circuito construido por la k-ésima hormiga
c rastro inicial de cada arista (constante fijada por el usuario)
Q constante fijada por el usuario; el rastro que recibe una arista depende de este valor
parámetro fijado por el usuario; (1- ) representa la cantidad de feromona que desaparece de una arista por efecto de la evaporación
Universidad de La Laguna | Experto en Logística y Transportes 73
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio
i
j
.
.
.
(ij , ij)
(ir , ir)
(im , im)
?
m
r
Universidad de La Laguna | Experto en Logística y Transportes 74
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Pseudocódigo
Procedure Sistema Hormiga;begin Inicialización repeat for k := 1 to n do begin i := k; repeat Escoge j Sk(i); i := j; until Solución Factible; Calcula incremento del rastro; end; Actualiza(Rastro); Almacena(Mejor Solución); until (criterio de parada);end.
ij = c
(ij , ij)
ijk Lk
ij ij
k
Universidad de La Laguna | Experto en Logística y Transportes 75
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Incremento y actualización del rastro
0
kkij
L
Q
si la arista (i,j) pertenece a la solución construida por la k-ésima hormiga
en otro caso
Incremento debido a la k-ésima hormiga
n
k
kijij
1
Incremento total
ijijij
Actualización
Universidad de La Laguna | Experto en Logística y Transportes 76
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Probabilidad de transición
0
)( iSririr
ijij
k
ij
k
p
si j Sk(i)
en otro caso
Universidad de La Laguna | Experto en Logística y Transportes 77
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Un ejemplo
1 2
3
45
6
025352
201552
510225
352025
552201
225510
D
Matriz de distancias
Universidad de La Laguna | Experto en Logística y Transportes 78
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Un ejemplo
01010101010
10010101010
10100101010
10101001010
10101010010
10101010100
Matriz de feromona inicial
7.707.443.337.447.70
7.701007.447.4450
7.441007.70507.44
3.337.447.707.707.44
7.447.44507.70100
7.70507.447.44100
Matriz de probabilidad de transición
707.0447.0333.0447.0707.0
707.01447.0447.05.0
447.01707.05.0447.0
333.0447.0707.0707.0447.0
447.0447.05.0707.01
707.05.0447.0447.01
Matriz de visibilidad
Universidad de La Laguna | Experto en Logística y Transportes 79
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Un ejemplo
Probabilidades de transición1 2 3 4 5 6 Aleat. Solución
1 0.322 0.144 0.144 0.161 0.227 0.000 (1 2_ _ _ _)2 0.336 0.237 0.212 0.212 0.031 (1 2 3 _ _ _)3 0.475 0.300 0.223 0.673 (1 2 3 5 _ _)5 0.585 0.414 0.842 (1 2 3 5 6 _)6 1.00 (1 2 3 5 6 4)
Incremento del rastro1
121
231
351
561
641
41 Q Valor objetivo9.496 9.496 9.496 9.496 9.496 9.496 100 10.53
3
45
6
Hormiga 1
21
Universidad de La Laguna | Experto en Logística y Transportes 80
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio | Un ejemplo
01010101010
10010101010
10100101010
10101001010
10101010010
10101010100
054.7903.3504.1618.2373.33
003.3572.52523.25
074.2473.3399.23
04.1674.24003.3599.13
18.23573.33058.45
73.3323.2599.2399.130
79.54
35.0335.03
52.72
35.03
45.58
Matriz de feromona inicial
Matriz de feromona tras una iteración
Universidad de La Laguna | Experto en Logística y Transportes 81
ETAPAS DEL PROCEDIMIENTO
1. Inicialización: Se fija el rastro inicial
2. Fase constructiva. Se construyen soluciones al problema empleando la información que suministra el rastro de feromona y alguna función heurística de lo apropiado de una elección.
3. Cálculo del incremento del rastro. Se calcula el incremento en la intensidad del rastro.
4. Actualizar el rastro de feromona. Se calcula el nuevo rastro de feromona.
5. Criterio de parada. Si el criterio de parada se cumple, finalizar la búsqueda. En caso contrario, volver al paso 2.
Universidad de La Laguna | Experto en Logística y Transportes 82
BIBLIOGRAFÍA
METAHEURÍSTICAS:
Red Española de Metaheurísticas: heur.uv.es
GRASP:
Mauricio Resende: www.research.att.com/~mgcr/
OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS:
Marco Dorigo: iridia.ulb.ac.be/~mdorigo
Ant Colony Optimization: www.aco-metaheuristic.org