Información Tecnológica-Vol. 16 N°3-2005, págs.: 45-56

GESTION Y OPTIMIZACION

La Gestión Presupuestaria de Distribución con un Algoritmo Genético Borroso

Distribution Budget Management with a Fuzzy Genetic Algorithm

C. Mendaña–Cuervo y E. López–González
Universidad de León, Facultad de Ciencias Económicas y Empresariales, Departamento de Dirección y Economía de la Empresa.
Campus de Vegazana, s/n., E–24071 León-España (e-mail: ddecmc@unileon.es; ddeelg@unileon.es)

Resumen

En este trabajo se presenta el diseño de un sistema de información para la toma de decisiones presupuestarias. Al tratarse de una decisión que afecta al futuro, este problema se caracteriza por la incertidumbre y no linealidad de la información disponible para su resolución. Además, el elevado número de variables que intervienen lo convierten en un problema de gran complejidad. El tratamiento de la incertidumbre se ha abordado con la aplicación de la Teoría de los Subconjuntos Borrosos y el desarrollo operativo se ha abordado utilizando Algoritmos Genéticos. El resultado del trabajo es la implementación de un Algoritmo Genético Borroso que facilita la gestión presupuestaria de distribución, incluyéndose un ejemplo de aplicación que permite contrastar su validez y operatividad.

Abstract

In this paper, the design of an information system for budget decision is presented. Being this a decision that affects the future, the problem is characterized by the uncertainty and not linearity of the information available for its resolution. Also, the high number of variables that are involved makes this a highly complex problem. The uncertainty has been treated using the Fuzzy Sets Theory and the operative development has been treated using Genetic Algorithms. The result of the work is the implementation of a Fuzzy Genetic Algorithm that facilitates distribution budget management, including an example of application that permits to verify its validity and operability.

Keywords: budget  distribution, budget management, genetic algorithms, information systems design

INTRODUCCIÓN

La distribución supone la planificación, implementación y control físico de los flujos de materiales y bienes finales desde los puntos de origen hasta los puntos de utilización, con objeto de satisfacer las necesidades de los consumidores a cambio de un beneficio.

Para orientar la presupuestación es preciso establecer los objetivos de distribución, de forma que una vez determinado el conjunto de objetivos para cada servicio, la empresa se encuentra preparada para diseñar un sistema que minimice los costes implicados (Kotler, 1991). De hecho, se puede considerar uno de los tópicos más importantes ya que es estratégico para el éxito de cualquier operación de manufactura, pues sus costes representan entre el 30 y el 75% de los costes totales. A estos efectos, cada posible sistema de distribución supone un coste total de distribución D expresado como sigue:

donde para cada sistema propuesto T es el coste total de transporte, FW es el coste fijo total de almacenamiento, VW es el coste variable total de almacenamiento (incluidas las existencias) y S es el coste total de ventas perdidas debido al retraso medio en la entrega, de conformidad con el sistema propuesto.

El sistema de distribución elegido será aquel que minimice el coste total de distribución, lo cual exige el examen de los costes asociados a los diferentes sistemas propuestos. Debido a la dificultad de medir S, la empresa tratará de minimizar el coste de distribución expresado por T + FW + VW, alcanzando el nivel objetivo de servicio al cliente.

La mayor dificultad se encuentra en la minimización de T, tratando de satisfacer, durante el período de estudio, demandas geográficamente distantes de los lugares o “fuentes” donde los productos están disponibles. Por tanto, dados los diferentes medios posibles de transporte, el presupuesto de distribución debe determinar en qué proporciones contribuirá cada “fuente” a satisfacer las diferentes demandas o “destinos”, la afectación de los medios de transporte disponibles a cada una de estas transferencias, y la presupuestación correspondiente.

Dentro de las decisiones de un presupuesto a corto plazo (C/P) que se encuadran en este ámbito sobresale la afectación de las disponibilidades en función de la demanda y el establecimiento de los circuitos de entrega. La complejidad combinatoria de este problema descrita en la literatura al respecto (Kotler, 1991; López–González y Rodríguez Fernández, 2000) implica la necesidad de utilizar mecanismos que sean resolutivos en altas cotas de complejidad. De hecho, el problema planteado se presenta como un problema de asignación cuadrática (Quadratic Assignment Problem, QAP), el cual fue introducido en el contexto económico por Koopmans y Beckman (1957) constituyendo uno de los problemas de optimización combinatoria más estudiado.

El QAP se describe como el problema de asignar un conjunto de actividades a un conjunto de localizaciones, con unas distancias entre las localizaciones y unos flujos entre las actividades. El objetivo consiste en colocar las actividades en las localizaciones de modo que la suma del producto entre flujos y distancias sea mínimo.

Asimismo, las condiciones de incertidumbre y no linealidad que pueden caracterizar este problema sugieren la necesidad de aplicar un tratamiento matemático que facilite operar con información expresada en términos inciertos.

Las consideraciones anteriores han suscitado la conveniencia de aplicar un algoritmo genético, por los buenos resultados de este tipo de heurísticas en problemas de similares características (López-González et al., 1997; Herrera et al., 1999, 2001; López González et al., 2000). Con relación al tratamiento de la incertidumbre, en el desarrollo del problema se ha abordado aplicando la Teoría de los Subconjuntos Borrosos.

PRESUPUESTO A C/P: LÍNEAS CLAVE

Afectación de las disponibilidades en función de la demanda

Se trata de un problema muy conocido en el campo de la investigación operativa, que consiste en buscar el coste mínimo de la distribución cuando se aprovisionan puntos de destino en una proporción variable a partir de diferentes “fuentes” (Anderson et al., 1993), como se muestra en la Figura 1.

La existencia de varios puntos origen de transporte y múltiples puntos de destino implica la necesidad no sólo de encontrar las mejores rutas entre ellos, sino también dar una solución al problema de la asignación de destinos a cada punto de origen. El problema tiene una complicación adicional si se tiene en consideración la existencia de posibles restricciones en los puntos de origen, por ejemplo en relación con la cantidad de demanda que puede cubrir cada uno.

En la literatura sobre este problema suele formularse utilizando programación lineal, aplicando el conocido método simplex, donde resulta aceptado seguir una estrategia general, como la del diagrama de flujo de la Figura 2 (Camm y Evans, 1995). También es común tratar este problema a través del denominado “método del transporte”. Una forma generalizada de reconocer un problema de transporte es por su estructura o naturaleza “de–hacia”, de un origen hacia un destino, donde cada “fuente” i (almacén de materias primas, fábrica, etc.), dispone de un stock a_j; cada destino j (almacén, cliente, etc.) demanda una cantidad d_j, de forma que el objetivo es el envío de cantidades x_ij de cada fuente i a cada destino j para satisfacer las demandas sin exceder las capacidades de las fuentes y de forma que la suma de los costes de transporte sea mínima:

Al afrontar este tipo de problemas, el conocimiento técnico supone que debe haber alguna forma de obtener una solución. De hecho, se conocen las fuentes, las capacidades, las demandas y los costes de cada ruta; debe existir, pues, una combinación óptima que minimice el coste.

Como se puede apreciar en el esquema de la Figura 2, la resolución del problema se afronta construyendo la matriz de transporte y estableciendo una solución inicial factible –óptima o no–, cuya comprobación se efectúa mediante una prueba, para lo cual existen varias técnicas como, por ejemplo, el método de la esquina noroeste (Charnes y Cooper, 1964) o el método de la aproximación de Vogel. Si la solución no es óptima, se revisa repitiendo la prueba, de forma que tras cada iteración, la solución alcanzada se aproxima más a la óptima (Hillier y Lieberman, 1980).

Entre los métodos que permiten pasar de una solución a otra se encuentra el Steping–Stone (Dantzig, 1963), con el que se asegura que al cabo de un número finito de iteraciones se alcanza el mínimo. Otro grupo de métodos que permiten obtener una buena solución rápidamente son los heurísticos, que también pueden ser utilizados para generar la primera solución factible del problema, y entre los que cabe destacar el método de Houthakker (1955) y el método de Hammer–Balas (Balas, 1965).

No obstante, también estos métodos plantean limitaciones que han sido detalladas en la literatura sobre este tema (Taha, 2004).

Organización de los circuitos de entrega

Además de establecer las cantidades transportadas desde cada fábrica a cada cliente, el presupuesto de distribución ha de determinar los circuitos a realizar por los vehículos, constituyendo frecuentemente la fase final de las operaciones de distribución y, en ocasiones, la fase inicial del aprovisionamiento (Arbones, 1990). Se recurre a ellos, en particular, para la entrega de mercancías distribuidas en pequeñas cantidades a numerosos clientes.

La organización de los circuitos de entrega consiste en determinar, por una parte, la composición del parque de vehículos necesario y, por otra, las reglas de su utilización cotidiana. Para poder proceder correctamente a la presupuestación, es preciso, en primer término, disponer de informaciones que pueden agruparse en cuatro categorías diferentes:

Estructura de la demanda y sus fluctuaciones: es decir, se trata de determinar la demanda por unidad de tiempo que debe distribuirse a cada zona, así como el número de clientes a los que hay que servir. En muchos casos esta información sólo puede conocerse de forma no precisa o aproximada.

Grafo de las distancias y de los tiempos recorridos: considerando la posibilidad de modificar los valores, por ejemplo, según las estaciones del año (puertos de montaña, niebla, etc.), en grandes aglomeraciones urbanas (condiciones de circulación), etc., por lo que resulta imposible establecer un grafo con valores precisos de los tiempos de recorrido.

Cuantía de los costes de entrega: ya que puede incurrirse en costes fijos e independientes de los kilómetros recorridos, pero también pueden existir costes variables (proporcionales, progresivos, regresivos u otros) en función del tipo de mercancía, distancia, etc. Su cuantificación en términos precisos resulta, en general muy difícil, por lo que se ha de considerar la posibilidad de operar con valores no precisos.

Métodos de organización de circuitos: ya que aunque este tipo de problemas son frecuentes, la utilización de métodos científicos se encuentra todavía lejos de conocer el desarrollo que justificaría su importancia. Esto es consecuencia, en gran medida, de su naturaleza que hace compleja la construcción de un modelo matemático único para representar los fenómenos que se tratan.

Por tanto, la información relativa a las variables implicadas en el establecimiento de los circuitos de entrega así como la demanda, en muchos casos no pueden ser estimadas en valores numéricos exactos, por lo que resultará especialmente útil poder utilizar herramientas matemáticas que permitan procesar información imprecisa o incierta.

En este trabajo la resolución del problema se ha planteado aplicando la Teoría de los Subconjuntos Borrosos (TSB), rama de la matemática que se ocupa del tratamiento tanto de lo subjetivo como de lo incierto (Zadeh, 1965; Kaufmann y Gil Aluja, 1987). Entre las alternativas que posibilita la TSB para el tratamiento de información expresada en valores inciertos, en el trabajo se ha optado por la utilización de números borrosos trapezoidales frente a los triangulares, ya que se puede admitir que los mismos mantienen un equilibro entre la representación de la vaguedad propia del problema objeto de estudio y la complejidad operativa.

PRESUPUESTO CON UN AG

Planteamiento del problema

Con el presupuesto de distribución se pretende suministrar las cantidades demandadas por los clientes desde las fábricas o los almacenes a un coste mínimo. La información necesaria para establecerlo se refiere a las siguientes variables:

Número de clientes (C) y sus demandas (D). La empresa ha de satisfacer las necesidades de sus clientes, sobre las cuales la información disponible es de tipo previsional y difícilmente expresable en valores conocidos y ciertos. Por ello, se sugiere utilizar números borrosos trapezoidales para la representación de las demandas de los clientes. Así, para n clientes se tiene que:

Número de fábricas (F) y sus producciones (P). Cada fábrica tiene un presupuesto de producción establecido para el período en estudio, de forma que se conoce la cantidad elaborada de cada producto en el período presupuestario. Suponiendo m fábricas:

Capacidad del vehículo de cada fábrica (V). Si se supone que cada fábrica dispone de un vehículo para realizar el transporte de sus mercancías a los clientes, el número de viajes que realice dependerá de su capacidad:

Coste de transporte del vehículo vacío por unidad de distancia (cv). En algunos casos el vehículo deberá realizar recorridos sin carga, bien porque haya agotado su contenido, debiendo rellenar para abastecer a otro cliente, o bien porque se trate del viaje de regreso a fábrica. Por tanto, se ha de considerar el coste de transporte del vehículo vacío que dependerá directamente de la distancia que recorra en esas circunstancias. Así, por ejemplo, si la distancia se mide en kilómetros, el coste de transporte será por cada uno de ellos que recorra el vehículo:

Aumento del coste de transporte por unidad de distancia y por unidad de mercancía (Δcv). Resulta lógico considerar que los recorridos realizados por los vehículos cargados incrementen los costes de transporte en vacío. Este aumento de los costes de transporte dependerá de la distancia recorrida, si bien la información relativa al mismo no suele ser del todo precisa, por lo que la utilización de números borrosos trapezoidales permitirá un mejor acercamiento a su representación:

Distancia entre fábricas y clientes (Df). La distribución se efectúa desde las fábricas a los clientes, por lo que es necesario conocer la distancia que los separa:

Distancia entre clientes (Dc). Las mercancías son transportadas desde un origen a varios destinos, por lo que en muchos casos es posible que, en función de la carga disponible, se realice una ruta que suministre a varios clientes. Por tanto, se ha de tener en cuenta la distancia que separa los diferentes destinos, pues determinarán el coste de transporte de la misma:

El planteamiento anteriormente realizado se aleja de las hipótesis de partida de los métodos tradicionalmente utilizados para la elaboración del presupuesto de distribución. Entre los diferentes motivos se encuentra el hecho de considerar una multiplicidad de variables, en muchos casos inciertas, que implican que el número de posibles combinaciones aumente de forma exponencial. En estas circunstancias, junto a la matemática propia de la TSB, es preciso utilizar herramientas que sean resolutivas en problemas con un alto grado de complejidad combinatoria, sugiriendo en este trabajo la utilidad de los Algoritmos Genéticos (AGs) para optimizar las rutas de distribución de la empresa en las condiciones descritas.

Los AGs son métodos basados en el proceso genético de los organismos vivos que se utilizan en la resolución de problemas de búsqueda y optimización, cuyo desarrollo se debe a Holland (1975).

Los AGs usan una analogía directa con el comportamiento natural, en el que los individuos de una población compiten entre sí, de forma que aquellos individuos con mayor aptitud para sobrevivir tienen mayor probabilidad de generar un gran número de descendientes mientras que los pocos dotados darán lugar a un número de descendientes menor. El comportamiento natural traducido en los AGs presenta las fases de la Figura 3.

Se genera una población de individuos cada uno de los cuales representa una solución factible al problema que se desea resolver. En función de la bondad de la solución que representa cada individuo, se le asigna una valoración que en definitiva establece el grado de efectividad de la solución que el individuo representa frente al resto de soluciones.

Cuanto mayor sea la adaptación de un individuo mayor será la probabilidad de que sea seleccionado para reproducirse y, en consecuencia, para que su material genético se propague en sucesivas generaciones. El proceso de reproducción se realiza cruzando el material genético del individuo con el de otro seleccionado de igual forma, generando una nueva población con mejores características que reemplaza a la anterior. A través de sucesivas generaciones las nuevas poblaciones estarán mejor adaptadas que las poblaciones de las que provienen. Si el AG está correctamente construido, en un tiempo razonable la población convergerá hacia una solución que se aproximará a la óptima del problema.

A este respecto resulta útil la definición de convergencia introducida por De Jong (1975), donde establece que si el AG ha sido correctamente implementado, la población evolucionará a lo largo de sucesivas iteraciones o generaciones de forma que la adaptación del mejor y el promedio general se incrementarán hacia el óptimo global. La convergencia es en consecuencia la progresión hacia la uniformidad: se establece que un gen ha convergido cuando el 95% de la población tiene el mismo valor para dicho gen. Por tanto, se plantea que la población converge cuando todos los genes de cada individuo lo hacen.

La resolución planteada en este trabajo para el problema de distribución descrito se ha abordado mediante la implementación de un AG básico. Por este motivo, se ha optado por utilizar los parámetros más usuales en este tipo de algoritmos, tanto para la selección como para los operadores genéticos, cuya descripción se pasa a realizar a continuación.

Generación de las soluciones

Existen distintas posibilidades de llevar a cabo la codificación de los individuos, siendo la más utilizada la que se basa en el alfabeto binario {0, 1}. No obstante, esta representación no resulta útil en muchos problemas de búsqueda, al no ser posible encontrar una codificación que de sentido a cada una de las posiciones de que consta el genotipo. Incluso, en casos en que sí es posible, ésta no garantiza que represente con fidelidad el dominio del problema, lo cual plantea la necesidad de establecer posibles soluciones al problema de representación o codificación que se ajusten al mismo. A este respecto, existen estudios (Fang, 1994) que establecen las normas básicas a tener en cuenta para el diseño de una codificación óptima y que no dependen del tipo de codificación utilizada. Por tanto, las buenas propiedades de los AGs no dependen del uso del alfabeto binario, razón por la cual en muchos casos se han utilizado codificaciones no binarias, más naturales para los problemas particulares a los que se desee aplicar. Entre estas codificaciones se pueden destacar la utilización de vectores de números reales, vectores de números enteros, listas ordenadas, expresiones en lenguaje lisp, matrices bidimensionales, etc.

En la resolución del problema planteado, las soluciones deben venir dadas por un conjunto de rutas de distribución, compuestas por las cantidades a transportar desde cada origen a cada destino, y el orden en el que estos últimos se van a abastecer. Por tanto, parece razonable que la codificación a utilizar venga representada por números enteros tanto para las rutas como para el orden, mientras que en relación a las cantidades a transportar su codificación (en números enteros o reales) dependerá de la unidad de medida del material de que se trate (kgs., cajas, envases, etc.).

En concreto, para codificar cada una de ellas de forma que resulte manejable por el algoritmo, se han utilizado dos matrices de (n × m) elementos, siendo n el número de fábricas y m el número de clientes. La primera de ellas contendrá las cantidades que se envían desde cada origen a cada destino, mientras que la segunda, recogerá el orden en el que se recorren los clientes que abastece cada fábrica. De este modo, se consigue abarcar todas las posibles combinaciones de presupuesto de distribución que se puedan presentar.

En relación a la población inicial del AG, ésta debería ser lo más variada posible, sobre todo para evitar convergencias prematuras. Según Michalewicz (1992), la forma más útil es la generación aleatoria, en la que las soluciones iniciales estarán distribuidas de manera uniforme en el espacio de búsqueda. No obstante, existen otras alternativas como la elección de una población inicial factible y/o próxima al óptimo utilizando el conocimiento específico.

En el caso objeto de estudio, la generación de las soluciones iniciales (población inicial) se realiza de forma aleatoria para cada matriz, teniendo en consideración las restricciones existentes como son capacidad de los vehículos, producción de cada fábrica, demanda de cada cliente, etc. Una vez generada aleatoriamente la población inicial se debe comprobar que cumplan las restricciones –eliminando aquellas soluciones no factibles–, consiguiendo que todos los individuos iniciales representen soluciones factibles al problema.

Evaluación de las soluciones

Con el fin de seleccionar las mejores soluciones, se evalúa cada una en función de los costes en que se incurriría si se llevara a la práctica dicha solución, de forma que aquellas con menor coste serán las más interesantes para la empresa.

En concreto, para cada fábrica, primero se determina el coste de transportar el vehículo cargado desde la misma al primer destino, en el que se descarga la cantidad asignada a ese cliente, siguiendo el vehículo en dirección al segundo destino o volviendo al origen si quedara vacío. Una vez que se han recorrido todos los clientes que la solución determina para dicha fábrica, el vehículo regresará vacío al origen, completándose el circuito. Por tanto, el coste de la solución se obtendrá como la suma de los costes de la distribución del conjunto de las fábricas, siendo las soluciones más adecuadas las de menor coste, por lo que la adecuación se obtiene como la inversa del coste de cada solución.

Proceso de selección

La selección de individuos que van a actuar como “padres” se realiza normalmente al azar, utilizando un procedimiento que favorezca a los mejor adaptados, para lo cual se asigna a cada individuo una probabilidad proporcional a su adaptación. A este procedimiento se le conoce con la denominación de “ruleta sesgada” cuyo objetivo es que los individuos mejor adaptados sean seleccionados, incluso varias veces por generación, mientras que aquellos individuos con una adaptación pequeña se crucen en muy pocas ocasiones.

No obstante, existen distintas posibilidades para seleccionar los individuos que se considerarán “padres” para la siguiente generación, considerándose tradicionalmente tres mecanismos para realizarla: selección proporcional a la adecuación (selección con ruleta), selección por ranking y selección por torneo.

En el problema planteado los individuos que se van a convertir en los padres de la siguiente generación han de ser elegidos por su mayor adecuación, es decir, por su menor coste. Para ello, al calcular la adecuación como la inversa del coste se utiliza el “método de selección con ruleta” (Holland, 1975) que emplea ésta como indicador de las posibilidades que tiene cada individuo de pasar el proceso de selección.

Operadores de cruce y mutación

El proceso de reproducción consiste en primer lugar en cruzar las soluciones buenas seleccionadas. La versión más común del operador de cruce es el cruce en un punto, el cual consiste en localizar un punto al azar en la cadena de cromosomas de los padres, de forma que los descendientes se obtienen intercambiando las cadenas de los progenitores entre sí. Sin embargo, existen varias alternativas que introducen variaciones en el operador de cruce clásico. Entre las más significativas se encuentran el cruce de n puntos, el cruce uniforme (Syswerda, 1989), el cruce segmentado y el cruce cíclico (Goldberg, 1989).

No obstante, el principal problema de estos operadores se plantea en el caso de aplicación a problemas con restricciones, en los que la actuación de los mismos puede producir individuos no factibles, como en el problema que nos ocupa. Existen diversas posibilidades para solucionar dicho problema, entre las que destacan: eliminar los individuos inválidos, emplear un mecanismo de reparación para producir soluciones correctas o utilizar una función de penalización que haga que las soluciones inválidas tengan una adecuación menor que las válidas.

En el problema objeto de estudio, al tratarse de cadenas complejas, se ha de practicar un cruce que mantenga la factibilidad en los “hijos”, por lo que se realiza un cruce en la matriz representativa de las cantidades a distribuir. Para combinar la información de estas matrices se ha optado por un cruce especial que consiste en una matriz que contiene el valor medio en enteros de cada celda de las matrices “padres” en aquellos casos en los que las diferentes fábricas coinciden en clientes. De esta forma, los descendientes de las matrices no representarán soluciones factibles al problema, ya que posiblemente los clientes no quedarán satisfechos y/o las fuentes quedarán descompensadas en cuanto a las cantidades ofertadas por cada una de ellas. Por este motivo, es preciso someter a las soluciones resultantes del cruce a un proceso que permita tratar los individuos no factibles convirtiéndolos en factibles, ajustando las cantidades obtenidas de este proceso.

El cruce en las cantidades transportadas trae consigo modificaciones en los circuitos realizados, por lo que no se ha considerado necesario realizar un cruce en la matriz representativa de los circuitos, con el objetivo de no alejar en exceso las soluciones resultantes de este operador de los individuos originales seleccionados como padres.

En segundo lugar, en el algoritmo desarrollado se incluye la posibilidad de aplicar un operador de mutación sobre las cantidades a distribuir desde cada fábrica a cada cliente. Si bien existen diferentes alternativas además del operador de mutación clásico como la mutación estándar, la mutación sobre genes, la mutación no estacionaria, mutación no uniforme, etc., la actuación de este operador plantea los mismos problemas que el operador de cruce en relación a los descendientes obtenidos. Por tanto, se deben de establecer mecanismos que faciliten el tratamiento de las soluciones no factibles obtenidas.

En el caso del AG implementado, para mutar las matrices y que sigan ofreciendo soluciones factibles se sugiere emplear el siguiente método: En primer término, se selecciona una fábrica de la solución que va a sufrir la mutación (F₁) y un cliente (C₁) de la misma que reciba alguna cantidad de mercancías. A continuación, se selecciona aleatoriamente otra fábrica (F₂) que tenga un cliente (C₂) con una cantidad mayor a la del cliente 1, con la finalidad de poder mutar sus cantidades entre sí, de forma que al cliente 1 en la fábrica 1 y al cliente 2 en la fábrica 2 se les sustrae la cantidad generada aleatoriamente y, a su vez, al cliente 1 en la fábrica 2 y al cliente 2 en la fábrica 1 se les añade dicha cantidad.

Por otro lado, al mutar las matrices de las cantidades, las rutas que recorren los vehículos de cada fábrica en la distribución deben ser reasignadas, de forma que las rutas sufren asimismo una mutación como consecuencia de la operativa anterior. Con ello, se consigue modificar la matriz representativa, manteniendo su viabilidad como solución del problema. Con estos pasos se consigue mutar la matriz de cantidades sin que deje de ser una solución factible al problema.

Finalmente, cabe poner de manifiesto que la actuación de estos operadores es probabilística, es decir, habitualmente no se aplican los operadores genéticos a todos los individuos, sino que se establece de una probabilidad de que se produzca el cruce (P_c, probabilidad de cruce) y una probabilidad de que se lleve a cabo la mutación (P_m, probabilidad de mutación). En un principio, Goldberg (1989) estableció como valor para la probabilidad de cruce el 60%, si bien estudios posteriores han analizado la posibilidad de adaptar dichas probabilidades al estado del proceso genético (Michalewicz, 1992). Por su parte, según los estudios realizados por Holland, la probabilidad aceptable para el operador de mutación sería la comprendida entre 0’1 y 1%.

Sin embargo, el valor de dichas probabilidades depende, entre otros factores, del tipo de problema y de la representación utilizada, siendo utilizados para perfeccionar el funcionamiento del algoritmo. En nuestro caso, la finalidad del trabajo no es implementar un algoritmo óptimo para un problema concreto, sino demostrar la utilidad de esta heurística en el problema de estudio. Por este motivo, en el software implementado se ha establecido la posibilidad de que el usuario final fije los valores de las probabilidades de cruce y mutación e, incluso, que los valores sean –al igual que el resto de información– borrosos.

Condición de terminación o parada

El criterio de terminación o parada es el mecanismo que determina cuando se debe concluir la ejecución del algoritmo, es decir, determina la finalización en la búsqueda de la solución. Para ello existen numerosas posibilidades: establecer un número máximo de evaluaciones de la función objetivo, establecer un número de iteraciones, fijar una solución cuya calidad se estima suficiente, etc.

En el modelo propuesto se ha optado porque el algoritmo se ejecute un número de generaciones determinado (a elección del usuario) hasta mostrar la mejor solución alcanzada. Además, con el fin de no perder buenas soluciones se ha introducido el elitismo (De Jong, 1975; Goldberg, 1989), tratando de evitar que se pierda la mejor solución de una generación hasta que no sea sobrepasada por otra superior en adecuación al problema.

Con las características descritas, se ha construido un Algoritmo Genético Borroso, implementado en Visual Basic, que permite llevar a cabo el proceso de elaboración del presupuesto de distribución en ambientes inciertos y cuando existe no linealidad en el comportamiento de las variables implicadas.

APLICACIÓN DEL MODELO

Con objeto de contrastar el modelo para la elaboración del presupuesto de distribución, a continuación se muestra un ejemplo de aplicación práctica del algoritmo desarrollado. El objetivo del ejemplo es facilitar la comprensión del AG borroso, por lo que se ha utilizado un número de variables manejable. No obstante, la velocidad de ejecución del algoritmo y los parámetros utilizados en su implementación hacen que el mismo sea generalizable:

i) Se supone una empresa con cuatro instalaciones productivas (F) siendo los valores asociados a cada una de las variables informativas del problema (producción, capacidad del vehículo, coste del transporte del vehículo vacío y aumento del coste de transporte derivado de la carga) los recogidos en la Tabla 1.

ii) La empresa abastece a ocho clientes diferentes ubicados en distintas localidades, para los cuales se ha estimado la demanda para el período de estudio, representada por los números borrosos trapezoidales de la Tabla 2.

iii) La empresa conoce además las distancias en kilómetros que separan sus cuatro instalaciones de los clientes (Df), recogidos en la Tabla 3, y las que separan los clientes entre sí (Dc) mostradas en la Tabla 4.

Como se ha comentado con anterioridad, los parámetros de funcionamiento del AG deben ser introducidos por el usuario del software. En la pantalla de la Figura 4 se muestra la captura de datos para los operadores de cruce y mutación, en la que se muestran los valores utilizados en el ejemplo, pudiendo observarse la utilización de una probabilidad de mutación superior a la de cruce, lo que trata de reducir el menor grado de variabilidad genética del operador de cruce. De forma análoga, el usuario podrá fijar el número de individuos y el número de generaciones como criterio de parada. Por tanto, los gráficos y datos mostrados en las figuras son ejemplos ilustrativos con los valores introducidos para dichas variables.

Tabla 1: Datos del presupuesto

Tabla 2: Demandas previstas

Tabla 3: Distancias entre fábricas

Tabla 4: Distancias entre clientes

De acuerdo con dicha información, el algoritmo debe elaborar un presupuesto de distribución económico, para lo cual deberá dar respuesta a dos cuestiones: qué fábricas abastecerán a los diferentes clientes y en qué cantidad, y cuál será la ruta que sigan los vehículos en la distribución de las mercancías. En concreto, la solución propuesta con las cantidades a distribuir desde cada fábrica a cada cliente se muestra en la Tabla 5.

Tabla 5: Solución propuesta

Finalmente, para el presupuesto de distribución propuesto como solución se estima incurrir en un coste de transporte aproximado (borroso) para el período analizado de:

(685.100, 948.600, 948.600, 1.187.100)

En cuanto a los circuitos a realizar en el proceso de distribución propuesto, el orden de las rutas para cada una de las fábricas se muestra en la Tabla 6.

Tabla 6: Orden propuesto por el AG

Finalmente, como ejemplo de la efectividad del modelo, la Figura 5 muestra gráficamente la evolución que experimentó el coste esperado de la mejor solución (individuo elitista) en cada generación, pudiendo observarse la tendencia decreciente que el mismo experimenta a medida que se suceden las generaciones.

CONCLUSIONES

El desarrollo del trabajo ha permitido plantear un modelo de resolución del problema del presupuesto de distribución, abordando dos de las dificultades inherentes al mismo:

a)   la necesidad de operar con información previsional, que afecta al futuro, por lo que en muchos casos será imprecisa e incierta.

b)   la complejidad combinatoria derivada del elevado número de variables que le afectan y de las interrelaciones entre ellas.

La solución planteada para el primer problema ha sido la aplicación de la Teoría de los Subconjuntos Borrosos que facilita la operativa con información imprecisa. La complejidad del problema ha sido tratada con una heurística (un algoritmo genético) que, si bien no garantiza la obtención de una solución óptima, sí facilita una solución próxima y cuya validez en problemas de búsqueda y optimización complejos ha sido ampliamente contrastada.

En consecuencia, el principal resultado del trabajo de investigación es un algoritmo genético borroso que permite elaborar el presupuesto de distribución considerando las variables del problema expresadas en valores imprecisos, proporcionando una solución próxima al óptimo en un escaso periodo de tiempo.

La validez del modelo queda puesta de manifiesto mediante su aplicación a un ejemplo numérico, que permite contrastar las ventajas que presenta el algoritmo genético borroso, tanto en el planteamiento del problema –al facilitar la obtención de información– como en su resolución. Además, el poder modificar los parámetros de funcionamiento del mismo, facilita la comprensión de su funcionamiento.

REFERENCIAS

Anderson, D.; S. Sweeney y T. Williams, Introducción a los modelos cuantitativos para administración. Grupo Editorial Iberoamérica, México DF – México (1993).

Arbones, E., Logística Empresarial. Marcombo, Barcelona– España (1990).

Balas, E., An additive algorithm for solving the linear programs with zero–one variables, Operations Research: 13 (4), 517–546 (1965).

Camm, J. y R. Evans, Management Science: Modelling Analysis and Interpretation. International Thomson Publishing, Cincinnati– USA(1995).

Charnes, A. y W.W. Cooper, Management Models and Industrial Applications of Linear Programming. John Wiley, New York– USA(1964).

Dantzig, G., Linear Programming and Extensions. Princeton UniversityPress, Princeton– USA(1963).

De Jong, K.A., “An Analysis of the Behaviour of a Class of Genetic Adaptive Systems”. Tesis Doctoral, Univ. of Michigan, USA(1975).

Fang, H., Genetic Algorithms in Timetabling and Scheduling, in Department of Artificial Intelligence. Universityof Edinburgh: Doctoral Dissertation (1994).

Goldberg, D., Genetic Algorithms in Search, Optimisation and Machine Learning. Addison Wesley, Boston– USA(1989).

Herrera, F.; E. López-González, C. Mendaña-Cuervo y M.A. Rodríguez-Fernández, Solving an Assignment Problem under Linguistic Valuations with Genetic Algorithms, European Journal of Operations Research: 119, 326–337 (1999).

Herrera, F.; E. López-González; C. Mendaña-Cuervo y M.A. Rodríguez-Fernández, A Linguistic Decision Model for Personnel Management solved with a Linguistic Biobjective Genetic Algorithm, Fuzzy Sets & Systems: 118, 47–64 (2001).

Hillier, F. y G. Lieberman, Introduction to Operations Research. Holden–Day, San Francisco– USA(1980).

Holland, J.H., Adaptation in natural and artificial systems. Universityof Michigan Press, Michigan– USA(1975).

Houthakker, H.S., On the numerical solution of the transportation problem, Jorsa: 3, 210–214 (1955).

Kaufmann, A. y J. Gil–Aluja, Técnicas operativas de gestión para el tratamiento de la incertidumbre. Hispano Europea, Barcelona-España (1987).

Koopmans, T.C. y M.J. Beckman, Assignment Problems and the Location of Economic Activities. Econometrica: 25, 53-76 (1957).

Kotler, P., Marketing Management: Analysis, Planning, Implementation and Control. Prentice–Hall, London– UK(1991).

López-González, E. y M.A. Rodríguez Fernández, Genetic Optimisation of a Fuzzy Distribution Model, International Journal of Physical Distribution and Logistics Management: 30 (7/8), 681–696 (2000).

López-González, E., M.A. Rodríguez Fernández y C. Mendaña Cuervo, The logistic decision making in management accounting solved with genetic algorithm. Mathware & Soft Computing, VII (2-3), 229–241 (2000).

López-González, E.; C. Mendaña-Cuervo y M.A. Rodríguez-Fernández, La selección de personal con un algoritmo genético borroso, Invest. Europeas de Dirección y Economía de la Empresa: 2 (2), 61–76 (1997).

Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs. Springer–Verlag, Berlin(1992).

Syswerda, G. Uniform Crossover in Genetic Algorithms. In Third International Conference on Genetic Algorithms. San Mateo–CA–: Morgan Kaufmann (1989).

Taha, H. Investigación de Operaciones, Prentice Hall, México (2004).

Zadeh, L.A., Fuzzy Sets. Information and Control (8), 338–353 (1965).

Monseñor Subercaseaux 667

La Serena - Chile

Tel.: (56-51) 2551158

Fax: (56-51) 2551158


citrevistas@gmail.com