Proyecto de optimización de rutas de vehículos con ventanas de tiempo soportado por algoritmos genéticos
Resumen
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.