Embed Size (px)
Citation preview
Universidad de Los Andes
20 de mayo del 2020
Evaluación y Diseño de Políticas de Almacenamiento de Alimentos de la Empresa Gate
Gourmet por Medio de Herramientas de la Optimización Discreta
Autor: Ángel Santiago Rugeles Schoonewolff
Asesor: José Fidel Torres Delgado Ph.D.
.
Bogotá, Colombia
Índice
1. INTRODUCCIÓN……………………………………………………………………….4
2. PLANTEAMIENTO DEL PROBLEMA………………………………………………5
3. JUSTIFICACIÓN DEL PROYECTO Y RESULTADOS ESPERADOS……………7
4. OBJETIVOS……………………………………………………………………………..8
5. CARACTERÍSTICAS DEL MODELO DE SOLUCIÓN…………………………….9
6. METODOLOGÍA……………………………………………………………………….10
7. MARCO TEÓRICO…………………………………………………………………….10
8. MODELO MATEMÁTICO……………………………………………………………24
9. RESTRUCTURACIÓN ÓPTIMA DE LAS BODEGAS……………………………..27
10. ALGORITMOS DE SOLUCIÓN……………………………………………………...32
11. RESULTADOS Y ANÁLISIS DE RESULTADOS…………………………………...43
12. CONCLUSIONES………………………………………………………………………60
13. RECOMENDACIONES………………………………………………………………..61
Índice de Ilustraciones
Ilustración 1: Servicio de Entrega Gate Gourmet en Zúrich (Vilches, 2018). ....................................................................... 4
Ilustración 2: Cadena de Suministro de una Empresa de Catering ........................................................................................ 5
Ilustración 3 : Los Trolleys de la Empresa en sus Respectivas Cámaras de Frio. ................................................................. 6
Ilustración 4 : Los trolleys de la Empresa en su Respectiva Cámara de Frio (Santiago de Chile) ........................................ 6
Ilustración 5: Registro de Temperatura de una Cámara de Frio en Santiago de Chile (Agosto y Septiembre del 2018) ....... 7
Ilustración 6: Explicación Gráfica Búsqueda Tabu (Wari & Wheihang, 2016). ................................................................. 19
Ilustración 7: Explicación Gráfica Búsqueda Iterativa (Wari & Wheihang, 2016) (Lara, 2018) ......................................... 21
Ilustración 8: Autores Recientes Metaheurísticas en Problema de Almacenamiento de Productos en Bodegas (Rojas et al.,
2019). .................................................................................................................................................................................. 22
Ilustración 9: La Coordinación de Dos Trolleys en un Periodo Específico ......................................................................... 24
Ilustración 10: Posibles Configuraciones de Bodega (Durik y Opetuk,2012) ..................................................................... 28
Ilustración 11: Configuraciones Clásicas (Tutam y White,2019). ....................................................................................... 29
Ilustración 12: Configuración Actual en la Cámara de Bogotá (Capacidad de 495 Trolleys Completos) ........................... 30
Ilustración 13: Configuración Propuesta para la Cámara de Bogotá (Capacidad de 470 Trolleys Completos) ................... 30
Ilustración 14: Configuración Actual en la Cámara de Lima (Capacidad de 341 Trolleys Completos) .............................. 31
Ilustración 15: Configuración Propuesta para la Cámara de Lima (Capacidad de 309 Trolleys) ........................................ 31
Ilustración 16: Configuración Actual en la Cámara de Santiago ......................................................................................... 32
Ilustración 17:Configuración Propuesta para la Cámara de Santiago (Capacidad de 421 Trolleys). .................................. 32
Ilustración 18: Cromosomas Representantes de la Solución ............................................................................................... 33
Ilustración 19: Diagrama de Flujo Algoritmo Asignación de Áreas ................................................................................... 35
Ilustración 20: Funcionamiento del Mecanismo de Corrección 2 (Chao et al,2015). .......................................................... 38
Ilustración 21: Funcionamiento Mecanismo de Corrección Extra....................................................................................... 40
Ilustración 22: Cruce en el Algoritmo Genético .................................................................................................................. 41
Ilustración 23: Tipos de Mutaciones Utilizadas .................................................................................................................. 42
Ilustración 24: Vecindario de Intercambio de Áreas para un Mismo Vuelo. ....................................................................... 42
Ilustración 25: Resultado del Segundo Vecindario de Intercambio de Áreas Entre Dos Vuelos ......................................... 43
Ilustración 26: Bodega de Bogotá con su Nueva Distribución Dividida en Áreas .............................................................. 44
Ilustración 27: Bodega de Santiago con su Nueva Distribución Dividida en Áreas ............................................................ 47
Ilustración 28: Bodega de Lima con su Nueva Distribución Dividida en Áreas ................................................................. 50
Índice de Tablas
Tabla 1: Posibles Términos de Problema de Almacenamiento (Rojas et al., 2019). ........................................................... 13
Tabla 2: Métodos de Solución de los Últimos 15 años para el Problema SLAP, Organizados por Número de Referencias
(Rojas et al., 2019). ............................................................................................................................................................. 15
Tabla 3: Soluciones Exactas del Problema de Almacenamiento por Porcentaje de Artículos. (Rojas et al., 2019) ............. 15
Tabla 4: Nomenclatura Soluciones Exactas (Rojas, 2019). ................................................................................................. 16
Tabla 5 Heurísticas del Problema de Almacenamiento por Porcentaje de Artículos (Rojas et al., 2019) ........................... 18
Tabla 6: Nomenclatura Heurísticas. (Rojas & al, 2019) ...................................................................................................... 18
Tabla 7: Metaheurísticas del Problema de Almacenamiento por Porcentaje de Artículos (Rojas et al., 2019) ................... 19
Tabla 8: Nomenclatura Metaheurísticas. (Rojas et al., 2019) .............................................................................................. 19
Tabla 9: Restricciones y Consideraciones Problema Almacenamiento de Bodega ............................................................. 23
Tabla 10: Restricciones de Cada Bodega por Ciudad ......................................................................................................... 28
Tabla 11:Resultados Simulados del Desplazamiento Promedio Dentro de la Bodega en Metros (Durik y Opetuk,2012) .. 29
Tabla 12: Información de Entrada ....................................................................................................................................... 33
Tabla 13: Zonas Asistidas de la Cámara de Bogotá con su Respectiva Capacidad y Convención ...................................... 44
Tabla 14 : Zonas Asistidas de la Cámara de Santiago con su Respectiva Capacidad y Convención ................................... 47
Tabla 15: Zonas Asistidas de la Cámara de Lima con su Respectiva Capacidad y Convención ......................................... 50
Tabla 16: Zonas Asistidas de Bogotá con la Demanda Incrementada un 14% .................................................................... 56
Tabla 17: Horizonte de Planeación (48 Periodos) de Bogotá con Demanda Incrementada ................................................. 56
Tabla 18: Zonas Asistidas de Lima con la Demanda Incrementada un 19% ....................................................................... 57
Tabla 19: Horizonte de Planeación (48 Periodos) de Lima con Demanda Incrementada .................................................... 57
Tabla 20: Zonas Asistidas de Santiago con la Demanda Incrementada un 30% ................................................................. 58
Tabla 21: Horizonte de Planeación (48 Periodos) de Santiago con Demanda Incrementada .............................................. 58
Índice de Gráficas
Gráfica 1: Número de Publicaciones en Revistas de Ingeniería Concernientes con el Problema de Almacenamiento de
Productos (Rojas et al., 2019). .................................................................................................................................................................................. 12 Gráfica 2 Resultados Búsqueda Tabú para el Vecindario de Reemplazo, Bogotá ............................................................................... 45 Gráfica 3: Resultados Búsqueda Tabú para el Vecindario de Intercambio, Bogotá ............................................................................ 45 Gráfica 4:Resultados Algoritmo Genético, Bogotá .......................................................................................................................................... 46 Gráfica 5:Tiempos de Convergencia para las Cuatro Soluciones, Bogotá .............................................................................................. 46 Gráfica 6: Resultados Búsqueda Tabu para el Vecindario de Reemplazo, Santiago ........................................................................... 48 Gráfica 7: Resultados Búsqueda Tabu para el Vecindario de Intercambio, Santiago ......................................................................... 48 Gráfica 8:Resultados Algoritmo Genético, Santiago ....................................................................................................................................... 49 Gráfica 9: Tiempos de Convergencia para las Cuatro Soluciones, Santiago .......................................................................................... 49 Gráfica 10: Resultados Búsqueda Tabu para el Vecindario de Reemplazo, Lima ............................................................................... 51 Gráfica 11: Resultados Búsqueda Tabu para el Vecindario de Intercambio, Lima ............................................................................. 51 Gráfica 12: Resultados Algoritmo Genético, Lima .......................................................................................................................................... 52 Gráfica 13: Tiempos de Convergencia para las Cuatro Soluciones, Lima ......................................................................................... 52 Gráfica 14: Capacidad Utilizada (Porcentajes) a lo Largo del Horizonte de Planeación para las Tres Cámaras ..................... 55 Gráfica 15: Resultados Búsqueda Tabu con Vecindario de Intercambio para las Tres Cámaras con Demanda Incrementada
.............................................................................................................................................................................................................................................. 59 Gráfica 16:Resultados Tiempo de Convergencia del Algoritmo de Búsqueda Tabu con Vecindario de Intercambio para las
Tres Cámaras con Demanda Incrementada ......................................................................................................................................................... 59
1. INTRODUCCIÓN
Gate Gourmet, empresa perteneciente a “Gategroup”, es el principal proveedor internacional de
servicios de catering y aprovisionamiento para aerolíneas y trenes. Desde su fundación en 1992,
atiende a 700 millones de pasajeros anualmente, sirve 35.000 bandejas diarias para 200 vuelos y para
el 2017 había incrementado sus ingresos en un 35% hasta los 3.900 millones de euros. (Vilches, 2018)
Ilustración 1: Servicio de Entrega Gate Gourmet en Zúrich (Vilches, 2018).
El volumen de las operaciones aéreas en la actualidad crece a medida que las necesidades de los
usuarios de aerolíneas demandan economía de tiempo y mejores condiciones de vuelo; para ello se
aumenta la frecuencia de vuelos a diferentes destinos y se mejoran las aeronaves para brindar mayor
capacidad y servicio. Como resultado se hace indispensable mejorar la provisión de los servicios
prestantes en las rutas. En cuanto a la logística, el diseño de un establecimiento de catering aéreo debe
tener como fundamento las necesidades en las áreas de almacenamiento y preparación de alimentos,
así como analizar las necesidades relativas a las áreas de servicios generales y apoyo. Una vez
planteado lo anterior, el establecimiento deberá atender con un flujo más racional, procurando que el
mismo esté sin interrupciones, sin cruces en las operaciones y en general, buscando las mejores
condiciones de operación.
A continuación, se presenta la cadena de suministros de servicios brindada por una empresa de
catering, incluyendo las decisiones operativas a las que debe enfrentarse continuamente. La
configuración presentada en la misma es del tipo pull, donde se manufactura dependiendo de las
órdenes de los clientes. Una característica de esta corporación en la relación planteada con sus
proveedores que suministran la materia prima. Al tratar con productos perecederos, la materia prima
solicitada por la empresa debe ser consumida en su totalidad, evitando así el almacenamiento de la
misma. En relación con el producto terminado, “Gate Gourmet” presenta dos modalidades de
almacenamiento; una bodega para aglomerar los carros e implementos necesarias para el correcto
empaquetamiento de la comida (bandejas, cubiertos, platos de cerámica, etc.) así como una cámara
en frio donde el producto terminado debe permanecer hasta el momento de su envío. Debido a
políticas y estudios previos, se determinó que los alimentos deben ser entregados a las aerolíneas con
una temperatura acotada entre los 0 y 5 grados Celsius, por lo que la comida debe permanecer en la
cámara de refrigeración entre 4 y 6 horas aproximadamente. Cabe resaltar que los carros donde se
carga la comida se encuentran hechos de materiales conductores permitiendo una convección con el
aire frio en el ambiente.
Ilustración 2: Cadena de Suministro de una Empresa de Catering
2. PLANTEAMIENTO DEL PROBLEMA
Actualmente, la planeación, así como el “scheduling” o la agenda del posicionamiento de los trolleys
en la zona de frio se está realizando por medio de una hoja de Excel, sin considerar el
aprovechamiento de recursos como lo son el espacio disponible, o el desplazamiento total en la
bodega. De igual manera, el procedimiento actual de planeación para el almacenamiento y
recolección no tiene una justificación ingenieril, impidiendo a los usuarios saber diferencias entre
configuraciones de posicionamiento, comparar alternativas de manera cuantitativa o generar
soluciones más allá de la lógica. Teniendo en cuenta que, tanto el espacio como la carga de trabajo
(personal en la cámara de frio) disponible en la bodega son limitados, se requiere una alternativa que
permita una mejor utilización de estos activos, así como una herramienta que le brinde soluciones de
posicionamiento claras a los usuarios encargados en la empresa.
Asimismo, dentro de la bodega de refrigeración se presentan ciertas reglas, las cuales debe cumplir
el personal. Estas reglas aglomeran diferentes restricciones en el posicionamiento de productos como
no ubicar los trolleys con la comida debajo de los rociadores de aire frio ya que estos pueden
humedecer y consecuentemente, deteriorar el producto, así como designar cierto espacio entre
rubricas de almacenamiento para que los caninos antidrogas puedan revisar el contenido de estos.
Estas reglas pueden variar de país a país, lo que hacer difícil su control en relación con el mejor
almacenamiento. En algunas instancias, la poca planeación ha causado la necesidad de violar estas
reglas como se muestra a continuación.
Ilustración 3 : Los Trolleys de la Empresa en sus Respectivas Cámaras de Frio.
A) Sao Paulo en Brasil B) Buenos Aires en Argentina
Ilustración 4 : Los trolleys de la Empresa en su Respectiva Cámara de Frio (Santiago de Chile)
Finalmente, en muchas instancias, debido a la poca regulación, no se ha cumplido el tiempo mínimo
que deben permanecer todos los pedidos dentro de la cámara, lo que evita que se llegue a un equilibrio
térmico entre la habitación y los productos perecederos. Como consecuencia, se han detectado
aumentos en la temperatura de la instalación en cuestión, como se muestra en la siguiente gráfica,
perteneciente a un estudio realizado en una de las cámaras de refrigeración principal de Santiago de
Chile. Esta expone instancias en las que se llegan incluso a más de 8 grados centígrados. Aparte del
incremento que se están generando actualmente en los costos logísticos, los cuales de por sí ya
constituyen cerca del 20 % de los costos de una compañía, la violación de las restricciones dentro de
la cámara de frio puede afectar considerablemente la calidad de los productos, como al recibir la
condensación de un rociador de aire que se encuentra goteando, o que no se refrigere correctamente
e inicie el proceso de descomposición.
Ilustración 5: Registro de Temperatura de una Cámara de Frio en Santiago de Chile (Agosto y Septiembre del 2018)
Tanto la reducción de costos como la prevención de estos problemas serán logrados por medio de un
modelo de optimización discreta que regule el almacenamiento de los alimentos en la bodega de frio,
así como sus periodos de entrada, minimizando el desplazamiento total diario dentro de la bodega.
3. JUSTIFICACIÓN DEL PROYECTO Y RESULTADOS ESPERADOS
Ronald Ballou, en su libro de logística empresarial, define los costos logísticos como los costos o
gastos ocultos enfrentados por una empresa a lo largo de su cadena de suministro. Estos costos
incluyen los gastos de almacenamiento, transporte, aprovisionamiento e incluso el costo del personal
encargado de estas funciones. Al ser ocultos, estos están distribuidos en diferentes ámbitos de la
empresa, lo que ciertamente dificulta su contabilidad. Sin embargo, su identificación y regulación es
esencial para sobresalir en el mercado y entre la competencia. Aquí es donde radica la importancia
de este proyecto, el cual busca disminuir los espacios gastados en almacenamiento y la carga de
trabajo vinculada con el desplazamiento para reducir los costos y maximizar el rendimiento de la
empresa en ese ámbito (Ballou, 2004). La utilización óptima de las cámaras de frio es una obligación
si, además de los costos almacenamiento, se consideran los costos de mantenimiento de la bodega
(tanto mantenimiento de infraestructura como el consumo energético en el control de la temperatura).
Del mismo modo, en la encuesta nacional de logística, realizada en el año 2018 por La República, se
encontró que el costo logístico nacional alcanza el 13.5%, una cantidad considerable. Entre sus
componentes, el almacenamiento de productos y bienes corresponde casi a la mitad de esta cifra, con
46.5 %, superando a incluso el transporte de productos. Además, se evidencia que estos costos son
inversamente proporcionales al tamaño de la empresa en cuestión. Las empresas grandes, las cuales
tienen una mejor estructuración logística y una toma de decisiones mejor respaldada gracias a su
recolección de información y toma de decisiones, tienen un gasto logístico que corresponde al 11 %
de los gastos totales. Por otra parte, las corporaciones micro, aquellas que operan en un sector pequeño
de la población o que se encuentran en sus años de iniciación, conllevan costos logísticos de casi un
cuarto de los costos totales. Asumir esta cantidad puede representar el éxito o el fracaso de una
empresa y su mal control puede perjudicar a una compañía grande como Gate Gourmet. Por ende,
este proyecto tiene una importancia significativa, permitiendo abreviar estos problemas y solventar
soluciones a los mismos.
Encuesta Costo Logístico Nacional 2018 (Monterrosa, 2018)
Además, al tratarse de productos perecederos, la calidad de estos es la principal prioridad de todo
servicio de catering. No obstante, ciertas violaciones como ingresar los productos tarde a la cámara
de frio, evitando que alcancen la temperatura de distribución óptima, que el tamaño de los pasillos
sea inferior a los mínimos legales estipulados, o que los trolleys absorban el agua condensada de los
rociadores deteriorando significativamente la disposición de los alimentos, puede generarle a la
empresa problemas legales. Por ende, asegurarle a GateGroup el cumplimiento de las normas puede
evitar complicaciones futuras y prepararse para cuando el crecimiento de la demanda supere el
espacio disponible. Utilizando los resultados de este proyecto, las directivas de la empresa podrán
tomar decisiones ajenas al almacenamiento de productos, como lo es alterar las dimensiones de las
bodegas de refrigeración, así como inaugurar nuevos centros de refrigeración.
4. OBJETIVOS
Objetivo Principal:
➢ Desarrollar una herramienta de fácil utilización con la cual se realice la planeación del
posicionamiento y horarios de entrada de los trolleys –contenedores de alimento de la
empresa Gate Gourmet– en la cámara de frio a partir de la agenda diaria de vuelos con
su respectiva cuantificación de carros de comida y periodos de salida.
Objetivos Secundarios:
➢ Adaptar el modelo a diferentes requerimientos con el fin de ser aplicado en diferentes
países con normas diferenciadoras.
➢ Aplicar más de un modelo de solución con el objetivo de determinar el más viable y
aplicable en cada situación. Esto les otorgará opciones a los usuarios de la empresa.
➢ Proporcionar un análisis de la robustez del algoritmo, observando su funcionamiento
en casos donde las bodegas se encuentran cerca de su capacidad límite. Estos hallazgos,
dictaminarán la utilidad del modelo de solución en estas situaciones, así como, según
sus pronósticos de crecimiento, el tiempo que la bodega podrá almacenar la demanda
pronosticada de los vuelos.
5. CARACTERÍSTICAS DEL MODELO DE SOLUCIÓN
Como se mencionó anteriormente, el objetivo principal del proyecto consiste en aglomerar las
soluciones del problema de almacenamiento de tal manera que sea utilizable por los usuarios de la
compañía. Para esto se utilizará un modelo de optimización discreta, el cual contará con las siguientes
características:
Inputs o Condicionales de Entrada (por cada vuelo):
• Nombre del Vuelo
• Número de Trolleys pertenecientes
• Binario Halal: Los vuelos de ciertas aerolíneas seguidoras del islam como “Emirates” o
“Turkish Airlines” son considerados vuelos halal y sólo pueden ser ubicados en una zona
específica previamente bendecida. Como parámetro de entrada, se utilizará un binario
clasificatorio que posibilitará su identificación (uno si es un vuelo halal y cero de lo
contrario).
• Horario de Salida: Requerido para realizar seguimiento y determinar el horario de entrada de
cada vuelo.
Restricciones:
• Restricción de espacio: Dentro de la bodega se presentan ciertas zonas muertas donde no es
posible ubicar trolleys. Estas son debajo de los rociadores y en algunos casos contra la pared
y las regiones Halal permanentes (regiones halal donde no es posible almacenar otro vuelo
diferente al halal). Intrínsecamente, los espacios que serán definidos como pasillos también
se consideran zonas prohibidas, ya que, en otro caso, la minimización del desplazamiento
total no sería posible.
• Restricción de tiempo: Por cuestiones de calidad, cada alimento debe permanecer al menos
cuatro horas dentro de la cámara de frio. No obstante, estudios previos demuestran que la
temperatura de las bodegas en ciertas instancias supera los 5 grados Celsius y que siempre se
presenta un consumo de tiempo en posicionar y recolectar los trolleys para el envío. Por lo
anterior, se llegó a la decisión de que cada trolley debe permanecer entre cuatro y seis horas
dentro de la cámara.
• Restricción de clase: Esta política de inventario plantea que los carros del mismo vuelo deben
ir juntos a fin de facilitar el trabajo del personal.
• Restricción de asignación. Una vez posicionado un conjunto de carros, estos no deben ser
trasladados a otro espacio hasta su salida.
• Restricción de Capacidad. Evidentemente, la restricción principal consiste en que, a lo largo
del día, en ningún horario, el número de carros debe superar la cantidad de espacios
disponibles de la bodega al descontar pasillos y espacios prohibidos.
Por último, se exponen las variables de decisión:
• Posicionamiento de cada vuelo dentro de la bodega.
• Horario de entrada de cada vuelo dentro de la bodega.
6. METODOLOGÍA
Revisión Bibliográfica:
Este proyecto será iniciado realizando una revisión bibliográfica profunda del problema de
almacenamiento de productos. En la literatura, este problema es comúnmente conocido como
“Location Assignment Problem” o “Storage Location Assignment Problem”. Dentro de la revisión se
identificarán las diferentes metodologías de solución, así como los campos en las que son aplicados
y finalmente, las restricciones que comúnmente manejan estas modelos de solución. A partir de los
modelos más utilizados para este problema, los que más se adapten a productos perecederos y
concuerden con el tipo de restricción considerada, será(n) seleccionado(s) para crear la mejor
solución. Cabe resaltar que se espera seleccionar al menos dos metodologías de solución, permitiendo
plantear una comparación y determinar cuál es la más efectiva. Del mismo modo, se dispondrá de
una visión más amplia a la hora de analizar los resultados y la vigencia de las bodegas en cuestión.
Planteamiento y construcción Modelos de Solución:
Una vez seleccionadas las herramientas que se utilizarán para solucionar el problema en cuestión, se
desarrollarán dos modelos de optimización discreta que cuenten con los mismos parámetros e inputs
de entrada, las variables de decisión, las restricciones y por último la función objetivo que se buscará
optimizar (en este caso minimizar). Cabe resaltar que este modelo debe ser de fácil utilización para
las directivas de planeación de la empresa.
Validación Algoritmos de Solución:
Las soluciones iniciales suelen tener ordenes de convergencia e incluso consumo de memoria bastante
altos, ya que se prioriza la convergencia de soluciones dentro de la región factible con funciones
objetivo aceptables. No obstante, el siguiente paso en seguida de converger en una solución aceptable,
es medir la robustez del modelo y subsecuentemente incrementarla en tal caso que lo requiera. Una
robustez alta representa que, sin importar el tamaño de la input o entrada, el algoritmo trabajará en
tiempos y consumirá espacios en la memoria secundaria razonables.
Selección del Mejor Modelo Construido:
Finalmente, se compararán los modelos robustos por medio de su efectividad sobre la función
objetivo y tiempos de convergencia con el fin de decidir el más eficiente. Este modelo seleccionado
otorgará las inferencias más confiables sobre la efectividad y vigencia de las cámaras de frio
estudiadas.
7. MARCO TEÓRICO
Contexto:
La tendencia empresarial de incrementar la variedad de productos disminuyendo tiempos de entrega
y espera ha incrementado la necesidad de operaciones logísticas óptimas, ya que estos costos
equiparan y en algunos casos superan a los costos de producción. Cifras recientes exponen que las
operaciones de bodega representan el 24 % de los costos logísticos totales en Estados Unidos
(Establish, 2016) y más del 25 % en Europa (At Kerney,2018). Por ende, la correcta aplicación de
dichas operaciones puede ser un factor decisivo en los ámbitos de competencia a los que se enfrentan
las corporaciones actualmente.
Los centros de distribución son un aspecto clave dentro de la cadena de suministro moderna. Muchas
empresas se han centrado en tratar de eliminar estas bodegas estableciendo un sistema de entrega
directa con el cliente. Por ejemplo, Dell planteó una política de cero inventarios, donde suple las
necesidades particulares de cada cliente a partir de materia prima, cuya recepción se coordina con
intermediarios en altamar. De esta manera, por medio de una configuración “pull” drástica y
debidamente coordinada, se mantiene en un contexto competitivo con empresas como Apple, Lenovo
y Hewlett Packard, sin almacenar materia prima ni producto terminado. No obstante, en muchos casos
esta tercerización de inventario y consecuente extracción de los centros de distribución de la cadena
de suministro no es posible (Rouwenhorst B., 2010). Lo anterior es debido a que se presenta la
incapacidad de reducir los tiempos de entrega efectivamente a los esperados, por lo que se requiere
servir a los clientes con inventario previamente almacenado en lugar de solicitar la materia prima para
suplir esa orden (Baker & Canessa, 2009). La empresa Gate Gourmet secunda este planteamiento;
aunque su configuración por excelencia se asemeja a una tendencia pull, en muchas instancias y
gracias a estimaciones previamente realizadas –en muchas ocasiones soportadas por la experiencia y
el conocimiento contextual en el área de aplicación– se suplen de una cantidad base de materia prima
sin la necesidad de conocer la cantidad exacta de alimentación que van a proveer. Asimismo, al
entablar una relación continua y periódica con sus clientes, conservan los carros o trolleys donde se
encuentra el servicio entregado y requieren subsecuentemente un lugar para guardarlos. De no seguir
estas prevenciones, en muchos casos sería imposible cumplir los tiempos de entrega, tendiendo en
consideración la cantidad de clientes y diferentes aerolíneas con las que trabaja la corporación
mencionada.
Considerando estas necesidades, las empresas requieren encontrar una manera de almacenar sus
productos minimizando no sólo el espacio que ocupan en la bodega (en tal caso de que estas
dimensiones no den abasto se requerirá de otro establecimiento, lo que conlleva nuevos costos de
mantenimiento y adquisición), sino también el desplazamiento total y por consiguiente el tiempo
consumido en el “picking” y preparación de los productos para el envío. Este problema tiene una
vigencia enorme. Las soluciones y aplicaciones de este problema datan de mitades del siglo XX, y
cuentan con un número considerable de metodologías de solución.
Problema de Almacenamiento de Bodega:
El problema de almacenamiento de bodega o “SLAP” consiste en decisiones operacionales, las cuales
descifran el posicionamiento óptimo de los productos en diferentes ubicaciones con el objetivo de
minimizar costos logísticos asociados a carga de trabajo, desplazamiento promedio, mantenimiento
de infraestructura entre otros. Estas decisiones abarcan los procedimientos de recepción de productos,
almacenamiento, preparación de pedidos y despacho, ya que busca minimizar el desplazamiento con
el que se llevarán a cabo estas operaciones. El problema en cuestión, el cual se encuentra relacionado
tanto con la acomodación como con los procesos de “picking”, presenta comúnmente una
programación computacional compleja al involucrar un gran número de parámetros como la
geometría de diseño del centro de distribución, el espacio habilitado, características propias del
producto como horarios de llegada y salida preestablecidas y por supuesto, la cantidad y distribución
de la demanda que rige la cadena de suministro. Al aglomerar tantas consideraciones, el problema es
considerado NP-hard (Rojas et al., 2019). Asimismo, las restricciones de estas prácticas se evidencian
en la disponibilidad del personal y su subsecuente carga de trabajo, los recursos disponibles para la
preparación efectiva de las ordenes, las políticas de agrupación y despacho (lo que lleva a la definición
de clases, donde objetos de diferente clase no pueden ser almacenados juntos) y finalmente, el espacio
disponible para almacenar al substraer zonas prohibidas y administrativas (Rouwenhorst B., 2010).
La complejidad de este problema proviene de la interpolación de dos problemas típicos de
optimización discreta, muy relacionados con el diseño de bodegas o centros de distribución: el “bin
packagin problem” y el “traveling salesman problem”, enfocados en definir el posicionamiento de
inventario y las rutas de recolección respectivamente. La complejidad computacional surge de la
necesidad de resolver características de ambos problemas simultáneamente, optimizando ciertos
factores operacionales como tiempo o distancia recorrida (Yener & Yazgan, 2019).
El problema de empaquetamiento de contenedores es un problema de almacenamiento de
optimización discreta con complejidad del orden NP duro. Este problema presenta una gran cantidad
de variaciones, como el empaquetamiento 2d,3d, por peso, por un valor subjetivo, etc. Esta situación
busca empacar un conjunto n de productos cada uno con su respectiva característica diferenciadora
en un conjunto de m contenedores de disponibilidad D. A pesar de su ordenamiento computacional,
este problema cuenta con un número bastante significativo de soluciones, ya que se encuentra entre
los problemas de optimización combinatoria más conocidos junto con el problema del viajero
frecuente (Gómez, 2016), y ha sido analizado, estudiado y profundizado por más de 40 años (Delorme
et al., 2016). Cabe resaltar que los temas de almacenamiento de productos han sido tratados por más
de 50 años, desde 1979, cuando Armstrong, Cook y Saipe realizaron un modelo de programación
lineal mixta (MILP) para determinar las políticas de picking utilizando el menor dimensionamiento
posible (Yener & Yazgan, 2019).
También, se resalta que la cantidad de artículos cubriendo modelos o casos de estudio en estos tópicos
de almacenamiento de productos, se ha incrementado significativamente en esta última década,
principalmente por las nuevas herramientas computacionales que permiten la convergencia de este
problema en un tiempo pseudo-polinomial. En esta última década, además de los modelos de
programación entera y mixta, las metaheurísticas y la simulación de eventos discretos se encuentran
en su auge.
Gráfica 1: Número de Publicaciones en Revistas de Ingeniería Concernientes con el Problema de Almacenamiento de
Productos (Rojas et al., 2019).
Por último, se resalta que este problema de asignación de productos es conocido en la literatura por
diferentes nombres, principalmente como asignación de almacenamiento o asignación de ubicación
de almacenamiento (estos nombres se presentan en el 80% de los trabajos relacionados con este tema
en los últimos 15 años).
Tabla 1: Posibles Términos de Problema de Almacenamiento (Rojas et al., 2019).
Optimización Discreta:
La optimización discreta, a diferencia de la optimización lineal, fuerza a sus variables de decisión a
tomar valores discretos, como por ejemplo enteros. Los problemas de optimización discreta se
encuentran entre los más difíciles de la ciencia computacional y pueden ser aplicados a una gran
variedad de campos como lo es la cadena de suministro, la logística y la manufactura entre otros.
Evidentemente, el problema de ubicación y asignación recae en esta categoría. Estos problemas son
conocidos como problemas NP complejos o “NP hard”. Esta taxonomía representa los problemas más
complejos, los cuales, no pueden ser resueltos en tiempo polinomial sin importar restricción o
consideración posible. Con la correcta aplicación de modelos matemáticos o heurísticas, es posible
conseguir un orden pseudo-polinomial (Gómez, 2016). Entre estos se encuentran:
❖ Travelling Salesman Problem
❖ Bin Packaging Problem
❖ Sport Scheduling Problem
❖ Graph Coloring Problem
❖ Magic Series Problem
❖ Sudoku
❖ Warehouse Location Problem
❖ Vehicle Routing Problem
❖ Knapsack Problem
❖ Vehicle Manufacturing Sequence Problem
❖ Set Cover Problem
Todos estos planteamientos tienen tres propiedades en común, las cuales son:
• Es posible obtener una solución en tiempo pseudo-polinomial.
• Si existe la posibilidad de solucionar un problema NP “hard” o duro, es posible solucionarlos
todos.
• La determinación de la solución óptima requiere de tiempo exponencial.
Al poseer una entrada relativamente grande, el orden exponencial es un problema ya que puede tomar
tiempos de convergencia masivos, lo que hace que el proceso de solución sea poco viable. Por ende,
se requiere llevar esta tendencia a una lo más similar a la lineal posible, disminuyendo los estándares
y conformándose con una solución, que, aunque no sea la óptima global, satisfaga los estándares
básicos y se encuentre en la región factible. De las diversas ramas de optimización, discreta, esta
revisión se centrará en la optimización combinatoria, así como sus diferentes alternativas de solución
(Baron et al., 2019).
Optimización Combinatoria:
A diferencia de la optimización lineal que determina el mínimo o máximo de una función lineal sujeta
a ciertas restricciones que delimitan su rango de acción, la optimización combinatoria busca
determinar la mejor decisión entre un banco de opciones disponibles. Normalmente, este set de
decisiones no tiene una organización lógica ya que estas se encuentran entrelazadas implícitamente,
lo que hace imposible tabularlas u organizarlas lógicamente. Al estudiar todas las opciones mediante
un proceso iterativo, existe la posibilidad de determinar la mejor solución si esta es factible. Aun así,
esta ruta medianamente óptima no es determinable por medio de lógica pura. Cabe resaltar que todos
los problemas planteados anteriormente clasifican en el rango de optimización combinatoria.
Asimismo, al tratarse de un sistema donde se selecciona una alternativa, los algoritmos de búsqueda
y los algoritmos avaros o “greedy” por naturaleza tienen la tendencia a encontrar una solución.
El mayor uso de esta optimización discreta aplica la herramienta conocida como combinatoria
poliédrica, la cual puede considerarse como la interacción entre programación línea y problemas de
optimización combinatoria. La optimización lineal, aunque muy útil es regida en un dominio continuo
y el objetivo de estas combinatorias es adaptar estas herramientas a campos discretos (Lend et al.,
2019).
La optimización combinatoria está compuesta por los siguientes parámetros:
● Un conjunto de n variables 𝑋 = {𝑥1, 𝑥2 … 𝑥𝑛}
● Los dominios asociados a estas variables 𝐷 = {𝐷1, 𝐷2, … 𝐷𝑛}
● Las restricciones específicas del problema
● La función objetivo a optimizar (maximización o minimización): 𝑂 = 𝑋1𝐷1, 𝑋2𝐷2, … 𝑋𝑛𝐷𝑛
La característica discreta de la herramienta permite definir un espacio de búsqueda exhaustiva. Es
importante resaltar que el problema de asignación de productos tiene normalmente un carácter de
límite superior, por lo que se busca minimizar la función objetivo (ya sea en desplazamiento o tiempo
de asignación) (Gómez, 2016). El problema será resuelto cuando se determine una solución global
(s*) donde la función objetivo sea la menor posible.
𝑆 = {𝑠 = {(𝑥1), (𝑥2), … , (𝑥𝑛)}|𝑥𝑖 ∈ 𝐷𝑖}
S es el espacio de búsqueda que satisface todas las restricciones del problema, compuesto por todas
las combinaciones factibles de las variables. Cada elemento de este espacio es una posible solución.
En otras palabras, cada miembro s satisface todas las restricciones y se encuentra en la región de
factibilidad. Aquí se buscará exhaustivamente la solución.
Por último, vale la pena mencionar que se presentan dos posibles formas de abordar estos problemas
en caso de que la solución óptima y global sea inalcanzable en tiempos de convergencia razonables.
La primer consiste en centrarse simplemente en la región de factibilidad y tomar como meta
minimizar la función objetivo. Esta práctica codiciosa suele llevar a mínimos locales. Por otro lado,
considerar explorar las regiones no factibles o menos efectivas puede revelar vecindades factibles y
con mayor funcionalidad que las actuales. Esta es la premisa principal de las metaheurísticas,
exploradas desde principios del siglo XXI.
Soluciones al Problema de Almacenamiento y Revisión Bibliográfica:
A continuación, se exponen los posibles modelos de solución para el problema de almacenamiento
de bodega, a fin de determinar la solución más adecuada para este problema. Estas soluciones
incluyen métodos exactos, reglas y políticas (SP&R), heurísticas, metaheurísticas, simulación,
métodos multa-criterio, y otras tendencias (OT). De entrada, se determina que las tres alternativas
menos respaldas no serán consideradas al brindar poco soporte bibliográfico. Asimismo, las Reglas
y Políticas son muy utilizadas para clasificar y diferenciar los productos a ingresar, impactando la
manera en la que se realizará el almacenamiento. No obstante, por sí mismas no se suele ser posible
alcanza una solución óptima, por lo que son comúnmente combinadas con otros procedimientos. Este
conlleva a que se descarten como metodologías de solución. No obstante, algunas de estas políticas
serán utilizadas, como lo es el sistema de clases, el cual, será administrado en el modelo de solución
aplicándose a las diferentes aerolíneas y la clasificación aleatoria, ya que, en la búsqueda local, un
cargamento será asignado a un espacio disponible aleatoriamente con el objetivo de cuantificar la
función objetivo con los respectivos trolleys en esa posición.
Tabla 2: Métodos de Solución de los Últimos 15 años para el Problema SLAP, Organizados por Número de Referencias
(Rojas et al., 2019).
Soluciones Exactas:
Del estudio literario presentado a continuación realizado por Rojas Reyes et al. (2019), se exponen
una gran cantidad de modelos matemáticos, principalmente modelos de optimización poliédrica como
programación mixta. A primera instancia, se observa que el 67% de las publicaciones actuales
presentadas aplican modelos de programación entera mixta, donde se presentan variables de decisión
tanto continuas como discretas. Mas del 80% de los modelos matemáticos exactos utilizados están
compuestos por programación mixta lineal, programación dinámica y programación binaria
respectivamente. Todos los estudios se encuentran en una categoría reciente, ya que el más antiguo
consta de 14 años a la fecha.
Tabla 3: Soluciones Exactas del Problema de Almacenamiento por Porcentaje de Artículos. (Rojas et al., 2019)
Tabla 4: Nomenclatura Soluciones Exactas (Rojas, 2019).
Abreviación Método
MILP “Mixed Integer Programming”
DP Dynamic Programming”
BL “Binary Programming”
NLP “Non-Linear Programming”
PF “Pareto Borders”
RO “Robust Optimization”
B&B “Branch and Bound Algorithms”
Programación Entera:
La programación entera corresponde a modelos exactos donde todas las variables de decisión son
forzadas a tomar valores enteros. Agregar esta discretización incrementa significativamente el tiempo
de convergencia al volver el problema no convexo y presentar la necesidad de probar diferentes
combinaciones. Un problema de optimización discreta que se adapta de manera eficiente a este tipo
de programación es el problema de localización de bodegas o “Warehouse Location Problem”.
En la problemática de las bodegas, se busca determinar entre un grupo de centros con su respectiva
posición, los que deben estar abiertos con el objetivo de suplir las demandas de los clientes.
Asimismo, se busca minimizar la suma entre los costos de apertura y mantenimiento y los costos de
transporte entre las bodegas y sus respectivos consumidores (Van Hentenryck, 2015).
Variables de Decisión:
• 𝑥𝑤 = {1 𝑠𝑖 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑖 𝑠𝑒 𝑒𝑛𝑐𝑢𝑒𝑛𝑡𝑟𝑎 𝑎𝑏𝑖𝑒𝑟𝑡𝑎
0 𝑑. 𝑙. 𝑐
• 𝑦𝑤𝑐 = {1 𝑠𝑖 𝑒𝑙 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑐 𝑒𝑠 𝑎𝑡𝑒𝑛𝑑𝑖𝑑𝑜 𝑝𝑜𝑟 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑤
0 𝑑. 𝑙. 𝑐
Parámetros:
• conjunto N compuesto por n bodegas disponibles
• conjunto M compuesto por m clientes a suplir
• costo fijo de apertura y mantenimiento para cada bodega (𝑐𝑤)
• costo de transporte entre bodega w y cliente c (𝑡𝑤𝑐)
Función Objetivo:
𝑚𝑖𝑛 ∑ 𝑐𝑤 ∗ 𝑥𝑤 + ∑ ∑ 𝑡𝑤𝑐 ∗ 𝑦𝑤𝑐
𝑚
𝑐=1
𝑛
𝑤=1
𝑛
𝑤=1
Restricciones:
• cada cliente solo debe ser atendido por una bodega: ∑ 𝑦𝑤𝑐 = 1𝑛𝑤=1
• Un cliente solo debe ser atendido por una bodega si esta se encuentra abierta. 𝑦𝑤𝑐 ≤𝑥𝑤 ∀ 𝑤 ∈ 𝑁, 𝑐 ∈ 𝑀
Programación Lineal Mixta (MILP):
Por otro lado, la programación Lineal Mixta permite que algunas variables de decisión tomen valores
continuos, aunque conservando algunas variables de decisión discretas. Esta relajación comúnmente
conlleva a una disminución en la complejidad computacional y por ende un menor tiempo de
convergencia y de memoria gastada (se disminuye considerablemente la correlación iterativa). Esto
explica la popularidad de estos modelos y por qué son los modelos exactos más utilizados (Van
Hentenryck, 2015).
Una alteración o relajación del problema de bodegas con relajación mixta consiste en cambiar la
variable de decisión ywc a una tendencia continua. Por consecuencia se remueve la restricción de que
un cliente debe ser atendido por una sola bodega. Y se agrega como parámetro la demanda de los
clientes. La nueva variable de decisión es:
0 ≤ 𝑦𝑤𝑐 ≤ 1 𝑒𝑙 𝑝𝑜𝑟𝑐𝑒𝑛𝑡𝑎𝑗𝑒 𝑑𝑒 𝑙𝑎 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒𝑙 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑐 cubierta por la bodega w
Heurísticas:
En el ámbito de las heurísticas, el estudio de Rojas et al. (2019) expone que, de todas las heurísticas
disponibles, predominan los procedimientos de algoritmos y los multi-estado con 53% y 23%
respectivamente. De las demás heurísticas se pudo identificar al menos un artículo para cada una.
Según Vidal et al. (2013), desde el año 1960, un amplio número de heurísticas ha intentado proponer
soluciones de manera constructiva. Una de las características fundamentales de estas es que operan
de una manera “ávida”, produciendo así decisiones definitivas que no pueden ser revocadas
posteriormente. En otras palabras, su tendencia codiciosa no les permite visitar vecindades que
disminuyan la función objetivo.
Los algoritmos y procedimientos consisten en algoritmos clásicos como árboles binarios y “divide
and conquer” superpuestos, permitiendo crear híbridos de los mismos. El objetivo de toda heurística
radica en la determinación de un mínimo local, debido a la incapacidad de hallar la función óptima.
El funcionamiento de toda heurística depende del planteamiento del problema y consecuentemente,
de la conectividad presente. Los puntos de una función objetivo corresponden a los estados que esta
puede tomar. Del mismo modo, los vecindarios o vecindades de estos estados corresponden a los
posibles espacios a donde es posible trasladarse la solución desde este punto de partida. El
planteamiento del problema –que aglomera la manera de purgar el espacio factible, así como las
restricciones y variables de decisión– define la conectividad de los vecindarios y que tan fácil es
trasladarse por el espacio factible (Van Hentenryck, 2015).
Por otra parte, la heurística multi estado, también conocida como la heurística de mínimos y máximos,
busca evitar escanear el espacio de factibilidad, pero manteniendo una tendencia codiciosa. Esta
práctica inicia eligiendo la variable con mayor cantidad de violaciones en sus restricciones y
subsecuentemente, le asigna el valor que minimice estas restricciones (movimiento premeditado y
codicioso). Seguidamente, se selecciona otra variable al azar y se le asigna el valor que minimice sus
violaciones (movimiento aleatorio). Esta combinación entre movimientos aleatorios y premeditados
otorga mínimos locales efectivos y en un orden de convergencia lineal en muchas situaciones, lo cual
es impresionante (Vidal et al., 2013).
Tabla 5 Heurísticas del Problema de Almacenamiento por Porcentaje de Artículos (Rojas et al., 2019)
Tabla 6: Nomenclatura Heurísticas. (Rojas & al, 2019)
Abreviación Método
SA&P “Algorithms and Procedures”
MS “Multi Stage Procedures””
CBH “Class Based Heuristics”
RBH “Rollout Heuristics”
SEQ “Sequencing Procedures”
MPO “Multi-Product Optimization Heuristics”
GH “Greedy Heuristics
EH “Exchange Heuristics”
HH “Hierarchical Procedures”
Metaheurísticas:
Las metaheurísticas, al igual que las heurísticas, son implementadas cuando los modelos matemáticos
son muy difíciles de solucionar o no brindan el resultado adecuado en un tiempo de convergencia
razonable. El objetivo de las metaheurísticas radica en escapar de mínimos locales para evaluar otras
instancias y territorios de la función objetivo y así, determinar el mejor entre los visitados. Cabe
resaltar que no necesariamente determina el valor óptimo, sólo establece el mínimo local más efectivo
que se determinó probando varios estados de la función objetivo (Van Hentenryck, 2015).
En la literatura se encuentran dos tipos de metaheurísticas, las de búsqueda local y las de tendencia
evolutiva. Los algoritmos de única solución metaheurística buscan una solución cercana a la óptima
por medio del análisis particular y enfocado de cada solución. La búsqueda local se lleva a cabo por
medio de pruebas locales en el espacio de solución. Existen cuatro metaheurísticas muy conocidas
concentradas en la búsqueda local: método de búsqueda local optima (Local Optimal Search Method),
métodos de búsqueda aleatoria (Random Search), simulación recocida (Simulated Annealing) y
búsqueda tabú (Tabu search). De la revisión literaria se observa que tres de las cuatro metaheurísticas
más aplicadas pertenecen a la categoría de búsqueda local. No obstante, en el primer lugar, con mayor
respaldo académico, se encuentran la búsqueda tabú y el algoritmo genético, correspondientes a la
búsqueda local y a la diferencia evolutiva respectivamente.
Tabla 7: Metaheurísticas del Problema de Almacenamiento por Porcentaje de Artículos (Rojas et al., 2019)
Tabla 8: Nomenclatura Metaheurísticas. (Rojas et al., 2019)
Abreviación Método
TS “Tabu Search”
GA “Genetic Algorithm”
ILS “Local Iterated Search”
SA “Simulated Annealing”
AC “Ant Colony Optimization”
LS “Local Search”
ANN “Artificial Neutral Networks”
Búsqueda Tabú:
La técnica conocida como búsqueda tabú se encarga de llevar registro de los nodos visitados y, por
ende, de los estados de la función objetivo donde se ha estado. Así, aunque la función quiera seguir
su tendencia codiciosa y converger en un mínimo local, si este nodo ya ha sido visitado, será
considerado como tabú o prohibido, forzando al modelo a desplazarse a otras vecindades que, a
primera instancia, no consideraría (Wari & Wheihang, 2016).
Ilustración 6: Explicación Gráfica Búsqueda Tabu (Wari & Wheihang, 2016).
La imagen anterior ilustra el comportamiento convencional de una búsqueda tabú. El punto A tendrá
el impulso por desplazarse al punto B, un mínimo local de la función y subsecuentemente el valor
más bajo que detecta desde su vecindad. No obstante, si este valor convergente ya fue visitado, será
marcado como tabú, obligando a la función a desplazarse a un punto que incrementa la función de
minimización y que nunca sería visitado de otra manera. Seguir esta tendencia puede llevar a un
nuevo contexto de la función que, al no ser local, nunca había sido visitado y que puede incluso tener
nuevos mínimos locales que superan al actual (punto C).
La mayor crítica acerca de la búsqueda tabú es la necesidad de tener estructuras de datos que
conserven una lista tanto de puntos considerados prohibidos como los sus respectivos valores en la
función objetivo. En un problema donde se estudian miles de puntos y combinaciones discretas, el
gasto en memoria puede llegar a ser considerable. Sin embargo, existen soluciones como lo son listas
dinámicas y el almacenamiento de transiciones en lugar de estados.
Algoritmo Genético:
El algoritmo genético, introducido por Holland en los años 70, busca, por medio de los principios de
la genética y herencia de atributos, determinar soluciones alternativas factibles. Esta pertenece a las
metaheurísticas poblacionales (siendo la más popular de las mismas), como lo son “Ant Colony
Optimization” y “Particle Swarm Optimization”.
Dicho algoritmo inicia con la recolección de soluciones factibles y aleatorias, catalogadas como la
población inicial. Los parámetros de optimización son codificados en cromosomas, asociados a cada
miembro de la población parental. Seguidamente, se crean descendencias con características cruzadas
al generar interacciones entre miembros de dicha población. Finalmente, se evalúan las descendencias
y selecciona el mejor descendiente de esa generación, para seguidamente incluirlo en lo que será la
población de la siguiente generación (Lara, 2018).
Simulación Recocida (Simulated Annealing):
Esta metaheurística es una variación de la heurística conocida como metrópolis, la cual, establece que
un estado actual sólo será cambiado si el movimiento dentro de la vecindad mejora la función objetivo
(tendencia codiciosa). No obstante, aceptará un movimiento degradante con una probabilidad de
aceptación (Wari & Wheihang, 2016):
𝑃𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑑𝑎𝑑 𝑑𝑒 𝑎𝑐𝑒𝑝𝑡𝑎𝑐𝑖ó𝑛 = exp (−∆
𝑡)
∆= 𝑓(𝑛) − 𝑓(𝑠)
Donde n es el estado al que se quiere trasladar la función objetivo, s es el actual estado óptimo actual
(donde la función objetivo llega al valor mínima o máxima respectivamente), y t es una temperatura
estabilizadora. El objetivo de este planteamiento es sofocar las tendencias codiciosas que no permiten
investigar otras vecindades que podrían llevar a óptimos locales no descubiertos. Evidentemente,
entre mayor sea la temperatura, mayor será la posibilidad de aceptar un movimiento degradante y
subsecuentemente, estudiar otras posibilidades y estados de convergencia. El objetivo de esta
heurística es balancear t y ∆ de tal manera que se exploren otras posibilidades pero que se mantenga
suficiente tendencia codiciosa para aterrizar en un mínimo local, el objetivo de toda heurística (Van
Hentenryck, 2015).
La simulación recocida se encarga de aplicar esta heurística, pero generando variaciones planeadas
de temperatura. Así, obtiene el esperado balance entre ∆ 𝑦 𝑡 de manera dinámica. La idea clave
consiste en iniciar con una temperatura muy alta y explicar las posibilidades de la función. Esto es
básicamente un recorrido aleatorio ya que se aceptarán casi todos los movimientos, sean perjudiciales
o efectivos. Con el paso de las iteraciones, la temperatura irá enfriándose y disminuyendo,
aumentando continua y dinámicamente los estándares de aceptación y rechazando cada vez más
movimientos. Cuando la temperatura tiende a un valor muy bajo, se tiene una búsqueda local
convencional. Esta es una excelente manera de probar diferentes mínimos locales al purgar el espacio
en gran medida.
Búsqueda Iterativa Local (“Local Iterated search”):
Este procedimiento tiene un fundamento básico pero eficiente. Se trata de ejecutar búsqueda local
convencional desde diferentes puntos de partida. La característica más importante de esta
metaheurística radica en su facilidad de ser combinada con otros algoritmos y de ser reiniciada desde
diferentes estados.
El pseudocódigo de esta práctica se muestra a continuación.
• Reinicia en un estado de solución aleatorio.
• Desde este punto, determinar un mínimo local. Esta búsqueda es codiciosa, por lo que solo
se aceptan movimientos que disminuyan la función objetivo.
• Comparar el mínimo local encontrado con el considerado el mínimo global. Si es mejor
guardarlo y reemplazar el valor en la estructura de datos.
• Reiniciar.
Cabe resaltar que estos puntos de partida pueden ser aleatorios o predeterminados por medio de la
técnica conocida como conexión de poder. Estas soluciones sofisticadas fuerzan a los nuevos puntos
de partida a tomar antiguas soluciones entre sus consideraciones aleatorias, permitiendo en ciertos
casos, mejorar la calidad de la solución (Van Hentenryck, 2015).
Ilustración 7: Explicación Gráfica Búsqueda Iterativa (Wari & Wheihang, 2016) (Lara, 2018)
La ilustración 7 explica el procedimiento de la búsqueda local iterativa, donde se inicia en un punto
aleatorio y se determina un mínimo local desde este. Seguidamente, se reinicia el estado de la solución
en busca de un nuevo valor que supere al óptimo actual. Cabe resaltar que este procedimiento no
garantiza la determinación del óptimo global, la calidad de la solución depende de la aleatoriedad de
los puntos de partida.
Ilustración 8: Autores Recientes Metaheurísticas en Problema de Almacenamiento de Productos en Bodegas (Rojas et al.,
2019).
La ilustración anterior presenta los autores concernientes de la aplicación de metaheurísticas en el
problema de almacenamiento de productos en bodega. Yang et al. (2017) centraron su investigación
en la disminución del tiempo de asignación y secuencia por medio de una búsqueda tabú. Por su parte,
Kim & Smith (2012) utilizaron Recocido Simulado enfocado en el intercambio correlacional para
minimizar el tiempo de desplazamiento para la preparación de la orden. Por su parte, Pan et al. (2015)
aplicó un algoritmo genético para determinar el espacio correcto para cada producto y balancear carga
de trabajo.
Decisión del Modelo de Solución:
Para solucionar el problema de localización se presentan en la literatura más de siete diferentes
alternativas. No obstante, sólo tres de estas opciones cuentan con un respaldo bibliográfico extenso y
permiten explorar todo el espacio de búsqueda. Estas son modelos matemáticos, heurísticas y
metaheurísticas
En primera instancia, aunque los modelos matemáticos sean los más numerosos, sólo 12 de los 31
artículos presentes presentan un resultado más allá de un planteamiento. Asimismo, algunas de estas
soluciones se aplican en problemas donde el espacio disponible es exactamente igual al espacio de
ocupación de los productos, reduciendo significativamente la complejidad computacional de Np-duro
a Np. El proyecto en cuestión no puede trabajar sobre esta suposición.
Por su parte, las heurísticas, las cuales presentan un respaldo bibliográfico considerable, presentan
una complicación. Normalmente, estas herramientas tienen la tendencia a caer en óptimos locales y
estancarse. De estas complicaciones se crearon las metaheurísticas, las cuales pueden estudiar un
esquema más global, generando independencia del punto de partida. Desde inicios del 2000, las
metaheurísticas han opacado a las heurísticas en términos de aplicación, por su flexibilidad y
adaptabilidad. La siguiente afirmación es respaldada por una revisión literaria realizada por Yener y
Yazgan (2019), lo que lleva a descartar esta alternativa de solución.
A partir de las consideraciones anteriores se seleccionan las metaheurísticas por adaptabilidad a
diferentes campos, y por su posibilidad de resolver un problema Np-duro. Asimismo, dentro de estas
investigaciones de las metaheurísticas, se encuentran artículos que tratan problemas con cierta
similitud al planteado en este proyecto, como Ene et al. (2016) que maneja un algoritmo genético
para asignación de lotes de tamaño variable, utilizando así la clasificación de clase (muy similar a la
entrada de vuelos cada uno con su propia carga) o Chen y Li (2015), quienes clasifican sus productos
a partir de su tiempo de permanencia dentro de la bodega e incluyen dentro de la función objetivo los
periodos de entrada y salida de la bodega (consideración necesaria para la precisión de los periodos
de entrada de cada vuelo). En conclusión, se centrará la atención en los algoritmos genéticos y en la
búsqueda tabú (ya que entre todas las metaheurísticas utilizadas, estas representan el 50% de los
artículos encontrados). Se espera poder solucionar el problema desde estas dos perspectivas diferentes
y subsecuentemente, determinar la mejor al comparar sus funciones objetivo y tiempo de
convergencia.
Contexto General del Problema
Tabla 9: Restricciones y Consideraciones Problema Almacenamiento de Bodega
Estudio
Académico
Capacidad y
Condiciones de
Bodega
Periodos de
Permanencia
Lotes,
Asignación y
Ruteo
Clasificación de
Productos
Demanda, Ventas o
Rotación
Recursos Logísticos
(Equipos y
Trabajadores)
Pan et. al
(2015)
X X X X X
Chan et. al
(2011)
X X X X X
Chen et. al
(2010)
X
X
Ene et. al
(2016)
X X X X
Carlo &
Giraldo (2012)
X X X
Ene & Ozturk
(2012)
X X X
Yang et. al
(2015)
X X X
Yang et. al
(2017)
X X X X
Kulak &
Egemen
(2011)
X X X X
Chen & Li
(2015)
X X X
Caso Gate
Gourmet
X X X X X
La tabla anterior expone las restricciones generales que se presentan comúnmente en los problemas
de almacenamiento de bodega. Capacidad y Condiciones de Bodega hace relación a restricciones de
espacio o condiciones físicas de las bodegas, como zonas prohibidas, distancias mínimas de pasillo,
etc. Periodos de Permanencia se refiere a las restricciones que imposibilitan o regulan la permanencia
de los SKU por tiempos específicos. Por su parte, Clasificación de Productos consta de aquellas
restricciones donde las características específicas de los productos impactan los almacenamientos.
Las restricciones de Lotes, Asignación y Ruteo plantean restricciones a partir de la asignación de
producto en los espacios disponibles o de un ruteo específico en la recolección, ente otros. Demanda,
Ventas y Rotación plantea aquellas restricciones que reglamentan el almacenamiento a partir de las
demandas o tendencias de marketing de los productos. Finalmente, Recursos Logísticos exponen las
limitaciones que se presentan en la carga de trabajo, ya sea disponibilidad de equipos, horario de
trabajos, cantidad de trabajadores entre otros.
El problema tratado en este proyecto involucra cinco de estos tipos de restricciones: una limitación
en los espacios disponibles, la imposibilidad de reasignar un vuelo previamente asignado, un control
en los tiempos de permanencia de los vuelos y diferenciaciones tanto por aerolíneas y vuelos halal
(clasificación por clase y tipo), como por su carga en trolleys a almacenar (clasificación por
demanda). Esta combinación específica de restricciones plantea la necesidad de generar un modelo y
soluciones originales, no encontradas en la literatura.
8. MODELO MATEMÁTICO
Uno de los principales objetivos de este problema es determinar el horario de ingreso de las unidades
de carga que contienen los alimentos a la bodega para que permanezcan al menos cuatro horas
adentro. Esto conlleva a la utilización de una política de almacenamiento por duración de
permanencia o DOS (“Duration of Stay”). Junto a esta política, se recomienda también un sistema
S/R, “storage and retrieval”, configurado en modo DC, donde cada operario podrá hacer en un
recorrido el almacenamiento o recolección de un SKU, y existe la posibilidad de entrelazar la
recolección de una carga con el almacenamiento de otra en una misma ruta (Chen et al., 2010). Este
modelo asume las siguientes suposiciones:
• El tiempo de posicionamiento/recolección de cada unidad de carga es independiente del
tiempo de desplazamiento.
• Los tiempos de desplazamiento son pequeños en relación con los tiempos de duración de las
unidades de carga.
• Todos los trolleys o unidades de carga requieren del mismo espacio (Chen et al., 2010).
• Los operarios de la bodega pueden operar en ciclos sencillos (sólo almacenamiento o
recolección) o en ciclos duales (los dos respectivamente). Asimismo, sólo pueden cargar una
unidad de carga simultáneamente (Chen et al., 2010).
El funcionamiento de los modelos de optimización discreta basados en diferenciación por
permanencia DOS dentro de la bodega, se fundamentan en la utilización de periodos de tiempo t y
variables binarias con el fin de controlar la entrada y/o salida de estos SKU a la bodega. Chen y Li en
su artículo del 2015, “Sequencing the Storages and Retrievals for Flow Rack Automated Storage and
Retrieval Systems with Duration-of-Stay Storage Policy” plantean un modelo que busca minimizar
el tiempo de desplazamiento y permanencia en la bodega a través de la definición de los periodos de
entrada y salida de los SKU, así como su ubicación. Este modelo será combinado con el modelo
planteado por Chen et al., en 2010, llamado “The Storage Location Assignment and Interleaving
Problem in an Automated Storage/Retrieval System With Shared Storage”, donde se establece la
capacidad de generar ahorros al coordinar la entrada de un grupo de productos con la salida de otro.
Cabe resaltar que como se planteó anteriormente, cada operador sólo puede cargar con un producto
(en este caso trolleys de comida) a la vez, lo que condiciona a que un producto de entrada sólo pueda
ser coordinado por uno de salida, así que la coordinación máxima entre dos lotes de producto de
diferente carga será la cantidad del lote más pequeño.
Ilustración 9: La Coordinación de Dos Trolleys en un Periodo Específico
Al coordinar la entrada de un trolley con la salida de otro, es posible ahorrar una distancia
proporcional a la suma entre la distancia de salida del trolley que se encuentra ingresando y la
distancia de entrada del trolley que se encuentra saliendo de la bodega, menos la distancia entre la
ubicación en la que fueron posicionados los dos trolleys en cuestión. A continuación, se presenta el
cálculo del ahorro para los dos trolleys coordinados en la imagen anterior. Se entrelaza la entrada del
carro 2 con la salida del carro 1.
𝐷𝑒𝑠𝑝𝑙𝑎𝑧𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑇𝑜𝑡𝑎𝑙 𝑆𝑖𝑛 𝐶𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑐𝑖ó𝑛 = 𝐷𝐸1 + 𝐷𝑆1 + 𝐷𝐸2 + 𝐷𝑆2
𝐷𝑒𝑠𝑝𝑙𝑎𝑧𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑇𝑜𝑡𝑎𝑙 𝐶𝑜𝑛 𝐶𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑐𝑖ó𝑛 = 𝐷𝐸2 + 𝐷12 + 𝐷𝑆1
𝐴ℎ𝑜𝑟𝑟𝑜 = 𝐷𝑆2 + 𝐷𝐸1 − 𝐷12
Donde:
• DE representa la distancia desde la entrada.
• 𝐷𝑆 representa la distancia de salida.
• 𝐷12 representa la distancia entre los dos puntos donde se encuentran ubicados los lotes de comida
entrelazados.
El problema es presentado como un modelo de optimización combinatoria:
Conjuntos, Subconjuntos y notaciones: 𝑁: 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑜 𝑡𝑟𝑜𝑙𝑙𝑒𝑦𝑠 𝑎 𝑎𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑟 ( 𝑛𝑜𝑡𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑖, 𝑗, 𝑚)
𝑉𝐻𝑎𝑙𝑎𝑙: 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑁 𝑞𝑢𝑒 𝑖𝑛𝑐𝑙𝑢𝑦𝑒 𝑙𝑎𝑠 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑎 𝑣𝑢𝑒𝑙𝑜𝑠 𝐻𝑎𝑙𝑎𝑙 ( 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑖) 𝑅𝑖: 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑁 𝑐𝑜𝑚𝑝𝑢𝑒𝑠𝑡𝑜 𝑝𝑜𝑟 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑚 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑢𝑒𝑑𝑒𝑛 𝑎𝑔𝑟𝑢𝑝𝑎𝑟 𝑐𝑜𝑛 𝑒𝑙 𝑎𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑖 𝑒𝑛 𝑚𝑜𝑣𝑖𝑚𝑖𝑒𝑛𝑡𝑜𝑠 𝑑𝑢𝑎𝑙𝑒𝑠(𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑚)
𝑆𝑚: 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑁 𝑐𝑜𝑚𝑝𝑢𝑒𝑠𝑡𝑜 𝑝𝑜𝑟 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑖 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑢𝑒𝑑𝑒𝑛 𝑎𝑔𝑟𝑢𝑝𝑎𝑟 𝑐𝑜𝑛𝑙𝑎 𝑟𝑒𝑐𝑜𝑙𝑒𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑚 𝑒𝑛 𝑚𝑜𝑣𝑖𝑚𝑖𝑒𝑛𝑡𝑜𝑠 𝑑𝑢𝑎𝑙𝑒𝑠( 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑖) 𝐾: 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑙𝑜𝑐𝑎𝑙𝑖𝑧𝑎𝑐𝑖ó𝑛𝑒𝑠 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒𝑠 𝑎 𝑙𝑙𝑒𝑛𝑎𝑟 ( 𝑛𝑜𝑡𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑘, 𝑘´)
ℎ𝑎𝑙𝑎𝑙: 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝐾 𝑢𝑏𝑖𝑐𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒𝑠 𝑢𝑛𝑖𝑐𝑎𝑚𝑒𝑛𝑡𝑒 𝑝𝑎𝑟𝑎 𝑣𝑢𝑒𝑙𝑜𝑠 𝐻𝑎𝑙𝑎𝑙 ( 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑘)
𝑃𝑟𝑜𝑏: 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑙𝑜𝑐𝑎𝑙𝑖𝑧𝑎𝑐𝑖ó𝑛𝑒𝑠 𝑝𝑟𝑜ℎ𝑖𝑏𝑖𝑑𝑎𝑠 ( 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑓)
𝑉: 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑣𝑢𝑒𝑙𝑜𝑠 𝑎 𝑠𝑢𝑝𝑙𝑖𝑟 ( 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑣)
𝑇: 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑠 𝑒𝑛 𝑒𝑙 ℎ𝑜𝑟𝑖𝑧𝑜𝑛𝑡𝑒 𝑑𝑒 𝑝𝑙𝑎𝑛𝑒𝑎𝑐𝑖ó𝑛 (𝑠𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎𝑟á 𝑙𝑎 𝑛𝑜𝑡𝑎𝑐𝑖ó𝑛 𝑡)
Parámetros:
𝑐𝑘: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑑𝑒𝑠𝑝𝑙𝑎𝑧𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑑𝑒 𝑏𝑜𝑑𝑒𝑔𝑎 𝑎 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑘
𝑐𝑘𝑘´: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑑𝑒𝑠𝑝𝑙𝑎𝑧𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑘 𝑎 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑘´ 𝑤𝑖𝑗𝑡 = {
1 𝑠𝑖 𝑒𝑙 𝑖𝑛𝑔𝑟𝑒𝑠𝑜 𝑑𝑒 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑝𝑢𝑒𝑑𝑒 𝑠𝑒𝑟 𝑎𝑔𝑟𝑢𝑝𝑎𝑑𝑎 𝑐𝑜𝑛 𝑙𝑎 𝑟𝑒𝑐𝑜𝑙𝑒𝑐𝑐𝑖ó𝑛 𝑑𝑒 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑗 𝑒𝑛 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡0 𝑑. 𝑙. 𝑐
𝐵𝑖𝑡 = {1 𝑠𝑖 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑎𝑏𝑎𝑛𝑑𝑜𝑛𝑎 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡 (𝑏𝑖 = 𝑡)
0 𝑑. 𝑙. 𝑐
𝑦𝑖𝑘𝑡 = {1 𝑠𝑖 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑒𝑠 𝑟𝑒𝑡𝑖𝑟𝑎𝑑𝑎 𝑑𝑒 𝑙𝑎 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑘 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡
0 𝑑. 𝑙. 𝑐
𝑛𝑖𝑙𝑣𝑡 = {1𝑠𝑖 𝑙𝑎 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑦 𝑙𝑎 𝑐𝑎𝑟𝑔𝑎 𝑙 𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑒𝑛 𝑎𝑙 𝑚𝑖𝑠𝑚𝑜 𝑣𝑢𝑒𝑙𝑜 𝑣 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡
0 𝑑. 𝑙. 𝑐
Variables de decisión:
𝑥𝑖𝑘𝑡 = {1 𝑠𝑖 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑒𝑠 𝑎𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑑𝑎 𝑑𝑒 𝑙𝑎 𝑢𝑏𝑖𝑐𝑎𝑐𝑖ó𝑛 𝑘 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡
0 𝑑. 𝑙. 𝑐
𝐴𝑖𝑡 = {1 𝑠𝑖 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑑𝑒 𝑐𝑎𝑟𝑔𝑎 𝑖 𝑖𝑛𝑔𝑟𝑒𝑠𝑎 𝑎 𝑙𝑎 𝑏𝑜𝑑𝑒𝑔𝑎 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡 (𝑎𝑖 = 𝑡)
0 𝑑. 𝑙. 𝑐
𝑢𝑖𝑚𝑡𝑘𝑘´ = {1 𝑠𝑖 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑎 𝑎𝑙𝑚𝑎𝑐𝑒𝑛𝑎𝑟 𝑖 𝑒𝑠 𝑎𝑔𝑟𝑢𝑝𝑎𝑔𝑎 𝑐𝑜𝑛 𝑙𝑎 𝑢𝑛𝑖𝑑𝑎𝑑 𝑎 𝑟𝑒𝑐𝑜𝑙𝑒𝑐𝑡𝑎𝑟 𝑚 𝑒𝑛 𝑒𝑙 𝑝𝑒𝑟𝑖𝑜𝑑𝑜 𝑡
0 𝑑. 𝑙. 𝑐
Cabe resaltar que k y k´ corresponden a las ubicaciones de i y m respectivamente. La agrupación
significa que el tiempo de salida de m corresponde al tiempo de entrada de i.
Función Objetivo:
min 𝑍 = ∑ ∑ ∑((2𝑥𝑖𝑘𝑡 ∗ 𝐴𝑖𝑡 ∗ 𝑐𝑘) + (2𝑦𝑖𝑘𝑡 ∗ 𝐵𝑖𝑡 ∗ 𝑐𝑘))
𝑇
𝑡=0
𝐾
𝑘=1
𝑁
𝑖=1
− ∑ ∑ ∑ ∑ 𝑢𝑖𝑚𝑡𝑘𝑘´
𝐾
𝑘,𝑘´=1
𝑇
𝑡=0𝑚∈𝑅𝑖
𝑁
𝑖=1
(𝑐𝑘 − 𝑐𝑘𝑘´ + 𝑐𝑘´) (1)
Sujeto a:
∑ ∑ 𝑥𝑖𝑘𝑡 ∗
𝑇
𝑡=0
𝐾
𝑘=1
𝐴𝑖𝑡 = 1 ∀𝑖 𝜖𝑁 (2)
∑ ∑ 𝑦𝑖𝑘𝑡 ∗
𝑇
𝑡=0
𝐾
𝑘=1
𝐵𝑖𝑡 = 1 ∀𝑖 𝜖𝑁 (3)
12 ≥ 𝑏𝑖 − 𝑎𝑖 ≥ 8 ∀𝑖 𝜖𝑁 (4)
∑ 𝑥𝑖𝑘𝑡 = 0 ∀𝑖 𝜖𝑁 , 𝑡 ∈ [0, 𝑎𝑖) ∪ (𝑏𝑖, 𝑇]
𝐾
𝑘=1
(5)
∑ 𝑦𝑖𝑘𝑡 = 0 ∀𝑖 𝜖𝑁 , 𝑡 ∈ [0, 𝑎𝑖) ∪ (𝑏𝑖, 𝑇]
𝐾
𝑘=1
(6)
𝑢𝑖𝑚𝑡𝑘𝑘´, 𝐵𝑖𝑡 , 𝐴𝑖𝑡 , 𝑦𝑖𝑘𝑡 , 𝑥𝑖𝑘𝑡 ∈ {0,1} (7)
∑ ∑ (
𝑓∈𝑝𝑟𝑜𝑏
𝑇
𝑡=0
𝑥𝑖𝑓𝑡 + 𝑦𝑖𝑓𝑡) = 0 ∀𝑖 𝜖𝑁 (8)
∑ ∑ (
𝑘∈ℎ𝑎𝑙𝑎𝑙
𝑇
𝑡=0
𝑥𝑖𝑘𝑡 + 𝑦𝑖𝑘𝑡) = 0 ∀𝑖 ∉ 𝑉ℎ𝑎𝑙𝑎𝑙 (9)
∑ ∑ 𝑥𝑖𝑘𝑡
𝑇
𝑡=0
𝐾
𝑘=1
= 1 ∀𝑖 𝜖𝑁 (10)
∑ ∑ 𝑦𝑖𝑘𝑡
𝑇
𝑡=0
𝐾
𝑘=1
= 1 ∀𝑖 𝜖𝑁 (11)
∑ ∑ ∑ 𝑢𝑖𝑚𝑡𝑘𝑘´
𝐾
𝑘,𝑘´=1𝑚∈𝑅𝑖
𝑇
𝑡=0
≤ 1 ∀𝑖 ∈ 𝑁 (12)
∑ ∑ ∑ 𝑢𝑖𝑚𝑡𝑘𝑘´
𝐾
𝑘,𝑘´=1𝑖∈𝑆𝑚
𝑇
𝑡=0
≤ 1 ∀𝑚 ∈ 𝑁 (13)
∑ 𝑢𝑖𝑚𝑡𝑘𝑘
𝑇
𝑡=0
´ ≤ 1
2∑(𝑥𝑖𝑘𝑡 + 𝑥𝑚𝑘𝑡)
𝑇
𝑡=0
∀𝑖 ∈ 𝑁, 𝑚 ∈ 𝑅𝑖, 𝑘, 𝑘´ ∈ 𝐾 (14)
∑ 𝑥𝑖𝑘𝑡 + 𝑥𝑗𝑘𝑡
𝑇
𝑡=0
≤ 1 + ∑ 𝑤𝑖𝑗𝑡 ∀𝑖, 𝑗 ∈ 𝑁, 𝑖 < 𝑗, 𝑘, ∈ 𝐾
𝑇
𝑡=0
(15)
𝑛𝑖(𝑖−1)𝑣𝑡 + 𝑛𝑖(𝑖+1)𝑘𝑡 ≥ 1 ∀𝑖, ∈ 𝑁, ∀𝑡, ∈ 𝑇 (16)
∑ ∑ ∑ 𝑥𝑖𝑘𝑡 ≤ |𝐾|
𝑇
𝑡=0
𝐾
𝑘=1
𝑁
𝑖=1
(17)
La función objetivo (1) busca minimizar el desplazamiento total de desplazamiento dentro de la
bodega. El primer tiempo corresponde a los tiempos de depósito y recolección de las unidades de
carga (se multiplica por dos para generar un recorrido ida/vuelta completa). Por otro lado, el segundo
término disminuye este tiempo al restar los ahorros logrados con las agrupaciones de almacenamiento
y recolección de unidades de carga. Las restricciones (2) y (3) establecen que el cargamento i sea
almacenado y retirado en los periodos 𝑎𝑖 y 𝑏𝑖 respectivamente. La restricción (4) fuerza a cada unidad
de carga a permanecer un mínimo de ocho periodos (cuatro horas) y un máximo de seis horas (12
periodos) dentro de la cámara. Por otro lado, las restricciones (5) y (6) evitan la posibilidad de que
las unidades de carga entren o salgan en tiempos inferiores a 𝑎𝑖 o superiores a 𝑏𝑖 respectivamente.
Por su parte, la restricción (7) define el comportamiento binario de las variables de decisión y las
restricciones (8) y (9) definen la imposibilidad de las unidades de carga de almacenarse en las zonas
prohibidas. En la octava restricción, en el subconjunto de localizaciones prohibidas no pueden ser
almacenadas unidades de carga. Algo similar sucede con la restricción nueve, excepto que, en esta,
las unidades de carga pertenecientes al subconjunto “VHalal” pueden utilizar estos espacios a su
gusto. Las restricciones (10) y (11) indican que cada unidad de carga debe ser
almacenada/recolectada sólo una vez en todo el horizonte de planeación. Asimismo, las restricciones
(12) y (13) indican que cada almacenamiento debe ser emparejado máximo con sólo un procedimiento
de recolección y viceversa. La restricción (14) menciona que dos unidades sólo pueden ser agrupadas
si i está por ser almacenada y m fue almacenada al menos cuatro horas antes. Finalmente, la restricción
(15) se asegura que, si 𝑤𝑖𝑗 es 0, las unidades de carga i y j>i, no se almacenen en la misma ubicación,
la restricción (17) se asegura que no se supere la capacidad de la bodega (número de ubicaciones
disponibles) y finalmente, la restricción (16) obliga a que al menos una de las cargas, anterior o
posterior, pertenezcan al mismo vuelo.
Tanto Han et al. (1987) como Chen et al. (2011) realizaron modelos secuenciales AS/RS con carga
aleatoria, utilizando modelos de clase y DOS (“duration of stay”) respetivamente. De este
planteamiento, ambos estudios concluyeron que el problema es muy complejo para realizar la
búsqueda del óptimo global, lo que los llevo a recurrir a heurísticas y búsqueda tabú respetivamente.
Han et al (1987) incluso hace la afirmación de que un problema de sólo 15 unidades de carga con
mismo número de espacios disponibles sin restricciones de clase puede tomar hasta 15 horas. El
problema presentado anteriormente consta de 17 restricciones, haciéndolo mucho más complejo que
los presentados en los artículos mencionados, lo que soporta la búsqueda de la solución por medio de
metaheurísticas. En el presente estudio se pondrá a prueba el modelo AS/RS en secuencia dual
(permitiendo tanto almacenamiento como recolección en un solo recorrido), generando una
diferenciación entre vuelos tanto por DOS (duración de permanencia), como por clase (la aerolínea a
la que pertenecen).
9. RESTRUCTURACIÓN ÓPTIMA DE LAS BODEGAS
El requerimiento de mantener los carros pertenecientes a cada vuelo juntos, impide al menos
computacionalmente, la capacidad de tratar cada carro como una unidad, lo que lleva a la proposición
de dividir la bodega en zonas, donde el objetivo de las metaurísticas será definir el área perteneciente
a cada vuelo, vigilando que no se violen las reglamentaciones planteadas (espacios prohibidos, rango
de horarios, vuelos halal, capacidad máxima de cada área en el horizonte de planeación etc.). No
obstante, inicialmente se debe determinar una configuración de la bodega que sea funcional y respete
las normas establecidas. Para este proyecto se tendrán en cuenta tres bodegas: Bogotá, Santiago de
Chile y Lima, cada una con sus propias condiciones y necesidades, como se expone en la siguiente
tabla.
Tabla 10: Restricciones de Cada Bodega por Ciudad
Ciudad Bogotá Santiago Lima
Espacios Prohibidos Si (Difusores) No Si (Difusores)
Vuelos Halal Si Si No
Restricciones de
Espacio
Si (20 cm entre filas y
paredes)
No No
Pasillo Mínimo 1.00 m 1.00 m 1.00 m
Dos de las tres bodegas cuentan con vuelos Halal, siendo Lima la excepción. Asimismo, dos de las
tres opciones tiene difusores, los cuales son constituidos como áreas prohibidas. En el caso de
Santiago, el aire frio es liberado del techo, permitiendo el uso total del espacio. Finalmente, Bogotá
se rige por unas políticas antidroga, por lo que entre cada fila de trolleys, así como con las paredes,
debe haber un espacio de al menos 20 cm para los caninos detectores.
Ilustración 10: Posibles Configuraciones de Bodega (Durik y Opetuk,2012)
Aparte de reconfigurar las bodegas con el objetivo de cumplir las reglamentaciones necesarias, se
requiere determinar las características pertenecientes a una configuración de bodega óptima y
seguidamente, aplicarlas a las cámaras en cuestión. Durik y Opetuk (2012), realizan un estudio
comparativo entre diferentes configuraciones de bodega con tal de afirmar cuál de estas opciones
brinda la menor distancia de almacenamiento y recolección promedio por medio de simulaciones.
Entre las configuraciones se encuentra el diseño tradicional, el layout con pasillo cruzado (tanto
perpendicular como paralelo a los puntos de entrada y salida) el layout de espina de pescado, y la
configuración Chevron. Los resultados de la simulación mostraron que la configuración de pasillo
cruzado perpendicular a los puntos de entrada es, dentro las opciones, la más optima, al permitir una
gran variedad de opciones de ruteo dentro de la bodega, seguida por la configuración de espina de
pescado. Esta afirmación fue soportada por Mahmut Tutam y Jhon White (2019) donde afirma que
para todos los recorridos en modalidad dual DC (como se esperan que funcionen los ahorros) en el
sistema de almacenamiento y recolección (sistema S/R), la configuración cruzada muestra su
superioridad al minimizar en mayor medida el desplazamiento y el tiempo dentro de la bodega. Se
concluye también que los mejores resultados se obtienen cuando los elementos se ubican
paralelamente a las paredes.
Ilustración 11: Configuraciones Clásicas (Tutam y White,2019).
Tabla 11:Resultados Simulados del Desplazamiento Promedio Dentro de la Bodega en Metros (Durik y Opetuk,2012)
Finalmente, Omer Ozturkoglu y Deniz Hoser (2019), con el objetivo de disminuir el desplazamiento
de la recolección de producto en las bodegas, proponen variaciones discretas de la configuración
cruzada con el pasillo principal posicionado perpendicularmente a las entradas. Entre sus hallazgos,
se encuentra que las hileras divididas a la mitad o a tres cuartos de su longitud exponen los
comportamientos más eficientes (la diferencia entre estas depende de la cantidad de entradas y
salidas) y además, que la organización de dos hileras de SKUs entre pasillos es lo más recomendado
con tal de no generar desplazamientos innecesarios.
Teniendo en consideración estos hallazgos, se procede a restructurar las bodegas concernientes en
este estudio. Las configuraciones actualmente utilizadas, aunque funcionales, violan las
jurisdicciones legales de almacenamiento o, con tal de maximizar el número de espacios disponibles,
no tienen en consideración el tiempo de desplazamiento de las bodegas.
En el caso de Bogotá, actualmente se utilizan pasillos de 70 centímetros (30 centímetros menos de
los mínimos legales) y se ubican deliberadamente trolleys debajo de los difusores. Además, la gran
mayoría de la bodega tiene una configuración cruzada paralela, lo que perjudica tanto el
desplazamiento general como la optimización del espacio disponible. La configuración actual cuenta
con una disponibilidad total de 495 trolleys completos.
Ilustración 12: Configuración Actual en la Cámara de Bogotá (Capacidad de 495 Trolleys Completos)
Ilustración 13: Configuración Propuesta para la Cámara de Bogotá (Capacidad de 470 Trolleys Completos)
Teniendo en cuenta las consideraciones, se aplicó la configuración cruzada perpendicular en toda la
bodega, restringiendo el espacio de las columnas y difusores. Del mismo modo, se establecieron
pasillos perpendiculares de 1 metro y paralelos de 2 metros, estos últimos con el objetivo de mejorar
considerablemente el desplazamiento en las aristas. Entre cada fila de carros, se encuentra una
distancia de 20 cm, al igual que las paredes. Esta nueva organización otorga una disponibilidad de
470 trolleys, lo que llevó a una disminución de espacios del 5.16 %.
En el caso de Lima, la configuración actual cuenta con pasillos de 80 cm, la utilización de espacios
prohibidos, y tres hileras de trolleys distanciadas por sólo 20 cm. Esto no es óptimo, ya que incrementa
tanto el desplazamiento como el tiempo de permanencia en la bodega al complicar la interacción con
la hilera del medio (Ozturkoglu & Hoser, 2019). Para llegar a esta es necesario manipular las otras
dos de los extremos.
Ilustración 14: Configuración Actual en la Cámara de Lima (Capacidad de 341 Trolleys Completos)
Ilustración 15: Configuración Propuesta para la Cámara de Lima (Capacidad de 309 Trolleys)
A continuación, se presenta la nueva configuración luego de ajustar la distancia de los pasillos y
eliminar la hilera central. Al no requerirse una planeación antidroga, se tiene una distancia entre
hileras y con la pared de 10 cm. La hilera ya se encontraba en configuración cruzada perpendicular,
por lo que no se necesitaron cambios posteriores. La nueva propuesta tiene una disponibilidad total
de 309 trolleys luego de restringir los espacios debajo de los rociadores. Esto es una disminución de
11.77% en relación con la configuración anterior.
Finalmente, en el caso de Santiago de Chile ya se cumplían los lineamientos básicos legales del
espacio como lo son pasillos y distancias. El único ajusto necesario fue encargarse del área triangular
en la esquina izquierda inferior. Como plantean Durik y Opetuk (2012), la configuración óptima
consta de carros paralelos a las paredes, lo que llevo a este posicionamiento. Seguidamente, se
evaluaron diferentes disposiciones en el resto de la zona con el fin de encontrar el mejor balance entre
el máximo número de carros y menor cantidad de desplazamiento lo que llevó a la configuración
mostrada a continuación. Esta propuesta cuenta con un total de 421 trolleys.
Ilustración 16: Configuración Actual en la Cámara de Santiago
Ilustración 17:Configuración Propuesta para la Cámara de Santiago (Capacidad de 421 Trolleys).
10. ALGORITMOS DE SOLUCIÓN
Previo a realizar la explicación de la búsqueda tabú y del algoritmo genético, se explicarán las
funciones que se utilizarán durante la ejecución de las metaheurísticas. Junto con las entradas del
modelo como vuelos con su respectiva carga y periodo de salida de la bodega (entre 0 y 47, siendo 0
las 0:00 horas cuando comienza el día y 47 las 23:30, el último periodo del día), se debe ingresar para
cada vuelo un área y un periodo de entrada. Se recuerda que estos periodos de tiempo serán
diferenciados por intervalos de media hora. Un ejemplo de estas entradas es evidenciado en la
siguiente tabla.
Tabla 12: Información de Entrada
Flight Trolleys Halal Flight Tout Tin Areas
81 15 0 0 -8 A
0633 4 0 0 -8 A
2779 4 0 0 -8 A
0074 8 0 8 0 B
0007 5 0 9 1 C
2110 14 0 10 2 D
0049 6 0 11 3 E
0531 8 0 12 4 F
2429 10 0 14 6 G
0126 5 0 15 7 H
1630 6 0 18 10 I
0138 5 0 18 10 J
A partir de la información de ingreso, se tomarán las dos últimas columnas que contienen los periodos
de entrada, así como de la asignación de posicionamiento para cada vuelo. Estas columnas serán
adaptadas a listas o cromosomas (como se muestra en la siguiente figura), las cuales, serán alteradas
en cada iteración de las metaheurísticas. La solución inicial o configuración default para los periodos
de entrada, será exactamente ocho periodos menos a los periodos de salida (el límite inferior de la
restricción).
Ilustración 18: Cromosomas Representantes de la Solución
Como se mencionó anteriormente, existe una imposibilidad de tratar cada trolley como unidad de
carga independiente. Se manipularían cromosomas de más de 650 alelos y computacionalmente,
considerando la restricción de que las cargas de un mismo vuelo deben ser almacenadas juntas para
su fácil manipulación, el gasto sería considerable. Esto llevó a la decisión de dividir la bodega en
zonas de tamaño variable y asignar los vuelos a dichas zonas, como muestra el cromosoma 2 de la
ilustración 18. El trabajo de las herramientas de solución consistirá en trasladar los vuelos a diferentes
zonas y alterar continuamente sus periodos de entrada, con el fin de minimizar el desplazamiento total
de almacenamiento y recolección diario en la bodega. A continuación, se expone el algoritmo
diseñado para determinar las zonas en las que las bodegas serán divididas, así como sus respectivas
capacidades.
Algoritmo Asignación de Áreas:
Para la realización de las metaurísticas y el almacenamiento de cargas del mismo vuelo, se debe
realizar la división de la bodega en zonas (cada una con su propia capacidad máxima) una vez
teniendo la configuración funcional y reglamentada. En la división de zonas se evidencian diferentes
tendencias. Para la realización de su algoritmo genético con el objetivo de almacenar respuestas en la
industria automovilística, Seval Ene y Nuzel Ozturk (2012) dividen su bodega en productos a partir
de un factor de peso 𝑤𝑖, definido a partir de su espacio y su demanda. Por su parte, Chao et al (2015)
dividen su bodega “pick and pass” en zonas iguales, todas con la misma capacidad y espacio de
ocupación. Probablemente, ambas aplicaciones tendrían utilidad en este problema, no obstante, no se
tiene conocimiento de en qué cantidad dividir las zonas considerando el mismo tamaño, y no es
recomendable generar una zona para cada vuelo ya que esto incrementaría considerablemente el gasto
computacional. Del mismo modo, tener muy pocas áreas haría el problema irrelevante. Teniendo todo
lo anterior en consideración, se diseñó del siguiente algoritmo de asignación, cuyos objetivos son:
• Definir el número de áreas necesarias para obtener una solución factible con la configuración
default de los periodos de entrada (periodos de salida -8).
• Que todos los vuelos puedan asignarse al menos un área.
• Que el horizonte de planeación (el día en cuestión) tenga factibilidad, es decir que en ningún
momento del día la capacidad de ninguna zona sea superada para la solución inicial de
periodos de entrada.
El algoritmo en cuestión iterará sobre todos los vuelos de la información de entrada (incluyendo los
periodos de entrada) y les asignará un área, cuya capacidad máxima será la carga de este vuelo, en
caso de que las previamente establecidas no puedan recibirlo. Finalmente, una vez exista un área que
pueda recibir todos los vuelos, los espacios sobrantes, no necesarios para asegurar factibilidad con
los periodos de entrada default, serán asignados a las áreas creadas más pequeñas en los tamaños más
comunes entre la carga de los vuelos. Esto con el objetivo de aumentar la probabilidad de las áreas
de llenarse a tope.
El procedimiento del algoritmo es el siguiente:
Paso 1: Definir la función HORIZON que genera la matriz del horizonte de planeación (48 X número
de áreas), la función FACTIBILITY que prueba la factibilidad de esta matriz y la función
FREQUENCY que realiza un diccionario teniendo en cuenta la frecuencia del número de trolleys por
cada vuelo, similar a un histograma. Las primeras dos funciones serán explicadas a fondo
posteriormente.
Paso 2: Recibir como entrada la totalidad de los vuelos del día, sus horarios y respectiva cantidad de
trolleys. Seguidamente, dividir esta entrada en dos a partir del número de áreas, los que son superiores
a la media y los que son inferiores. Cada mitad será almacenada en un data frame pandas, organizadas
de mayor número de trolleys a menor (“upper_df” y “lower_df” respectivamente).
Paso 3: Definir una variable “max_spaces” con la capacidad de la bodega luego de la reconfiguración.
Paso 4: Iniciar la inspección con la mitad superior y crear un área con el mismo número de trolleys
del primer vuelo (este es el vuelo con mayor número de carros de todo el día).
Paso 5: Para el resto de los vuelos de la mitad superior, recorrerlos uno a uno adicionándolos a un
marco vacío (“object1_df”) e inspeccionando este último, observando si los vuelos almacenados
pueden estar en las áreas existentes sin generar infactibilidad. En caso de que no, crear una nueva
área, tomando como su capacidad máxima la carga de este vuelo. Guardar todas las áreas creadas en
una lista junto con su capacidad. Para esto se utilizan las funciones HORIZON y FACTIBILITY.
Paso 6: Repetir los pasos 4 y 5 con la mitad inferior (el marco vacío se llamará “object2_df”).
Paso 7: Obtener una cantidad promedio de áreas a partir de la suma de las dos listas establecidas. De
esta manera, se tomarán todas las áreas de la mitad superior y el número necesario de la mitad inferior
para cumplir con este promedio (a esto se le llamará “real_zones”).
Paso 8: Sumarle la capacidad de las áreas sobrantes que no se utilizaron a las áreas con menor
capacidad para cumplir factibilidad. En este punto, la suma de las capacidades de las áreas que
finalmente sí se establecieron, es el número mínimo de espacios con tal de cumplir factibilidad con
los horarios de entrada default.
Paso 9: Obtener la resta entre “max_spaces” y la suma de todas las áreas creadas, esto dará el número
de espacios de la bodega sin asignar a ninguna área, los sobrantes que no son fundamentalmente
necesarios con los periodos de entrada default.
Paso 10: Utilizar la función FREQUENCY con la mitad inferior para obtener un diccionario de las
frecuencias de la cantidad de trolleys por vuelo (“frequ”), dando la frecuencia de cargas de los vuelos.
Seguidamente a partir de esta frecuencia, dividir el espacio sobrante no asignado, aún de la bodega,
en estas cantidades de mayor a menor frecuencia por su porcentaje en el total de frecuencias.
Paso 11: Finalmente, recorrer este diccionario y sumar en términos de las cantidades de los vuelos
planteados a la que en ese momento sea el área más pequeña. Esto permitirá tener áreas de tamaño
similar, reduciendo las diferencias entre las mismas.
El siguiente diagrama de flujo expone el procedimiento detallado del algoritmo de asignación de
áreas, donde la línea roja representa el seguimiento principal, mientras las líneas negras exponen
bucles, recorridos y condicionales.
Ilustración 19: Diagrama de Flujo Algoritmo Asignación de Áreas
Función para la realización del horizonte de planeación:
Esta función genera el horizonte de planeación a partir del “data frame” de entrada. Esta matriz tiene
dimensiones de 48 x número de áreas. El día es dividido en periodos de 30 minutos como ya se había
establecido.
Paso 1: Crear un data frame de 48 por número de áreas, cuyo índice será el número del periodo y
sus columnas sean las zonas de la bodega. Iniciar este marco de datos en 0.
Paso 2: Hacer un doble recorrido sobre este nueva data frame y sobre cada vuelo de la información
de entrada. Básicamente por cada periodo de tiempo, recorrer todos los vuelos.
Paso 3: Si en el rango creado entre el periodo de entrada y el periodo de salida del vuelo se encuentra
el periodo en cuestión, sumarle la cantidad de trolleys de ese vuelo a su respectiva área. De lo
contrario continuar.
Función de Prueba de Factibilidad:
Esta función se ejecuta en conjunto con la anterior y sirve para determinar la factibilidad de la
solución. Cabe resaltar que, tanto en el algoritmo genético como en la búsqueda tabú, si se encuentra
una sola infactibilidad, la función está configurada para romper los recorridos y regresar falso
automáticamente.
Paso 1: Se realiza una doble iteración sobre el marco de datos creado en la función anterior. Se itera
cada periodo y para cada periodo el número total de áreas. Esto es un ciclo anidado.
Paso 2: Se compara el número de trolleys que se encuentran en cada área en cada periodo a su
respetiva capacidad máxima.
Paso 3: Si en algún periodo, algún área supera su capacidad máxima, regresar falso. De lo contrario
regresar verdadero.
Función para Calcular la Función Link:
Esta función tiene como objetivo cuantificar la utilidad de la solución y ser una herramienta
comparativa entre soluciones a partir de la función link. Esta es una adaptación de la función objetivo
al caso de zonas asistidas, donde el último término representa el ahorro al conectar la entrada de un
vuelo con la salida de otro.
𝐿𝑖𝑛𝑘 𝐹𝑢𝑛𝑐𝑡𝑖𝑜𝑛 = ∑ 𝐶𝑣𝐷𝐸𝑣𝑧 +
𝑉
𝑣=1
∑ 𝐶𝑣𝐷𝑆𝑣𝑧
𝑉
𝑣=1
− ∑ ∑ 𝐶𝑚𝑖𝑛𝑣𝑚(𝐷𝑆𝑣𝑧 + 𝐷𝐸𝑚𝑧´
𝑉
𝑣=1𝑚𝜖𝑅𝑖
−𝐷𝑣𝑚𝑧𝑧´)
Donde:
• 𝑉 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒 𝑎𝑙 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑣𝑢𝑒𝑙𝑜𝑠 𝑣. • 𝑅𝑖𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒 𝑎𝑙 𝑠𝑢𝑏𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑉 𝑑𝑒 𝑙𝑜𝑠 𝑣𝑢𝑒𝑙𝑜𝑠 𝑚 𝑐𝑢𝑦𝑎 𝑠𝑎𝑙𝑖𝑑𝑎 𝑒𝑠 𝑐𝑜𝑛𝑒𝑐𝑡𝑎𝑑𝑎 𝑐𝑜𝑛 𝑙𝑎
𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑑𝑒 𝑢𝑛 𝑣𝑢𝑒𝑙𝑜 𝑣.
• 𝐶𝑣 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒 𝑎 𝑙𝑎 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑡𝑟𝑜𝑙𝑙𝑒𝑦𝑠 𝑑𝑒𝑙 𝑣𝑢𝑒𝑙𝑜 𝑣
• 𝐷𝐸 𝑦 𝐷𝑆 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛 𝑎 𝑙𝑎𝑠 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎𝑠 𝑑𝑒𝑠𝑑𝑒 𝑙𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑦 𝑠𝑎𝑙𝑖𝑑𝑎 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑙 𝑣𝑢𝑒𝑙𝑜 𝑣 𝑒𝑛 𝑙𝑎 𝑧𝑜𝑛𝑎 𝑧.
• 𝐶𝑚𝑖𝑛𝑣𝑚 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒 𝑎 𝑙𝑎 𝑐𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑚í𝑛𝑖𝑚𝑎 𝑑𝑒 𝑡𝑟𝑜𝑙𝑙𝑒𝑦𝑠 𝑒𝑛𝑡𝑟𝑒 𝑙𝑜𝑠 𝑣𝑢𝑒𝑙𝑜𝑠 𝑣 𝑦 𝑚
• 𝐷𝑣𝑚𝑧𝑧´ 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒 𝑎 𝑙𝑎𝑠 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎 𝑒𝑛𝑡𝑟𝑒 𝑙𝑎𝑠 𝑧𝑜𝑛𝑎𝑠 𝑧 𝑦 𝑧′𝑑𝑜𝑛𝑑𝑒 𝑠𝑒 𝑒𝑛𝑐𝑢𝑒𝑛𝑡𝑟𝑎𝑛 𝑣 𝑦 𝑚
Paso 1: Recibir dos listas o cromosomas (es decir, las soluciones) que serán evaluadas,
correspondientes a las horas de entrada y las áreas de posicionamiento de los vuelos. Estas,
evidentemente, siempre deberán tener la misma longitud.
Paso 2: Se observa que ninguna hora de entrada sea inferior al periodo cero y si es el caso se lleva a
cero. Esto se debe a que todos los vuelos se deberán ingresar en el mismo día y un periodo inferior a
cero se refiere al día anterior.
Paso 3: Se realiza una doble iteración sobre el cromosoma de las horas de entrada y sobre el marco
de datos con la información del vuelo (este debe ser una copia del original debido a que, cada vez que
se establezca una coordinación entre vuelos, ese vuelo será removido del marco para que no sea
coordinado con ningún otro). Por cada horario de entrada recorrer todos los vuelos.
Paso 4: Definir una lista provisional que se reinicie cada vez que se cambia de periodo de entrada
durante el recorrido.
Paso 5: En caso de que el periodo de salida del vuelo v en cuestión sea igual al periodo que entrada
sobre el que se está iterando, guardar este vuelo en la lista provisional, junto al vuelo al que pertenece
el periodo sobre el que se itera, el mínimo entre el número de trolleys de ambos vuelos y la distancia
de las áreas en las que se encuentran.
Paso 6: Al observar todos los vuelos, si este periodo de entrada coordina con más de un periodo de
salida, se escogerá a aquel que posea la distancia entre áreas más corta, ya que este es el término
negativo del ahorro. Para esto se organiza la lista provisional (ahora una lista de listas) de mayor a
menor con respecto a esta distancia.
Paso 7: En caso de haber conexión entre dos vuelos, se guarda toda esta información de nuevo en la
lista permanente (lista de listas ya que cada conexión como tal es una lista) que se utilizará para
calcular el ahorro. Asimismo, se remueve este vuelo del marco de datos, ya que no pueden haber más
de dos vuelos conectados.
Paso 8: Iterar sobre el marco de datos que contiene todos los vuelos y calcular dependiendo de su
área y número de trolleys, el desplazamiento total de entrada y salida.
Paso 9: Iterar sobre la lista permanente y sumar el ahorro total.
Paso 10: Restar el desplazamiento total de entrada salida menos el ahorro total. Finalmente se obtiene
el valor de la función objetivo.
Función Mecanismo Corrección 1:
Esta función busca asegurarse de que, con los valores presentados en la lista de horarios de entrada,
la cual será continuamente cambiada por la búsqueda tabú y el algoritmo genético, cumplan con estar
en el rango de 4 y 6 horas u 8 y 12 periodos.
Paso 1: Hacer un recorrido e iterar sobre cada uno de los periodos de entrada.
Paso 2: Comparar cada periodo de entrada con el respetivo periodo de salida de su respectivo vuelo,
en caso de que (𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑠𝑎𝑙𝑖𝑑𝑎 − 𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑒𝑛𝑡𝑟𝑎𝑑𝑎 > 12) o (𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑠𝑎𝑙𝑖𝑑𝑎 − 𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑒𝑛𝑡𝑟𝑎𝑑𝑎 < 8),
fijar el periodo de entrada en el mínimo posible, es decir (𝑝𝑒𝑟𝑖𝑜𝑑𝑜𝑠𝑎𝑙𝑖𝑑𝑎 − 8)
Función Mecanismo Corrección 2:
Esta función se centra en encontrar una solución factible del posicionamiento de trolleys a partir de
una no factible (generada por los constantes cambios que hacen las metaheurísticas), trasladando
vuelos a otras zonas. Este mecanismo de corrección fue utilizado por Chao et al. (2015) en su
algoritmo genético para un sistema de almacenamiento “pick and pass”. El algoritmo observa qué
áreas se encuentran sobre capacitadas y seguidamente busca transportar esta carga de producto extra
(en el caso de este problema trasladar vuelos) al área con mayor capacidad disponible. En el caso de
que ningún área pueda recibir esta carga completa de x productos sin exceder su capacidad, se
intercambiará dos cargas de tal manera que ambas áreas se encuentren dentro de su disponibilidad. A
continuación, se evidencia un ejemplo de este mecanismo de corrección donde cada patrón representa
un lote (en este caso una carga perteneciente a un vuelo) de producto que debe ser movido en su
totalidad. El funcionamiento de este mecanismo adaptado al problema teniendo en cuenta los 48
periodos de planeación es el siguiente:
Ilustración 20: Funcionamiento del Mecanismo de Corrección 2 (Chao et al,2015).
Paso 1: Recepción de la lista de las áreas asignadas a los vuelos como entrada.
Paso 2: Iterar sobre la matriz del horizonte de planeación formada partir de esta lista y el arreglo
formado a partir de los vuelos previamente ingresados a la bodega por medio de la función
HORIZON.
Paso 3: Dentro de la iteración evaluar si alguna zona en algún periodo de tiempo supera su capacidad
máxima, similar a la función FACTIBILITY.
Paso 4: Si es así guardar el área problema junto con su exceso (número de trolleys actual menos
capacidad máxima).
Paso 5: A partir del marco de datos de entrada con la información de los vuelos, determinar todos
los vuelos de esta zona problema cuyo tiempo en bodega tenga incluido el periodo en cuestión.
Básicamente, se recopilan los vuelos que están causando la infactibilidad y se organizan en una lista
de mayor a menor a partir de su carga de trolleys.
Paso 5: Determinar para este periodo las zonas con disponibilidad (número de trolleys actuales no
supera su capacidad máxima), recopilarlas en un diccionario y organizarlas de mayor a menor.
Paso 6: Analizando el marco de datos de entrada al intercambiar la columna de áreas con la lista de
posicionamiento de entrada, determinar los vuelos de cada área con disponibilidad, también de mayor
a menor cantidad de trolleys.
Paso 7: Hacer un doble recorrido, iterando sobre el diccionario de las áreas y los vuelos del área no
factible en este periodo. Para cada área con disponibilidad se iterará sobre todos los vuelos.
Paso 8: Se plantea una condicional, si la cantidad de carros de este vuelo es menor o igual a la
capacidad actual de esta zona.
Paso 9: Si se responde si al condicional anterior, se plantea una nueva condición a partir del horizonte
de planeación. Si alguna de las áreas disponibles puede recibir un vuelo de la zona problema sin violar
la factibilidad por los periodos (de 8 a 12) que debe estar ese vuelo en la bodega se hará el cambio.
Si este es el caso, los recorridos serán rotos.
Paso 10: Si, por el contrario, ninguno de las zonas puede recibir en su totalidad los vuelos problema,
se creará una tercera iteración por los vuelos de cada área disponible, es decir se plantean 3 ciclos
anidados.
Paso 11: Se plantea un condicional, si la diferencia entre la cantidad de trolleys del vuelo de la zona
problema y el vuelo de la zona disponible es menor o igual a la disponibilidad de la zona disponible,
pasar a la siguiente condicional, de lo contrario cambiar de vuelos. Por lógica la cantidad de carros
del vuelo de la zona problema debe ser superior al vuelo de la zona disponible, de otro modo el
intercambio seria inefectivo.
Paso 12: En caso de que ambas zonas puedan manejar el intercambio, realizarlo. Cabe resaltar que
es probable que los vuelos intercambiados no tengan el mismo rango de periodos de permanencia,
por lo que es fundamental revisar que los cambios sean posible en los periodos de ambos vuelos, ya
que es posible que la zona disponible reciba en algunos periodos el vuelo de la zona problema sin
haber llegado al periodo de entada del vuelo que donó y viceversa.
Paso 13: En tal caso de que se haga el intercambio romper las tres iteraciones y continuar con la
prueba de factibilidad en el horizonte de planeación.
Función Mecanismo Corrección Extra:
Para probar la eficacia del algoritmo de corrección 2, se generaron una gran cantidad de soluciones
aleatorias a partir de la solución inicial factible de entrada, se les aplicó el algoritmo de corrección de
áreas y finalmente se verificó su factibilidad. Entre los resultados, menos de la mitad de las soluciones
aleatorias corregidas (aproximadamente un 40%) dieron como resultado una propuesta factible con
los periodos de entrada default (4 horas antes de su periodo de salida). Se presentaron una gran
cantidad de instancias en los que, hacer intercambios para todos los periodos de permanencia de los
vuelos en las áreas problema, fue imposible. Esto llevó a generar un nuevo mecanismo de corrección
llamado el mecanismo de corrección extra, el cual, tiene como objetivo liberar la zona disponible que
presenta mayor probabilidad de recibir los vuelos problema para que pueda hacerse el traslado. El
funcionamiento del algoritmo se presenta a continuación:
Paso 1: Recepción de la lista de las áreas asignadas a los vuelos como entrada.
Paso 2: Iterar sobre la matriz del horizonte de planeación formada partir de esta lista y el arreglo
formado a partir de los vuelos previamente ingresados a la bodega por medio de la función
HORIZON.
Paso 3: Dentro de la iteración evaluar si alguna zona en algún periodo de tiempo supera su capacidad
máxima, similar a la función FACTIBILITY.
Paso 4: Si es así, guardar el área problema junto con su exceso (número de trolleys actual menos
capacidad máxima).
Paso 5: Se determinan los vuelos pertenecientes al área problema en este periodo, se organizan de
mayor a menor y se realiza un recorrido por ellos.
Paso 6: Para esos vuelos, se determina la mejor área promedio en el periodo de permanencia del
vuelo en cuestión. Es decir, se evalúan las disponibilidades de las demás áreas en los periodos de
entrada y salida de este vuelo problema, se saca el promedio y a partir de este valor se determina las
mejores áreas para recibir este vuelo.
Paso 7: Se plantea un doble recorrido, pasando por los vuelos no factibles, seguido por las áreas
disponibles promedio.
Paso 8: Condicional planteada: ¿La capacidad de esta área disponible promedio cuando está libre
(su capacidad máxima) es mayor que el tamaño de carga de vuelo? De ser así continuar al siguiente
paso, de lo contrario cambiar de área disponible promedio.
Paso 9: Se obtienen los vuelos de esta área disponible promedio organizadas de mejor a menor que
interactúan con este periodo. Los vuelos son organizados por cantidad de trolleys, de mayor a menor.
Paso 10: Se realiza un recorrido por los vuelos del área disponible promedio sobre la que se está
iterando. Esto forma un triple ciclo anidado (vuelos del área problema-áreas promedio disponibles-
vuelos de cada área promedio disponible).
Paso 10. Si alguna otra área disponible puede recibir la carga de los vuelos de esta área disponible
promedio en todos los periodos que este/estos apliquen, realizar el cambio.
Paso 11: Si luego de realizar cambios con las otras áreas de capacidad positiva, la zona disponible
promedio puede recibir el vuelo de la zona problema realizarlo; de lo contrario cambiar de zona
disponible promedio o de vuelo no factible si ya se revisaron todas las zonas con disponibilidad con
ese vuelo.
Paso 12: Continuar el análisis de factibilidad con otras zonas y otros periodos del horizonte de
planeación.
Ilustración 21: Funcionamiento Mecanismo de Corrección Extra.
Algoritmo Genético:
En este algoritmo genético, el cromosoma será dividido en tres partes. En los extremos se encuentran
los vuelos Halal, así como los vuelos con una carga de trolleys bastante grande (más de tres veces la
carga media de los vuelos en el día de trabajo). Esta división se realiza ya que los vuelos halal tienen
su área destinada y no pueden estar en ninguna otra zona, por lo que no tiene sentido probar diferentes
zonas en este vuelo. Por su parte, considerando el algoritmo de generación de áreas, es bastante
probable que estos vuelos con cargas considerables no puedan estar en las áreas diferentes a las
generadas específicamente para ellos, ya que superan su capacidad, y considerarlos en la parte
evolutiva del cromosoma sólo será gasto computacional. Esta decisión surgió como resultado del caso
de Lima, donde la existencia de dos vuelos con carga muy grande (cada uno de los cuales sólo podía
estar en su respectiva área creada para ellos) generan una gran cantidad de soluciones no factibles,
por lo que se decidió fijarlos en el área de la solución inicial factible.
El algoritmo genético cuenta con las siguientes etapas:
• Generar una población inicial y torneo de selección.: A partir de una solución inicial factible,
se generará una población de soluciones aleatorias que serán los cimientos del cambio
generacional y del algoritmo genético como tal. En cada generación, se tomarán
aleatoriamente tres soluciones de la población y se compararán a partir de la función objetivo
para decidir los padres de esta generación. Este procedimiento es conocido como torneo de
selección. Se seleccionó este último en lugar de la ruleta rusa ya que el primero coordina
mejor con el elitismo, que repite individuos en la población. Cabe resaltar que este proceso
no se aplicará a la solución de los periodos de entrada ya que estos no tendrán cruce, por lo
que no es necesario el planteamiento de padres e hijos. En cada generación, se le realizará
únicamente la mutación a este cromosoma.
Previo a la realización de algoritmo genético, se determina tanto el tamaño de la población inicial, así
como el número de generaciones sobre las cuales se iterará. En la búsqueda de determinar la
asignación de almacenamiento de bodega óptima por medio de un algoritmo genético, Carlo y Giraldo
(2012) variaron la población inicial entre 10 y 100 individuos, y 100 y 500 iteraciones. Entre sus
resultados, determinaron que luego de la población inicial de 20 y de 300 iteraciones, el modelo no
presentó mejora significativa. Teniendo esto en consideración, se iterará durante 100 generaciones,
para observar si la función objetivo disminuye a lo largo del proceso evolutivo.
• Realizar el cruce o “crossover”: El cruce busca crear descendencia a partir de los dos padres
realizando intercambio de cromosoma. Solo la solución concerniente al posicionamiento de
áreas tendrá cruce, ya que es bastante probable que los periodos de entrada, a diferencia de
las áreas, sean muy específicos y no valga la pena intercambiarlos. A continuación, se
muestra un ejemplo del proceso de cruce en los cromosomas concernientes a este problema.
Ilustración 22: Cruce en el Algoritmo Genético
• Efectuar la mutación: La mutación consistirá en alterar algunos alelos del cromosoma con
una probabilidad de mutación (normalmente inferior al 30%). Se presentan dos posibilidades
de mutación evidenciadas en las siguientes figuras. La primera consiste en cambiar algunos
alelos específicos del cromosoma de manera aleatoria. Uno de los hijos de la solución de
zonas efectuará esta mutación, junto con el cromosoma de periodos de entrada. En el
cromosoma de entrada, el alelo será cambiado por otra zona aleatoria, mientras que los alelos
del cromosoma de periodo de entrada incrementarán o disminuirá en uno. Por su parte, la
segunda mutación genera una inversión en dos puntos específicos. Esta se aplicará a uno de
los hijos de la solución de áreas, ya que no es de gran utilidad para el cromosoma de periodos
de entrada. La siguiente imagen expone las dos mutaciones que serán utilizadas. Luo et al.
(2016) utilizan, al igual que este proyecto, ambas mutaciones en lo que llaman algoritmo
genético modificado, el cual, aunque no mejora el resultado final de la función objetivo,
converge a ella mucho más rápido en menos iteraciones.
• Aplicar Mecanismos de Corrección: De esta manera se corregirán los problemas de
factibilidad que surgirían por los dos procesos anteriores.
Ilustración 23: Tipos de Mutaciones Utilizadas
• Elitismo: Al final de cada generación, los resultados producidos se convierten en la población
base de la siguiente, lo que le otorga el componente evolutivo. El elitismo se centra en
identificar de la nueva población, la descendencia tanto sobresaliente como deficiente, a partir
de la función objetivo y reemplazarla. Esta herramienta, presentada por Ene y Ozturk (2012),
elabora un mayor número de cromosomas sobresalientes luego de haber eliminado los más
ineficientes e incrementa la probabilidad de seleccionar padres competentes. La beneficencia
que brinda el elitismo es más significativa con el mecanismo del torneo de selección, el cual
permite la existencia de cromosomas idénticos en la población.
Búsqueda Tabú:
Esta metaheurística utilizará dos vecindarios. Se llegó a la decisión de utilizar dos vecindarios
diferentes y compararlos para aumentar el espectro de soluciones disponibles para los usuarios de la
empresa; las restricciones específicas de este problema no imposibilitan la utilización de ninguno de
estos vecindarios. El primer vecindario consiste en todas las posibles soluciones que se generan al
cambiar el área asignada de un vuelo por otra seleccionada aleatoriamente. La siguiente figura expone
el vecindario para un vuelo en particular.
Ilustración 24: Vecindario de Intercambio de Áreas para un Mismo Vuelo.
Por otra parte, el segundo vecindario, consiste en las soluciones generadas al intercambiar las áreas
de dos vuelos específicos. Este es el vecindario más utilizado en las soluciones por búsqueda tabú al
problema SLAP, ya que no muchos estudios consideran la variación en el tiempo y, al considerar una
única instancia de tiempo, dos productos o lotes no pueden ser asignados al mismo espacio (el arreglo
o cromosoma de la solución no presenta la posibilidad de repetir zonas entre sus alelos). La siguiente
figura muestra la solución creada al intercambiar los dos vuelos, la cual será evaluada posteriormente.
Ilustración 25: Resultado del Segundo Vecindario de Intercambio de Áreas Entre Dos Vuelos
Kulak et al. (2011) plantean estos vecindarios, refiriéndose a ellos como reemplazo e intercambio
respectivamente. En su proyecto, los autores anteriormente mencionados, al igual que Otto et al.
(2015) recurren al vecindario de intercambio. Este es el más popular ya que en muchas soluciones del
problema de almacenamiento y recolección, el arreglo de solución no puede repetir valores. Sin
embargo, como este problema no presenta dichas exigencias, se aplicarán ambos vecindarios con el
objetivo de compararlos.
La búsqueda tabú cuenta con las siguientes etapas:
• Generación del vecindario: A partir de la solución inicial, se genera el vecindario compuesto
por todas las soluciones que se pueden generar realizando intercambio de áreas o de vuelos,
dependiendo de cual vecindario se esté considerando.
• Verificación de Factibilidad: Se estudia la factibilidad de las nuevas soluciones consideradas
y se almacenan aquellas que cumplen con estos requisitos.
• Alteración de la Solución de Tiempos de Entrada: El hecho de considerar todo el vecindario
generado al incrementar o disminuir los periodos de entrada en uno, conllevaría un enorme
gasto computacional, ya que se tendría un vecindario de más de 1 millón de soluciones
posibles, formado por la combinación de los vecindarios de ambas soluciones, tanto del
posicionamiento como de los periodos de entrada. Debido a lo anterior, se decidió
implementar la misma mutación del algoritmo genético a la solución de periodos de entrada
y sólo realizar un estudio exhaustivo de los vecindarios de posicionamiento de los vuelos (no
más de 2500 soluciones por iteración en el caso de las tres bodegas estudiadas).
• Clasificar las Soluciones Factibles dependiendo de la función objetivo. La mejor solución
factible del vecindario, es decir la que minimice en mayor medida el desplazamiento
promedio, será considerada la solución actual.
• Revisión con la Búsqueda Tabú: Se cerciora de que la solución actual no esté en la búsqueda
tabú, de ser así se considera la segunda mejor del vecindario factible como la solución actual.
Esta comparación se realizará con dos cifras decimales, asegurándose que no sean soluciones
similares sino exactas las que se están rechazando, ya que no se tiene certeza de a que nuevos
vecindarios llevará estos cambios, por más pequeños que sean.
• Se agrega la solución actual a la búsqueda tabú, y si está lleno a su límite de capacidad,
eliminar la solución más antigua.
• Cada cinco interacciones, alterar el tamaño de la búsqueda tabú haciéndola dinámica. Si se
generó una disminución, en la siguiente iteración se eliminarán todos los excesos para
adecuarse al nuevo tamaño de esta. De esta manera se evita el detrimento que la búsqueda
tabú puede tener con la memoria computacional (Van Hentenryck, 2015).
11. RESULTADOS Y ANÁLISIS DE RESULTADOS
A continuación, se presentan los resultados de las bodegas en las tres ciudades, así como los resultados
de aplicar las tres soluciones mencionadas durante 100 iteraciones. Se aplicaron 100 iteraciones en
cada caso con el fin de identificar las tendencias, tanto de la disminución de la función objetivo, así
como de los tiempos de convergencia en todos los casos de estudio. Del mismo modo, se considerará
una situación en la búsqueda tabú donde no se altere el resultado inicial de los periodos de entrada de
los vuelos, y todos estos sean fijados a 4 horas antes de su periodo de salida con el fin de detectar su
importancia y la disminución aportada por los ahorros de coordinación de producto. Los algoritmos
se aplicaron en Python 3.7, en un computador ASUS VivoBook S con un Intel CORE i7.
Bogotá:
Para el caso de Bogotá, el algoritmo de asignación de áreas dividió la bodega en 15 áreas, con
capacidades bastante similares, mostradas en la siguiente figura y tabla. De las tres ciudades
involucradas en este estudio, Bogotá tiene la mayor concentración de vuelos en los mismos periodos
y consecuentemente es el que más áreas diferenciadas necesita. La similitud entre los tamaños de las
áreas revela que no hay vuelos con cargas considerablemente grandes. Asimismo, intercambiar la
distribución de las áreas generadas no produce grandes discrepancias en la función objetivo. Esta es
la ventaja de buscar que las áreas tengan tamaños similares al asignar los espacios residuales a las
zonas con menor capacidad.
Ilustración 26: Bodega de Bogotá con su Nueva Distribución Dividida en Áreas
Tabla 13: Zonas Asistidas de la Cámara de Bogotá con su Respectiva Capacidad y Convención
A B C D E F G H I J K L M N O
66 59 68 66 63 59 61 60 58 60 67 59 60 67 67
La siguiente ilustración expone los resultados de 100 iteraciones de la búsqueda tabú con el vecindario
de intercambio de áreas para el mismo vuelo. Se exponen dos curvas de la metaheurística: cuando se
muta la solución de periodos de entrada (azul) y cuando estos se establecen en cuatro horas previas a
la hora de salida de la bodega y no se iteran (roja). La distancia total de la solución inicial factible es
de 29947 metros recorridos durante el posicionamiento y recolección de los carros. La solución,
considerando la iteración de los periodos de entrada registra el mínimo local de 25141 metros totales,
una reducción del 16.04%. Por el contrario, al no variar los periodos de entrada, el mínimo local
logrado es de 26178 metros, una reducción del 13.59%. En términos de comportamiento, ambas
curvas inician con una disminución exponencial de la función objetivo, hasta que entran en tendencias
cíclicas y asintóticas respectivamente.
Gráfica 2 Resultados Búsqueda Tabú para el Vecindario de Reemplazo, Bogotá
Gráfica 3: Resultados Búsqueda Tabú para el Vecindario de Intercambio, Bogotá
Los resultados obtenidos en la búsqueda tabú de Bogotá aplicando el otro vecindario disponible,
convergen en un mínimo alcanzado de 25135 metros, una reducción del 16.06%, siendo menor al
alcanzado con el vecindario de intercambiar únicamente áreas. Además, aunque su comportamiento
es bastante similar a su contraparte, el comportamiento cíclico es menos marcado a excepción del
final.
A continuación, se presentan los resultados de las 100 iteraciones con el algoritmo genético. De la
gráfica se resalta la notable mejora a la función objetivo en la primera iteración, así como su
comportamiento volátil donde, aunque se alcancen picos y mínimos locales consecutivamente, no hay
una clara tendencia de mejora. El mínimo alcanzado fue de 25546, una reducción del 14 %, inferior
a los resultados de la búsqueda tabú con ambos vecindarios.
Gráfica 4:Resultados Algoritmo Genético, Bogotá
Finalmente se exponen los tiempos de convergencia de las cuatro soluciones. La búsqueda tabú donde
se aplica el vecindario de alteración a una misma área y no se alteran los periodos de entrada, tiene el
menor tiempo de convergencia de 6666 segundos o 1.85 horas. Los periodos de funcionamiento para
las búsquedas tabú con el vecindario de cambio de área e intercambio de vuelos son de 8866 o 2.46
horas y 11174 segundos o 3.1 horas respectivamente. Por último, la solución con mayores
requerimientos de tiempo es el algoritmo genético, necesitando para producir las 100 generaciones
alrededor de 15078 segundos o 4.18 horas.
Gráfica 5:Tiempos de Convergencia para las Cuatro Soluciones, Bogotá
Santiago de Chile:
En el caso de Santiago, el algoritmo de asignación de áreas dividió la bodega en 10 áreas, todas con
una capacidad muy cercana, entre 41 y 43 espacios disponibles. Esto informa que Santiago no tiene
una gran concentración de vuelos en periodos específicos (a diferencia del caso de Bogotá) y que
tampoco tiene vuelos con una carga considerablemente grande.
Ilustración 27: Bodega de Santiago con su Nueva Distribución Dividida en Áreas
Tabla 14 : Zonas Asistidas de la Cámara de Santiago con su Respectiva Capacidad y Convención
A B C D E F G H I J
42 42 42 42 43 43 43 42 41 41
La siguiente ilustración expone los resultados de 100 iteraciones de la búsqueda tabú con el vecindario
de intercambio de áreas para el mismo vuelo para la bodega de Santiago de Chile. Se exponen dos
curvas de la metaheurística: cuando se muta la solución de periodos de entrada (azul) y cuando estos
se establecen en cuatro horas previas a la hora de salida de la bodega y no se iteran (roja). En el caso
de Santiago, la distancia total de la solución inicial factible es de 11753 metros recorridos durante el
posicionamiento y recolección de los carros. La solución considerando la iteración de los periodos de
extrada registra el mínimo local de 8936 metros totales, una reducción del 23.93%. Por el contrario,
al no variar los periodos de entrada, el mínimo local logrado es de 9568, una reducción del 18.6%.
En términos de comportamiento, ambas curvas inician con una disminución exponencial de la función
objetivo, hasta que entran en tendencias cíclicas y asintóticas respectivamente.
Gráfica 6: Resultados Búsqueda Tabu para el Vecindario de Reemplazo, Santiago
Gráfica 7: Resultados Búsqueda Tabu para el Vecindario de Intercambio, Santiago
Los resultados en la búsqueda tabú en Santiago aplicando el otro vecindario disponible, convergen
en un mínimo alcanzado de 8693 metros, una reducción del 26.03%, siendo el menor alcanzado de
todas las soluciones aplicadas. Además, aunque su comportamiento es bastante similar a su
contraparte, el comportamiento cíclico es un poco menos volátil.
A continuación, se presentan los resultados de las 100 iteraciones con el algoritmo genético. Al igual
que en el caso de Bogotá, se resalta la efectividad de las primeras iteraciones, así como su
comportamiento errático sin una clara tendencia de mejora. El mínimo alcanzado fue de 9721 metros,
una reducción del 17.28 %, inferior a los resultados de la búsqueda tabú con ambos vecindarios.
Gráfica 8:Resultados Algoritmo Genético, Santiago
Gráfica 9: Tiempos de Convergencia para las Cuatro Soluciones, Santiago
Con respecto al criterio de tiempos de convergencia, la búsqueda tabú donde se aplica el vecindario
de alteración a una misma área y no se alteran los periodos de entrada, tiene el menor tiempo de
convergencia de 3310 segundos o 1.85 horas. Los periodos de funcionamiento para las búsquedas
tabú con el vecindario de cambio de área e intercambio de vuelos son de 5657 segundos o 1.57 horas
y 6453 segundos o 1.79 horas respectivamente. Por último, la solución con mayores requerimientos
de tiempo es el algoritmo genético, necesitando para producir las 100 generaciones alrededor de 4383
segundos o 1.21 horas.
Lima:
El algoritmo de formación de áreas obtuvo, en el caso de lima, un total de catorce áreas disponibles.
De esta asignación se resaltan las áreas A y B de 45 y 40 espacios respectivamente, lo que lleva a la
conclusión de que Lima tiene concentración de vuelos en ciertos periodos (entre las 6 y 8 de la tarde)
y al menos dos vuelos con una carga enorme en comparación con la carga media de los demás vuelos.
Ilustración 28: Bodega de Lima con su Nueva Distribución Dividida en Áreas
Tabla 15: Zonas Asistidas de la Cámara de Lima con su Respectiva Capacidad y Convención
A B C D E F G H I J K L M N
45 40 20 18 19 19 19 17 21 19 17 19 19 17
Las gráficas para Lima (100 iteraciones) de la búsqueda tabú con el vecindario de intercambio de
áreas para el mismo vuelo, presentan los mismos comportamientos y ratio de resultados que las
gráficas de las ciudades anteriores. La distancia total de la solución inicial factible es de 10833 metros
recorridos durante el posicionamiento y recolección de los carros. La solución considerando la
iteración de los periodos de entrada registra el mínimo local de 8388 metros totales, una reducción
del 22.6%. Por el contrario, al no variar los periodos de entrada, el mínimo local logrado es de 8403
metros, una reducción del 22.5%. En términos de comportamiento, ambas curvas inician con una
disminución exponencial de la función objetivo, hasta que entran tendencias cíclicas y asintóticas
respectivamente.
Gráfica 10: Resultados Búsqueda Tabu para el Vecindario de Reemplazo, Lima
Los resultados en la búsqueda tabú en Bogotá aplicando el otro vecindario disponible convergen en
un mínimo alcanzado de 8225 metros, una reducción del 24.18%., siendo menor al alcanzado con el
vecindario de intercambiar únicamente áreas. Además, aunque su comportamiento es bastante similar
a su contraparte, es comportamiento cíclico es menor marcado a excepción del final.
Gráfica 11: Resultados Búsqueda Tabu para el Vecindario de Intercambio, Lima
A continuación, se presentan los resultados de las 100 iteraciones con el algoritmo genético. De la
gráfica se resalta la notable mejora a la función objetivo en la primera iteración, así como su
comportamiento divergente donde, aunque se alcancen picos y mínimos locales consecutivamente,
no hay una clara tendencia a la mejora. El mínimo alcanzado fue de 8817 metros, una reducción del
18.61 %, inferior a los resultados de la búsqueda tabú con ambos vecindarios.
Gráfica 12: Resultados Algoritmo Genético, Lima
Finalmente, se exponen los tiempos de convergencia de las cuatro soluciones. La búsqueda tabú en
la cual se aplica el vecindario de alteración a una misma área y no se alteran los periodos de entrada,
tiene el menor tiempo de convergencia de 4892 segundos o 1.35 horas. Los periodos de
funcionamiento para las búsquedas tabú con el vecindario de cambio de área e intercambio de vuelos
son de 6941 segundos o 1.92 horas y 10192 segundos o 2.83 horas respectivamente. Por último, la
solución con mayores requerimientos de tiempo es el algoritmo genético, necesitando para producir
las 100 generaciones alrededor de 17629 segundos o 4.89 horas.
Gráfica 13: Tiempos de Convergencia para las Cuatro Soluciones, Lima
Análisis de Resultados
Del conglomerado de resultados obtenidos en las tres ciudades, se afirma que, aunque el algoritmo
genético tiene una mejora significativa en la primera iteración gracias a su variabilidad que surge de
diferentes fuentes, presenta los resultados menos satisfactorios al compararse con los otros dos
métodos de solución. Esto se debe principalmente a una convergencia prematura que no permite
indagar profundamente en el espacio de solución, así como a las correcciones de factibilidad, las
cuales, pueden afectar la disminución de la función objetivo. Estas correcciones se realizan seguidas
de los procesos evolutivos, tanto sobre la descendencia mutada de la solución de las zonas asignadas,
como sobre la solución de periodos de entrada y no tienen en consideración sí dichos cambios
incrementan o decrementan la función objetivo (la factibilidad es su única prioridad). En términos de
tiempos de funcionamiento, el algoritmo genético mostró, tanto en Lima como en Bogotá, los tiempos
de convergencia más altos. Este tiempo se consume ya que, en cada familia de cada generación, se
debe determinar una solución mutada de tiempos de entrada que genere factibilidad en la
descendencia también mutada.
Del mismo modo, se observa una relación exponencial entre el número de áreas y los tiempos de
operación de esta metaheurística. Para el caso de Santiago, con diez áreas, las 100 generaciones se
llevaron a cabo en un tiempo cercano a los 4000 segundos. Por su parte, los casos de Bogotá y Lima,
con 15 y 14 áreas, requieren de 15000 y 17000 segundos respectivamente para efectuar las 100
generaciones (entre 4 y 6 horas). Estas son diferencias drásticas si son comparadas con aquellas
presentadas en la búsqueda tabú, donde incluso la búsqueda tabú con el vecindario de intercambio en
Santiago, tomó más tiempo para converger que su algoritmo genético. Para el algoritmo genético es
difícil tener una tendencia de mejora constante, debido a que la solución de periodos de entrada es
alterada en todas las familias y las correcciones para cumplir con los requisitos de factibilidad no
consideran la función objetivo, ni qué corrección incrementa o disminuye el desplazamiento total en
la bodega.
Por otro lado, ambos algoritmos de búsqueda tabú aseguran la factibilidad para seguidamente, realizar
comparaciones de eficacia entre las soluciones factibles, lo que genera soluciones con mayor
optimalidad. Se concluye que, en un problema con estas restricciones, la búsqueda tabú demostró una
mayor efectividad a la hora de minimizar el desplazamiento total en las bodegas. Entre todas las
opciones, el vecindario de intercambio de áreas entre dos vuelos reveló la mayor efectividad al
generar cambios más drásticos en la función objetivo, al involucrar dos vuelos en lugar de uno. Aun
así, el vecindario de intercambio de áreas para un vuelo otorga soluciones cercanas al mejor
vecindario en un tiempo mucho menor. Esto se debe a que, aunque el algoritmo de solución sea el
mismo, la búsqueda cuyo vecindario consista en el intercambio de soluciones de dos vuelos, presenta
una cantidad de soluciones mucho mayor, ya que como se explicó anteriormente, el número de áreas
recae entre las 10 y 15, mientras que la longitud de los arreglos de cromosomas de solución
normalmente supera los 65 unidades ( hay más de 65 vuelos por día en promedio en las tres áreas).Del
mismo modo, al haber mayor número de soluciones que considerar, es más fácil para la búsqueda
tabú con el vecindario de intercambio de áreas para el mismo vuelo, converger más rápidamente,
aunque no encuentre soluciones tan buenas como su contraparte.
Finalmente, el no iterar los tiempos de entrada aumenta las distancias totales, empeorando la solución
considerablemente a cambio de brindar mejores tiempos de convergencia, por lo que se concluye que
la iteración de los tiempos de entrada con tal de maximizar los ahorros es beneficiosa y recomendada.
Aplicar la mutación para la solución de periodos de entrada en la búsqueda tabú resultó ser
beneficioso, ya que este híbrido permite disminuir la función objetivo de la solución inicial al no sólo
generar ahorros, sino al forzar a los mecanismos de corrección a realizar cambios que permitieron
estudiar nuevas variaciones de la función objetivo. Asimismo, la comparación entre la búsqueda tabú
al iterar o no iterar los periodos de entrada demuestra la funcionalidad de los ahorros, los cuales son
los que brindan la diferencia. Las soluciones obtenidas al no iterar los tiempos de entrada tienen
comportamiento asintótico al caer en un mínimo local y no tener la capacidad de explorar otros
territorios de la función objetivo. Todas las gráficas dónde se iteran los periodos de entrada de los
vuelos tienen comportamientos un tanto cíclicos, sin tendencia de mejora fija por la aleatoriedad del
mecanismo de alteración o mutación de la solución de los periodos de entrada. No obstante, la
solución del algoritmo genético demuestra un comportamiento más errático y volátil, ya que, durante
el cruce, la mutación y la corrección realizan cambios más drásticos que en la búsqueda tabú y
además, se realizan en cada familia (las alteraciones de los periodos de entrada en la búsqueda tabú
se efectúan cada 5 iteraciones). Se muestra que los tiempos de convergencia de Lima exponen el
comportamiento menos lineal entre las tres ciudades ya que, durante su periodo de menos
disponibilidad, cuando las zonas asistidas se encuentran más ocupadas, se presentan vuelos de tamaño
mediano (20 carros) que son difíciles de ubicar y los mecanismos de corrección requieren tiempo para
lograrlo. Bogotá es la siguiente con esta tendencia (a menor medida) debido a que, para el número de
zonas con el que cuenta, le es más difícil al mecanismo de corrección generar soluciones factibles
que a Santiago, la más lineal de las tres y la cámara que menos zonas necesita.
La decisión de cuál vecindario utilizar, teniendo conocimiento de las ventajas y desventajas de cada
uno, recae en el usuario. Si se cuenta con muy poco tiempo, se recomienda la utilización del algoritmo
genético ya que tiene las disminuciones más marcadas en las primeras cinco iteraciones. Si se cuenta
con una gran cantidad de tiempo, la búsqueda tabú con el vecindario de intercambio de zonas entre
vuelos es la más aplicable, ya que minimizará en menor media la función objetivo. Finalmente, la
búsqueda tabú con el vecindario de intercambio de zonas para el mismo vuelo, brinda soluciones
aceptables en tiempos no tan altos.
Prueba de Robustez
Con el fin de probar la robustez del algoritmo, se buscaron escenarios donde las bodegas se
encontraran más llenas y a partir de esto, evidenciar su eficacia en esos casos. Al no tener información
de otros vuelos que permitieran cargar a mayor medida la bodega, se decidió incrementar el número
de trolleys de todos los vuelos en un porcentaje especifico, con el objetivo de determinar la posibilidad
y también facilidad del algoritmo con mejor rendimiento (búsqueda tabú con intercambio de vuelos)
de encontrar soluciones factibles y mejorar a lo largo de las iteraciones la función objetivo de
desplazamiento total. La determinación del incremento porcentual que tendrán las cargas de los
vuelos se obtuvo de la gráfica 14, que expone la capacidad total porcentual de las bodegas a lo largo
de los 48 periodos que componen un día.
De la gráfica, se afirma que la cámara de frio de Bogotá, es efectivamente la más saturada de las tres
opciones, alcanzando su pico en el periodo 33 (4:30 pm) con una capacidad utilizada de 84.89%.
Lima por su parte, alcanza el pico en el periodo 39 (7:30 pm), contemplando un uso del 79.94%. A
diferencia de sus contrapartes, la cámara de Santiago cuenta con una enorme capacidad a lo largo de
todo su horizonte de planeación. En el peor de los casos, asumiendo que todos los vuelos funcionan
el mismo día, esta solo llega a una utilización del 65.32 % de su capacidad máxima.
Según estudios previos, realizados por la empresa Gate Gourmet, en los próximos años se espera
alcanzar un crecimiento del 30 %. Infortunadamente, las cámaras de Bogotá y Lima, al respetar las
reglamentaciones legales vigentes, solo pueden recibir un aumento del 15 % y 20 % respectivamente,
a menos que decidan instaurar nuevos vuelos en los periodos de las bodegas donde no se alcanzan
estas capacidades (entre las 4 y 8 pm). Por el contrario, la bodega de Santiago puede recibir este
aumento de demanda sin muchos inconvenientes, sin importar el horario de recepción.
Gráfica 14: Capacidad Utilizada (Porcentajes) a lo Largo del Horizonte de Planeación para las Tres Cámaras
Inspeccionando las capacidades de las bodegas en el horizonte de planeación, se decide incrementar
las cargas de los vuelos de Bogotá, Lima y Santiago en 14,19 y 30 % respectivamente. Este aumento
cambiará la disponibilidad de las áreas, más sin embargo, la cantidad de áreas se mantendrá al no
incluir más vuelos. Las siguientes tablas muestran las zonas generadas, así como la solución inicial
formada a partir de los mecanismos de corrección, demostrando que efectivamente, los algoritmos
cuentan con la capacidad de generar soluciones factibles.
En el caso de Bogotá , el periodo 33 llega a tener 906 de las 940 posiciones ocupadas. En Lima, esta
solución alcanza los 297 espacios de los 309 disponibles y finalmente, para Santiago, se llega a una
utilización de 359 puestos de los 421 a disposición.
Por último, se repitió la aplicación del algoritmo de búsqueda tabú con intercambio de áreas entre
vuelos a estas soluciones iniciales, alterando tanto los periodos de entrada como la asignación de
zonas. El resultado muestra que las funciones objetivo de las ciudades disminuyen entre un 12 y 19
% logrando optimizar en estos casos extremos el desplazamiento total. La asignación es lograda
gracias a las capacidades determinadas por el algoritmo de asignación de áreas que establece los
espacios restantes a los necesarios a las zonas más pequeñas en los tamaños de los vuelos más
frecuentes, incrementando las combinaciones posibles durante la agrupación.
Bogotá:
Tabla 16: Zonas Asistidas de Bogotá con la Demanda Incrementada un 14%
A B C D E F G H I J K L M N O
75 63 58 60 58 63 66 66 66 65 59 62 62 59 58
Tabla 17: Horizonte de Planeación (48 Periodos) de Bogotá con Demanda Incrementada
A B C D E F G H I J K L M N O Total
0 13 17 19 13 17 17 19 17 22 48 46 19 19 0 0 286
1 13 17 19 13 17 17 19 17 22 48 46 19 19 0 0 286
2 13 17 19 13 17 17 19 17 22 48 46 19 19 0 0 286
3 13 17 19 13 17 17 19 17 22 48 46 19 19 39 17 342
4 32 40 35 13 17 17 19 17 22 48 46 19 19 39 17 400
5 19 40 35 13 17 17 19 17 22 48 46 19 19 39 17 387
6 19 23 16 0 0 0 0 0 19 48 46 19 19 39 17 265
7 19 23 16 39 0 0 0 0 0 0 46 19 19 39 17 237
8 19 23 16 39 0 0 0 0 0 0 0 19 19 39 17 191
9 19 23 16 39 0 0 0 0 0 0 0 0 0 39 17 153
10 19 23 16 39 13 0 0 0 0 0 0 0 0 39 17 166
11 19 23 56 39 13 0 13 17 17 0 18 19 0 39 17 290
12 19 23 56 39 13 0 13 17 17 0 18 37 49 19 0 320
13 58 63 57 56 30 63 32 66 66 49 36 45 49 41 22 733
14 58 63 57 56 30 63 32 66 66 49 36 45 49 41 22 733
15 58 63 57 56 30 63 32 66 66 49 36 45 49 41 22 733
16 58 63 57 17 30 63 32 66 66 49 36 45 49 41 22 694
17 58 63 57 17 30 63 32 66 66 49 36 45 61 41 22 706
18 58 63 57 34 30 63 32 66 66 49 36 45 61 41 22 723
19 58 63 57 34 17 63 32 66 66 49 18 45 61 41 22 692
20 58 63 17 34 17 63 19 49 49 49 18 26 61 41 22 586
21 58 63 17 34 17 63 19 49 49 49 18 8 12 22 22 500
22 0 0 0 17 0 0 0 0 0 0 0 0 12 0 0 29
23 75 0 0 17 0 0 0 0 0 0 0 0 12 0 0 104
24 75 0 0 17 0 0 0 0 0 0 0 0 12 0 0 104
25 75 0 0 17 0 0 0 0 0 0 0 0 12 0 0 104
26 75 0 57 17 0 0 0 0 0 0 0 0 0 0 0 149
27 75 0 57 0 57 0 38 0 0 0 0 0 0 0 0 227
28 75 17 57 3 57 63 65 66 0 26 55 0 7 0 0 491
29 75 17 57 3 57 63 65 66 66 64 55 30 7 49 0 674
30 75 36 57 3 57 63 65 66 66 64 55 30 7 49 0 693
31 75 36 57 3 57 63 65 66 66 64 55 62 56 49 0 774
32 0 36 57 60 57 63 65 66 66 64 55 62 56 49 57 813
33 75 54 57 60 57 63 65 66 66 64 55 62 56 49 57 906
34 75 54 57 60 57 63 65 66 66 64 55 62 56 49 57 906
35 75 54 0 60 57 63 65 66 66 64 55 62 49 49 57 842
36 75 54 0 60 0 63 27 66 66 64 55 62 49 49 57 747
37 75 37 0 57 0 0 0 0 66 38 0 62 49 49 57 490
38 75 37 17 57 0 0 0 0 0 0 0 32 49 0 57 324
39 75 18 17 57 0 0 0 0 0 0 0 32 49 0 57 305
40 75 18 17 57 0 0 0 0 0 0 0 0 0 0 57 224
41 75 18 17 0 0 0 0 0 0 0 0 0 0 0 0 110
42 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 17
43 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 17
44 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 17
45 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 17
46 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 17
47 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Lima:
Tabla 18: Zonas Asistidas de Lima con la Demanda Incrementada un 19%
A B C D E F G H I J K L M N
54 48 24 17 17 20 18 20 19 20 23 19 19 19
Tabla 19: Horizonte de Planeación (48 Periodos) de Lima con Demanda Incrementada
A B C D E F G H I J K L M N Total
0 18 5 5 10 0 0 0 0 0 0 0 0 0 0 38
1 0 0 0 10 6 0 0 0 0 0 0 0 0 0 16
2 17 0 0 10 6 0 0 0 0 0 0 0 0 0 33
3 17 0 0 10 6 0 7 0 0 0 0 0 0 0 40
4 17 0 0 10 6 0 7 10 0 0 0 0 0 0 50
5 17 0 0 10 6 0 7 10 0 0 0 0 0 0 50
6 17 0 0 10 6 0 7 10 12 0 0 0 0 0 62
7 17 0 0 10 6 0 7 10 12 6 0 0 0 0 68
8 17 0 0 10 6 0 7 10 12 6 0 0 0 0 68
9 17 0 0 0 6 0 7 10 12 6 0 0 0 0 58
10 23 6 6 7 6 7 14 10 12 6 7 6 6 7 123
11 6 6 6 7 6 7 14 16 18 13 7 6 6 7 125
12 6 6 6 7 6 7 7 16 18 13 9 6 6 7 120
13 54 6 6 7 6 7 7 6 18 13 9 6 6 7 158
14 54 47 6 7 6 7 7 6 18 13 9 13 6 7 206
15 54 47 12 14 16 12 14 16 6 13 9 13 6 7 239
16 54 47 12 14 16 12 14 16 6 7 9 13 6 7 233
17 54 47 12 14 16 12 14 16 6 7 9 13 6 7 233
18 54 47 12 14 16 12 14 16 13 7 9 13 6 7 240
19 48 41 6 7 10 5 7 16 13 14 2 7 0 0 176
20 48 41 6 7 10 5 7 10 7 7 2 7 0 0 157
21 48 41 6 7 10 5 7 10 7 7 0 7 0 0 155
22 0 41 6 7 10 5 7 10 7 7 0 7 0 0 107
23 0 0 6 7 10 5 7 10 7 7 0 0 0 0 59
24 0 0 0 0 0 0 0 0 7 7 10 0 0 0 24
25 0 0 0 0 0 0 0 0 7 7 15 0 0 0 29
26 0 0 0 0 0 0 0 0 7 7 15 0 0 0 29
27 0 0 0 0 0 0 0 0 0 7 15 0 0 0 22
28 54 0 0 0 0 0 0 0 0 0 15 0 0 0 69
29 54 48 0 17 0 0 0 0 0 0 15 0 0 0 134
30 54 48 0 17 0 0 0 0 0 0 15 0 7 0 141
31 54 48 24 17 0 0 0 0 0 0 15 0 7 0 165
32 54 48 24 17 0 0 0 0 0 0 15 0 7 0 165
33 54 48 24 17 0 0 0 0 19 18 5 19 19 19 242
34 54 48 24 17 0 0 0 0 19 18 0 19 19 19 237
35 54 48 24 17 0 0 0 0 19 18 23 19 19 19 260
36 54 48 24 17 0 0 0 0 19 18 23 19 19 19 260
37 0 48 24 17 17 0 0 0 19 18 23 19 19 19 223
38 7 0 24 17 17 14 18 0 19 18 23 19 19 19 214
39 41 39 24 17 17 14 18 17 19 18 23 19 12 19 297
40 41 39 0 17 17 14 18 17 19 18 23 19 12 19 273
41 41 39 0 17 17 14 18 17 19 18 23 19 12 19 273
42 41 39 0 17 17 14 18 17 0 0 23 0 0 0 186
43 41 39 0 17 17 14 18 17 0 0 23 0 0 0 186
44 41 39 0 17 17 14 18 17 0 0 0 0 0 0 163
45 41 39 0 17 17 14 18 17 0 0 0 0 0 0 163
46 41 39 0 17 0 14 18 17 0 0 0 0 0 0 146
47 34 39 0 0 0 0 0 17 0 0 0 0 0 0 90
Santiago:
Tabla 20: Zonas Asistidas de Santiago con la Demanda Incrementada un 30%
A B C D E F G H I J
44 43 44 41 41 42 41 41 42 42
Tabla 21: Horizonte de Planeación (48 Periodos) de Santiago con Demanda Incrementada
A B C D E F G H I J Total
0 5 5 5 4 9 0 0 0 0 0 28
1 5 5 5 4 9 5 5 0 0 0 38
2 5 5 5 4 9 5 5 5 5 0 48
3 10 18 5 4 9 5 5 5 5 21 87
4 10 13 0 4 9 5 5 5 5 21 77
5 10 13 0 4 9 5 5 5 5 21 77
6 10 13 12 20 9 5 5 5 5 21 105
7 10 13 12 20 22 26 15 5 5 21 149
8 10 13 19 20 22 26 15 5 5 21 156
9 10 13 19 16 13 26 15 5 5 21 143
10 10 13 19 16 13 21 10 5 10 26 143
11 10 13 19 16 13 21 10 0 5 26 133
12 9 0 19 16 13 21 10 0 5 5 98
13 9 26 19 16 13 21 10 0 5 5 124
14 9 26 24 23 13 21 10 0 5 5 136
15 9 26 12 7 13 21 10 0 5 5 108
16 9 26 12 7 4 5 5 35 5 5 113
17 9 26 5 7 4 5 5 35 8 8 112
18 14 26 5 7 4 5 5 35 8 8 117
19 14 31 5 7 4 5 5 35 3 3 112
20 14 31 10 12 4 5 5 35 3 3 122
21 5 31 10 12 4 5 5 35 3 3 113
22 5 5 10 12 4 5 5 35 3 3 87
23 5 5 5 5 20 5 5 35 3 3 91
24 5 5 5 5 20 5 5 35 3 3 91
25 5 5 5 5 16 0 0 0 3 3 42
26 5 5 5 5 16 5 29 0 0 0 70
27 0 10 5 10 16 5 29 0 0 0 75
28 0 5 5 10 16 5 29 0 0 0 70
29 0 5 0 5 34 14 29 0 0 0 87
30 0 5 0 5 34 14 29 0 0 0 87
31 0 5 0 5 34 14 29 0 0 0 87
32 0 5 21 5 18 14 29 4 0 0 96
33 29 10 44 5 41 14 29 4 29 0 205
34 29 10 44 34 41 14 29 4 29 0 234
35 29 39 44 34 41 9 29 4 29 0 258
36 29 34 44 36 41 35 29 4 29 0 281
37 29 34 44 36 41 35 29 27 29 0 304
38 29 34 44 36 23 42 29 27 29 29 322
39 38 34 44 41 37 42 29 36 29 29 359
40 38 34 44 41 37 42 29 36 29 29 359
41 38 34 23 41 37 42 29 32 29 29 334
42 9 29 0 41 14 42 29 32 0 29 225
43 9 29 0 12 14 42 29 32 0 29 196
44 9 0 0 12 14 42 0 32 0 29 138
45 9 0 0 5 14 16 0 32 0 29 105
46 9 0 0 5 14 16 0 9 0 29 82
47 9 0 0 5 14 0 0 9 0 0 37
Gráfica 15: Resultados Búsqueda Tabu con Vecindario de Intercambio para las Tres Cámaras con Demanda Incrementada
Gráfica 16:Resultados Tiempo de Convergencia del Algoritmo de Búsqueda Tabu con Vecindario de Intercambio para las
Tres Cámaras con Demanda Incrementada
De la gráfica de tiempo se muestra que hay un aumento considerable en los tiempos de convergencia,
en especial para Bogotá y Lima al tener las bodegas más saturadas. Esto se debe, a que los
mecanismos de corrección consumen mucho más tiempo en producir correcciones factibles, ya sea
por el incremento de áreas no factibles en diferentes periodos del horizonte o porque se requieren más
pruebas para hacer los intercambios o traslados pertinentes de estos algoritmos, lo que explica el
repentino aumento en estas dos bodegas al compararse con Santiago. Por último, se observa que estos
tiempos pierden linealidad, esto a causa de instancias puntuales en las que están trabajando los
mecanismos de corrección, para que las soluciones de la asignación de áreas se adapten a las
soluciones de cambio de periodos de entrada que se están alterando constantemente.
12. CONCLUSIONES
• Se forjaron en total tres herramientas de solución para el problema de posicionamiento
de carros en las bodegas de Bogotá, Santiago y Lima. La decisión de cuál utilizar recaerá
en las directivas de la empresa, teniendo en cuenta las restricciones que se presenten y
necesidades particulares que requiera.
• Los tres algoritmos de solución son adaptables a diferentes restricciones como vuelos
previamente ingresados, asignación de vuelos halal y el tratamiento con vuelos con
carga de tamaño considerable.
• Al restructurar las bodegas a una nueva configuración que cumple con las
reglamentaciones legales y las características de un layout óptimo, se concluye que las
bodegas de Lima y Bogotá tendrán que invertir y ampliarse en preparación a su
incremento en carga pronosticada para los próximos años. Por su parte, la cámara de
Santiago podrá seguir funcionando con su capacidad actual por los siguientes años
planeados.
• Se probó la robustez del algoritmo siendo capaz de producir soluciones factibles cuando
los centros de frio se encuentran cerca de su capacidad máxima. Esto es gracias a los
mecanismos de corrección, así como a la función de asignación que produce las áreas
en base de los tamaños de los vuelos.
• Entre los algoritmos, la búsqueda tabú con el vecindario de reemplazo de áreas para el
mismo vuelo, demostró ser el método de solución más balanceado en relación con la
calidad de la función objetivo que brinda y el tiempo de convergencia que necesita.
• La búsqueda tabú con el vecindario de intercambio de áreas entre dos vuelos, es la
solución que mejor minimiza el desplazamiento total de almacenamiento y recolección.
• Los resultados exponen cómo el aumento del número de áreas incrementa los tiempos
de convergencia considerablemente, en especial en el algoritmo genético, donde los
periodos de entrada son alterados cada familia de cada generación y la asignación de
zonas debe acoplarse mediante los mecanismos de corrección a estos nuevos periodos
de entrada. El tiempo de funcionamiento de los mecanismos de corrección depende de
la cantidad de áreas a las que tiene que recorrer.
• Después de una revisión exhaustiva de todos los posibles modelos a aplicar con el
objetivo de solucionar el almacenamiento de trolleys para la empresa Gate Gourmet, el
presente estudio expone dos soluciones (búsqueda tabú y algoritmo genético) con base
en un modelo S/R en ciclo dual. Por ende, se concluye que este proyecto aporta, al estado
del arte de almacenamiento y diseño en centros de distribución, una combinación
novedosa entre este modelo, una coordinación de cargas y una política de
almacenamiento DOS, considerando una clasificación por lotes, clases y demanda de los
trolleys.
13. RECOMENDACIONES
• La función de generación de áreas, por medio de la variable “max_spaces” –generada
por el algoritmo– informa, a partir de la disponibilidad de la bodega y la planeación de
vuelos de ese día, si la cámara cuenta con el número de espacios suficientes para generar
una solución factible (en tal caso de que esta esté negativa luego de la aplicación del
algoritmo, significa que el algoritmo tuvo que crear espacios adicionales para cumplir
la factibilidad en el horizonte de planeación). De esta manera, esta función puede ser
utilizada para observar si la disponibilidad de la bodega es suficiente o esta necesita una
ampliación.
• Con base a los resultados obtenidos, se recomienda, tal como planteó Carlo y Giraldo
(2012), utilizar en cada generación una familia de 20 individuos. Asimismo, con base a
la volatilidad presentada en los resultados del algoritmo genético, se recomienda fijar
las probabilidades de mutación en 24 y 8 % respectivamente.
• Las metaheurísticas tienen gran dependencia de la solución inicial, por lo que se sugiere
buscar un buen punto de partida. Apoyarse por medio de los mecanismos de corrección
y la función de factibilidad.
• Los mecanismos de corrección tienen una tendencia a mover los vuelos a las zonas más
grandes, ya que es más probable que tengan una disponibilidad mayor. Se sugiere darle
prioridad al posicionamiento de estas zonas de tal manera que tengan la menor suma
de distancia a entrada y salida.
Referencias Baker, P., & Canessa, M. (2009). Warehouse Design: A Structured Approach. (E. Sevier,
Ed.) European Journal of Operational Research 193, 425-436.
Ballou, R. (2004). Lógistica: Administración de la cadena de Suministro (Pearson
Education ed.).
Baron, et al. (2019). Almost Robust Discrete Optimization. European Journal of
Operational Research 276, 451-465.
Cardenas, M. (2018). Creating Hard-to-Solve Instances of Travelling Salesman Problem.
Applied Soft Computing 71, 268-276.
Carlo, H., & Giraldo, G. (2012). Toward Perpetually Organized Unit-Load Warehouses.
Science Direct, 1003-1012.
Chao Hsien, J., Shih, P.-H., Wu, M., & Lin, J. (2015). A Storage Assignment Heuristic
Method Based on Genetic Algorithm for a Pick-and-Pass Warehousing System.
Science Direct. Computers and Industrial Engineering 81, 1-13.
Chen, L., Lavegnin, A., & Riopel, D. (2010). The Storage Location Assignment and
Interleaving Problem in an Automated Storage/Retrieval System with Shared
Storage. International Journal of Production Research, 991-1011.
Chen, L., Lavegnin, A., & Riopel, D. (2011). A Tabu Search Algorithm for the Relocation
Problem in a Warehouse System. Production Economics, 147-156.
Chen, Z., Li, X., & Gupta, J. (2015). Sequencing the Storage and Retrievals for Flow-Rack
Automated Storage and Retrieval Systems with Duration-of-Stay Storage Policy.
Taylor Francis. International Journal of Production Research 54, 984-998.
Delorme, M., & et al. (2016). Bin Packaging and Cutting Stock Problems: Mathematical
Models and Exact Algorithms. European Journal Research 255, 1-20.
Dukic, G., & Upetuk, T. (2012). Warehouse Layouts. (R. Manzini, Ed.) Springer-Verlag,
55-69.
Ene, S., & Ozturk, N. (2012). Storage Location Assignment and Order Picking
Optimization in the Automotive Industry. Springer-Verlag, 787-797.
Ene, S., Kucucoglu, I., Aksoy, A., & Oztuk, N. (2016). A Genetic Algorithm for
Minimizing Energy Consumption in Warehouses. Science Direct. Energy 114, 973-
980.
Gómez, J. (2016). Solución al Problema de Distribución de Planta (FLP) de Múltiples
Niveles, un Elevador y Departamentos Desiguales a Travez de Métodos
Metaheurísticos. Bucaramanga: Universidad Industrial de Santander.
Han, M., McGinnis, L., Shich, J., & White, J. (1987). On Sequencing Retrievals in an
Automated Storage/Retrieval System. IIE Transactions 3, 56-66.
Kulak, O., Sahin, Y., & Egemen, M. (2011). Joint Order Batching and Picker Routine in
Single and Multiple-Cross-Aisle Warehouses Using Cluster-Based Tabu Search
Algorithms . Springer Science + Bussiness Media ,LLC., 52-80.
Lara, F. (2018). Método Metaheurístico de Reasignación de Productos en un Centro de
Distribución de Autopartes. Bogotá: Universidad Militar Nueva Granada.
Lend, S. e. (2019). Combinatorial Optimization with Iteration Costs: Complexity and
Solveable Cases. Discrete Optimization 33, 101-117.
Luo, G.,et al. (2016). A Modified Genetic Algorithm for Agricultural By-Products
Logistics Delivery Route Planning Problem. Springer International Publishing ,
193-205.
Monterrosa, H. (13 de 12 de 2018). La República. Obtenido de Logística se lleva 13,5% de
los ingresos de las compañías en Colombia:
https://www.larepublica.co/economia/logistica-se-lleva-135-de-los-ingresos-de-las-
companias-en-colombia-2805319
Osman Kulak, Y. S. (2012). Joint Order Batching and Picking Routing in Single and
Multiple Cross-Aisle-Warehouses Using Cluster-Based Tabu Search Algorithms.
Springer Science, 52-80.
Otto, A., Boysen, N., Scholl, A., & Walter, R. (2015). Ergonomic Workplace Design in a
Fast Pick Area. Springer, 960-969.
Ozturkoglu, O., & Hoser, D. (2019). A Discrete Cross-Aisle Model for Order-Picking
Warehouses. Science Direct European Journal for Operational Research 275, 411-
430.
Peng Yang, L. M. (2013). An Integrated Optimization of Location Assignment and
Storage/Retrieval Scheduling in Multi-Shuttle Automated Storage/Retrieval
Systems. Springer Science + Bussiness Media New York 2013, 1145-1159.
Rojas, et al. (2019). The Storage Location Assignment Problem: A Literature Review.
International Journal of Industrial Engineering 10, 199-224.
Rouwenhorst B., e. a. (2010). Warehouse Design and Control: Framework and Literature
Review. (ElSevier, Ed.) European Journal of Operational Research 122, 515-533.
Tutam, M., & White, J. (2019). Multi-Dock Unit Load Warehouse Designs with a Cross
Aisle. Science Direct Trasnportation Research Part E 129, 247-262.
Van Hentenryck, P. (2015). Discrete Optimization. Via Coursera. Melbourne: The
University of Melbourne.
Vidal, et al. (2013). Heuristics for Multi-Attribute Vehicle Routing Problems: A Survey
and Synthesis. European Journal of Operational Research 231, 1-21.
Vilches, V. (13 de 07 de 2018). Expansion. Recuperado el 14 de 10 de 2019, de Fuera de
Serie:
https://www.expansion.com/fueradeserie/gastro/2018/06/28/5b30b84b268e3e3f0a8
b45d2.html
Wang, X., & Tian, J. (2011). Dynamic Programming for NP-Hard Problems. Procedia
Engineering 15, 3396-3400.
Wari, E., & Wheihang, Z. (2016). A Survey in Metaheuristics for Optimization in Food
Manufacturing Industy. Applied Soft Computing 46, 328-343.
Yan, B., Yan, C., Long, F., & Tan, X.-C. (2015). Multi-Objective Optimization of
Electronic Product Goods Location Assignment in Stereostopic Warehouse Based
on Adaptive Genetic Algorithm. Springer Science + Bussiness Media New York ,
1273-1285.
Yang, P., Peng, Y., Ye, B., & Miao, L. (2017). Integrated Optimization of Location
Assignment and Sequencing in a Multi-Shuttle Automated Storage and Retrieval
Systems Under Modified 2n-Cycle Pattern. Taylor Francis, Engineering
Optimization 49:9, 1604-1620.
Yener, F., & Yazgan, H. (2019). Optimal Warehouse Design: Literature Review and Case
Study Application. (ElSevier, Ed.) Computers and Industrial Engineering 129, 1-
13.
