Source: http://docplayer.es/7389996-5-ajuste-de-parametros-de-la-busqueda-tabu.html
Timestamp: 2018-12-13 02:56:04+00:00

Document:
5. AJUSTE DE PARÁMETROS DE LA BÚSQUEDA TABÚ - PDF
Download "5. AJUSTE DE PARÁMETROS DE LA BÚSQUEDA TABÚ"
Juan Luis Camacho Godoy
1 5.Ajuste de parámetros de la búsqueda tabú 5. AJUSTE DE PARÁMETROS DE LA BÚSQUEDA TABÚ El algoritmo de Búsqueda Tabú (TS) utiliza un gran número de parámetros asociados a distintas etapas de la resolución. Algunos de ellos han sido estudiados en la literatura científica en problemas de optimización combinatoria y otros son específicos del modelo aplicado en esta tesis. De este modo, es necesario identificar qué valores o dominios de los parámetros conducen a las mejores soluciones y en especial, analizar el comportamiento general del algoritmo de optimización. Uno de los principales problemas para la calibración y ajuste de los parámetros del problema es disponer un marco de comparación de los resultados y performance de la herramienta de cálculo con otras técnicas disponibles. Si bien el algoritmo TS es un método generalizado y testeado en un amplio conjunto de aplicaciones, se debe garantizar que la solución resultante de su aplicación se encuentra cercana al óptimo o puede resolver problemas de forma más eficiente que las demás metodologías. En este punto, se debe manifestar la inexistencia para la comunidad científica de un conjunto de problemas de referencia que permita comparar la eficiencia de cada algoritmo. Ejemplos de estas referencias son la familia de problemas conocida como Solomon s Benchmark Problems en el campo del Vehicle Routing Problem con ventanas temporales y los problemas de localización óptima de hubs aéreos en EE.UU. detallados en O Kelly y Brian (1998). Ambas familias no son de aplicación en nuestro caso ya que el primer grupo se basa en redes One-to-Many y el segundo grupo plantea la modelización como un problema de flujos sin considerar las rutas de vehículos. Para poder superar esta problemática, se ha generado una batería de 6 problemas de distribución de distinto tamaño y distintos volúmenes de carga para analizar la bondad M. Estrada (2007) 137
2 Análisis de estrategias eficientes en la logística de distribución de paquetería de los resultados y determinar el ajuste y calibración necesaria de los valores de los parámetros del algoritmo. Adicionalmente, en Barcos (2002) se recogen tres ejemplos sencillos de redes de distribución de empresas de paquetería de muchos orígenes a muchos destinos en las que se han evaluado sus soluciones óptimas por programación matemática entera y se ha comparado con las soluciones encontradas con el algoritmo de ACO (Ant Colony Optimization). Estos tres ejemplos se utilizarán para comparar las soluciones del algoritmo TS con otros modelos y técnicas ANÁLISIS DE RESULTADOS EN BATERÍAS DE AJUSTE La globalidad de los problemas creados para el ajuste de parámetros tienen las coordenadas (x i,y i ) de cada delegación i =1,..N T generadas aleatoriamente en un cuadrado de 500 km de lado. Por otro lado, el plazo temporal para realizar la distribución es de 10 horas, de forma que toda delegación i =1,..N T presenta el tiempo de apertura h 1,i =0 y el tiempo máximo de recepción h 2,i =10 horas. Todas las delegaciones de la región de servicio presentan unos tiempos unitarios de carga y descarga homogéneos e iguales a 0,01horas/m 3 y 0,005 horas/m 3 respectivamente. Así mismo, los vehículos utilizados en todos los problemas presentan una capacidad de 80 m 3 efectivos para el transporte de carga y se desplazan a una velocidad igual a 80 km/h. Las características particulares de cada problema de referencia p1-p6 en cuanto a demanda y número de delegaciones se detalla a continuación: p1-16 delegaciones (4 de ellas hub), con 257 envíos con carga w ij [0;100] m 3 p2-16 delegaciones (4 de ellas hub), con 108 envíos con carga w ij [0;10] m 3 p3-45 delegaciones (6 de ellas hub), con 680 envíos con carga w ij [0;100] m 3 p4-45 delegaciones (6 de ellas hub), con 520 envíos con carga w ij [0;10] m 3 p5-88 delegaciones (12 de ellas hub), con 532 envíos con carga w ij [0;100] m 3 p6-88 delegaciones (12 de ellas hub), con 532 envíos con carga w ij [0;10] m 3 Los problemas p1, p3 y p5 hacen referencia a estructuras de transporte con volúmenes de envíos distribuidos aleatoriamente en el dominio [0;100] m 3, por lo que habrá un porcentaje significativo de envíos con carga completa (FTL). En este sentido, en un arco de una ruta existirá una probabilidad baja de poder transportar más de 2 envíos sin superar la capacidad del vehículo. Por el contrario, en los problemas p2, p4 y p6 los volúmenes de mercancía de cada par (i,j) son asignados aleatoriamente en el dominio 138 M. Estrada (2007)
3 5.Ajuste de parámetros de la búsqueda tabú [0;10] m 3, por lo que se trata de un problema LTL (envíos con carga muy inferior a la capacidad). En este caso, en el cubrimiento de un arco de una ruta r se deberá transportar un número alto de envíos para consolidar carga a través de estrategias peddling y hub & spoke para garantizar la productividad del vehículo. Tabla 5.1. Características de los problemas generados para la batería de ajuste de parámetros Problema tipo Criterio Criterios de parada Lista Tabú Tamaño problema Tipo de carga aceptación de la solución Iteraciones máximas Reinicialización por no mejorar la solución factible o infactible Tabu tenure, θ (iteraciones tabú) Reducido (16 delegaciones) Medio (45 delegaciones) Grande (88 delegaciones) Envíos con carga importante w ij [0;100] m 3 Envíos con carga reducida w ij [0;10] m 3 Algoritmo básico Algoritmo con aceptación potenciada N 1 =500 N 1 =1000 N 1 =2000 N 2 =N 3 =10N T N 2 =N 3 =4 N T N 2 =N 3 =2 N T N 2 =N 3 =0,8 N T N 2 =N 3 =0,2 N T Bajo:10 Medio:50 Alto:100 considerando una capacidad de C=80 m 3 ) Con todo, las principales características y atributos que se han incluido en la generación de la batería de calibración y análisis de la herramienta de resolución propuesta se detallan en la Tabla 5.1. Los aspectos y parámetros que se pretenden analizar sobre el comportamiento del algoritmo de Búsqueda Tabú integrado dentro de la herramienta matemática de resolución son los siguientes: Criterio de aceptación de la configuración actual como mejor solución x opt. Se han desarrollado 2 algoritmos con distintos criterios de aceptación de la solución. Si f(x ) y f(x opt ) son respectivamente el coste de la solución x en la iteración k del programa y el coste de la mejor solución encontrada hasta el momento, el criterio de aceptación de la solución del algoritmo básico es que siempre haya estrictamente una reducción de costes tal y como detalla la fórmula (5.1). Por su lado, el algoritmo con aceptación potenciada permite la incorporación de soluciones que igualen el coste actual para promover la reestructuración de la solución y así explorar nuevas configuraciones (perturbaciones de tipo 1 y 2). El criterio de aceptación en este caso se basa en la ecuación (5.2). M. Estrada (2007) 139
4 Análisis de estrategias eficientes en la logística de distribución de paquetería f x') < f ( x ) (5.1) ( opt f x') f ( x ) (5.2) ( opt Tiempo de computación y número de iteraciones máximo N 1 en relación al tamaño del problema. Se ha considerado 3 valores de N 1 =500 N T, 1000 N T y 2000 N T, para los que se han calculado los 6 problemas tipo comprobando su tiempo de cálculo. Parámetros N 2 y N 3 (número de iteraciones máximas en las que no se mejora la solución factible e infactible respectivamente). Se han considerado 5 valores posibles de N 2 y N 3 en función del tamaño de problema N T : 10 N T, 4 N T, 2 N T, 0,8 N T y 0,2 N T (se asume en cada escenario que N 2 =N 3 ) Parámetro tabu tenure θ. Este parámetro representa el número de iteraciones en las que un elemento de la solución se considera tabú. Se han identificado 3 posibles valores del parámetro θ =10, 50 y 100. Con todo, el número total de escenarios de calibración para cada uno de los problemas de referencia resultantes de cruzar los distintos aspectos de estudio configura una batería con 90 problemas. El detalle de los resultados obtenidos se adjunta en el Anexo A3. Cabe decir que por el gran tiempo de cálculo del problema de 88 delegaciones, únicamente se ha procedido a su cálculo para N 1 =2000 N T y para valores potencialmente óptimos de N 2 y N Criterio de aceptación Los resultados demuestran que el algoritmo con la aceptación potenciada con un criterio de aceptación determinado por la ecuación (5.2) siempre presenta una búsqueda diferencial de la mejor solución en relación al algoritmo básico; si bien también encuentra las peores soluciones cuando los parámetros de ajuste del algoritmo no se aplican correctamente. En el caso del problema de tamaño reducido (16 delegaciones), la mejor solución encontrada con el algoritmo con aceptación potenciada presenta una reducción del 9,2% sobre la solución inicial encontrada con el procedimiento heurístico en el problema p1 (envíos FTL a carga completa). Sin embargo, en el caso del problema p2 (envíos LTL con carga muy inferior a la capacidad), la reducción de la mejor solución con el 140 M. Estrada (2007)
5 5.Ajuste de parámetros de la búsqueda tabú algoritmo con aceptación potenciada asciende al 30,7 % de la solución inicial del algoritmo de Búsqueda Tabú. A nivel general, la mejora de la solución del algoritmo con aceptación potenciada es del 26,1% para el problema p2 y del 6,3% en el problema p1 con un criterio de parada N 1 =2000N T. El algoritmo con aceptación potenciada siempre encuentra las mejores soluciones comparativamente con el algoritmo básico. Las 5 mejores soluciones obtenidas con el algoritmo con aceptación potenciada presentan una reducción media del 2,1% con las respectivas soluciones del algoritmo básico. En el caso del problema p2 (envíos LTL) la reducción asciende al 4,8 %. Si se analiza el problema de tamaño medio (45 delegaciones), la mejora del resultado de la configuración inicial con el algoritmo con aceptación potenciada marcada con la expresión (5.2) es del 6,4% en el problema p3 y del 19,5% en el problema p4. A nivel general, el ahorro medio en el problema p3 y p4 por este algoritmo es del 3,5% y 12,5% respectivamente con el criterio de parada máximo de N 1 =2000N T. El porcentaje de mejora de las cinco mejores soluciones del algoritmo de aceptación potenciada es del 2,3% en el problema p3 y del 3,7 % en el caso del problema p4 en relación al algoritmo básico. Finalmente, en el problema de grandes dimensiones (88 delegaciones), el algoritmo con aceptación potenciada proporciona un ahorro medio de la solución de partida del algoritmo de Búsqueda Tabú del 7,7% en el problema p5 y del 15,0 % en el problema de carga p6 adoptando N 1 =2000N T. La reducción media del coste de las 5 mejores soluciones con este algoritmo es del 2,1 % en relación al algoritmo básico aplicado al problema de carga completa p5 y del 5,5% con el algoritmo básico. De esta forma, los resultados avalan la generación e inclusión de los movimientos o perturbaciones del tipo M1 ó M2 detallados en el subcapítulo 4.5 (algoritmo TS) para cambiar la estructura de la solución en cada iteración aunque no reduzcan el coste. En el algoritmo básico, estos movimientos únicamente son adoptados a la solución actual si van seguidos de un movimiento que reduzca el coste de la solución antes de que se llegue al criterio de parada N 2 o N 3. En cambio, en el algoritmo con aceptación potenciada los movimientos M1 y M2 son adaptados a la solución actual incluso si no mejoran el coste (no empeoran la solución). Cabe destacar que el algoritmo de aceptación potenciada obtiene resultados relativamente peores en relación al algoritmo básico en problemas con un número de iteraciones máximas bajo (N 1 =500N T ). M. Estrada (2007) 141
6 Análisis de estrategias eficientes en la logística de distribución de paquetería Tiempo de computación Los tiempos de cálculo y la bondad de la solución presentan un comportamiento distinto según el tamaño del problema y las características de los volúmenes de carga a transportar (problema de envíos a carga completa FTL o parcial LTL). No se ha percibido un comportamiento distinto de esta variable entre el algoritmo básico y el algoritmo de aceptación potenciada. En este punto se debe destacar el trade-off existente entre el número máximo de iteraciones o tiempo de cálculo y la bondad de la solución. El objetivo es buscar una solución aceptable en un tiempo computacional acotado. A nivel general, los resultados reflejan obviamente que las mejores soluciones se han encontrado en los casos en que el criterio de parada tenía asociado un número más elevado de iteraciones (N 1 =2000N T ). La herramienta de cálculo se ha programado con lenguaje VisualBasic 6.0. y ha sido ejecutada con un ordenador personal con procesador Intel Core2 Duo de 1024Mb de RAM y 530MHz. El tiempo de computación en el problema de tamaño reducido (16 delegaciones) varía significativamente según el tipo de problema. En el problema p1 (envíos a carga completa) los tiempos de resolución oscilan entre los 25 segundos para N 1 =500N T (8000 iteraciones como máximo), un valor medio de 49 segundos para N 1 =1000N T (máximo de iteraciones) y un valor medio de 96 segundos para N 1 =2000N T (32000 iteraciones). Se puede estimar un rendimiento medio de 322 iteraciones/s. Por su lado, en el problema p2 los tiempos de cálculo se reducen de forma relevante: 15 segundos cuando N 1 =500N T, 29 segundos para N 1 =100N T y finalmente unos 55 segundos para N 1 =2000N T. En este caso, la velocidad de cálculo del algoritmo asciende a un valor medio de 557 iteraciones/s. Este hecho es debido a que el número de envíos totales en el problema p2 representa el 50% del número de envíos gestionados en el problema p1. En el caso de los problemas de tamaño medio (45 delegaciones), el hecho de tener envíos FTL a carga completa o envíos LTL a carga parcial no condiciona de forma significativa el tiempo de cálculo. En el problema p3 el algoritmo presenta una velocidad media de 134 iteraciones/s. En particular, se necesitan 168s para su resolución cuando N 1 =500N T (22500 iteraciones), 336s cuando N 1 =1000N T (45000 iteraciones) y 672s cuando N 1 =2000N T (90000 iteraciones). En el caso de la resolución del problema p4, la velocidad de cálculo es de 169,3 iteraciones/s con una variación estimada por σ=23,4 it/s. A nivel general, el algoritmo alcanza el número total de iteraciones 142 M. Estrada (2007)
7 5.Ajuste de parámetros de la búsqueda tabú máximo después de 132s cuando N 1 =500N T, 266s cuando N 1 =1000N T y 531s cuando N 1 =2000N T. En el problema de gran tamaño (88 delegaciones) únicamente se ha evaluado el coste computacional de resolución para el caso N 1 = 2000N T que conduce a las mejores soluciones. En el caso del problema p5 de carga completa, el ritmo medio de iteraciones por segundo es de 116,5 it/s. La solución se obtiene en estos casos al cabo de 1510 segundos. Por otro lado, en el problema p6 con envíos LTL a carga parcial, la productividad del algoritmo alcanza un valor medio de 130,9 iteraciones/s, y son necesarios 1344 segundos para alcanzar el criterio de parada. En este sentido, siguiendo la metodología para el estudio de complejidad algorítmica propuesta en Robusté et al. (1990), se puede concluir que tanto el algoritmo de FULL- TL (envíos a carga completa) y LESS-TL (envíos a carga parcial) presentan una complejidad del orden, como máximo, de O(N 2 T ). Este atributo se justifica por haber de ordenar y asignar cada uno de los N 2 T envíos entre las delegaciones de estudio. En el caso que la matriz de envíos entre las delegaciones presente valores nulos, la complejidad computacional se reducirá. En este sentido, la complejidad computacional 3 asociada al algoritmo de refinamiento de Búsqueda Tabú es del orden de ( N N ) O, 4 T donde N 4 es el número máximo de soluciones del vecindario a analizar (en esta tesis se ha limitado este valor para limitar el tiempo computacional) Parámetros N 2 y N 3 Como se ha comentado anteriormente, los parámetros N 2 y N 3 fijan las iteraciones máximas permitidas sin que el algoritmo haya mejorado la mejor solución factible y la mejor solución (factible o infactible) respectivamente. En realidad el cumplimiento del número de iteraciones máximas de N 2 o N 3 no es un criterio de parada sino un criterio de reinicialización del proceso a partir de la mejor solución encontrada. Cuando se cumple el criterio de parada fijado por N 2 o N 3, el algoritmo vuelve a empezar el proceso de optimización a partir de una de las mejores soluciones encontradas hasta el momento. A nivel general, las mejores soluciones encontradas se han obtenido cuando N 2 =N 3 ={0,2N T ; 0,8 N T ; 2N T }, sin poder determinar un valor óptimo exacto para todas sus aplicaciones. Los casos en que N 2 >2N T y N 3 >2 N T conllevan resultados pobres y no se recomienda su aplicación. Estos valores de los parámetros implican que, durante un alto número de iteraciones, el algoritmo pueda estar operando con soluciones infactibles M. Estrada (2007) 143
8 Análisis de estrategias eficientes en la logística de distribución de paquetería o de peor coste. Por lo tanto el criterio de búsqueda de la solución es permisivo para explorar regiones de alto coste durante bastante tiempo. En particular, los resultados constatan que el número de iteraciones consecutivas necesarias para explorar zonas infactibles o de peor coste para superar un mínimo local se puede acotar a 20. Este resultado difiere con las conclusiones detalladas en Brandao (2005), donde se establecía un criterio de parada lineal con el tamaño del problema N T. Esta diferencia puede ser resultado de que los problemas analizados en Brandao (2006) eran relativos al VRP (one-to-many) y su tamaño presentaba una mayor variación (número máximo de clientes superior a 150). El algoritmo con aceptación potenciada y el algoritmo básico siguen el criterio anterior de un número máximo de iteraciones. En el problema de tamaño reducido (16 delegaciones), el algoritmo con aceptación potenciada encuentra los resultados más satisfactorios en el problema p2 cuando N 2 =N 3 = 0,8N T -2N T mientras que en el problema p1 (volúmenes de carga importantes) los valores más significativos se encuentran para N 2 =N 3 =0,2 N T -0,8 N T. El algoritmo básico sigue a nivel general esta tendencia pero presenta una variación superior del valor óptimo de N 2 y N 3. En el problema de tamaño medio, los valores de N 2 =N 3 =0,2N T predominan entre las mejores soluciones para el algoritmo de aceptación potenciada. En el caso del algoritmo básico, en los problemas de carga completa p3 se encuentran las mejores soluciones para N 2 =N 3 =0,2N T -0,8N T, pero este algoritmo es significativamente menos eficiente. COSTE PARA EL PROBLEMA C (45 TERMINALES) CON N1=500 Y N2=0,2 Coste ( ) Iteración Fig. 5.1.a) Evolución del coste con el núm. de iteraciones del problema p3 para N 1 =500 N T y N 2 =0,2N T 144 M. Estrada (2007)
9 5.Ajuste de parámetros de la búsqueda tabú COSTE PARA EL PROBLEMA C (45 TERMINALES) PARA N1=500 Y N2= Coste ( ) Iteración Fig. 5.1.b) Evolución del coste con el núm. de iteraciones del problema p3 para N 1 =500 N T y N 2 =10 N T COSTE PARA EL PROBLEMA D (45 TERMINALES) PARA N1=500 Y N2=0, Coste ( ) Iteración Fig. 5.1.c) Evolución del coste con el núm. de iteraciones del problema p4 para N 1 =500 N T y N 2 =0,2 N T COSTE DEL PROBLEMA D (45 TERMINALES) PARA N1= 500 Y N2=10 Coste ( ) Iteración Fig. 5.1.d) Evolución del coste con el núm. de iteraciones del problema p4 para N1=500 NT y N2=10 N T Finalmente, en el problema de gran dimensión (88 delegaciones), la consideración de N 2 =N 3 =0,2N T lleva a las mejores soluciones especialmente para el algoritmo con aceptación potenciada. En las Figuras 5.1.a), b) c) y d) se puede comprobar la evolución del coste de la solución real en cada iteración durante la aplicación del algoritmo de TS en el problema p3 y p4. Se puede comprobar en las Figuras 5.1.b) y d) que el hecho de adoptar N 2 =N 3 =10N T =450 iteraciones hace que el proceso de exploración se efectúe durante M. Estrada (2007) 145
10 Análisis de estrategias eficientes en la logística de distribución de paquetería muchas iteraciones en regiones infactibles, que son penalizadas en la función de coste por el término g f (x ) de la ecuación (4.28). En cambio, en el caso de las Figuras 5.1. a) y c) se puede comprobar que el proceso de optimización permite adoptar soluciones infactibles o de coste superior (proceso de subir la colina) pero los parámetros N 2 y N 3 impiden que se efectúe durante un número de iteraciones importante. Este hecho produce un alto número de reinicializaciones de la solución, que conduce a las mejores soluciones y a un comportamiento diferencial del algoritmo TS Parámetro tabu tenure (θ) El parámetro tabu tenure (θ) representa el número de iteraciones en que un atributo de la solución (cadena de nodos o envíos específicos) son considerados tabús, es decir, no pueden ser utilizados para generar una nueva solución, según la nomenclatura propuesta por Glover y Laguna (2002). Los mejores resultados obtenidos con las baterías de problemas p1-p6 no presentan un nivel de variación importante en relación con este parámetro en la misma escala que sucede con los criterios de parada N 2 ó N 3. En el caso del algoritmo con aceptación potenciada se distingue un comportamiento diferencial para θ=100, especialmente cuando se consideran problemas de envíos con carga inferior a la capacidad del vehículo (problemas LTL). El hecho de considerar un parámetro tabu tenure alto impide el comportamiento cíclico del algoritmo y por tanto, guiar la búsqueda hacia regiones no exploradas. Para el caso del algoritmo básico, no se identifica un comportamiento preferencial del algoritmo en función de este parámetro. A nivel general, se recomienda la utilización del algoritmo con aceptación potenciada, con un número de iteraciones máximas fijado por N 1 >=2000 N T. En relación al criterio de reinicialización de la búsqueda, los resultados justifican un límite de 20 iteraciones sucesivas. Este criterio puede ser equivalente a fijar N 2 =N 3 =(0,2-0,8)N T, dependiendo del tamaño del problema. 146 M. Estrada (2007)
11 5.Ajuste de parámetros de la búsqueda tabú 5.2. ANÁLISIS DE LA IMPLANTACIÓN DE LA ESTRATEGIA PEDDLING EN ORIGEN Y DESTINO El objetivo de este apartado se centra en la valoración de la bondad de aplicación de la estrategia de envío peddling así como la cuantificación de los ahorros de coste producidos en distintas tipologías de problemas. Se han generado dos baterías distintas de problemas para este análisis que cubran un amplio espectro de tipologías de redes de distribución que puedan tener interés o representatividad real. La primera batería está comprendida por problemas con distintos números de delegaciones, distinto número de terminales de consolidación y variación del volumen de mercancía de cada envío en 3 dominios diferenciados. De este modo, el volumen de mercancía a transportar entre dos puntos i,j (w ij ) puede oscilar entre [0;80] m 3, [0;20] m 3 y [20;40] m 3. Los problemas de esta batería están operados por una flota homogénea de vehículos de 80 m 3 con un coste diario F=260 y un coste kilométrico de c d =0,4 /km. A la vez, estos problemas comparten los mismos valores de las siguientes coeficientes: coste de parada c p =15 y coste de transferencia en terminal hub de c t,i =10 /m 3 i H. Los resultados obtenidos se muestran en la Tabla 5.2. Tabla 5.2. Resultados del estudio de la estrategia peddling en su aplicación a la primera batería de problemas Carga N hubs Límite inf (m 3 ) Límite sup (m 3 ) Envíos (i,j) Algoritmo básico Algoritmo con Mov. Peddling Coste inicial (%) Coste inicial ( ) Coste TS ( ) Rutas Coste inicial ( ) Coste TS ( ) Rutas Coste TS (%) Rutas (%) , , , ,17% 12,61% 11,96% , , , ,10% 20,33% 20,90% , , , ,43% 11,33% 10,00% ,35% 16,37% 17,16% ,50% 17,59% 16,67% ,33% 11,20% 11,03% ,72% 8,34% 7,72% ,98% 8,45% 8,29% ,26% 5,95% 5,91% , , ,33% 7,86% 7,44% , , , , ,20% 12,33% 10,84% , , , ,97% 10,93% 10,61% , , , , ,99% 12,09% 11,27% , , , ,75% 1,66% 0,00% , , , , ,34% 5,47% 5,13% , , , ,70% 11,19% 10,97% , , , , ,89% 9,44% 9,62% , , , ,91% 6,44% 5,75% Ahorro Los resultados demuestran que a nivel general la inclusión de la estrategia peddling en origen o destino en el algoritmo siempre conlleva una reducción de los costes finales de la distribución en todos los problemas analizados (columna coste TS de la Tabla 5.2) en relación al algoritmo básico sin estrategia peddling, así como una reducción del número de rutas. El ahorro de los costes totales presenta un valor medio de 10% al igual que la M. Estrada (2007) 147
12 Análisis de estrategias eficientes en la logística de distribución de paquetería reducción del número de rutas efectuadas. Estos costes finales han sido calculados aplicando el algoritmo metaheurístico de refinamiento de la solución Tabu Search TS comentado en el capítulo 4. Sin embargo, la mejora generalizada de la solución final se basa en que la solución inicial de partida del procedimiento Tabu Search (obtenida con el algoritmo heurístico que incluye la estrategia peddling) siempre es mejorada por el movimiento peddling. Se puede comprobar en las columnas relativas al coste inicial de la Tabla 5.2 que la mejora de la solución de partida es muy significativa, con un valor medio del 12 %. Por lo tanto, aunque la aplicación del proceso de refinamiento logra reducir iterativamente el coste del sistema de distribución, es esencial conseguir una buena solución inicial con la inclusión de la estrategia peddling. Por otro lado, se debe constatar que los mejores resultados de mejora de la estrategia peddling se obtienen en problemas con envíos con carga muy inferior a la capacidad del vehículo. Si se analiza el porcentaje medio de ocupación de un solo envío respecto la capacidad de los vehículos (ecuación 5.3), se constata que los problemas con volúmenes de carga pertenecientes al dominio w ij [0;20]m 3 (valor mínimo de o r en la batería de problemas) son los que presentan una mayor eficiencia de la estrategia peddling. Esto es debido a las mayores probabilidades de poder transportar a la vez dos o más envíos sin vulnerar la restricción de capacidad de la flota. A su vez, se puede comprobar que los problemas con cargas w ij [0;80]m 3 presentan unos rangos de costes más acordes con los obtenidos por el algoritmo básico sin estrategia peddling. w o = ij (5.3) r C La segunda batería de problemas se ha generado para poder valorar el comportamiento de la estrategia peddling en un mismo sistema físico de distribución al variar los coeficientes de coste y la flota de los vehículos. Se ha considerado tres tipologías de flota de distinta capacidad y costes unitarios: un conjunto de vehículos de 80 m 3 de capacidad, otro de 52,5m 3 y finalmente un conjunto de vehículos ligeros de 33,5 m 3 utilizable. En lo referente a los costes de parada se han analizado 2 posibilidades relativamente divergentes con valores de 5 /parada y 50 /parada. Por otro lado, el rango de los costes de transferencia en hub ha sido más extenso, permitiéndose una variación en 0.1, 1, 5 y 10 /m 3 transferido, tal y como se refleja en la Tabla 5.3. El sistema físico de distribución aplicado a todos los problemas de esta segunda batería se caracteriza por una red de 38 delegaciones con posibilidad de transferencia en 6 de 148 M. Estrada (2007)
13 5.Ajuste de parámetros de la búsqueda tabú ellas, y una carga asociada a los envíos entre delegaciones que varía uniformemente en el dominio [0;80]m 3. Cabe destacar que en los problemas con vehículos de mayor tamaño, los 751 envíos entre delegaciones del sistema pueden ser transportados indivisiblemente. Sin embargo, en los demás problemas con una flota reducida, el número de envíos totales entre delegaciones origen y destino se incrementa al tener que fraccionar la carga entre varios vehículos para cumplir la restricción de capacidad. En el caso de vehículos de 52,5 m 3 se realizan 936 envíos en distintos vehículos, mientras que en el caso de camiones de 33,5 m 3 este valor asciende a 1175 envíos. Tabla 5.3. Resultados del estudio de la estrategia peddling en su aplicación a un problema con 38 delegaciones variando los coeficientes de coste Coste Coste Cost Algoritmo básico Algoritmo con Mov. Peddling Ahorro coste Capacidad transfer en vehículo kilométrico envíos Coste Coste TS Coste Coste TS Coste Coste TS Rutas parada ( ) (m3) hub ( /m3) ( /veh- ( /km) inicial ( ) ( ) Rutas inicial ( ) ( ) Rutas inicial (%) (%) 5 0, , ,47% 11,73% 11,45% 50 0, , ,77% 6,19% 6,54% , ,78% 11,40% 10,81% , ,15% 4,62% 5,77% , ,37% 12,20% 10,94% , ,23% 5,53% 6,08% , ,59% 12,94% 12,13% , ,81% 6,21% 7,25% 5 0, ,5 0, ,87% 10,89% 11,21% 50 0, ,5 0, ,74% 6,12% 7,81% ,5 0, ,32% 8,48% 9,01% ,5 0, ,95% 4,60% 6,91% ,5 0, ,05% 10,79% 10,09% ,5 0, ,00% 5,29% 6,74% ,5 0, ,87% 10,95% 9,73% ,5 0, ,41% 6,30% 7,51% 5 0, ,5 0, ,57% 6,76% 6,76% 50 0, ,5 0, ,70% 3,26% 3,90% ,5 0, ,47% 6,65% 6,82% ,5 0, ,94% 1,79% 2,36% ,5 0, ,07% 7,73% 7,42% ,5 0, ,92% 2,84% 3,68% ,5 0, ,12% 8,99% 8,88% ,5 0, ,86% 2,07% 2,53% Los resultados detallados en la Tabla 5.3 demuestran que la eficiencia de la estrategia peddling depende relativamente del valor del coeficiente de coste por paradas. En los casos en que este coeficiente presenta valores bajos (5 /parada), la mejora de la solución final en relación al algoritmo básico es significativa, con un rango de valores entre el 6,8-13 %. En cambio, en los problemas con el valor de este coeficiente más elevado (50 /parada), el porcentaje de mejora se limita al intervalo 2,3-7,3%. Adicionalmente, la distinta ocupación relativa de un envío (indicador o c de la ecuación 5.3) también aparece como un aspecto de afectación a la bondad de la aplicación de la estrategia peddling. Se puede comprobar que los valores mínimos del porcentaje de mejora anterior corresponden a la flota de mínima capacidad, esta es la que presenta un valor de o c mayor (igual a 0,4/0,335). En estos casos, los vehículos realizan más desplazamientos a carga completa por lo que no se puede aplicar la estrategia peddling sin violar la capacidad. En cambio, la flota de mayor capacidad presenta un factor de M. Estrada (2007) 149
14 Análisis de estrategias eficientes en la logística de distribución de paquetería carga menor, por lo que la eficiencia de la estrategia peddling es superior. Este efecto se repite igual como sucedía en la primera batería de problemas. En un tercer nivel, se debe destacar que la variación del coeficiente de coste de transferencia en terminal hub no tiene una incidencia clara en el comportamiento de la estrategia peddling COMPARATIVA DE RESULTADOS CON SOLUCIÓN ÓPTIMA Como se ha anticipado, en Barcos (2002) se plantean tres problemas (PB-1, PB-2, PB- 3) de redes de distribución de muchos orígenes a muchos destinos en los que se ha determinado la solución óptima por medio de un software de resolución de programación matemática. Los problemas están compuestos por 4 puntos origen de envío de mercancía (O1-O4), varios puntos destino de mercancía (D1-D3) y una o dos terminales hub que permiten la rotura y consolidación de carga (H1-H2). Las topologías de los problemas se corresponde con las redes de las Figuras 5.2.a), b) y c) respectivamente. O1 O2 l H1 D1 O3 O4 d Fig.5.2.a) Esquema de la red del problema PB-1 l/2 O1 O2 D1 l H1 H2 l O3 O4 d D2 Fig.5.2.b) Esquema de la red del problema PB M. Estrada (2007)
15 5.Ajuste de parámetros de la búsqueda tabú O1 O2 D1 D2 l H1 H2 O3 O4 d D3 Fig.5.2.c) Esquema de la red del problema PB-3 Por su lado, los flujos de mercancía a transportar se detallan en la Tabla 5.4.a), b) y c) respectivamente para el problema PB-1, PB-2 y PB-3 expresados en unidades de volumen. En cada problema se asume que los vehículos que realizan la distribución tienen una capacidad C=10 unidades de volumen, y que los costes temporales de vehículo F, los costes de inventario de la mercancía c i son nulos, el coste kilométrico c d =1 y que d=9; l=2. En el problema PB-1 se considera un coste de transferencia en hub y un coste de parada nulos. En el problema PB-3 el coeficiente en todas las terminales H1 y H2 se ha considerado muy superior al coste kilométrico (c t,h2 >>c d ; c t,h1 >> c d ) y coste de parada nulo. Finalmente, los costes de parada c p y los costes de transferencia en las terminales hub se han considerado variables en el problema PB-2 según la Tabla 5.5. Tabla 5.4.a) Matriz de envíos O-D en el problema P-B1, b) Matriz de envíos O-D en el problema PB-2 c) Matriz de envíos O-D en el problema PB-3 a) Problema PB1 b) Problema PB-2 c) Problema PB-3 D1 D1 D2 D1 D2 D3 O1 2 O1 1 2 O O2 3 O2 1 2 O O3 2 O3 1 1 O O4 1 O4 1 1 O Tabla 5.5.Coeficientes de coste de parada y coste de transferencia adoptados en el problema PB-2 CASO Coste de parada (c p ) Coste de transferencia en ambos hubs (c t ) PB-2a 0 0,7 PB-2b 4 0 PB-2c 1 0,5 Cabe decir que en Barcos (2002) existen otros escenarios de los tres problemas planteados (PB-1, PB-3) que producían una ruta interhub entre las terminales H1, H2. Como se ha formulado en el capítulo 3, las consideraciones realizadas en esta tesis no M. Estrada (2007) 151
16 Análisis de estrategias eficientes en la logística de distribución de paquetería incluyen esta posibilidad y por lo tanto no se han analizado por imposibilidad de comparación entre soluciones. Con todo, las soluciones de los problemas con el algoritmo TS planteado en esta tesis se encuentran resumidas en la Tabla 5.6. El algoritmo TS utilizado ha integrado la mejora de movimientos peddling detallados en el subcapítulo 4.6. Se puede comprobar que en todos los casos se llega a la solución óptima, aunque en el caso PB-1 la solución encontrada con el TS presenta el mismo coste pero tiene una configuración distinta. Se debe resaltar especialmente que los problemas tipo que se muestran en Barcos (2002) no representan una situación real de problemas de distribución. En particular, se puede ver que todos los problemas presentan una zona exportadora (conjunto de nodos O i, i=1,..4) que no recibe ningún envío y una zona importadora (conjunto de nodos D j, j=1,..,3) sin ningún envío como origen. Este hecho ha producido que la aplicación del algoritmo de TS sin la mejora de aplicación de estrategias peddling (detallada en capítulo 4.6) no conduzca a buenas soluciones. Este algoritmo básico generaba como solución inicial el mismo número de envíos que rutas. La ineficiencia de la solución de partida y la limitación de aplicación de movimientos peddling en este programa no ha permitido llegar a la solución óptima. De este modo, se debe recalcar la importancia de aplicación de la mejora de los movimientos peddling que se ha propuesto en esta tesis. Tabla 5.6. Resultados obtenidos en la resolución de los problemas detallados en Barcos (2002) A. LessTL+ Peddling mejorado S. Óptima Coste Rutas Coste Rutas PB-1 14,04 r 1 :O2-O1-O3-O4-D1 14,04 r 1 :O1-O3-O4-O2-D1 PB-2a 30 r 1 :O4-O3-O1-O2-D1 r 2 :O2-O1-O3-O4-D2 30 r 1 :O4-O3-O1-O2-D1 r 2 :O2-O1-O3-O4-D2 PB-2b 70 Ídem PB-2a 70 Ídem PB-2a PB-2c 40 Ídem PB-2a 40 Ídem PB-2a PB-3 26,9 r 1 :O1-O2-O4-D3 r 2 :O3-D1-D2-D3 26,9 r 1 :O1-O2-O4-D3 r 2 :O3-D1-D2-D3 152 M. Estrada (2007)
Tesis Doctoral ANÁLISIS DE ESTRATEGIAS EFICIENTES EN LA LOGÍSTICA DE DISTRIBUCIÓN DE PAQUETERÍA
Tesis Doctoral ANÁLISIS DE ESTRATEGIAS EFICIENTES EN LA LOGÍSTICA DE DISTRIBUCIÓN DE PAQUETERÍA Autor: Miquel Àngel Estrada Romeu Ingeniero de Caminos, Canales y Puertos Director de la tesis: Prof. Francesc
Índice 1. TABLA RESUMEN... 2 2. OBJETO... 2 3. ALCANCE... 2 4. RESPONSABILIDADES... 3 5. ENTRADAS... 3 6. SALIDAS... 3 7. PROCESOS RELACIONADOS... 3 8. DIAGRAMA DE FLUJO... 4 9. DESARROLLO... 5 9.1. FLOTAS
PAUTAS DE CORRECCIÓN Prueba de diagnóstico 3
TECNOLOGÍA PARA PINTAR MAQUETA ASTRONÓMICA Utilizar distintos tipos de números y sus operaciones básicas. Interpretar información. Resolver problemas cotidianos. Utilizar los números y sus operaciones.

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución