Universidad de La Laguna | Experto en Logística y Transportes 1 Experto en Logística y Transportes Módulo 4: Transporte José A. Moreno Pérez, J. Marcos

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

[email protected], [email protected]

webpages.ull.es/users/jamoreno, webpages.ull.es/users/jmmoreno

mailto:[email protected]

mailto:[email protected]


Introducción

Heurísticas

Métodos constructivos

Búsquedas por entornos

GRASP

Optimización basada en Colonias de Hormigas


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, ….


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.


PROBLEMAS

OPTIMIZAR f(x)

s.a: x S

f(), función objetivo

S, región factible o espacio solución

OPTIMIZAR, minimizar, maximizar


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)


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


HEURÍSTICAS


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


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


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.


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


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


Heurística: desde el cliente actual nos movemos al cliente más cercano que no hayamos visitado

HEURÍSTICAS | Segunda Interpretación | Ejemplo


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


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


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.


¿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.


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.


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:

http://www.antoptima.com/


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.


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


CLASIFICACIÓN


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


MÉTODOS CONSTRUCTIVOS


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.


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.


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.


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.


BÚSQUEDAS POR ENTORNOS


MOVIMIENTOS | Modificando una solución

Movimiento: modificación de una solución

Coste = 300 um

Coste = 280 um

2-intercambio de aristas



Coste = 300 um

Coste = 295 um

intercambio de almacenes



Coste = 300 um

Coste = 270 um

Reasignación de un cliente



¿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.


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


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)


Ó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.



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.



…

…


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.


BÚSQUEDA LOCAL

Coste = 300 um Coste = 280 um

Coste = 250 um


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.


Posibles localizaciones:

Puntos de demanda:

Problema de la 2-mediana con distancia euclídea

INCONVENIENTE DE UNA BÚSQUEDA LOCAL (i)


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)


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)


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


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.


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


GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES


Alternativa: GRASP

Fase constructiva

Fase de postprocesamiento

Empaquetando rectángulos con GRASP


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


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


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




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


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


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


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


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


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


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



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.




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 | Postprocesamiento | Idea


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


GRASP 1 = Repeticiones del método constructivo escogiendo, al

azar, un elemento de LRC1





GRASP 4 = GRASP 2 + Postprocesamiento

GRASP 5 = GRASP 3 + Postprocesamiento

GRASP | Variantes


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


OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS

Hormigas reales

Explicamos su comportamiento

¿Cómo usar lo anterior?

Etapas del procedimiento


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.


HORMIGAS REALES

OBSTÁCULO

OBSTÁCULO


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.


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.


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


¿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.


¿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


¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio

i

j

.

.

.

(ij , ij)

(ir , ir)

(im , im)

?

m

r


¿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


¿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


¿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


¿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



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



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



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


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.


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

http://www.research.att.com/~mgcr/

Documents

Universidad de La Laguna | Experto en Logística y Transportes 1 Experto en Logística y Transportes Módulo 4: Transporte José A. Moreno Pérez, J. Marcos