Algoritmos Genéticos Aplicados a la Gestión de Inventarios de Artículos No Perecederos (página 2)

Capitulo III – Diseño de la Solución

1. Escenario y Planteo del Marco de Gestión.

Como fue explicado en el capitulo 1, los objetivos de la gestión de inventarios son suministrar el nivel requerido de servicio a los clientes y reducir la suma de todos los costes implicados. Para conseguir ambos objetivos, se ha de responder a una cuestión básica: ¿Cuánto se debe pedir cada vez y cuales son los costos asociados a esas cantidades?.

El planteamiento tradicional es muy restrictivo y no se ajusta a lo que en la realidad del mundo empresarial ocurre. Por ello, cuando una empresa desee calcular la cantidad económica de pedido, debe representar la situación real. Los costes de lanzamiento y de pedido no son los únicos que intervienen.

A continuación se desarrollara el modelo de gestión de inventario resuelto mediante el modelo tradicional y posteriormente mediante algoritmos genéticos.

Algunas de las características en las que están enmarcados los Artículos no perecederos, en base al modelo matemático elegido son:

• Los productos no perecederos utilizan una demanda independiente. Los plazos de entrega ("lead time") de los artículos, es decir el tiempo que transcurre desde que se emite la orden hasta que se recibe el articulo, es conocida y constante.

Es importante recordar que la demanda independiente es la que es influida por las condiciones del mercado.

• La reposición se hace cuando el nivel de existencias llega al stock mínimo.

En este caso consideraremos que existe una cantidad del producto que se mantiene en existencia, a fin de absorber variaciones de demanda o plazo de entregas o situaciones imprevistas. El nivel de protección es un parámetro adicional que se fija políticamente para cada artículo.

• El costo de agotamiento es infinitamente alto y no esta permitido el déficit del producto.
• El costo unitario de adquisición es dependiente de la cantidad a pedir.
• El tamaño máximo del lote es de 1600 unidades.

En la gráfica (ver figura 3.1) se puede observar como se comporta este tipo de gestión de inventarios.

La variable Sr es el stock de reposición. Cuando se llega a ese nivel se sugiere efectuar el pedido de reposición de mercaderías. El Lt es el tiempo entre el pedido y la recepción de la mercadería. La variable Sp, es el stock de protección, el cual es de relevante importancia mientras transcurre el tiempo de pedido y el tiempo de entrega.

La variable T será la que marque la diferencia de tiempo entre un pedido y otro.

Figura 3.1 – Grafico de Stock de Fluctuación con protección

En este contexto supongamos una empresa que comercializa un conjunto de artículos no perecederos (productos Terminados).

Esta empresa alquila depósitos los cuales admiten hasta 400 unidades en almacenamiento y los costos serán más económicos en función a la cantidad de artículos comprados.

Existe un acuerdo con el proveedor, el cual propone un costo por unidad variable en función a la cantidad que compre.

Asimismo el costo de Almacenamiento será variable ya que en este escenario se plantea que cada depósito puede contener hasta 400 unidades. Esto implica que el de alquiler se ira incrementando por cada 400 unidades.

Ante este escenario veamos el cuadro de costos por unidad y de parámetros el cual desarrolla por completo el escenario en que se gestionará. (Ver cuadros 3.2 ).

* Se supone una tasa de interés del %10

Fig. 3.2 Cuadro de variables y Parámetros

1. Calcularemos en primer lugar, los valores de los parámetros del problema.

   Para ello debemos tener en cuenta que, en este caso, el costo de almacenamiento está dado por el costo operativo (seguros, alquiler y calefacción) y por el capital inmovilizado.

   Por otra parte el costo administrativo de emisión de la orden y el costo de la inspección (en el supuesto que es independiente del lote) forman parte del costo de la orden.

   Para este caso se plantea la solución tomando como costo unitario 40 $/u

   1. b = 40$/u

      c = 10 $/u.mes + 15 $/u.m3.2m3/u+40 $*0.1*1/mes = 45 $ u.mes

      k = 1000 + 3000 = 4000 $/Orden

      D = 12.000 u/Año = 1000 u/mes

      Sp = (12.000 u/año)*(año/240 días).5 días = 250 u

      LT = 2 días

   2. Cálculo de los Parámetros
   3. Cálculo de Costos y Cantidades a Pedir

   Una vez calculados los parámetros, se procederá al cálculo de los siguientes ítems :

   Cálculo del Lote óptimo

   q* = √(2*k*D/T*c) = √(2*4000*1000 / 45) = 421,64 = 422 u/lote

   Cálculo del Stock de Reorden

   Sr = 250 +(12000/240)*2 = 350 u

   Cálculo del Costo Total Esperado

   CTE = 40*1000+1/2*45*400+4000*(1000/400) = 59000 $/año

2. Desarrollo de la Solución Clásica

   Para aplicar la técnica de algoritmos genéticos a la solución del problema propuesto se deberá desarrollar la representación seleccionada, así también como la estructura del cromosoma.

   También la forma en que genera la población inicial y como se realiza la selección, cruza y mutación de cada cromosoma.

   1. La codificación más común de las respuestas es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar. En este trabajo los cromosomas manejarán un tamaño de 11 bits.

   2. Representación

      Cada cromosoma implicará cantidades a pedir y estarán representados en forma binaria.

      Supongamos un ejemplo para una población de 4 elementos en donde las cantidades aleatoriamente generadas son 40, 401, 1201, 608 la representación para cada uno de ellos será respectivamente tal cual se muestra en la figura 3.3.

      1024	512	256	128	64	32	16	8	4	2	1
      0	0	0	0	0	1	0	1	0	0	0

      1024	512	256	128	64	32	16	8	4	2	1
      0	0	1	1	0	0	1	0	0	0	1

      1024	512	256	128	64	32	16	8	4	2	1
      1	0	0	1	0	1	1	0	0	0	1

      1024	512	256	128	64	32	16	8	4	2	1
      0	1	0	0	1	1	0	0	0	0	0

      Fig. 3.3 – Ejemplo de la Estructura de un Cromosoma.

   3. Estructura del Cromosoma

      La forma de generar la población inicial será aleatoria.

      Generar la población inicial al azar es lo más rápido, y lleva bastantes generaciones al algoritmo genético llegar a buenas soluciones. Para el caso de ejemplo que se desarrollara, supondremos que la población inicial será aleatoria tomando valores que iran desde 1 a 1600 unidades.

      En consecuencia adoptaremos a modo ejemplo que la población inicial estará compuesta por 4 cromosomas cuyo valor en base decimal será 40, 401, 1201, 608. (Ver representación binaria de cada cromosoma en sección 3.4.2)

      

   4. Generación de la Población Inicial

      Como se explicó en el capítulo 2, la forma de ponderar cada solución, es mediante la función de adaptación.

      La función de aptitud no es más que la función objetivo de nuestro problema de optimización. Una característica que debe tener esta función es que debe ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez. La misma será el promedio de costos dividida el costo total esperado de cada una de las soluciones.

      Aquellos cromosomas cuyo resultado esté por debajo del promedio serán seleccionados para la próxima iteración. La misma será el promedio de costos de todas las soluciones dividido costo total esperado. (Ver figura 3.5.)

      CTE = (Σ Ci / N) / (b.D+1/2.q*.c.T+k.D/q*+c.Sp.T ).

      3.5 Formula de la Función de adaptación.

      Para una mejor comprensión veamos como se aplicaría la función de adaptación para cada una de los cromosomas que forman parte de la población inicia.

      El calculo del costo total esperado podrá observarse en la figura 3.6

      Cromosoma C(i)	Costo Total Esperado	Valor
      40	(10 $/u.mes) + (15 $/u.m3 * 2m3/u)+(0.5 $/mes*2m)+(40 $ * 0.1* 1/mes)	45 $ u.mes
      401	(10 $/u.mes) + (30 $/u.m3 * 2m3/u)+(0.5 $/mes*2m)+(32 $ * 0.1* 1/mes)	72 $ u.mes
      608	(10 $/u.mes) + (60 $/u.m3 * 2m3/u)+(0.5 $/mes*2m)+(26 $ * 0.1* 1/mes)	134$ u.mes
      1201	(10 $/u.mes) + (30 $/u.m3 * 2m3/u)+(0.5 $/mes*2m)+(32 $ * 0.1* 1/mes)	72 $ u.mes

      Fig. 3.6. Calculo del Costo Total Esperado

      Una vez obtenidos los costos se obtendrá el promedio de los mismos (Σ Ci / N), siendo n la cantidad de cromosomas; el cual dividirá a los costos expresados en la columna valor de la tabla 3.6, obteniendo así el coeficiente adaptativo para cada cromosoma C(i).

      Cromosoma C(i)	Función de Adaptación (Σ Ci / N)/CTE	Valor	Prox. Generación
      40	81/45	1.8	1
      401	81/72	1.1	1
      608	81/134	1.1	1
      1201	81/72	0.6	0

      Fig. 3.7 representación de la Función de Adaptación.

   5. Función de Adaptación

      El operador de selección a utilizar, es el basado en el ranking, en donde los cromosomas se ordenan de acuerdo a sus valores para la función de adaptación.

      Luego, se seleccionan para la reproducción a los primeros m (tamaño de la población dividido 2) cromosomas que estén por debajo del promedio CTE de todos los cromosomas.

      Tal como se representa en la figura 3.7 para cada cromosoma la aplicación de el promedio de CTE sobre el CTE de cada cromosoma obtiene como resultado un numero del cual la parte entera indicara la cantidad de cromosomas de ese tipo que pasaran a la próxima instancia para poder reproducirse.

      En consecuencia los seleccionados para el método de cruza serán los valores que se visualizan en la figura 3.8. La cantidad de individuos seleccionados esta indicada en la columna Prox. Generación.

      Cromosoma C(i)	Función de Adaptación (Σ Ci / N)/CTE	Valor	Prox. Generación
      40	81/45	1.8	1
      401	81/72	1.1	1
      608	81/134	1.1	1

      Fig. 3.8 Representación de Cromosomas Seleccionados.

   6. Selección

      El método de reproducción seleccionado es el de Cruza Monopunto el cual consiste en separar a los padres en dos partes para formar dos hijos intercambiando las partes de cada padre.

      Aquí se describe un ejemplo real de Reproducción entre dos cromosomas, en donde el punto de cruza es la posición 5.

      En el ejemplo se tienen los cromosomas que representan las cantidades a pedir 401 y 608. El criterio para determinar cuales cromosomas son los que deben cruzarse, es un criterio de aleatoriedad, ya que los mismos son seleccionados de a pares al azar.

      Siguiendo el ejemplo y teniendo en cuenta que los cromosomas seleccionados son 40, 401 y 608, se toma el par de cromosomas 401 y 608, para que los mismos se crucen, obteniendo dos nuevos hijos (Ver figura 3.9)

      

   7. Reproducción

      La mutación permite mantener diversidad en la población disminuyendo el riesgo de convergencia prematura. Cada gen es mutado con una probabilidad, generalmente baja. La probabilidad puede ser constante durante toda la búsqueda genética o bien adaptativa.

      En el primer caso no se comparte información, en cambio en el segundo, se utilizan frecuentemente estadísticas de la población para adaptar la velocidad de mutación. El método de mutación seleccionado es el de Mutación Simple [Goldberg; 1989], el cual durante la aplicación, elige en forma aleatoria un gen, el cual se muta con cierta probabilidad, habitualmente muy baja.

      La probabilidad de mutación se mantiene constante durante las sucesivas generaciones. Debido a esto es bastante difícil que la probabilidad elegida sea adecuada en todo momento, y por lo tanto, el operador de mutación no es bien explotado.

      El ejemplo es el que se expresa en la figura 3.10

      

      Una vez concluida la mutación ya la nueva población esta lista para una nueva iteración. Para ver como seria el esquema de la nueva generación ver Fig. 3.11

      

   8. Mutación
   9. Criterio de Terminación y Tamaño de la Población Inicial
3. Desarrollo de la Solución Utilizando Algoritmos Genéticos

Se ha hecho notar [Estivill-Castro, 2000] que tamaños de población excesivamente grandes retrasan la convergencia del algoritmo genético, impidiéndole competir con otro tipo de métodos. En el algoritmo propuesto, comienza con una población inicial de n cromosomas, siendo n la cantidad definida.

Con respecto al criterio de terminación se decidió utilizar el Criterio de convergencia de identidad o luego de una cantidad fija de iteraciones.

1. 1. 1. Esta especificación tiene como objetivo analizar y documentar las necesidades funcionales que deberán ser soportadas por el sistema a desarrollar. Para ello, se identificarán los requisitos que ha de satisfacer el nuevo sistema mediante investigación, el estudio de los problemas de las unidades afectadas y sus necesidades actuales. Además de identificar los requisitos se deberán establecer prioridades, lo cual proporciona un punto de referencia para validar el sistema final que compruebe que se ajusta a las necesidades del usuario.

         La especificación debe definir en forma clara, precisa, completa y verificable todas las funcionalidades y restricciones del sistema que se desea construir.

         Esta especificación se ha realizado de acuerdo al estándar "IEEE Recomended Practice for

         Software Requirements Specifications (IEEE/ANSI 830-1993)"

      2. Objetivo
      3. Alcance
   2. Introducción.
2. Capitulo IV – Especificación de Requerimiento del Software

Nombre del Software: AGSTOCK

El sistema deberá poder administrar inventarios fluctuantes con punto de protección utilizando algoritmos genéticos.

El software se encarga de sugerir una cantidad a pedir, la cual calificaremos como cantidad optima a pedir, en un contexto de entradas variables e inciertas.

El sistema tendrá un sentido de optimización constante. Es decir que buscará un universo de soluciones, en donde cada solución es la cantidad a pedir, y evaluará "la mejor" en función a los costos de cada solución.

Los beneficios son :

• Respuesta rápida de procesamiento
• Sugerencia de cantidad óptima a pedir.
• Minimización de costos de inventarios.

1. Definiciones

   Tab Index : Significa que cada objeto de entrada al formulario estará ordenado de manera que el formulario pueda tener una buena navegabilidad.

   Fixed: Se refiere a que los formularios tendrán un tamaño fijo no pudiendo ser modificados por el usuario

   Spinners: Control que permite el incremento y decremento de sus valores mediante sus botones indicadores.

   Visual Fox.: Control que permite el incremento y decremento de sus valores mediante sus botones indicadores.

   Abreviaturas

   CTE : Se refiere al costo total esperado. Ver capitulo 1 sección 1.5

   Acrónimos

   IEEE: Institute of Electrical & Electronics Engineers

   XLS: Extensión de archivo soportada por Microsoft Excel

   DBF: Extensión de archivo soportada por Microsoft Visual Fox

2. Definiciones, acrónimos y abreviaturas.
3. Referencias

Para la recaudación de este texto se han tenido encuentra el siguiente documento:

IEEE Std 830- IEEE Guide to Software Requeriments Specifications. IEEE Standards

Board.

1. Esta sección nos presenta una descripción general del sistema con el fin de conocer las

   funciones que debe soportar, los datos asociados, las restricciones impuestas y cualquier otro factor

   que pueda influir en la construcción del mismo.

   2. Perspectiva del Software.
2. Descripción General.

Interfaces de Usuario.

El objetivo es definir patrones conceptuales suficientemente expresivos en el ámbito del espacio del problema, para traducirlos adecuadamente a su correspondiente representación software.

• Acceso de tecla rápida.
• Navegabilidad de los formularios con "Tabs"
• Pantallas de borde "Fixed"
• Tab Index de los controles en secuencia.
• Utilización de Valores por defecto
• Mensajes de Error, advertencia, y Confirmación
• Agrupación de valores de entrada por Categorías. Ej. Costos de almacenamiento, Costos de preparación
• Utilización de spinners para valores numéricos incrementales en 1

Interfaces del Sistema

• Nombre: FRMCalculoCostos

• Objetivo: La interfaz tiene como objetivo permitir la entrada de todas las variables inherentes al modelo de stock con punto de reposición y las variables inherentes al método de algoritmos genéticos utilizado.

Deberán ingresarse los costos de preparación, de almacenamiento, la cantidad de depósitos utilizados, la demanda mensual estimada y la cantidad de días entre el pedido y la entrega.

También debe ingresarse el tamaño de la población inicial y la cantidad de generaciones.

De esta manera la interfaz será la encargada de proponer una cantidad "optima" sugerida. Esta cantidad sugerida será en función al menor costo total esperado.

• Diseño Aplicado

Objetos "Input"

Objetos "Input"

Objetos que invocan acciones

• Nombre: FRMImprimir

• Objetivo: La siguiente interfaz, es la encargada de definir el destino de la salida de los reportes.

Los reportes disponibles son el de la evolución de cada generación y el de el costo promedio por cada generación.

Para ambos casos lo que permite esta interfaz es poder darle un destino de archivo xls, dbf, pantalla o impresora, según se desee.

• Diseño Aplicado

Objetos "input"

Objetos que invocan acciones

Interfaces de hardware

La aplicación se ejecutará sobre el cliente, con los procesos e interfaz de usuario ejecutándose en el mismo y éste solicitando requerimientos al servidor que cumple su proceso. El sistema operativo de los clientes será MS Windows, XP, 2000, 9x o bien MS Windows NT 4.0 Workstation. No posee un sistema de gestión de bases de datos

Interfaces de Software

Microsoft Excel. Este producto será utilizado para poder lograr visualizar las salidas .xls del aplicativo.

Interfaces de Comunicación

No existen interfaces comunicación.

Restricciones de Memoria

El sistema requiere un mínimo de 32 mb de memoria RAM y un disco principal de 8 MB

1. El aplicativo permitirá la carga de las variables de entrada que se refieren al modelo matemático de stock utilizado y también las variables de entrada para el algoritmo genético.

   En este contexto la función del software desarrollado es proveer de una cantidad óptima sugerida, para efectuar la reposición del stock.

2. Funciones del Software

   Los objetivos de esta tarea son identificar a los responsables de cada una de las unidades y a

   los principales usuarios implicados.

   En la organización se identificaron los siguientes usuarios:

   Grupo de Administradores de Inventarios: Formados por los Responsables de administrar el stock de cada tipo de producto.

   Grupo de Logística: Formado por los gerentes de logística.

   Grupo de Lectores: Formado por los alumnos y profesionales informáticos. También profesores de la institución.

3. Características del Usuario
4. Suposiciones y Dependencias.

El sistema desarrollado esta basado en un modelo matemático que se utiliza en los entornos que necesitan stock de protección.

Los criterios de algoritmos genéticos utilizados son: Selección aleatoria, Cruza monopunto, selección basada en ranking y mutación aleatoria.

No esta preparado para otros criterios.