•

Urango-Narváez, Hernández-Riaño y López-Pereira / INGE CUC, vol. 16 no. 1 pp. 53-66. Enero - Junio, 2020

Un Método Metaheurístico para resolver el problema de Distribución de Instalaciones de Áreas Desiguales y Dimensiones Fijas

A metaheuristic method to solve the Unequal Area Facility Layout Problem

DOI: http://doi.org/10.17981/ingecuc.16.1.2020.04

Artículo de Investigación Científica. Fecha de Recepción: 15/03/2019. Fecha de Aceptación: 02/09/2019

Wilmer Urango-Narváez

Universidad de Córdoba. Montería (Colombia)

wurangonarvaez86@correo.unicordoba.edu.co

Helman Hernández-Riaño

Universidad de Córdoba. Montería (Colombia)

hhernandez@correo.unicordoba.edu.co

Jorge López-Pereira

Universidad de Córdoba. Montería (Colombia)

jotalopez@correo.unicordoba.edu.co

.

Para citar este artículo:

W. UrangoNarváez, L. H. Hernández-Riaño y J. López-Pereira, “Aplicación de la Búsqueda Armónica para el problema de formación de celdas de manufactura”, INGE CUC, vol. 16, no. 1, pp. 53-63, 2020. DOI: http://doi.org/10.17981/ingecuc.16.1.2020.04

.

Resumen

Introducción− El Problema de Distribución de Instalaciones de Áreas Desiguales y Dimensiones Fijas (UA-FLP), es un problema de optimización combinatoria no lineal, bien conocido por buscar la mejor ordenación de estaciones de trabajo que poseen áreas y/o dimensiones distintas; estudios recientes muestran métodos aproximados, como metaheurísticas, para resolver este tipo de problemas, o en su defecto muestran innovación en la modelación matemática del mismo. Cabe resaltar que el efecto de los decodificadores como variable del problema no había sido analizada hasta este momento.

Objetivo− Determinar si existe diferencia significativa en la calidad de la solución ofrecida por cada una de las combinaciones Metaheurística-Decodificador.

Metodología− Se propusieron dos metaheurísticas, un Algoritmo Genético Básico y un algoritmo llamado N2; al igual que dos decodificadores: el decodificador en Espiral y el decodificador en Abanico. Posteriormente se realizó un experimento simple cuyo factor experimental fue la combinación Meta­heurística-Decodificador y la variable dependiente fue la función objetivo del problema analizado.

Resultados− El diseño experimental mostró que la combinación, metaheurística N2 y decodificador en Espiral ofrecen los resultados de mejor calidad.

Conclusiones− Existe diferencia significativa en la combinación Metaheurística-Decodificador. En específico se puede afirmar que, para el problema en cuestión, la metaheurística N2 es más eficiente que el Algoritmo Genético Básico. Añadido a esto, también se puede concluir una gran influencia de los decodificadores a la hora de resolver un UA-FLP.

Palabras clave− Problema de Distribución de Instalaciones; Algoritmo Genético; algoritmo N2; decodificador; metaheurística; optimización.

Abstract

Introduction− The Unequal Area Facility Layout Problem (UA-FLP), is a problem of combinatory optimization no lineal, well known for looking for the best ordination of stations work that possess areas and/or distinct dimensions; recent studios show approximate methods, like metaheuristics, to resolve this type of problems, or in his defect show innovation in the modelacion mathematical of the same. Fits to highlight that the effect of the decoders like variable of the problem had not been analyzed until this moment.

Objective− Determine if it existed significant difference in the quality of the solution offered by each one of the combinations Metaheuristic-Decoder.

Methodology− They proposed two metaheuristics, a Basic genetic algorithm and an algorithm called N2, to the equal that two decoders: the Decoder in spiral and the Decoder in blower, later realized a simple experiment whose experimental factor was the combination Metaheuristic-Decoder and the dependent variable was the objective function of the problem analyzed.

Results− The experimental design showed that the combination, metaheuristic N2 and Decoder in spiral offer better quality results.

Conclusions− It exists significant difference in the combination Metaheuristic- Decoder. In specific can affirm that for the problem in question, the metaheuristic N2 is more efficient than the Basic Genetic Algorithm. Added to this, also can conclude that the decoders have big influence on the hour to resolve an UA-FLP.

Keywords− Facility Layout Problem; Genetic Algorithm; N2 Algorithm; Decoder; Metaheuristic; Optimization.

I. Introducción

El Problema de Distribución de Instalaciones (FLP, por sus siglas en inglés Facility Layout Problem), es un problema de optimización combinatoria no lineal, bien conocido por buscar la mejor ordenación de estaciones de trabajo, maquinas, o cualquier otro tipo de recurso en un dominio delimitado de terreno, sin que exista solapamiento, esto con el fin de minimizar los costos de manejo y flujo de materiales, mejorando así la productividad y plazos de entrega [1]. Es muy utilizado en áreas de la Ingeniería Industrial y Logística considerando que los costos de transporte entre estaciones de trabajo son responsables del 20 al 50% de todos los gastos de la producción [2]. Esta última afirmación es una de las justificaciones del presente trabajo de investigación, ya que con la optimización de la distribución de los recursos de trabajo se estarían disminuyendo en gran proporción los costes de producción dentro de las organizaciones; cabe resaltar que la investigación también tiene gran valor debido a que se esta analizando un aspecto de este problema poco estudiado, lo que otorga novedad al presente estudio.

Este trabajo aborda un caso específico de los FLP, como es el Problema de Distribución de Instalaciones de Áreas Desiguales y Dimensiones Fijas (UA-FLP), siendo este una versión más compleja que la versión original, aunque busca los mismos objetivos, pero tiene en cuenta una restricción adicional la cual consiste en tener por lo menos un par de “tipos de recurso” diferentes en áreas y/o dimensiones y dichas dimensiones son inmodificables [3].

En la actualidad se ha optado por resolver este tipo de problemas mediante métodos metaheurísticos debido a los buenos resultados que estos ofrecen en un tiempo de ejecución aceptable [4]. Dentro de estos métodos se pueden resaltar los expuestos a continuación.

En primer lugar se menciona los Algoritmos Genéticos (GA), que han demostrado ser una de las mejores metodologías de resolución para este tipo de problemas, un claro ejemplo lo muestra el algoritmo Genético de clave Aleatoria con un Modelo de Isla (IMGA, del inglés Island Model Genetic Algorithm) y una novedosa forma de ubicar las estaciones de trabajo (decodificador), propuesta que logro encontrar buenas soluciones en comparación con resultados hallados anteriormente en la literatura [5]. Por otra parte, existen trabajos que muestran un tipo de IMGA, capaz de encontrar buenas soluciones para problemas de gran tamaño en un tiempo de cómputo aceptable, esto mediante la evolución paralela de varias poblaciones que mantiene su diversidad y logra alcanzar resultados de mejor calidad en menos generaciones [4]. Otro enfoque de GA propone un Algoritmo Genético Básico (BGA) y un GA con restricciones de cuadrantes y fases de descomposición (DRQGA); en este estudio se logró demostrar la eficiencia de ambas propuestas, en donde la restricción principal del DRQGA se basa en que las estaciones de trabajo no pueden cruzar el eje X o Y, y utiliza este método para encontrar soluciones de mejor calidad durante la fase de descomposición[2].

En segundo lugar se pueden mencionar el Optimizador de Enjambre de Partículas (PSO, del inglés Particle Swarm Optimization), el cual en ciertos trabajos ofrece resultados de buena calidad, mediante la obtención de un frente de Pareto que otorga al tomador de decisión una flexibilidad para elegir las opciones más convenientes [6]. Todo esto lo hace mediante una propuesta de un PSO Multiobjetivo (MOPSO, de sus siglas en ingles Multi-Objective Particle Swarm Optimization), en el cual propone un Método de División de Espacios (OSD, por sus siglas en inglés Objective Space Division) para mejorar los efectos de la metodología propuesta por los autores.

En tercer lugar se encuentra el Recocido Simulado (SA), el cual se basa en el recocido físico de los sólidos [7]. Un claro ejemplo de esta metodología propone además de una nueva Modelación Matemática No Lineal de Enteros Mixtos (MINLP), una metaheurística de recocido simulada con una heurística de arranque múltiple que ayuda a encontrar mejores resultados debido a su buen mecanismo de exploración. Este trabajo logro resultados de mejor calidad en comparación con los conjuntos de instancias seleccionadas para ese estudio [8].

Por último, se alcanza a mencionar el Ant System o Sistema de Hormigas, un algoritmo relativamente joven que ha demostrado ofrecer buenos resultados [9]; el cual propone este algoritmo con varios métodos de búsqueda local y un decodificador de árbol de corte para resolver el UA-FLP. Esta propuesta es bastante robusta y alcanza a mejorar el resultado de algunas de las instancias tomadas de la literatura, por tal motivo puede considerarse como buen candidato para resolver este tipo de problemas.

Por otra parte, se encuentra la metaheurística propuesta N2, ya implementada [10]. La aplicación inicial de este algoritmo está dirigida un Problema de Enrutamiento de Vehículos Capacitados para Productos Perecederos. Esta propuesta mezcla diferentes algoritmos tales como, la optimización por enjambre de partículas, algoritmo cromático y la búsqueda tabú. El resultado de esta hibridación muestra la potencia que resulta al extraer las mejores características de cada algoritmo, sorprendentemente los resultados de esta propuesta superaron los resultados de un set de instancias bien conocidas encontradas en la literatura. Cabe resaltar que hasta la fecha no se tiene evidencia de la implementación de esta metaheurística a un problema de Distribución de Instalaciones de Áreas Desiguales y Dimensiones Fijas.

Añadido a lo anterior, un tema importante a mencionar en este trabajo es el efecto de los decodificadores en la calidad del resultado, los cuales hasta el momento solo algunos han realizado esta investigación, la cual demuestra que los decodificadores tienen gran influencia en el proceso de encontrar buenas soluciones para un problema de UA-FLP [11]. Lo anterior se demuestra utilizando un algoritmo genético Básico y dos decodificadores distintos, y en efecto los resultados para las mismas instancias seleccionadas bajo el mismo algoritmo tenían un margen de diferencia estadísticamente aceptable, demostrando así que los decodificadores influyen en resultado de ese problema.

También se puede mencionar como la presente investigación busca demostrar el potencial del algoritmo N2 y el efecto de las combinaciones resultantes, Metaheurística-Decodificador sobre la calidad de la solución.

II. Metodología

Para comprobar la eficiencia de la metaheurística propuesta fue necesario compararlo con otro ya existente que ofreciera buenos resultados para un problema de UA-FLP, por tal razón se escogió un Algoritmo Genético Básico para realizar dicha comparación. Añadido a lo anterior también se tuvo en cuenta el efecto de los decodificadores en las soluciones obtenidas. Con base en los antecedentes se quiere demostrar el potencial del algoritmo N2 y del efecto de las combinaciones resultantes del Metaheurística-Decodificador sobre la calidad de la solución. El procedimiento utilizado para alcanzar el objetivo propuesto se describe en esta sección.

A. Modelo Matemático

Para el estudio se utiliza el modelo matemático (1), el cual plantea una función multiobjetivo conformada por la minimización del costo de flujo de materiales entre estaciones, y la minimización de las relaciones de cercanía entre las mismas [12].

El costo entre el flujo de materiales está definido por (1):

Dónde i y j representan el conjunto de estaciones; n es el número de estaciones a ubicar; d(i, j) representa la distancia rectilínea entre los centroides de la estación i y la estación j; f(i, j) representa la cantidad de flujo de materiales entre las estaciones i y j; c(i, j) representa el costo unitario por unidad de distancia por cantidad de flujo entre la estación i y la estación j.

Por otro lado, se muestra (2), la cual representa la relación lógica entre estaciones, relaciones de cercanía:

Dónde: REL (i, j) representa la relación lógica entre las estaciones ir.

Cabe resaltar que la relación de cercanía establecida es independiente del flujo de materiales y dependen solo y únicamente de la relación lógica entre cada par de estaciones ij. Los posibles valores de dichas relaciones fueron establecidos por otra investigación [12], y estos valores se visualizan en la Tabla 1:

Tabla 1. Relaciones de cercanía.

Tipo de Relación	Valor Asignado
Relaciones esenciales	410
Relaciones muy importantes	130
Relaciones importantes	50
Relaciones normales	30
Relaciones indiferentes	10
Relaciones indeseables	0

Fuente: [12].

Hasta el momento, en la literatura no existen problemas en los cuales se combine (1) y (2), por tanto, las relaciones de cercanía se implantaron de manera aleatoria, donde cada valor tiene la misma probabilidad de ocurrencia.

Continuando con la misma idea, se muestran (1) y (2) ya unidas en una sola (3):

Dónde: α es un factor de ponderación que varía entre los valores de 0 a 1; y Z es el valor de la función objetivo que se quiere minimizar.

Por otro lado, las distancias entre los centroides fueron medidas con el sistema de Manhattan (4):

Las ecuaciones que restringen las distancias en mención son (5), (6), (7), (8) y (9):

Donde:

h(i): Medida del alto de la estación i.

p(j): Variable binaria. Toma el valor de 0 cuando la dimensión en x de la estación i es igual al ancho w(i) y el valor de 1 cuando la dimensión en x de la estación i es igual al alto h(i).

dx(i, j): Es la distancia horizontal que existe entre los centroides de las estaciones i y j.

dy(i, j): Es la distancia vertical que existe entre los centroides de las estaciones i y j.

X(i): Es la coordenada en X del punto inferior izquierdo de la estación i.

Y(i): Es la coordenada en Y del punto inferior izquierdo de la estación i.

Ahora las restricciones que controlan el solapamiento entre estaciones son las siguientes (10), (11), (12), (13) y (14):

Donde:

B: Es definida como una constante muy grande y es igual a la sumatoria del máximo entre el ancho y el alto de las estaciones.

L(i, j): Es una variable binaria que toma el valor de 1 cuando la instalación i está a la derecha de la instalación j y 0 en caso contrario.

M(i, j): Es una variable binaria que toma el valor de 1 cuando la instalación i está por encima de la instalación j y 0 en caso contrario.

Q(i, j): Es una variable binaria que toma el valor de 1 cuando la instalación i está a la izquierda de la instalación j y 0 en caso contrario.

T(i, j): Es una variable binaria que toma el valor de 1 cuando la instalación i está por debajo de la instalación j y 0 en caso contrario.

Las ecuaciones (1) y (2) representan las dos funciones objetivo analizadas en el problema, minimizar el costo de flujo de materiales y minimizar las relaciones de cercanía respectivamente. La ecuación (3) representa la suma ponderada de las dos funciones objetivo mencionadas. La ecuación (4) representa el cálculo de la distancia rectilínea entre cada par de estaciones. Las restricciones (5) y (6) hallan la distancia rectilínea horizontal entre los centroides de cada par de estaciones. Las restricciones (7) y (8) hallan la distancia rectilínea vertical entre los centroides de cada par de estaciones. Por ultimo, las restricciones (10), (11), (12), (13) y (14) se encargan de que no exista solapamiento o superposición entre las estaciones de trabajo ni que estas se salgan del dominio de ubicación.

B. Decodificadores

Llamaremos decodificador a toda técnica de acomodamiento espacial utilizada para organizar estaciones de trabajo dentro de un dominio de ubicación disponible.

En trabajos anteriores, se explica a detalle el decodificador en Espiral y decodificador en Abanico, que son los utilizados en esta investigación y la importancia de estos en los resultados finales [11] .

Dicho trabajo afirma que el decodificador en Espiral ubica la primera estación de trabajo en el centro del dominio de ubicación y con respecto a esta, ubica el resto de las estaciones de trabajo llevando un patrón que simula la forma de una espiral, el procedimiento completo de este proceso se evidencia la Fig. 1 y la Fig. 2 donde muestra una forma más clara y sencilla del comportamiento de este decodificador.

Fig. 1. Decodificador en Espiral.

Fuente: Autores.

Fig. 2. Ilustración del decodificador en Espiral.

Fuente: [11].

Por otro lado, el decodificador en Abanico ubica la primera estación de trabajo en la esquina inferior izquierda del dominio de ubicación y el resto de las estaciones se localizan alrededor de los costados que quedan disponibles (arriba, derecha) simulando el movimiento de un abanico, el proceso completo puede observarse en la Fig. 3 y se ilustra en la Fig. 4.

Fig. 3. Decodificador en Abanico.

Fuente: [11].

Fig. 4. Ilustración del decodificador en Abanico.

Fuente: Autores.

C. Instancias

Como se mencionó inicialmente, se escogieron ocho instancias de la literatura para este estudio. Dichas instancias van desde 15 hasta 49 estaciones de trabajo con sus respectivas referencias, y son mostradas en la Tabla 2. Se escogieron dichas instancias por sus características, ya que sus dimensiones estaban dadas en la modalidad ancho por alto. Además, estaban propuestas las cantidades de los flujos de materiales entre las estaciones.

Tabla 2. Referencias de las instancias.

Nombre Instancia	Tamaño (número de estaciones)	Fuente
1(18)	18	[13]
2(36)	36
4(49)	49	[12]
3(33)	33
5(40)	40	[14]
6(15)	15
7(20)	20
8(30)	30

Fuente: Adaptado a partir de [13], [12] y [14].

Cabe resaltar que en la literatura aún no se encuentran instancias en las cuales estén de manera simultánea los datos de relaciones de cercanía, costo de flujo de materiales y dimensiones de las estaciones de trabajo, por lo tanto, los datos faltantes (Relaciones de Cercanía y Costo de Flujo de Materiales) fueron propuestos por los autores de este trabajo.

En ese orden de ideas, las relaciones de cercanía se hallaron con la ayuda de la función randsample de la biblioteca de Matlab; esta función escoge de manera aleatoria elementos de un vector, teniendo cada elemento la misma probabilidad de ser seleccionado. Para este caso, dichos elementos son los valores mostrados en la Tabla 1 (para cada par de estaciones ij se seleccionó de manera aleatoria un valor de la Tabla 1) y dicho valor se asignó a la relación de cercanía entre las estaciones ij. Cabe resaltar que los valores hallados se restringieron de tal manera que formaran una matriz simétrica al final.

Por otro lado, los costos de flujo de materiales de cada par de estaciones de trabajo se hallaron con la distribución uniforme, colocando un valor mínimo de 5 y un valor máximo de 50. En este caso, los valores de las combinaciones reciprocas (reprocesos) a cada combinación de estaciones halladas, se les multiplico por un porcentaje aleatorio. Por ejemplo, si el costo de transportar un material de la estación “A” a la estación “B” es de 50 US, entonces el costo de transportar ese mismo material de la estación “B” a la estación “A” es de 50*(0,35) US, donde 0,35 es un porcentaje aleatorio.

D. Experimentos computacionales

Se optó por realizar un experimento simple cuyo factor experimental fue la combinación Metaheurística-Decodificador y la variables dependientes fueron los diferentes resultados arrojados por la función objetivo de cada iteración, cuyos valores fueron hallados por medio de (3).

Antes de realizar el experimento se buscó determinar los parámetros adecuados para utilizar la metaheurística N2, y para ello se realizó un experimento factorial el cual consistió en definir varias combinaciones de los parámetros óptimos originales [10]. Para esto se asignaron valores por encima y por debajo de los óptimos, donde cabe resaltar que los valores óptimos originales no garantizan que sean los parámetros óptimos para el UA-FLP (Tabla 3).

Tabla 3. Valores propuestos para los parámetros del algoritmo N2 en UA.FLP.

NgenN	N	ABRAM	T	PRAM
1000	5	50	10	0,05
1500	10	100	30	0,07
2000	20	150	40	0,1

Fuente: Autores.

Donde:

NgenN: Es el número de partículas que se general de manera aleatoria, tener en cuenta que por cada corrida de tamaño NgenN se selecciona solo la mejor partícula.

N: Es el numero de veces que se ejecuta el parámetro NgenN.

ABRAM: Es el número de iteraciones antes de un arranque múltiple.

T: Es el número de iteraciones donde no se va a realizar un intercambio, a partir de un intercambio realizado.

PRAM: Es el porcentaje de vecinos que se va a visitar luego de realizarse un movimiento.

Posteriormente se corrieron 5 réplicas para cada combinación posible de los parámetros de la Tabla 3 con un tiempo de ejecución de 30 minutos, para lo cual se escogió la instancia de mayor tamaño debido a su complejidad a la hora de resolverse. Al final se escogieron los parámetros que alcanzaron el costo más bajo para la función objetivo (3). Los parámetros óptimos para el UA-FLP analizado se muestran en la Tabla 4.

Tabla 4. Parámetros de N2 para el UA-FLP.

NgenN	N	ABRAM	T	PRAM
2000	10	50	40	0,07

Fuente: Autores.

De manera paralela, se escogieron los parámetros utilizados para el Algoritmo Genético Básico con una probabilidad de cruce del 95% y una probabilidad de mutación del 5%, se escogieron estos valores ya que en la literatura se afirma que son los adecuados para este tipo de problemas [4].

Posteriormente, se buscó determinar para cada una de las instancias, un factor que equilibrara la proporción del valor de cada función objetivo (F1, F2), esto con el fin de normalizar el resultado y obtener una mayor precisión en el análisis.

Para encontrar dichos factores, se tuvo que determinar el número de replicas para realizar la corrida, para ello se escogió el método de muestreo con base en las curvas de operación característica presentado en Montgomery (2004) [15]. El método consiste en determinar un número de réplicas que permita generar un alto grado de potencia para el diseño experimental, y así darle una mayor confiabilidad al estudio (15).

Donde:

a: Numero de niveles, que para este caso es 4.

D: Variación de la variable de respuesta, en la cual, a partir de las n réplicas se considera que habrá diferencias significativas. Por tanto, se establece que a partir del 5% del valor de la media (0,05 t̅), se considerarían diferencias significativas.

σ2: Estimación de la varianza.

Para determinar el numero de replicas se seleccionó una metaheurística (Algoritmo Genético Básico), una instancia 1(18) y se fijo un tiempo de 30 minutos para cada replica. Obteniendo unos resultados como se muestra en la Tabla 5.

Tabla 5. Resultados de las curvas de operación característica.

N	Ф2	Ф	v1	v2	Beta	Alpha
1	2,1898	1,4798	3	0	-	-
2	4,3796	2,0927	3	3	0,320	0,680
3	6,5694	2,5630	3	6	0,150	0,850
4	8,7592	2,9596	3	9	0,015	0,985
5	10,9490	3,3089	3	12	0	1

Fuente: Autores.

Cuando el valor de Alpha en la Tabla 5 supera el 90% se dice que el valor de n correspondiente representa un numero de replicas adecuado.

Ahora, para encontrar el valor de los factores se realizaron 5 réplicas por instancia, ya que cumple con la condición, con los dos decodificadores y se escogió al azar una meta­heurística, que para este caso fue el Algoritmo Genético Básico. Al final se promediaron las diferencias que existían entre los valores encontrados (FO) por cada replica para cada una de las instancias (Tabla 6).

Tabla 6. Factores de Normalización.

Instancia	A1	A2
1(18)	4,36719977	1
2(36)	163,499439	1
4(49)	101,276274	1
3(33)	89,001325	1
5(40)	1	5,19994484
6(15)	1	5,49771129
7(20)	1	5,54888294
8(30)	1	6,46630228

Fuente: Autores.

En la Tabla 6 el valor de A1 es el factor de la función F1 y A2 es el factor de la función F2.

Consecutivamente, se realizaron 21 corridas, dentro de cada corrida de se efectuaron 5 réplicas por cada instancia por cada combinación Metaheurística-Decodificador, en cada corrida se cambió el valor de α entre 0 y 1, en una variación de 0,05.

III. Resultados

Una vez obtenidos los resultados se procedió a realizar la prueba no paramétrica de medianas de Mood, se escogió esta prueba ya que los residuos de los resultados analizados en la ANOVA no cumplieron los supuestos de normalidad. Los resultados obtenidos se muestran en la Tabla 7 y Fig. 5. Cabe resaltar que antes de realizar el análisis estadístico se normalizaron todos los resultados obtenidos mediante la fórmula z = (x – u)/σ, esto con el fin de que todos los datos de las diferentes combinaciones Metaheurística-Decodificador tuvieran una distribución semejante, lo cual es conveniente a la hora de aplicar la prueba no paramétrica de Mood.

Tabla 7. Resumen de los resultados de la tabla de Mood.

Total n = 3360
Gran mediana = 0,0748762
Factor	Tamaño de la Muestra	n < =	n >	Mediana	LC inferior 95,0%	LC superior 95,0%
Genético-Abanico	840	203	637	0,808186	0,746502	0,871404
Genético-Espiral	840	541	299	-0,289143	-0,378361	-0,177309
N2-Abanico	840	265	575	0,559571	0,501687	0,626725
N2-Espiral	840	671	169	-0,556804	-0,632938	-0,496385
Estadístico = 708,362 Valor-P = 0,0

Fuente: Autores.

Fig. 5. Gráfico de Caja y Bigotes para las combinaciones Metaheurística-Decodificador.

Fuente: Autores.

Además, para cada una de las corridas del experimento se utilizó el software MATLAB R2015-B con un tiempo límite de 15 minutos para cada una de las réplicas. Esto se realizado en una computadora con procesador Intel(R) Xeon(R) CPU E3-1225 v5, de 8GB RAM y con sistema operativo Windows 10 Pro de 64 bits.

La prueba de medianas de Mood evalúa la hipótesis de que las medianas de las 4 combinaciones Metaheurística-Decodificador son iguales, esto lo realiza contando el número de observaciones en cada muestra a cada lado de la mediana global, la cual para este caso es igual a 0,0748762. Como puede observarse en la Tabla 7, el Valor-p es igual a 0,0 el cual es menor a 0,05 por lo que se puede afirmar que las medianas de las 4 combinaciones son significativamente diferentes, con un nivel de confianza del 95%, en otras palabras, las combinaciones analizadas tienen una influencia estadísticamente aceptable en el resultado del problema UA-FLP analizado. Además de esto, se puede afirmar que los resultados de mejor calidad los ofrece la combinación N2-Decodificador en Espiral, ya que según la Fig. 5, esta tiene la mediana ubicada más a la izquierda, lo que significa que ofrece resultados menores, en comparación con las demás combinaciones. Cabe resaltar que la afirmación anterior tiene validez debido a que los intervalos mostrados en la tabla no se intersecan entre sí.

Siguiendo la lógica anterior, la combinación Genético-Decodificador en Espiral queda en segundo lugar, la combinación N2-Decodificador en Abanico queda en tercer lugar, y deja en último lugar la combinación Genético-Decodificador en Abanico.

Un ejemplo gráfico de la afirmación anterior se muestra en las Fig. 6, Fig. 7, Fig. 8, y Fig. 9, las cuales representan el orden de las combinaciones anteriormente mencionadas para la instancia 4(49). Y la parte cuantitativa de estos resultados se observa en la Tabla 8.

Tabla 8. Resultados cuantitativos para la instancia 4(49).

Instancia 4(49)
Figura	F.O.	f1	f2
6	53420779,0981	10822099,0981	42598680,0
7	54490281,5192	54490281,5192	0
8	55211924,1229	2853823,62298	52358100,5
9	55970370,0000	0	55970370,0

Fuente: Autores.

Fig. 6. Grafica de la instancia 4(49) resuelta con la combinación N2-Decodificador en Espiral.

Fuente: Autores.

Fig. 7. Grafica de la instancia 4(49) resuelta con la combinación Genético-Decodificador en Espiral.

Fuente: Autores.

Fig. 8. Grafica de la instancia 4(49) resuelta con la combinación N2-Decodificador en Abanico.

Fuente: Autores.

Fig. 9. Grafica de la instancia 4(49) resuelta con la combinación Genético -Decodificador en Abanico.

Fuente: Autores.

IV. Conclusiones

Hasta el momento no se había aplicado la metaheurística N2 al problema de Distribución de Instalaciones de Áreas Desiguales y Dimensiones Fijas, de igual manera no se había tenido en cuenta, paralelamente, la influencia de los decodificadores en la calidad de los resultados. Por tal motivo este trabajo se enfocó en esta parte nunca explorada en la literatura científica, en ese orden de ideas se presenta las siguientes conclusiones.

En primer lugar, como resultado del análisis de la Tabla 7 y de la Fig. 5, cumpliendo con el objetivo propuesto, se logra demostrar la significancia estadística que posee la correcta elección tanto de la metaheurística como del decodificador a la hora de resolver un problema de UA-FLP, en efecto se puede afirmar que la combinación entre las metaheurísticas y los decodificadores seleccionados poseen una diferencia significativa al momento de resolver un problema de UA-FLP. Esto nos lleva a confirmar que es necesario tener en cuenta este aspecto a la hora de resolver este tipo de problema si se quieren encontrar buenos resultados.

En segundo lugar, se puede afirmar que el algoritmo N2 propuesto ha alcanzado los mejores resultados para todas las instancias analizadas con la ayuda del decodificador en Espiral. Dicha combinación encontró los valores mínimos en comparación con los resultados obtenidos por las demás combinaciones, y por ello se puede decir que el algoritmo N2 es una meta­heurística que brinda soluciones de buena calidad para resolver un problema de UA-FLP.

En tercer lugar y, por último, se obtuvo un resultado inesperado, el cual demuestra que el decodificador tiene un efecto más relevante que la metaheurística en el resultado alcanzado para cada instancia resuelta, ya que, en todos los casos, las dos mejores soluciones siempre las ofrece el mismo decodificador y no la misma metaheurística, por tanto, se puede decir que la selección del decodificador para un UA-FLP tiene más importancia que la selección del método de solución. Se aclara que ambas son importantes a la hora de resolver el problema, que de hecho es la primera conclusión, pero eso no opaca que el decodificador tiene una gran influencia en la solución.

Con la culminación de este trabajo, se propone para estudios futuros el manejo de estaciones de trabajo con dimensiones dinámicas en las cuales el algoritmo que se proponga sea capaz de encontrar las dimensiones óptimas para cada una de las estaciones de trabajo, además de esto se desea que dicho algoritmo pueda reducir el tiempo de cálculo para instancias de gran tamaño. Y en el mismo sentido, también se propone como trabajo futuro tener en cuenta otro tipo de funciones objetivos, por ejemplo, la calidad de la distribución resultante para una instancia dada.

Financiamiento

Artículo de investigación científica derivado del proyecto de investigación “Diseño de un modelo para la solución del Problema de Localización y Ruteo de Vehículos para distribución de Productos Perecederos de Consumo Masivo considerando Flota Propia y Sub­contratada”, financiado por “Universidad de Córdoba”. Año de inicio: 2018, año de finalización: 2019.

Agradecimientos

A la participación y trabajo realizado con anterioridad sobre la programación y adaptación de su metaheurística [10] al problema en cuestión de esta investigación.

Referencias

[1] H. Neghabi, K. Eshghi and M. H. Salmani, “A new model for robust facility layout problem,” Inf. Sci. (Ny)., vol. 278, pp. 498–509, Sep. 2014. https://doi.org/10.1016/j.ins.2014.03.067

[2] F. G. Paes, A. A. Pessoa and T. Vidal, “A hybrid genetic algorithm with decomposition phases for the Unequal Area Facility Layout Problem,” Eur. J. Oper. Res., vol. 256, no. 3, pp. 742–756, Feb. 2017. https://doi.org/10.1016/j.ejor.2016.07.022

[3] G. C. Armour and E. S. Buffa, “A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities,” Manage. Sci., vol. 9, no. 2, pp. 294–309, Jan. 1963. https://doi.org/10.1287/mnsc.9.2.294

[4] J. M. Palomo-Romero, L. Salas-Morera and L. García-Hernández, “An island model genetic algorithm for unequal area facility layout problems,” Expert Syst. Appl., vol. 68, pp. 151–162, Feb. 2017. https://doi.org/10.1016/j.eswa.2016.10.004

[5] J. F. Gonçalves and M. G. C. Resende, “A biased random-key genetic algorithm for the unequal area facility layout problem,” Eur. J. Oper. Res., vol. 246, no. 1, pp. 86–107, Oct. 2015. https://doi.org/10.1016/j.ejor.2015.04.029

[6] J. Liu, H. Zhang, K. He and S. Jiang, “Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem,” Expert Syst. Appl., vol. 102, pp. 179–192, Jul. 2018. https://doi.org/10.1016/j.eswa.2018.02.035

[7] R. Şahin, “A simulated annealing algorithm for solving the bi-objective facility layout problem,” Expert Syst. Appl., vol. 38, no. 4, pp. 4460–4465, Apr. 2011. https://doi.org/10.1016/j.eswa.2010.09.117

[8] M. Z. Allahyari and A. Azab, “Mathematical modeling and multi-start search simulated annealing for unequal-area facility layout problem,” Expert Syst. Appl., vol. 91, pp. 46–62, Jan. 2018. https://doi.org/10.1016/j.eswa.2017.07.049

[9] Komarudin and K. Y. Wong, “Applying Ant System for solving Unequal Area Facility Layout Problems,” Eur. J. Oper. Res., vol. 202, no. 3, pp. 730–746, May. 2010. https://doi.org/10.1016/j.ejor.2009.06.016

[10] J. D. Galarcio, M. P. Buelvas, P. A. Nisperuza, J. M. López and H. E. Hernández, “Una nueva metaheurística aplicada al problema de ruteo de vehículos capacitados (cvrp) para la distribución de productos perecederos,” Rev. Ing. e Innovación, vol. 5, pp. 60–72, Dec. 2017. Disponible en https://revistas.unicordoba.edu.co/index.php/rii/article/view/1107

[11] W. D. Urango and H. E. Hernández, “Efecto de los decodificadores en la calidad de la solución para un problema de distribución de instalaciones UA-FLP,” Rev. Ing. e Innovación, vol. 5, pp. 73–80, May. 2017. Disponible en https://revistas.unicordoba.edu.co/index.php/rii/article/view/1256

[12] A. D. Moreno, A. A. Álvarez, V. M. Noble and J. M. López, “Optimización multiobjetivo del problema de distribución de planta: Un nuevo modelo matemático,” Rev. Ing. y Compet., vol. 16, no. 2, pp. 247–267, Jul. 2014. https://doi.org/10.25100/iyc.v16i2.3700

[13] G. Xu and L. G. Papageorgiou, “Process plant layout using an improvement-type algorithm,” Chem. Eng. Res. Des., vol. 87, no. 6, pp. 780–788, Jun. 2009. https://doi.org/10.1016/j.cherd.2008.12.004

[14] W. Chiang, “Visual facility layout design system,” Int. J. Prod. Res., vol. 39, no. 9, pp. 1811–1836, Jan. 2001. https://doi.org/10.1080/00207540110035192

[15] D. C. Montgomery, “Diseño y análisis de experimentos,” México, D.C., MX: Iberoaméricana, 2004.

Wilmer Urango Narváez es Ingeniero Industrial de la Universidad de Córdoba (Montería, Colombia). Actualmente colaborador en el área de investigación del departamento de Ingeniería Industrial de la Universidad de Córdoba. https://orcid.org/0000-0002-2522-257X

Helman Hernández Riaño es Ingeniero Industrial de la Universidad Distrital Francisco José de Caldas (Bogotá, Colombia) y Doctor en Ingeniería Industrial (Barranquilla, Colombia). https://orcid.org/0000-0003-3042-2573

Jorge López Pereira es Ingeniero Industrial de la Universidad de Córdoba (Montería, Colombia) con Máster en Ingeniería Industrial (Barranquilla, Colombia). https://orcid.org/0000-0001-7317-8772