Optimización 2

Tarea 2

Felipe Magdalena Parra

Departamento de Ingeniería Industrial, Universidad de Concepción

11 de diciembre de 2020

1. Metaheurística Propuesta

En el Algoritmo 1, se propone la metaheurística Iterated Local Search (ILS), a la cual se le realizan modificaciones. Para efectos de resolución de éste problema, ella consta de cuatro componentes: solución inicial (línea 1), una estrategia de búsqueda local (líneas 2 y 6), una estrategia de perturbación (línea 5), y un criterio de aceptación (línea 8). El algoritmo contempla la solución inicial obtenida (s*), y la solución que se obtiene al perturbar y posteriomente aplicar la heurística 2-OPT (s_1). En las siguientes subsecciones se presentan con mas detalles la representación, función objetivo, solución inicial, estrategia de búsqueda local, estrategia de perturbación , criterio de aceptación y parámetros.

Algorithm 1 Iterated Local Search (modificado)

[pic 1][pic 2]

1. s ← vcm_densidades_y_acortar ( )

1. s ← heuristica_2OPT (s)

1. s* ← s

1. for i ← 0 hasta cantidad de iteraciones do

1. s_1 ← perturbacion (s*)

1. s_1 ← heuristica_2OPT (s_1 )

1. if f(s_1) < f(s*) then

8:        if criterio de aceptacion (f(s_1) − f(s∗) ≤ f(s∗) ∗ −0, 00001 : s_1, s∗) se cumple then

1. s* ← s_1

1. end if
2. end if

1. end for

[pic 3]

1.1.        Representación

La representación usada es la de permutación, donde la solución viene dada por s = {v1, v2, ..., vn} . Se tiene que v1 = vn = 0, mientras que los demás vértices corresponden a instalaciones que forman parte de la solución.

1.2.        Función objetivo

Se utiliza la suma de las distancias euclidianas entre nodos (ya sea entre dos nodos de instalaciones diferentes, o entre un nodo de instalación y el nodo de depósito). Lo anterior se detalla en la ecuación 1.

i=1

1

1.3.        Solución inicial

Siguiendo la lógica del vecino más cercano, se considerarán las densidades de cada uno de los eventuales nodos de destino en el proceso de construcción de la solución. Esto es, para cada uno de ellos, se calcula el cociente entre la cantidad de clientes que eventualmente pueda abastecer y la distancia que existe entre dicho nodo y el último nodo agregado a la solución actual. Así, se selecciona el nodo de instalación con mayor densidad, y se agrega a la solución actual. El proceso se detiene cuando al agregar algún nodo de instalación a la solución actual, la cantidad recolectada de beneficio se vuelve mayor o igual a la cantidad mínima solicitada (P). Luego, se procede a verificar si es posible eliminar algún nodo de instalación de dicha solución, manteniendo la condición de beneficio mínimo (P). Todo el procedimiento anterior se presenta en el Algoritmo 2.

Algorithm 2 vcm_densidades_y_acortar

[pic 4][pic 5]

Entrada: I : instalaciones, C : clientes, P: beneficio mínimo, B: posibles conexiones entre instalaciones y

clientes, dij: costos de las aristas

Salida: Ruta

1. S ← φ

1. Q ← len(φ ∪ I)
2. Se crea una lista L donde se incorporan los clientes que se van beneficiando.
3. Se crea una lista A que contiene, para cada instalación, todos los clientes a los cuales puede abastecer (según los datos de cada instancia).

1. Se crea una lista F , que contiene la cantidad de beneficio que aporta cada instalación que va agregándose a la solución.
2. while len(S) < Q do

1. if len(L) ≥ P then

1. break
2. end if

1. Se crea una lista (o se vacía y luego vuelve a llenarse) E que contiene, para cada instalación, los clientes a los cuales puede abastecer y que no han sido beneficiados.
2. Se crea una lista (o se vacía y luego vuelve a llenarse) D que contiene, para cada instalación, el cociente entre la cantidad de clientes que puede abastecer (y que no han sido beneficiados) y la distancia entre dicha instalación y el último nodo agregado a la solución.

1. maximo ← max D

1. ubicacion ← D index maximo

1. U BICACION ← ubicacion + 1

1. quantity ← 0

1. for i in A[U BICACION] do
2. if i not in L then

1. L ← L append i

1. quantity ← quantity + 1

1. if len(L) ≥ P then

1. break
2. end if

1. end if

1. end for

1. F ← F append quantity

1. S ← S ∪ {UBICACION}
2. end while

1. S←S∪{φ}
2. Se crea una lista G, que contiene a todos los clientes que se han beneficiado.
3. exceso ← len(G) − sum(F )

1. F [−1] ← F [−1] + exceso

1. En base a lo anterior, se recorre la lista F para verificar si es posible eliminar una instalación de la solución, tal que la condición de beneficio mínimo siga cumpliéndose.

[pic 6]

2

1.4.        Estrategia de búsqueda local

Se aplica la heurística 2 - OPT, la cual recibe una solución y en base a ella, recorre iterativamente las aristas y va intercambiando pares sucesivos de ellas en la ruta. Para lo anterior, se toman dos aristas sucesivas y se calcula la suma de las distancias asociadas a cada una. Enseguida, se intercambian de posición el nodo de llegada de la primera arista en cuestión con el nodo de entrada de la segunda arista en cuestión, y se calcula la suma de las distancias asociadas a estas nuevas aristas. Si la suma de las distancias asociadas a estas nuevas aristas es menor a la suma de las distancias asociadas a las aristas iniciales, entonces estos cambios se guardan en otras variables auxiliares, puesto que el algoritmo a medida que recorre las aristas en forma iterativa, busca la mejor opción de intercambio de aristas de manera de reducir lo más posible el costo total de la ruta. Si al final del proceso, efectivamente se detecta una posibilidad de mejora en la solución, entonces se aplica la modificación de posiciones de nodos en la ruta. De lo contrario, el algoritmo simplemente devuelve la solución inicial que recibió como parámetro. El procedimiento anterior es descrito en el Algoritmo 3.

...