Proyecto de optimización de rutas de vehículos con ventanas de tiempo soportado por algoritmos genéticos

Abstract

A lo largo de la historia el hombre ha tratado de adaptarse al entorno para cubrir una serie de necesidades, que un principio fueron básicas, pero a medida que transcurre el tiempo se van convirtiendo en más complicadas. El hombre en todo este tiempo ha tratado de imitar a la Naturaleza en mayor o menor grado para la consecución de sus objetivos. Con los Algoritmos Genéticos se pretende dar un paso más imitando la Teoría de la Evolución. El problema planteado es de un interés creciente en nuestros días, ya que las empresas tienen unos altos índices de calidad en sus especificaciones y quizá lo que más diferencia a unas de otras es la calidad en los servicios, entre ellos la distribución. Este problema, con las restricciones que plantea es inabordable con las técnicas matemáticas clásicas, de aquí el interés de utilizar los Algoritmos Genéticos, que permiten una adaptación del problema al medio y una evolución hacia la solución óptima. El proyecto diseña y suministra un elemento de análisis y estructuración de rutas de transporte, de cara a maximizar una función multicriterio, cuyos elementos en, algunos casos, son objetivos contrapuestos. La característica primordial del sistema es tener un alto grado de versatilidad, ya que en principio, al ser una consultoría estratégica la empresa desde la que se pretende instaurar, no tiene definido el tipo de cliente en el que se va a realizar la implantación. Como consecuencia es un importante elemento de ayuda para empresas del sector logístico. Un punto previo a la descripción del sistema es la definición de las "ventanas de tiempo", es la base de las especificaciones de los clientes y se definen como el intervalo tolerable de servicio y dentro de éste el intervalo deseable para ser servidos. Ninguna de las soluciones posibles es viable si se encuentra fuera de una "ventana de tiempo". El proceso que se sigue en el sistema comienza por la asignación de una serie de coeficientes mediante la valoración de una serie de cuestionarios, estos pesos serán los coeficientes de la función multicriterio. El paso siguiente es la elección de clientes que van a ser servidos, incluidos en una ruta, así como los vehículos que se asignan por parte de la empresa suministradora. Una vez establecidos estos parámetros el sistema asigna las distancias y los tiempos entre los distintos clientes (según sea el tipo de ruta: fija, variable en el día, etc.). Es en este momento cuando se introduce el algoritmo genético con sus técnicas de evolución; el proceso comienza con la generación de dos rutas aleatorias y su evaluación con la función multicriterio. Estas rutas serán los "padres" de la siguiente generación y sus "hijos" serán evaluados por la función objetivo. Una vez real izadas las evaluaciones se elegirán como creadores de la siguiente generación los dos mejores individuos de entre los "padres" y los "hijos". Para llegar al resultado óptimo de satisfacción de restricciones se aplican sistemas de optimización de soluciones basados en la programación lineal. Si se produce un estancamiento en el proceso se introduce un elemento "inmigrante" que se encargará de variar las condiciones de las soluciones, para volver a generar una nueva solución. La solución resultante será la que presente un menor valor resultado de la función multicriterio. El sistema es de fácil implantación, ya que el periodo calculado para su puesta en marcha en una empresa es de quince días. Además el sistema puede ser fácilmente amortizable por una empresa, debido a los fuertes ahorros en transporte que supone su implantación para las empresas. El sistema se acompaña con un software en el que se desarrolla todo el proceso.