Repositorio Institucional de Documentos

TRABAJO FIN DE MÁSTER 2009 - 2010 MODELIZACIÓN DE PROBLEMAS DE CÁLCULO DE RUTAS DE LARGA DISTANCIA CON LLENADO ÓPTIMO DE VEHÍCULOS (VRP + BPP) PROGRAMA OFICIAL DE POSGRADO EN INGENIERÍA MECÁNICA Y DE MATERIALES MÁSTER EN SISTEMAS MECÁNICOS Universidad de Zaragoza Centro Politécnico Superior EUITIZ Codirector Director Autor Dr. D. David Escuín Finol Catedrático D. Emilio Larrodé Pellicer Dª. Beatriz Royo Agustín Septiembre 2010 Área de Ingeniería e Infraestructura de los Transportes Departamento de Ingeniería Mecánica MODELIZACIÓN DE PROBLEMAS DE CÁLCULO DE RUTAS DE LARGA DISTANCIA CON LLENADO ÓPTIMO DE VEHÍCULOS (VRP + BPP) Resumen El transporte de mercancías supone un reto en la actualidad, ya que cada vez prima más la inmediatez. Además, aunque este paso de la cadena de suministro no supone un valor añadido al producto, sí que incrementa su precio. Por otro lado, una de las grandes preocupaciones es el consumo energético y la contaminación. Estos motivos, además de los económicos, son los que han llevado a muchos investigadores a dirigir sus esfuerzos hacia la optimización del transporte. A este tipo de cuestiones se las conoce como VRP o “vehicle routing problem” Se ha comprobado, durante el estudio del estado del arte, que los problemas VRP se centran en un escenario que difiere del presentado en este trabajo. En este caso, en el contexto analizado, un pedido se caracteriza por tener dos localizaciones, el origen donde se recoge la mercancía y el destino donde se deposita. La distancia entre estos puntos es grande necesitando controlar el tiempo de conducción, de disco, de desplazamiento y el de espera para llegar dentro de las ventanas temporales impuestas. Además, existen distintos tipos de mercancía y la capacidad es limitada. Es decir, se persigue modelar este escenario presentando la función objetivo a minimizar y las restricciones que lo caracterizan. Gracias a esto, se puede plantear la metodología de resolución que mejor se ajusta. En este caso, se ha basado en la adaptación de dos investigaciones analizadas: para la agrupación de pedidos y generación de las rutas se ha acomodado un algoritmo sustentado en colonias de hormigas; y para aprovechar al máximo la disposición de los artículos, se han utilizado técnicas heurísticas de forma que también se determina si un pedido puede ser servido en esa ruta. Índice Documento Principal ..................................................................................................................... 2 1) Introducción .............................................................................................................................. 2 1.1) Objetivo del TFM ................................................................................................................ 2 1.2) Marco del TFM ................................................................................................................... 3 1.3) Estructura del documento ................................................................................................. 4 2) Descripción del problema ......................................................................................................... 6 2.1) Introducción ....................................................................................................................... 6 2.2) Características del problema ............................................................................................. 8 2.2.1) Características generales del transporte nacional de mercancías ............................................ 8 2.2.2) Características singulares del problema de transporte de este TFM ........................................ 9 2.3) Requisitos del problema .................................................................................................. 10 3) Solución del problema: Metodología ...................................................................................... 12 3.1) Introducción ..................................................................................................................... 12 3.2) Datos ................................................................................................................................ 12 3.3) Estructura del algoritmo global ........................................................................................ 13 3.4) Metaheurística para la planificación de rutas .................................................................. 14 3.4.1) Estructura general del algoritmo ............................................................................................. 14 3.4.2) Construcción de la solución ..................................................................................................... 17 3.5) Heurística para el llenado de vehículos ........................................................................... 18 3.5.1) Estructura general del algoritmo ............................................................................................. 18 3.5.2) Heurísticas de inserción de ítems ............................................................................................ 20 4) Función objetivo y restricciones ............................................................................................. 24 4.1) Introducción ..................................................................................................................... 24 4.2) Definiciones previas ......................................................................................................... 24 4.2.1) Parámetros .............................................................................................................................. 27 4.2.2) Variables .................................................................................................................................. 27 4.3) Función objetivo............................................................................................................... 28 4.4) Restricciones .................................................................................................................... 29 5) Conclusiones ........................................................................................................................... 32 Referencias Bibliográficas: .......................................................................................................... 34 Documento Principal Trabajo Fin de Máster -2009/2010 Documento Principal 2 1) Introducción El presente documento tiene como finalidad presentar un Trabajo Fin de Máster, en adelante TFM, realizado en el ámbito de la Ingeniería Mecánica, concretamente “organización, gestión y planificación”, y apoyado por conocimientos de la Ingeniería Informática. Para ello se ha elaborado una memoria dividida en dos partes bien diferenciadas. En la primera de ellas, se encuentra el documento principal, que consiste en una explicación de lo que se ha hecho durante todo el tiempo de desarrollo, dividida en cuatro apartados. La segunda parte, ya más extensa, recoge toda la información intrínseca del trabajo, plasmada en un conjunto de 9 anexos. La elaboración de una memoria es fundamental ya que en ella se muestra el TFM, es decir, la información textual de lo que se ha realizado, que permita conocer el trabajo al interesado o no en la materia. 1.1) Objetivo del TFM El objetivo del TFM es el estudio y análisis de un escenario de transporte peculiar para determinar la expresión matemática que representa la función de costes a minimizar y describir la metodología a seguir para optimizar el llenado de vehículos y reducir los kilómetros Trabajo Fin de Máster -2009/2010 Documento Principal 9 La relación entre orígenes y destinos determinará la posibilidad de agrupamiento. El volumen de carga a transportar entre un origen ri y un destino ei correspondientes a un pedido Pi suelen ser elevados, aunque en muchas ocasiones se consideran cargas completas cuando no lo son, permitiendo en estos casos juntar a varios clientes en un vehículo. El volumen de las cargas, la variable tiempo y el coste de manipulación hacen que el orden de llenado de camión se realice siguiendo una estructura LIFO o “Last in first out”. Es decir, el último cliente al que se le ha recogido la mercancía será el primero en ser entregado y por ello la posición en el vehículo será la más cercana a la puerta. 2.2.2) Características singulares del problema de transporte de este TFM En este apartado se listan las características que se han definido para este problema en particular. - Existencia de ventanas temporales en el origen y en el destino de un cliente. Lo que es igual a que tanto ri como ei, correspondientes a un pedido Pi, poseen un intervalo temporal en el que se exige la realización de la operación correspondiente. La amplitud de este intervalo temporal depende del tipo de cliente. - Presencia de tres tipos de carga que permiten clasificar la mercancía en uno de estos tres conjuntos: frio, isotermo o normal. La clase de carga frío exige vehículos con cámara. La clase isotermo se considera alimentación y no necesita frío. La carga isotermo se puede mezclar con la carga frío si y sólo si viajan en un vehículo con temperatura controlada. Sin embargo, ninguna de estas dos se permite que viajen mezcladas con la mercancía calificada como normal. - Los tipos de clientes que se tienen se clasifican en dos grupos. Se considera que existen almacenes propios donde se realizan labores de picking. Estos almacenes se encuentran distribuidos por la geografía española tal y como se muestra en la figura 2.1 y se les denomina clientes internos. Por otro lado se tienen a las fábricas, almacenes y plataformas independientes que solicitan el movimiento de mercancías entre ellos, a este grupo de clientes se les va a llamar clientes externos. La diferencia será la amplitud de las ventanas temporales: para los internos se consideran ventanas más amplias, ya que se puede flexibilizar la hora de preparación del pedido en función de la hora en que se determina la entrega y recogida; en cambio, para los clientes externos las ventanas serán muy restrictivas. Trabajo Fin de Máster -2009/2010 Documento Principal 10 Figura 2.1. Localización de los almacenes de los clientes internos. En el anexo VI se incluye un caso práctico que explica el problema con más detalle, con el objeto de que el interesado comprenda la complejidad de alcanzar la finalidad perseguida. 2.3) Requisitos del problema Una vez explicado el escenario de trabajo, en este apartado se listan los requerimientos que debe satisfacer la solución. - Existe un conjunto de clientes {N}. - Un cliente está formado por el par origen – destino o recogida – entrega representado por Pi (ri, ei), tal y como se explico en el apartado 2.2. - Los clientes pueden ser tanto internos como externos. - La prioridad de ambos tipos de clientes es equitativa. - Se deben satisfacer las ventanas temporales para cada operación de un cliente Para la recogida y para la entrega, es decir, VT (recogida/entrega) = [hmin, hmax]. - Si se llega antes de hmin se aplicará un tiempo de espera. Si se llega tras hmax el pedido no será servido. - Se debe considerar el tiempo de conducción, el tiempo de disco y el tiempo descanso. - Se tienen que tener en cuenta las clases de carga ya que esto determina compatibilidad a la hora de mezclarse en un vehículo y restringe el tipo de camión a usar. - La capacidad del vehículo es limitada, se denomina C y es la misma para todos los vehículos. - Las dimensiones de un vehículo son limitadas, se considera LxW a la superficie del suelo, es decir, L corresponde al largo y W al ancho. - No se permite apilabilidad, es decir, que los paquetes monten unos encima de otros. - No se puede superar la capacidad C del vehículo. - No se puede sobrepasar la superficie disponible del suelo del vehículo. - El orden de agrupamiento de los clientes será LIFO. Trabajo Fin de Máster -2009/2010 Documento Principal 11 Trabajo Fin de Máster -2009/2010 Documento Principal 12 3) Solución del problema: Metodología 3.1) Introducción En este apartado del documento se describe la metodología propuesta para la resolución del problema planteado en el apartado 2 de este documento. Para ello, y en primer lugar, se describen los datos que son necesarios para modelar el problema. En segundo lugar, se presenta el esquema global del algoritmo que generara la solución general. Por último, se describen los dos algoritmos metaheurísiticos necesarios para realizar la planificación de las rutas y encontrar la ubicación optima de los paquetes de cada cliente en el vehículo. 3.2) Datos Los datos necesarios para la resolución del problema se listan a continuación. Una descripción más precisa sobre la estructura, tipos, etc. se encuentra en el anexo IX. Punto: Con este dato se caracteriza la estructura de datos utilizada para representar las localizaciones correspondientes al origen y al destino de un pedido. O lo que es lo mismo, posición geográfica e intervalo temporal de operación (entrega o recogida). Trabajo Fin de Máster -2009/2010 Documento Principal 13 Ítem: Contendrá las dimensiones de un paquete correspondiente a un pedido. Pedido: Esta estructura define los atributos que determinan a un pedido. Es decir, el punto de origen de donde se recoge y el punto destino al que es transportado el pedido, los kilos a transportar, el conjunto de ítems,… Matriz Distancias: Cada celda de la matriz será la distancia real (carretera) que separa el punto de la columna i con el punto de la columna j, siendo j distinta de i. Tipología: Tipos de carga a transportar: Frio, Isotermo, Normal. Ruta: Secuencia de pedidos. Solución: Secuencia de rutas. Vehículo: Características que definen al medio de transporte: capacidad, dimensiones, tipo de carga que transporta. 3.3) Estructura del algoritmo global El algoritmo general planteado se divide en tres etapas, tal y como se muestra en la figura 3.1. A continuación, se describe a grandes rasgos el significado de cada una representada con una caja. Una explicación más detallada de este esquema se encuentra en el anexo VII. Figura 3.1. Estructura algoritmo general. Trabajo Fin de Máster -2009/2010 Documento Principal 14 Sacar Completos: Tiene como objeto sacar de la agrupación o del cálculo aquellos pedidos que se consideran carga completa. Como salida se obtienen las rutas directas Ψ0 y las cargas sobrantes que van al paso siguiente para ser agrupadas. Clasificación en tipos y compatibilidades: En este caso, encontramos únicamente los pedidos que no alcanzan para viajar solos en un vehículo, es decir, pueden viajar agrupados. Para satisfacer la restricción de compatibilidad y reducir el número de pedidos que entraran en la combinación se divide el conjunto en dos grupos (Frio + Isotermo y Normal). Realizar Agrupación: El objetivo es realizar la agrupación de clientes de cada subconjunto del paso anterior (Frio + Isotermo y Normal). En este apartado se aplican las técnicas metaheuristicas de planificación de rutas y llenado del camión, que se explican en los siguientes apartados. Como resultado de este paso se obtienen los itinerarios con los pedidos agrupados Ψ1 = Ψ1FIU Ψ1N. Como resultado del algoritmo se obtendrán las rutas a realizar por los vehículos. La solución será por lo tanto, S = Ψ0 U Ψ1. 3.4) Metaheurística para la planificación de rutas En este apartado se plantea el algoritmo adaptado a partir de una investigación realizada por L. Barcos, V. Rodríguez, M.J. Álvarez y F. Robusté denominado “Routing design for less-than-truckload motor carriers using Ant Colony Optimization”. El objetivo es realizar la agrupación de los pedidos en vehículos con el objeto de disminuir el número de recursos a utilizar y el kilometraje total recorrido. 3.4.1) Estructura general del algoritmo Este algoritmo está basado en una metaheurística denominada “Algoritmo de colonia de hormigas”, descrito en el anexo V, y se ejecutará dos veces en paralelo, con la intención de reducir el tiempo consumido. La entrada para cada uno de los procesos será uno de los subconjuntos clasificados en el proceso “Clasificación en tipos y compatibilidades” representado en la figura 3.1. La estructura general del algoritmo se muestra en la figura 3.2. A continuación, se realiza una breve descripción de cada etapa. Para encontrar, un análisis más detallado de este algoritmo hay que recurrir al anexo VII. Trabajo Fin de Máster -2009/2010 Documento Principal 15 Figura 3.2. Estructura general del algoritmo de planificación de rutas. El primer paso tiene como objetivo reducir el número de posibles combinaciones del subconjunto seleccionado. Para ello, se definen cuatro grupos de candidatos {G1}, {G2}, {G3} o {G4}. En este TFM se ha considerado que un pedido está constituido por el par origen – destino, y se establecen una serie de relaciones con el resto de pedidos. A continuación, se describen las correspondencias que se pueden generar entre pedidos, apoyadas por un dibujo para facilitar la compresión. La formulación y descripción más detallada de estas relaciones se explica en el anexo VII. Mismo origen y mismo destino {G1} Se define {Gi1}, como el conjunto de pedidos que tienen el mismo origen y el mismo destino que el pedido Pi(ri, ei). En la figura 3.3 se muestra el significado de {Gij1}, es decir la relación {G1} entre el pedido i y el pedido j. Figura 3.3. Relación {G1} entre el pedido i y el pedido j. ei, ej ri, rj Trabajo Fin de Máster -2009/2010 Documento Principal 16 Mismo origen y distinto destino {G2} Se define {Gi2}, como el conjunto de pedidos que tienen el mismo origen y diferente destino que el pedido Pi(ri, ei). En la figura 3.4 se muestra el significado de {Gij2}, es decir la relación {G2} entre el pedido i y el pedido j. Figura 3.4. Relación {G2} entre el pedido i y el pedido j. Distinto origen y mismo destino {G3} Se define {Gi3}, como el conjunto de pedidos que tienen distinto origen y mismo destino que el pedido Pi(ri, ei). En la figura 3.5 se muestra el significado de {Gij3}, es decir la relación {G3} entre el pedido i y el pedido j. Figura 3.5. Relación {G3} entre el pedido i y el pedido j. Distinto origen y distinto destino {G4} Se define {Gi4}, como el conjunto de pedidos que tienen distinto origen y distinto destino que el pedido Pi(ri, ei). En la figura 3.6 se muestra el significado de {Gij4}, es decir la relación {G4} entre el pedido i y el pedido j. Figura 3.6. Relación {G4} entre el pedido i y el pedido j. En el caso {G2}, {G3} y {G4}, los conjuntos serán ordenados en orden creciente de distancias. En el primer caso será la que existe entre los destinos, en el segundo entre los orígenes y en el tercero la suma de la distancia presente entre los orígenes y los destinos. Una vez finalizado el paso anterior, se ordenan los pedidos a agrupar en una lista de mayor a menor distancia entre el origen y el destino del pedido. A continuación, comienzan dos bucles. El primero de ellos es el que determina el refinamiento de la solución, es decir, cuantas veces se va a pulir la mejor solución encontrada hasta el momento. En el interior de este bucle se encuentra otro proceso iterativo en el que se ei, ej rj rj rj, rj ej ei ej ei rj rj Trabajo Fin de Máster -2009/2010 Documento Principal 17 genera la colonia de hormigas, es decir, se genera un número de soluciones igual al número de iteraciones del bucle. La colonia de hormigas es resultado de la ejecución de un algoritmo denominado “construcción solución” -explicado en el apartado 3.4.2.- Correlativamente, se realiza el refinamiento de la mejor solución encontrada hasta el momento. Para ello, primero, se selecciona la mejor solución de la colonia de hormigas, después, se realiza una mejora local sobre la misma, explicada también en el anexo VII, y por último se compara si ésta es mejor que la mas buena encontrada en las iteraciones anteriores. En caso afirmativo, ésta pasa a ser la solución, en caso contrario, se deja la que estaba. Por último se actualiza el valor de la feromona. Para determinar si una solución es viable y evaluar si una propuesta es mejor que otra, se necesita definir una función objetivo y las restricciones que la delimitan. Esta función y limitaciones son explicadas en el apartado 4 de este documento. 3.4.2) Construcción de la solución Este es el algoritmo encargado de generar la solución, es decir, la agrupación de pedidos en rutas. El esquema de funcionamiento se presenta en la figura 3.7 y después se explica en líneas generales el significado de este esquema. Una descripción más detallada del mismo se encuentra en anexo VII. Figura 3.9. Construcción solución. Trabajo Fin de Máster -2009/2010 Documento Principal 18 De la lista ordenada de pedidos se selecciona el primero de ellos. A continuación, se comprueba si existe algún candidato disponible para agrupar con este. En caso negativo, se comprueba si existen más pedidos en la lista ordenada y se coge el siguiente, si no existen más pedidos es porque se ha obtenido la solución. En caso de existir algún candidato en {G1}, {G2}, {G3} o {G4}, se selecciona el primero de cada lista. Si resulta más de uno, la hormiga lo selecciona de forma probabilística, tal y como se explica en el anexo VII. A continuación, se comprueba si la solución es viable, para ello se utiliza la función objetivo y restricciones descritas en el apartado 4 de este documento. Para comprobar la viabilidad, una de las restricciones a satisfacer es si los ítems del pedido caben en el hueco del camión, para ello se utiliza el algoritmo explicado en el siguiente apartado 3.5. En caso de resultar viable, este pedido es eliminado de todas las listas de candidatos en las que aparece y de la lista de ordenados. Si la ruta permite insertar otro pedido (no está saturada en capacidad o tiempo) o en caso de que el candidato no sea viable se sigue examinando la lista de candidatos hasta que se satura o no quedan candidatos para el pedido inicial. Entonces esta ruta pasa a la solución del problema, se elimina el pedido inicial de todas las listas en las que aparece y se pasa a examinar el siguiente pedido de la lista de ordenados en caso de existir. Si no hay mas pedidos en esta lista la solución con el conjunto de rutas a realizar es devuelta. 3.5) Heurística para el llenado de vehículos Gracias a esta heurística se permite realizar un llenado del camión que resulte óptimo, ya que se utilizan procedimientos que determinan cuál es la mejor ubicación, de forma que si no encuentra ninguna disposición para insertar los ítems, una de las restricciones a satisfacer por la función objetivo resulta violada. 3.5.1) Estructura general del algoritmo Para encontrar la solución se ha adaptado la propuesta realizada por Emmanouil E. Zachariadis, Christos D. Tarantilis y Christos T. Kiranoudis en 2007 denominada “A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints. El proceso seguido por el algoritmo se presenta en la figura 3.10, es explicado a continuación. Como entrada al algoritmo se tiene el conjunto de ítems del pedido Pi, caracterizados con sus dimensiones, la superficie disponible del vehículo y la disposición del conjunto de ítems de los (i-1) pedidos anteriores. Con esta información se tiene que encontrar la ubicación Trabajo Fin de Máster -2009/2010 Documento Principal 25 Pedidos: una instancia del problema planteado contiene f pedidos. El juego de f pedidos está compuesto a su vez por f recogidas C = {r1,…, rf} y f entregas E = {e1,…, ef}.El problema se define con un grafo G = (P, A) donde P = {P1,…Pf} representa el conjunto de pedidos. Cada pi є P se representa por una par de nodos o puntos. El primer nodo simboliza la recogida de la mercancía y el segundo la entrega, es decir, pi = (ri, ei)  i є ,1,…, f-. Por tanto se tienen 2F nodos o puntos donde 2F = N. El problema se puede representar a su vez como G = (N, A), con N número de nodos o puntos y A  N x N representa las posibilidades de viaje entre los nodos. A cada arco (i, j) є A, le corresponde un coste en función de la distancia entre el nodo i y el nodo j. Cada orden tiene una demanda no negativa qi expresada en kilogramos y esta misma demanda lixwi expresada en m2  i є ,1,…, f-. Vehículos: Se tendrá un conjunto de vehículos para realizar las rutas V = {v1,…, vm}. Los vehículos de los que se dispone tienen la misma capacidad, misma superficie y misma velocidad, siendo Q la capacidad, LxW la superficie y V la velocidad. Se tendrán dos tipos de vehículos {Frio, Normal} y se dispondrá de un número ilimitado de cada tipo en cada origen de una ruta. El vehículo partirá del origen del primer pedido de la ruta y finalizará en el destino del primer pedido. Por tanto se tendrá que m ≤ f, siendo m el número de vehículos necesarios para realizar las expediciones y f el número de pedidos. Además, sea mf el número de vehículos de tipo frio necesarios y mn los vehículos de tipo normal, entonces mf + mn = m. Matriz de distancias: El problema se ha definido como G = (N, A), donde N = C U E y n = 2f el número de nodos y A = NxN la matriz de distancias asimétrica. Cada componente de la matriz A es la distancia real por carretera entre el nodo i y el nodo j. Es decir, sea di,j la distancia entre el punto i y el punto j, entonces: N j i, j), A(i,d ji,  (1) N j i, dd , ij, ji,  (2) Tiempo de Viaje: Se define ti, j como el tiempo necesario para recorrer di, j o distancia entre dos puntos i, j a una velocidad V. N j i, dt V / ji, ji,  (3) Ruta: Una ruta comienza en el origen del primer pedido y finaliza en el destino del primer pedido de la misma. Está formada por un conjunto de pedidos F’, con un total de f’, que son servido una sola vez, es decir, la recogida se realiza una vez y la entrega una sola vez siguiendo Trabajo Fin de Máster -2009/2010 Documento Principal 26 la estructura Lifo (primero en recoger, ultimo en entregas). Es decir, para cada vehículo h = (1,..., m) una ruta es una secuencia de puntos, donde cada par de puntos corresponde a un pedido y son servidos según la estructura Lifo, por consiguiente: M] [1, h R, g e g r h 1 f'g f' 1g    (4) Ventanas Temporales: Cada par de puntos correspondientes a un pedido tienen ventanas temporales. La ventana temporal de un nodo i viene dada por el intervalo [ai, bi] donde ai y bi representan la cota inferior y la superior para realizar la operación (entrega, recogida) respectivamente. Si un vehículo llega al nodo antes de ai se le permite esperar hasta ai y comenzar el servicio a continuación, incurriendo en una penalización que se representa por el coste en función del tiempo de espera. Para asegurar que se cumple la ventana temporal se define di para denotar cuando el vehículo sale del nodo i y si cuando comienza el servicio en el nodo i. A la hora de calcular di y si, se tienen que considerar los tiempo de ir de un nodo i a un nodo j, el tiempo de servicio en el nodo i (TS), tiempo de descanso (TC) en caso de superar el tiempo límite de conducción (LC) y el tiempo de descanso (TD) si se supera el límite de disco. Compatibilidades: Se tienen 3 tipos de mercancía, {F, I, N}, frio, isotermo y normal respectivamente, de forma que un pedido pertenecerá a uno y solo uno de los 3 y se tienen 2 tipos de vehículos {F,N}, frio y normal donde un vehículo pertenecerá a uno y solo uno de los dos. Sea clase(Pi) tipo de mercancía al que pertenece el pedido i y clase(vk) tipo de vehículo al que pertenece el responsable de realizar la ruta k, se define: ],1[,, caso. otro cualquier en 1, {F})clase(v y {F} )clase(P y {I} ) clase(P si 0, {N})clase(v y {F} ) clase(P si 0, }{ )clase(P y {N} ) clase(P si 0, kji ki ji MkNji N Pk ij                    (5) Gracias a (5) se garantiza que una mercancía clasificada como normal no puede viajar mezclada con otra. Por ejemplo, si pertenece a la clase frío debe transportarse obligatoriamente en vehículo con cámara. Sin embargo, se permite mezclar un pedido frío con uno isotermo si el vehículo es de la clase frio y un isotermo puede ser llevado en un vehículo normal, si viajan solo pedidos de ese tipo. Trabajo Fin de Máster -2009/2010 Documento Principal 27 4.2.1) Parámetros T: coste por unidad de distancia recorrida (€/ km). O: coste de una operación ,recogida, entrega- (€) B: coste por unidad de tiempo (€/ min). Q: capacidad del vehículo en kg. LxW: superficie del vehiculo. M: vehículos para realizar las rutas. TS: tiempo necesario para realizar una operación {recogida, entrega}. F: número de pedidos u órdenes. N: número de nodos, será igual a 2F. LD: limite del tiempo de disco. LC: limite del tiempo de conducción. DD: tiempo de descanso por superar LD. DC: tiempo de descanso por superar LC. V: velocidad (km/ h). 4.2.2) Variables Rk: ruta k correspondiente al vehículo k  k є *1, M+. dij: distancia entre el nodo i y el nodo j  i, j є N. tij: tiempo entre el nodo i y el nodo j, será dij / V,  i, j є N. xijk: el vehículo k va del nodo i al nodo j. pi: peso del pedido i  i є F. dik: instante en que el vehículo k abandona el nodo i,  i є N y  k є *1, M+ Trabajo Fin de Máster -2009/2010 Documento Principal 28 sik: instante de servicio o llegada del nodo i por el vehículo k.  i є N y  k є *1, M+ sd0k: instante de inicio de disco del vehículo k  k є *1, M+. Inicialmente será la del origen del primer pedido y se actualizará con la hora de servicio del último nodo antes de hacer el descanso DD cuando se ha excedido LD. sc0k: instante de inicio o de conducción del vehículo k  k є *1, M+. Inicialmente será la del origen del primer pedido y se actualizará con la hora de servicio del último nodo antes de hacer el descanso DC cuando se ha excedido LC. α = ítems (Pi), contiene el conjunto de ítems del pedido Pi con sus dimensiones y capacidad. lihxwih: superficie del ítem h perteneciente al nodo i  i є N y  h є α. 4.3) Función objetivo Minimizar la función de costes. ) )(min( 0 0 1 )1(* 0 0 1 BxsaONxdT N i N j M k k ijjkj N i N j M k k ijij        Donde:     N i N j M k k ijij xdT 0 0 1 .. , coste desplazamiento del nodo i a j por el vehiculo k. ON , coste del total de las operaciones. ) )( 0 0 1 )1(* Bxsa N i N j M k k ijjkj      penalización por llegar antes de inicio de ventana temporal. Sujeta a: M k ,Nj i, 1,x M 1k N 1j k ij     (6) En (6) se asegura que un solo vehículo sirve el pedido. Trabajo Fin de Máster -2009/2010 Documento Principal 29 4.4) Restricciones Restricción de capacidad:     N i N j k ijiQxp 0 0 M][1,k , (7) )items(Xα,][1,k ,))(( i 0 0 0       N i N j k ij h ihih MWLxwl  (8) En (7) se atestigua que el peso de los pedidos insertados en el vehículo k no supera la masa máxima autorizada Q; en (8) se verifica que la suma de la superficie de los ítems de todos los pedidos de un vehículo k, no sobrepasa la superficie disponible del vehículo LxW. Restricciones temporales: N i ,b i i s (9) M k N, i , 0 )TC) max(TD, TS 1 (s -d k i i  i w (10) N i ,s i i a (11) N i ,  ii as (12) En (9) se asegura que el momento de llegada al nodo i es anterior al fin de su ventana temporal; en (10) que la salida del punto i se produce después de: haber llegado, realizado el servicio, la espera en caso de producirse y el descanso oportuno en caso de haber superado uno de los límites temporales, de conducción o de disco; en (11) que se debe llegar después del inicio de la ventana temporal, sin embargo, se permite llegar antes (12), aunque implicando una penalización que se representa en la función de costes a minimizar. A su vez las variables de las expresiones (9), (10), (11) y (12) deben satisfacer las siguientes restricciones, donde w1i es el tiempo de espera al inicio de la ventana temporal del punto i; por otro lado, se define sc0K y sd0k como instante de reset de contador del tiempo de conducción y tiempo de disco. M k N, j i, , 1 x si s k ij,j  jii td (13) N i , )}s -( max{0, 1  iii aw (14) Trabajo Fin de Máster -2009/2010 Documento Principal 30 M k N, i , LD) s - (s y LC) s - (s si TD),max(TC, LD) s - (s y LC) s - (s si TC, LD) s - (s y LC) s - (s si TD, LD)s - (s y LC) s - (s si ,0 TC) max(TD, k d0i k c0i k d0i k c0i k d0i k c0i d0i k c0i                     k k (15) M k N, i , LC) s - (s si ,s LC) s - (s si , 1i si , s k c0i k c0 k c0i 1 k c0               i d d (16) M k N, i , LD) s - (s si ,s LD)s - (s si , 1i si , s k c0i k d0 k c0i 1 k d0               i d d (17) Con (13) se define la hora de llegada a un punto sj, en (14) el tiempo de espera w1i y con (15) el tiempo de descanso a realizar en ese punto por el vehículo k, es decir, max(TD,TC)k, que aparecen en (11). Gracias a (16) y (17) se determina el valor de la hora de inicio de puesta a cero del contador de tiempo de conducción sc0k y la hora de inicio de puesta a cero del contador que controla el tiempo de disco sd0k del vehículo k respectivamente. ],1[,, caso. otro cualquier en 0, k. vehículo el por recorrido es j)(i, arco el si 1, MkNjix k ij         (18) Gracias a (18), se determina si un vehículo k sirve al punto j tras el punto i. Trabajo Fin de Máster -2009/2010 Documento Principal 31 Trabajo Fin de Máster -2009/2010 Documento Principal 32 5) Conclusiones La planificación y gestión del transporte de mercancías es un tema que despierta un gran interés, debido en gran medida a que es una paso común en la cadena de suministro para todo tipo de bienes, ya sean de primera necesidad, de lujo, etc. que incrementa el coste de los mismos pero no aumenta su valor de utilidad. Esto, junto al hecho de que en la actualidad se premia la inmediatez, de forma que el intervalo temporal entre la realización de un pedido y la disposición del mismo es cada vez menor. Por otro lado, una de las grandes preocupaciones de hoy en día es el consumo energético y la contaminación. Estos motivos, además de los económicos, son los que han llevado a muchos investigadores a promover estudios con el objetivo de reducir el número de vehículos empleados, los kilómetros recorridos, introducir el mayor número de paquetes…. Es decir, a dirigir sus esfuerzos hacia la optimización del transporte, consiguiendo reducir los costes, el consumo de combustible y la contaminación. Gracias a este TFM he iniciado el camino para la realización de lo que será mi futura tesis doctoral, ya que me ha sido de gran utilidad para comprender el complejo campo de la planificación y optimización de rutas en el transporte de mercancías. Además, he adquirido los conocimientos para entender e interpretar el estado del arte y poder aplicarlos a un escenario concreto. En esta labor, lo más complejo es diseñar la función objetivo y las restricciones a las Trabajo Fin de Máster -2009/2010 Documento Principal 33 que esta se ajusta con la terminología utilizada en este tipo de problemas; otra de las dificultades es encontrar la técnica metaheurística que mejor se adapta a los requisitos del problema debido a la cantidad de métodos y soluciones propuestas. Con el trabajo realizado se podrá generar una herramienta basada en el método propuesto, que satisfaga la función objetivo y restricciones y sea aplicada a un caso real para determinar la calidad del estudio. Este paso, no se ha incluido en el trabajo ya que no entraba dentro de los objetivos planteados y debido a que se trataría de un trabajo de programación más acorde a un proyecto de ingeniería informática. 34 Referencias Bibliográficas: [1] Estudio y descripción del problema: Francisco Aparicio Izquierdo: INGENIERÍA DEL TRANSPORTE, Editoriales Dossat, 2008 Juan de Dios Ortúzar: MODELOS DE TRANSPORTE, Universidad de Cantabria, 2008 [2] Estado del arte: Emmanouil E. Zachariadis, Christos D. Tarantilis, Christos T. Kiranoudis: A GUIDED TABÚ SEARCH FOR THE VEHICLE ROUTING PROBLEM WITH TWO DIMENSIONAL LOADING CONSTRAINTS, European Journal of Operational research, 2007 L. Barcos, V. Rodríguez, M. J. Álvarez, F. Robusté: ROUTING DESIGN FOR LESS THAN TRUCKLOAD MOTOR CARRIERS USING ANT COLONY OPTIMIZATION, Tansportation Research Part E available at SceinceDirect, 2009 David Escuin Finol: DESARROLLO DE UN ALGORITMO BASADO EN TECNICAS HEURISTICAS PARA LA RESOLUCION DE PROBLEMAS DE GESTION DE TRANSPORTE, Universidad de Zaragoza, 2010 Francisco Baptista Pereira, Jorge Tavares: BIO INSPIRED ALGORITHMS FOR THE VEHICLE ROUTING PROBLEM, Springer, 2009 Mitsuo Gen, Runwei Cheng: GENETIC ALGORITHMS AND ENGINEERING OPTIMIZATION, John Wiley and sons, 2000 [3] Anexo NP-Completo: http://www.uv.es/jkliment/Documentos/TeoComp.pc.pdf http://www.ucm.es/info/pslogica/automatas.pdf [4] Anexo VRP: http://redalyc.uaemex.mx/redalyc/pdf/1492/149212815002.pdf http://www.liacs.nl/assets/Masterscripties/2010-01FrankTakes.pdf http://neo.lcc.uma.es/radi-aeb/WebVRP/