Aplicación Informática para la Planificación de Rutas de Transporte PDF

DESARROLLO DE UNA APLICACIÓN INFORMÁTICA PARA LA RESOLUCIÓN DEL PROBLEMA DE PLANIFICACIÓN DE RUTAS DE TRANSPORTE EN ENTORNOS DINÁMICOS Eduardo Guillén Solórzano, [email protected]...

DESARROLLO DE UNA APLICACIÓN INFORMÁTICA PARA LA RESOLUCIÓN DEL PROBLEMA DE PLANIFICACIÓN DE RUTAS DE TRANSPORTE EN ENTORNOS DINÁMICOS Eduardo Guillén Solórzano, [email protected] Susana Barbeito Roibal, [email protected] Manuel Martínez Carballo, [email protected] Universidade da Coruña ABSTRACT En este trabajo se presenta un nuevo software para la resolución del conocido problema de la planificación de rutas de transporte en entornos de tiempo restringido, también denominado VRPTW. Este nuevo software de resolución se fundamenta en el algoritmo desarrollado a tal efecto y que ha sido denominado ALADIN (Algoritmo de Adición en Inserción). Este algoritmo integra procedimientos de construcción de las rutas de transporte en los que se implementan reglas de adición e inserción de nodos para configurar las diferentes rutas que han de ser servidas. El software desarrollado presenta numerosas ventajas derivadas de su flexibilidad tanto para la modificación de los datos de partida, como para la introducción de nuevos parámetros de usuario, lo que permiten su aplicación incluso en entornos dinámicos en los que las visitas surgen a medida que las rutas se van cubriendo por la flota de vehículos. Palabras Clave: VRPTW, Métodos Heurísticos, Optimización, Logística, Rutas de Transporte 1. INTRODUCCIÓN En esta sección se presentan los datos de partida que configuran el problema conocido como Vehicle Routing Problem with Time Windows, y que hace referencia a la planificación de rutas de transporte con ventanas de tiempo. La descripción del problema consiste en que un número determinado de vehículos dispuestos en un almacén central y con unas capacidades y tiempo limitadas, deben de servir a un conjunto de clientes dispersos aleatoriamente en el espacio, ciertas cantidades de mercancía, y que han de suministrarse en momentos concretos del horizonte temporal de planificación. Esta planificación de rutas ha de realizarse recorriendo una distancia total mínima, siendo este el objetivo último del problema. Notación Para la resolución de este problema se ha desarrollado un algoritmo aproximativo de solución y se ha programado una aplicación informática de apoyo a la toma de decisiones por parte del usuario. La interfaz del programa se presenta en la figura 1. Esta interfaz contempla dos áreas básicas. En el lado izquierdo de la interfaz se presentan todos los datos requeridos por el programa para la aplicación de las reglas de decisión, y en el lado derecho se proporcionarán las soluciones al usuario. Figura 1. Imagen de la Interfaz de la aplicación 1 En la sección de los datos de partida se contemplan los siguientes: Nodo: La columna nodo identifica a todos y cada uno de los nodos existentes en el problema, siendo 0 el nombre del nodo que hace de depósito, y 1.... N los nombres de los siguientes nodos. En una planificación real, los nombres de los nodos serían propiamente nombres de clientes o de ciudades. Coordenada X: Es la coordenada relativa al eje horizontal, y que se podría identificar con las coordenadas geográficas del nodo en cuestión. En este caso se correspondería con la “longitud” Mide la distancia horizontal con respecto al eje de ordenadas. Coordenada Y: Analógicamente representa la coordenada relativa al eje vertical, y por ello se identificaría con la “latitud”. Mide la distancia vertical con respecto al eje de abscisas. Demanda: La demanda hace referencia a la cantidad de producto demandada por el cliente en cuestión. Se podría identificar con los kilogramos, litros, o cualquier otra unidad de medida que se ha de servir, o bien recoger, si aplicamos el criterio de recogidas. Si bien en este trabajo no se ha contemplado la coexistencia de recogidas y entregas simultáneas. Tiempo de apertura: El tiempo o momento de apertura hace referencia al momento temporal en el que el nodo en cuestión abre para la entrega de mercancías, y a partir del cual ha de entrar un vehículo para realizar el servicio. Tiempo de cierre: Es el momento temporal en el que el nodo en cuestión cierra sus puertas y a partir del cuál no podría ser servido por ningún vehículo. Horizonte total de planificación: El nodo central o depósito marca el horizonte temporal en el que abren y cierran todos los nodos. Tiempo de servicio: Por último, se establece la última variable que es el tiempo de servicio requerido por el vehículo para realizar la entrega en el nodo correspondiente. Número de nodos de los que consta el problema: Esta variable del problema hace referencia al número total de clientes que han de ser servidos desde el depósito central, y que puede oscilar según los problemas que se traten de resolver. En los problemas tipo aportados en la literatura generalmente se contemplan problemas de 100 nodos con diferentes distribuciones de los mismos. Sin embargo también se han desarrollado versiones más simplificadas con 50 y 25 nodos de estos mismos problemas tipo. Por ello en este trabajo se ha optado por establecer la posibilidad de introducir cantidades variables de clientes a ser servidos por la flota de camiones disponible, para poder afrontar cualquiera de los problemas tipo de la literatura, así como para garantizar una mayor adaptabilidad de los fundamentos del algoritmo a la situación real del problema. Estos nodos cuentan además con el nodo central o depósito desde el que parten y al que han de llegar todos y cada uno de los camiones. Este nodo se identifica con el nodo 0, por ello el número total de nodos de todo problema será el número de clientes +1. Igualmente se establecen como datos el número de vehículos disponible para realizar la planificación de las rutas, así como la capacidad máxima de cada uno de los vehículos. En el cuadrante inferior izquierda se contemplan los diferentes parámetros de las que consta el problema. Estos parámetros son definidos por el usuario para conseguir diferentes soluciones. Número inicial de rutas R: Este parámetro obedece a la necesidad de planificar desde el comienzo del horizonte un número determinado de rutas, a partir del cuál se irá incrementando en función de las necesidades del problema. Se corresponde con el número total de nodos semilla con los que el usuario decide iniciar la planificación. Parámetro β: Se trata del parámetro penalizador de desplazamientos elevados en las posibles inserciones simples de nodos cada vez que se considera un nodo crítico. 2 Parámetro γ: Consiste en el parámetro penalizador de desplazamientos en las posibles inserciones dobles de nodos entre el nodo cabeza de ruta y el nodo crítico anterior. Recordemos que se considera conjuntamente con el parámetro β. 2. MÉTODO DE CÁLCULO A partir de la introducción de estos datos, el programa establece el conjunto de relgas y algoritmos necesarios para obtener una solución. Estas reglas se han integrado dentro de un algoritmo heurístico de solución denominado ALADIN, en el que se utilizan reglas básicas para la construcción de las rutas. Este algoritmo constituye el alma del programa y su objetivo es resolver el problema de forma aproximativa en un tiempo muy reducido, de manera que la solución se devolverá posteriormente a la Interfaz para su representación. Los detalles del algoritmo se recogen en las siguientes líneas. La notación del mismo es la siguiente: N Número total de clientes i Índice de los clientes: i = 1, 2, …, N xi Abscisa de la posición del cliente i yi Ordenada de la posición del cliente i tsi Tiempo de servicio del cliente i. V Número total de vehículos disponibles k Índice de los vehículos. k=1,...,V q Capacidad de los vehículos en consideración di Demanda del cliente i tai Momento de apertura del cliente i tci Momento de cierre del cliente i ta0 Momento de apertura del depósito central tc0 Momento de cierre del depósito central dij Distancia entre i y j. El algoritmo calcula una matriz de distancias entre todos y cada uno de los nodos, incluyendo tanto los clientes como el depósito central. Las distancias entre cada par de nodos i y j se calcula a través de la fórmula de Pitágoras que proporciona la distancia euclidea entre dos puntos. tij Tiempo de desplazamiento entre el cliente i y el cliente j, equivalente a la distancia teki Tiempo de espera antes de visitar el nodo i por el vehículo k. LRk Lista de nodos que pertenecen a la ruta k. Se trata de un vector de nodos ordenados que indican las sucesivas visitas que realiza el vehículo k. trk Momento en el que se encuentra el vehículo k. Esta variable será igual a la suma de los tiempos de desplazamiento entre los nodos que visita este vehículo k, más los tiempos de servicio de los nodos de la ruta k, más las esperas que se han de realizar antes de visitar cada uno de los nodos de la ruta k. Los tiempos de desplazamiento de los nodos será la suma de tpq cuando q>p ck Carga total del vehículo k. La carga total del vehículo k es la suma de las demandas de los nodos que ha visitado. CRk La cabeza de la ruta k se corresponde con el nodo en el que está ubicado el vehículo k. Dk Distancia total recorrida por el vehículo k. Esta variable es igual a la suma de los desplazamientos entre los nodos que visita este vehículo. Ek Espera total que realiza el vehículo k. 3 En los siguientes apartados se detallan las reglas de decisión que subyacen del algoritmo desarrollado en este trabajo para la resolución del VRPTW. En las figuras 2 y 3 se recoge el diagrama de flujo del algoritmo en el que se ha resumido de forma muy escueta su funcionamiento y reglas básicas. Estas reglas se analizan y desarrollan con mayor profundidad en las próximas líneas. Obtención de datos desde la interfaz A Creación L0=[1,…,N] Depósito central=0 Parámetros R, ß, ? Cálculo de la matriz de distancias Obtención de la lista L1 de R nodos i críticos con min hi=tci-t0i Generación de ruta k para nodos i LRk= CRk= ck=0 trk=0 Dk=0 Ek=0 Selección del nodo i con min hi=tci-t0i Si ¿Es hi < min ts? No Obtención de la lista L2 de nodos m de L0 que cumplen: tam tom tam+ tsm + tmi tci t0m+tsm+tmi tci t0m+tsm+tmi+nhi =tci t0m+tmi ßt0i t0m + tmi + ti0 + teki tc0 teki=[tai-(t0i)]+ dm+di q Adición directa del nodo i a la ruta k LRk=[0, i] ¿Hay nodos en L2? No CRk=[i] ck=di trk=t0i+ tsi + teki Si Dk=t0i Ek=teki teki=[tai-(t0i)]+ Obtención de la lista L3 de nodos m y l de L2 que cumplen tam t0m tal tom+tsm+tml t0m+tsm+ tml+tsl+tli tci t0m+tsm+ tml+tsl+tli+ nh'i = tci t0m+ tml+tli ß ? t0i t0m +tml+ tli + ti0 +teki tc0 teki=[tai-(t0m+tsm+tml+tsl+tli)]+ dm+dl+di q Escojo el nodo m de ¿Hay nodos en L3? No L2 que max nhi Si Inserción doble de los nodos m y l Inserción simple del nodo m de L3 que max nh'I entre el depósito y el nodo i LRk=[0, m, l, i] LRk=[0, m, i] CRk=[i] CRk=[i] ck= dm + dl + di ck= dm + di No trk= t0m + tsm + tml + tsl + tli+tsi+teki trk=t0m + tsm+tmi+tsi+teki Dk= t0m + tml+ tli Dk= t0m + tmi Ek=teki Ek=teki teki=[tai-(t0m+tsm+tml+tsl+tli)]+ teki=[tai-[t0m+tsm+tmi)]+ Elimino los nodos i, m, y l de las listas ¿Está vacía L1? Si B Figura 2. Primera fase del Algoritmo ALADIN 4  B A Finalizo las rutas. Si Regresan los vehículos a 0 LR'k=[LRk, 0] ¿Hay nodos en L0? No CR'k= c'k= ck tr'k=trk +tCRk o Si D'k= Dk + tCRk o E'k=Ek Regeneración de la lista L1 con R nodos i críticos con min tci Calculo para las rutas k y todos los nodos i de L1 hi=tci-[trk+tCRk i] Selecciono nodo i con min tci y ruta k para la que min tCRk i ¿Es hi