Metaherísticas aplicadas a la optimización de rutas de transporte en vehículos con restricción de carga en 2-dimensiones

Universidad de Las Palmas de Gran Canaria Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería Tesis Doctoral METAHEURÍSTICAS APLICADAS A LA OPTIMIZACIÓN DE RUTAS DE TRANSPORTE EN VEHÍCULOS CON RESTRICCIÓN DE CARGA EN 2-DIMENSIONES Autor Óscar Luis Domínguez Rivero Las Palmas de Gran Canaria - Octubre de 2015 ªAD DE LAS PALMAS DE GRAN CANARIA Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en lngenieria EDUARDO RODRÍGUEZ BARRERA, SECRETARIO DEL INSTITUTO UNIVERSITARIO DE SISTEMAS INTELIGENTES Y APLICACIONES NUMÉRICAS EN INGENIERÍA (SIANI) DE LA UNIVERSIDAD DE LAS PALMAS DE GRAN CANARIA, CERTIFICA Que el Consejo de Doctores del Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería (SIANI), en su sesión de fecha 26 de octubre de 2015, tomó el acuerdo de dar el consentimiento para la tramitación de la Tesis Doctoral titulada "Metaheurísticas aplicadas a la optimización de rutas de transporte en vehículos con restricción de carga en 2-dimensiones", presentada por el doctorando D. Óscar Luis Domínguez Rivero, dirigida por el Dr. D. Ignacio Agustín de la Nuez Pestana y el Dr. D. Ángel Alejandro Juan Pérez, a la vista de la idoneidad y calidad de su contenido, interés y relevancia del tema. Para que así conste, y a los efectos oportunos se expide el correspondiente certificado a 26 de octubre de 2015. Universidad de Las Palmas de Gran Canaria Programa de doctorado: Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería Instituto Universitario de Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería Tesis Doctoral METAHEURÍSTICAS APLICADAS A LA OPTIMIZACIÓN DE RUTAS DE TRANSPORTE EN VEHÍCULOS CON RESTRICCIÓN DE CARGA EN 2-DIMENSIONES Autor: Óscar Luis Domínguez Rivero Dirigida por: Dr. Ángel Alejandro Juan Pérez Dr. Ignacio Agustín de La Nuez Pestana Universitat Oberta de Catalunya Universidad de Las Palmas de Gran Canaria Las Palmas de Gran Canaria, Octubre de 2015 Agradecimientos Son muchas las personas y entidades que han hecho posible la realización de esta Tesis. En primer lugar, quisiera expresar mi más sincero agradecimiento y admiración a los profesores Dr. D. Ángel Alejandro Juan Pérez y Dr. D. Ignacio Agustín de la Nuez Pestana, codirectores de esta tesis, por haber aceptado la dirección de la misma, por su orientación, su apoyo constante y por facilitarme los medios necesarios para su consecución. Además, deseo agradecer, especialmente, su paciencia y disponibilidad permanente a lo largo de estos años, que me han permitido compaginar las responsabilidades laborales y familiares, con el desarrollo del presente trabajo de investigación. También agradezco la ayuda que he recibido de todas aquellas personas con las que he tenido la suerte de colaborar, de una u otra forma, durante este periodo de investigación, especialmente a Cesar Cuenca, Enoc Martínez, Javier Faulín, Daniel Guimarans, Barry Barrios, Alba Agustín y Djamila Ouelhadj. A Máquinas Opein, S.L., “más que máquinas”, fuente de inspiración y soporte constante, le agradezco la oportunidad de haber podido desarrollarme profesionalmente y aprender lo que no está en los libros. Con la esperanza de que en un futuro próximo se puedan recoger los frutos de este trabajo. El desarrollo de una tesis doctoral implica un coste de oportunidad importante, la mayor parte de este coste reside en el tiempo que no he podido dedicar a mi familia. Por ello, quiero agradecer a mi familia su apoyo incondicional y su comprensión durante todos estos años. 4Índice general 4. Algoritmo MS-BR para el 2L-HFVRP no restringido. 107 4.1. Introducción. .................................. 107 4.2. Descripción del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 4.3. Principales características del algoritmo propuesto. . . . . . . . . . . . . . . 109 4.4. Experimentos computacionales. . . . . . . . . . . . . . . . . . . . . . . . . 113 4.5. Análisis de los resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5. Algoritmo ILS-BR para el 2L-HFVRP secuencial. 127 5.1. Introducción. .................................. 127 5.2. Descripción del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.3. Descripción del algoritmo propuesto. . . . . . . . . . . . . . . . . . . . . . . 131 5.4. Detalle a bajo nivel mediante pseudo-código. . . . . . . . . . . . . . . . . . 133 5.5. Experimentos computacionales. . . . . . . . . . . . . . . . . . . . . . . . . 139 5.6. Análisis de los resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6. Algoritmo LNS-BR para el 2L-VRPCB. 153 6.1. Introducción. .................................. 153 6.2. Descripción del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.3. Descripción del algoritmo LNS-BR. . . . . . . . . . . . . . . . . . . . . . . 157 Índice general 5 6.4. Experimentos computacionales. . . . . . . . . . . . . . . . . . . . . . . . . 163 6.4.1. Resultados experimentales para el problema 2L-VRPCB. . . . . . . . 163 6.4.2. Resultados experimentales para el problema 2L-CVRP. . . . . . . . . 164 6.4.2.1. Resultados experimentales para el problema 2L-CVRP con carga orientada secuencial (2|SO|L). . . . . . . . . . . . . 171 6.4.2.2. Resultados experimentales para el problema 2L-CVRP con carga no orientada secuencial (2|SR|L). . . . . . . . . . . . 177 6.5. Análisis de los resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 6.5.1. Análisis de los resultados para el 2L-VRPCB. . . . . . . . . . . . . . 177 6.5.2. Análisis de los resultados para el 2L-CVRP. . . . . . . . . . . . . . . 182 7. Conclusiones y futuras líneas de investigación. 185 7.1. Conclusiones................................... 185 7.2. Publicaciones................................... 188 7.2.1. Revistas. ................................ 188 7.2.1.1. Artículos aceptados. . . . . . . . . . . . . . . . . . . . . . 188 7.2.1.2. Artículos en revisión. . . . . . . . . . . . . . . . . . . . . 189 7.2.2. Congresos. ............................... 189 7.3. Futuras líneas de investigación. . . . . . . . . . . . . . . . . . . . . . . . . . 190 6Índice general Bibliografía 193 Índice de figuras 1.3.1.Distribución modal intra-europea del transporte de mercancías en 2013. . . . 21 1.3.2.Evolución del precio del gasóleo de automoción de 1998 a 2015. . . . . . . . 23 1.3.3.Parque de camiones rígidos autorizados para el transporte de mercancías por carreteraenEspaña(2014)............................ 25 1.3.4.Reducción en la emisión de contaminantes para camiones pesados, según normativaeuropea.................................. 27 1.3.5.Relación entre el crecimiento del PIB y el transporte de mercancías para 15 países europeos, entre 1991 y 2002. . . . . . . . . . . . . . . . . . . . . . . 29 1.3.6.Crecimiento del transporte de mercancías entre 1990 y 2005, para distintos modos de transporte interior (EU-27). . . . . . . . . . . . . . . . . . . . . . 30 1.4.1.Emisiones de CO2/ t-km, frente a la carga útil transportada. . . . . . . . . . . 33 1.4.2.Emisiones de CO2/ t-km, en relación a la carga útil transportada y el porcentaje de trayecto circulando en vacío. . . . . . . . . . . . . . . . . . . . . . . 34 8Índice de figuras 1.4.3.Características de la carga en relación al grado de utilización de la capacidad decargadelvehículo............................... 35 1.4.4.Consumo de combustible y eficiencia en relación al tipo de vehículo (Francia 2004)....................................... 37 1.5.1.Ejemplo descriptivo del problema de rutas de vehículos (VRP). . . . . . . . 42 1.6.1.Gráficas de carga y rutas correspondientes a una solución ejemplo de un problemaclásicodel2L-CVRP. .......................... 47 3.3.1.Flujograma del algoritmo MSBR . . . . . . . . . . . . . . . . . . . . . . . . 82 3.5.1.Comparación mediante diagrama de cajas de la calidad de las soluciones, BEST10, entre las metaheurísticas ACO y MS-BR para el problema 2|UR|L. 99 3.5.2.Diagrama de cajas comparando las diferencias respecto a las mejores soluciones conocidas, BKS, obtenidas por los distintos algoritmos considerados, para el2|UO|L..................................... 103 3.5.3.Evolución de la mejor solución encontrada cuando aumenta el tiempo de computación y el número de réplicas, tomando como ejemplo la instancia 36 clase 5, (2|UO|L). .................................... 104 3.5.4.Evolución de la mejor solución encontrada cuando aumenta el tiempo de computación y el número de réplicas, tomando como ejemplo la instancia 21 clase 3, (2|UR|L). .................................... 105 4.3.1.Flujograma del algoritmo MS-BR para resolver el problema 2L-HFVRP. . . . 110 4.5.1.Diagrama de cajas representando los costes totales por algoritmo y clase. . . . 123 Índice de figuras 9 4.5.2.Diagrama de cajas de diferencias (Gaps) por clase. . . . . . . . . . . . . . . 123 4.5.3.Diferencias entre las versiones de carga orientada (UO) y no orientada (UR), según instancia y clase, para el algoritmo MS-BR. . . . . . . . . . . . . . . . 124 5.1.1.Ejemplo de carga secuencial para un pequeño caso con 3 vehículos. . . . . . 128 5.3.1.Esquema general de nuestro algoritmo ILS-BR. . . . . . . . . . . . . . . . . 132 5.6.1.Diagrama de cajas de costes totales para SA_HLS O (orientada), ILS-BR orientada (OBS O), ILS-BR con rotación (OBS R). . . . . . . . . . . . . . . 149 5.6.2.Diferencias porcentuales (Gap) entre los algoritmos SA_HLS O (orientada), ILS-BR orientada (OBS O) e ILS-BR con rotación (OBS R). . . . . . . . . . 150 5.6.3.Ejemplo de solución de carga secuencial para la instancia 10 y clase 3. . . . 151 6.2.1.Ejemplo de una ruta que combina entrega y recogida de mercancía, incluyendo las dos soluciones de carga correspondientes. . . . . . . . . . . . . . . . . . 156 6.3.1.Flujograma del algoritmo del procedimiento Pack-And-Route para el LNS-BR. 161 6.5.1.Comparación de resultados para el 2L-VRPCB, para las diferentes ratios, con y sin rotación de los artículos. . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.5.2.Comparación de metaheurísticas para el 2L-CVRP, sin rotación de artículos (2|SO|L). .................................... 183 6.5.3.Comparación de metaheurísticas para el 2L-CVRP, con rotación de artículos (2|SR|L)...................................... 184 Índice de tablas 1.1. Principales extensiones del VRP. . . . . . . . . . . . . . . . . . . . . . . . . 44 2.1. Clases usadas para la generación de los artículos a cargar. . . . . . . . . . . . 62 3.1. Principales características de las instancias de referencia para el problema 2LCVRP....................................... 92 3.2. Comparación entre el algoritmo ACO y el algoritmo MS-BR, clase 1 . . . . . 94 3.3. Comparación entre el algoritmo ACO y el algoritmo MS-BR para la versión 2|UR|L,clase2.................................. 95 3.4. Comparación entre el algoritmo ACO y el algoritmo MS-BR para la versión 2|UR|L,clase3.................................. 96 3.5. Comparación entre el algoritmo ACO y el algoritmo MS-BR para la versión 2|UR|L,clase4.................................. 97 3.6. Comparación entre el algoritmo ACO y el algoritmo MS-BR para la versión 2|UR|L,clase5.................................. 98 12 Índice de tablas 3.7. Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la clase 1. . . . . . . . . . . . 100 3.8. Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 2. . . 101 3.9. Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 3. . . 101 3.10. Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 4. . . 102 3.11. Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 5. . . 102 4.1. Tabla de características para los diferentes tipos de vehículos. . . . . . . . . . 115 4.2. Comparación de resultados entre SA_HLS y MS-BR - Clase 1. . . . . . . . . 116 4.3. Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MSBR no orientado (con posibilidad de rotación) - Clase 2. . . . . . . . . . . . . 117 4.4. Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MSBR no orientado (con posibilidad de rotación) - Clase 3. . . . . . . . . . . . . 118 4.5. Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MSBR no orientado (con posibilidad de rotación) - Clase 4. . . . . . . . . . . . . 119 4.6. Comparación de resultados entre SA_HLS (orientado), MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - Clase 5. . . . . . . . . . 120 Índice de tablas 13 4.7. Comparación de resultados entre SA_HLS (orientado), MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - promedio Clases 2 a 5. . 121 5.1. Comparación de resultados entre SA_HLS y ILS-BR - Clase 1. . . . . . . . . 141 5.2. Comparación de resultados entre SA_HLS orientado, ILS-BR orientado y ILS-BR no orientado - Clase 2. . . . . . . . . . . . . . . . . . . . . . . . . . 142 5.3. Comparación de resultados entre SA_HLS orientado, ILS-BR orientado y ILS-BR no orientado - Clase 3. . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.4. Comparación de resultados entre SA_HLS orientado, ILS-BR orientado y ILS-BR no orientado - Clase 4. . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.5. Comparación de resultados entre SA_HLS orientado, ILS-BR orientado y ILS-BR no orientado - Clase 5. . . . . . . . . . . . . . . . . . . . . . . . . . 145 5.6. Comparación de resultados entre SA_HLS orientado, ILS-BR orientado y ILS-BR no orientado - promedio Clases 2 a 5. . . . . . . . . . . . . . . . . . 146 5.7. Comparación de resultados entre MS-BR y ILS-BR para la versión de carga 2|UO|L - promedio Clases 2 a 5. . . . . . . . . . . . . . . . . . . . . . . . . 147 6.1. Resultados para el 2L-VRPCB, clase 1. . . . . . . . . . . . . . . . . . . . . 165 6.2. Resultados para el 2L-VRPCB, clase 2 para las versiones de carga 2|SO|L y 2|SR|L. ..................................... 166 6.3. Resultados para el 2L-VRPCB, clase 3 para las versiones de carga 2|SO|L y 2|SR|L. ..................................... 167 20 Introducción. 1.2. Ámbito general de la tesis. La logística es una función básica de la mayor parte de las organizaciones, y especialmente en las de carácter empresarial. Se puede definir la logística como una actividad que permite el suministro de bienes y servicios desde los lugares donde se ofertan hasta los lugares donde se demandan, con la finalidad de satisfacer unas necesidades explícitas o subyacentes. La logística, que abarca por ejemplo, el transporte y el almacenamiento, representa entre el 10% y el 15% del coste de un producto acabado para las empresas europeas1. Según Yao et al. (2015), en China, por ejemplo, el beneficio medio de la industria logística alcanza solamente el 3%, siendo los costes del transporte los que mayor influencia tienen sobre el coste logístico total. Por lo tanto, como cualquier otra actividad dentro del ámbito empresarial, la gestión logística debe realizarse tratando de optimizar los métodos y medios empleados para un nivel de servicio determinado. Otro concepto asociado con la gestión logística en el mundo empresarial es la cadena de suministro osupply chain. En este caso se crea una red o cadena entre diferentes empresas productoras, manipuladoras y/o distribuidoras de un producto específico. En concreto, la cadena de suministro abarca los pasos que se necesitan para obtener un bien o servicio desde el proveedor hasta el cliente. La gestión de la cadena de suministro es un proceso crucial para muchas empresas, ya que su optimización se traduce en menores costes para la empresa y/o un mejor nivel de servicio al cliente. El objetivo de la cadena es alinear las operaciones internas para mejorar el servicio al cliente, minimizando el tiempo de ciclo y los recursos empleados. El transporte de mercancías constituye una parte esencial dentro de los conceptos expuestos de logística o cadena de suministro. El presente trabajo de investigación se circunscribe dentro del ámbito del transporte de mercancías y más concretamente dentro del transporte de 1Fuente: Comisión Europea, MEMO/11/197. 1.3 Transporte de mercancías por carretera. 21 Figura 1.3.1: Distribución modal intra-europea del transporte de mercancías en 2013. mercancías que se realiza por carretera. En el siguiente apartado se introduce brevemente la problemática asociada a dicho sector de actividad. 1.3. Transporte de mercancías por carretera. 1.3.1. El sector del transporte de mercancías por carretera. El transporte de mercancías por carretera es un sector de vital importancia en la economía mundial. La mayor parte de las mercancías que se consumen diariamente, han sido transportadas por vehículos. Los vehículos que transportan mercancías por carretera, permiten que hogares y empresas distribuidas geográficamente, puedan intercambiar bienes con otros lugares. Esto hace posible una mayor libertad a la hora de elegir la ubicación geográfica de los hogares y las empresas. Lo cual favorece, por ejemplo, un mejor reparto de la actividad económica entre las zonas urbanas y las zonas rurales. En la figura 1.3.1 se muestra como el transporte de mercancías por carretera, es el mo- 22 Introducción. do de transporte más utilizado dentro del territorio europeo (EU-28)2. Aproximadamente la mitad de las t-km transportadas en Europa, se realizan por carretera, lo que supuso en 2013 aproximadamente 1.669 millones de t-km. El sector del transporte de mercancía en general, y por ende en el que se realiza por carretera, está afectado por diversos factores externos, dentro de los cuales se pueden destacar los siguientes: •La globalización, es un factor que ha repercutido significativamente sobre la demanda de transporte de mercancías. La fabricación es cada vez más especializada y fragmentada. Los fabricantes integran cada vez más componentes o piezas realizados por terceros, en muchas ocasiones provenientes de diferentes partes del mundo. Todo lo anterior ha provocado un aumento creciente de la demanda de servicios de transporte de mercancías. •La alta dependencia de los combustibles procedentes del petróleo. En el transporte por carretera, afecta particularmente el aumento de los precios del gasóleo de automoción, especialmente desde finales del siglo pasado. En el caso de España, debido fundamentalmente a un aumento de la demanda de este tipo de combustible, así como a un aumento en la fiscalidad aplicable al gasóleo de automoción. En la figura 1.3.2 se observa la evolución del precio del gasóleo de automoción en España3. •Mejora de la red viaria, especialmente en los últimos 20 años. La red de carreteras de España tiene, a 31 de diciembre de 2013, 165.361 km. Además de este viario, los ayuntamientos tienen a su cargo 489.698 km de los cuales 361.517 km son interurbanos4. España disponía en el año 2000 de 9.049 km de vías de gran capacidad (autopistas de peaje, libres y autovías), mientras que en el año 2012 contaba con un total de 14.701 2Fuente: EUROSTAT. 3Fuente: Ministerio de Industria, Energía y Turismo. 4Fuente: Ministerio de Fomento. 1.3 Transporte de mercancías por carretera. 23 Figura 1.3.2: Evolución del precio del gasóleo de automoción de 1998 a 2015. km, siendo el país de Europa con mayor longitud de vías de este tipo. El segundo país era Alemania con 12.879 km y Francia el tercero con 11.465 km5. En España, el sector del “transporte terrestre (carretera y ferrocarril) y por tubería”, supuso en el año 2012 en torno al 2,15% del Valor Añadido Bruto (VAB) a precios básicos6. Según el Instituto Nacional de Estadística (INE), este mismo sector, durante el año 2013 tuvo un volumen de negocio de 31.610 millones de euros, generado por unas 108.180 empresas, que ocuparon a 307.047 personas de media en ese mismo periodo. Estos datos muestran una de las características del sector del transporte de mercancías por carretera en España, su alto nivel de atomización, con una ratio de aproximadamente 2,84 trabajadores por empresa, y una facturación promedio de unos 292.198 euros. El trabajo realizado por Vassallo et al. (2014), aporta datos económicos relevantes del 5Fuente: EUROSTAT, “length of motorway”, datos de 2012, actualizados a 02/03/15. 6Fuente: Ministerio de Fomento. Observatorio de mercado del transporte de mercancías por carretera. 24 Introducción. sector de transporte de mercancías por carretera, entre los que se encuentran los relativos a la recaudación fiscal del sector. Según este trabajo, el transporte de mercancías por carretera aportó 13.548,63 millones de euros, en impuestos y tasas durante el año 2012. Ese mismo año, el gasto en conservación de la red de carreteras interurbana fue de 1.445,71 millones de euros. Estos datos contrastan con los del transporte de mercancías por ferrocarril, que aportó ese mismo año en fiscalidad específica y cánones 98,11 millones, mientras que el gasto de mantenimiento de la red ferroviaria para este mismo año fue de 1.593,74 millones de euros. Por lo tanto, queda claro que el transporte de mercancía por carretera es capaz de cubrir los gastos de mantenimiento de la red de carreteras interurbanas, mientras que en caso del transporte de mercancías por ferrocarril no cubre los gastos correspondientes a la red ferroviaria. Ha esta misma conclusión llegó el estudio realizado por el Instituto Alemán de Investigación Económica (DIW), realizado en 2009, sobre los costes de infraestructura7del transporte por carretera y del ferroviario en Alemania durante el año 2007, así como el grado de cobertura logrado por ambos medios de transporte. Según dicho estudio el transporte de mercancías por carretera cubría el 99% de los costes de infraestructura de la red de carreteras, mientras que el tráfico ferroviario de mercancías cubría tan solo el 11% de sus costes de infraestructura8. Según la Encuesta Permanente de Transportes de Mercancías por Carretera (EPTMC), referidos al año 2014, los vehículos pesados, de más de 3,5 toneladas, autorizados para el transporte de mercancías por carretera realizaron 169 millones de operaciones de transporte9, trasladando 1.185 millones de toneladas y generando 196 mil millones de toneladas-kilómetro. Mientras que la distancia media de las operaciones de transporte fue de 108 kilómetros. El parque de vehículos pesados autorizados para el transporte de mercancías por carretera 7Todos los costes financieros que comienzan desde la construcción, operación y mantenimiento de una infraestructura. 8Fuente: VDA (Verband der Automobilindustrie). Politikbrief 02/2009. 9Es el desplazamiento de una única clase de mercancía desde un lugar de origen, en en que se carga la mercancía, a uno de destino, en el que se descarga. Según esta definición, el desplazamiento en el mismo vehículo de dos clases diferentes de mercancías se considera dos operaciones de transporte distintas, siendo sólo uno el desplazamiento realizado por el vehículo. 1.3 Transporte de mercancías por carretera. 25 Figura 1.3.3: Parque de camiones rígidos autorizados para el transporte de mercancías por carretera en España (2014). en España, en el año 2014, estaba formado por 302.037 vehículos10. Estos vehículos se dividen a su vez en dos grandes categorías: 1. Los camiones rígidos, constituían algo más de la mitad del parque total (52,78%), eran 159.425 vehículos. En la figura 1.3.3 se hace una clasificación de este tipo de vehículo, en función de su capacidad de carga. 2. Las vehículos denominados cabezas tractoras, que generalmente arrastran un semirremolque, constituían el resto del parque, 142.612 vehículos. En Canarias, sin embargo, la distribución del parque de vehículos pesados era muy diferente. De un total de 12.856 vehículos pesados, el 86,83% eran camiones rígidos, mientras que las cabezas tractoras apenas llegaban a 1.693 unidades. 10Fuente: D. G. de Transporte Terrestre. Ministerio de Fomento. Datos a 31 de diciembre. 26 Introducción. 1.3.2. Contaminación ambiental producida por el transporte de mercancías por carretera. El transporte en general tiene unos efectos peligrosos sobre el medio ambiente y las personas. Concretamente el transporte de mercancías por carretera, además de los accidentes de tráfico, genera un impacto sobre el medio ambiente, que incluye elementos tales como: •El ruido, generado por los vehículos al circular, especialmente los que obtienen su energía de motores de combustión interna, generalmente gasoil de automoción. •Emisión de contaminantes con efectos tóxicos sobre los ecosistemas y las personas, dentro de los que se destacan: • Gases de efecto invernadero, especialmente el dióxido de carbono (CO2) y óxidos de nitrógeno (NOX). • Dióxido de azufre (SO2), principal causante de la lluvia ácida. • Monóxido de carbono (CO). • Hidrocarburos gaseosos de diverso tipo, denominados generalmente como compuestos orgánicos volátiles (COV). • Material particulado tipo hollín (PM). •Ocupación del suelo de las infraestructuras de transporte por carretera. Debido a los avances tecnológicos y a las regulaciones medioambientales, los vehículos son cada vez más eficientes y menos contaminantes. El consumo de combustible de los vehículos de transporte de mercancías, ha mejorado considerablemente en los últimos 40 años. En el caso de los vehículos comerciales pesados, (más de 3,5 toneladas de MMA), el consumo medio ha pasado de unos 50 litros/100 km en 1970, hasta unos 30 litros/100km en 201411. 11Fuente: VDA (Verband der Automobilindustrie). 1.3 Transporte de mercancías por carretera. 27 Figura 1.3.4: Reducción en la emisión de contaminantes para camiones pesados, según normativa europea. 28 Introducción. En relación a la reducción en la contaminación producida por los camiones pesados, la figura 1.3.4 muestra claramente la reducción en los límites máximos de contaminación admitidos, en función de la reglamentación europea sobre la materia. Desde la entrada en vigor de la primera norma el 1 de octubre de 1990, denominada Euro 0, hasta la actual Euro 6, de fecha 1 de enero de 2014, se ha producido una drástica reducción en los límites máximos admisibles para gases y partículas contaminantes. La normativa europea controla los siguientes gases: Óxidos de Nitrógeno (NOX), Monóxido de carbono (CO), Hidrocarburos (HC) y Partículas en suspensión (PM). En el caso de los camiones, las partículas en suspensión están relacionadas con la energía generada, por lo que son medidas en g/kWh. Sin embargo, hasta el momento, aunque pueda resultar sorprendente, estas normas no tienen en cuenta las emisiones de CO2. En cuanto a la contaminación por CO2, generada por el transporte de mercancías por carretera, existen diferentes estimaciones al respecto. Una de ellas es la que proporciona el European Committee for Standardization (CEN), en el documento titulado “Common methodology for the calculation and declaration on energy consumption and greenhouse gas (GHG) emissions related to a transport service (of goods, passengers or both)”, en el cual establece el valor para la emisión de CO2en función del consumo de combustible del vehículo, para el caso del gasoil de automoción este valor estimado es de 2,9 kg de CO2/litro. Otra estimación, como la de la Oficina Catalana de Cambio Climático (2012), propone una ratio ligeramente inferior de 2,61 kg de CO2/litro. Asimismo, un estudio realizado por Piecyk y McKinnon (2010) en Gran Bretaña, sobre la contaminación por dióxido de carbono producida por el transporte de mercancía por carretera, proponía una ratio parecida de 2,63 kg de CO2/litro. Por lo tanto, para un camión actual con un consumo medio aproximado de 30 l/100km, se tendría un nivel supuesto de emisiones entre 0,87 y 0,783 kg de CO2/km. 1.3 Transporte de mercancías por carretera. 29 Figura 1.3.5: Relación entre el crecimiento del PIB y el transporte de mercancías para 15 países europeos, entre 1991 y 2002. 1.3.3. El futuro del sector del transporte de mercancías por carretera. La evolución del sector vendrá en gran medida condicionada por el crecimiento económico previsto. Es bien conocida la relación entre el producto interior bruto (PIB) y el transporte de mercancías en los países, por ejemplo, en la figura 1.3.5 se observa dicha relación para el periodo 1991-2002, en 15 países de la Comunidad Europea12. Ante un escenario de crecimiento moderado de la economía en Europa, para los próximos años se espera que el transporte de mercancías, incluido el sector por carretera, siga creciendo. En la figura 1.3.6 se puede apreciar una proyección de este crecimiento estimado, según la Agencia Europea de Medio Ambiente (EEA). A continuación, se resumen las principales líneas que marcarán el futuro del sector, especialmente en el ámbito europeo, durante las próximas décadas1314: 12Fuente: EUROSTAT. 13Road Transport - A change of gear. Publications Office of the European Union. European Union, (2012). 14VDA (Verband der Automobilindustrie). VDA’s Commercial Vehicle Symposium 2015. 36 Introducción. 1.4.2. Influencia del recorrido. Las características del recorrido escogido, como la distancia, la orografía de la ruta, el tipo de vía y su estado, etc., condicionan en gran medida los costes asociados al transporte de la mercancía. Generalmente se suele prestar más atención a la distancia, sin embargo en ocasiones el tipo de vía u otras características, pueden hacer más eficiente la elección de recorridos alternativos de mayor distancia aunque más rápidos o con menores costes asociados. En el caso del tipo de vía, no es lo mismo que el vehículo circule por una autopista o autovía que por una carretera local. Lógicamente, las vías rápidas suelen permitir costes más bajos por t-km. Algunos trabajos como el realizado por Combes y Lafourcade (2005) sobre la red viaria francesa, ponen de manifiesto la magnitud de esta influencia. La orografía y el trazado de la carretera, son características que inciden en los costes del transporte. Las vías que siguen un trazado sinuoso, con continuas pendientes ascendentes y descendentes, o con mayor incidencia de tramos curvos, suponen un mayor consumo de combustible y reducen la velocidad media del trayecto. Por otra parte, las vías con un pavimento irregular o en mal estado, aumentan el rozamiento y obligan a reducir la velocidad, lo que también ocasiona mayores costes para el transporte. Por consiguiente, si bien es cierto que la distancia a recorrer es un factor de primer nivel a tener en cuenta, a la hora de confeccionar el itinerario del vehículo, conviene tener presente otras características del recorrido que también influyen en el coste final del transporte de mercancías por carretera. 1.4 Eficiencia del transporte de mercancías por carretera. 37 1.4.3. Influencia del tipo de vehículo. Generalmente, cuanto mayor es la capacidad de carga de un vehículo, mayor es su tasa de consumo de combustible. Sin embargo, al aumentar la capacidad de carga, suele producirse una mejora en la relación entre el consumo de combustible y las toneladas por kilómetro transportadas. En la figura 1.4.4 se puede apreciar un ejemplo ilustrativo, confeccionado a partir de datos suministrados por Leonardi et al. (2008), según estadísticas del transporte de mercancías en Francia durante el año 2004. Figura 1.4.4: Consumo de combustible y eficiencia en relación al tipo de vehículo (Francia 2004). Conviene por tanto, disponer de un vehículo que se adapte a las características de la carga a transportar. Es decir, un vehículo en el que se utilice el máximo de capacidad útil del vehículo, y cumpla con las limitaciones impuestas por las infraestructuras de transporte. Siguiendo este mismo criterio, cuando una empresa de transportes planifica las características de su flota de vehículos, parece lógico considerar un cierto grado de heterogeneidad. Esta 38 Introducción. diversidad facilita la adaptación de la flota a la naturaleza de la carga a transportar y permite mejorar la eficiencia del transporte. 1.5. Optimización de rutas de transporte. 1.5.1. Antecedentes. El interés de la humanidad por encontrar las mejores rutas de transporte, no es sin lugar a dudas una cuestión reciente. Desde la antigüedad, el ser humano ha tratado de buscar el mejor camino o sendero, para el transporte de personas, animales, bienes o mercancías. Incluso en el mundo animal se pueden encontrar multitud de ejemplos, desde insectos como las hormigas hasta las aves migratorias, en los que una especie debe afrontar un problema de transporte. Desde el punto de vista científico, uno de los primeros trabajos documentados sobre la materia data del siglo XVIII, donde Leonhard Euler trata el famoso problema de los 7 puentes de Köningsberg. Posteriormente, en el siglo XIX, el irlandés W.R. Hamilton y el británico a T. Kirkman inventaron el denominado “Icosian Game”, que se considera el antecedente más importante del conocido como problema del viajante de comercio (Travelling Salesman Problem - TSP). 1.5.2. El problema del viajante de comercio (TSP). Es uno de los problemas clásicos, dentro de la optimización combinatoria, relacionados con el transporte, sobre los que se ha realizado un mayor esfuerzo investigador. En este problema, el viajante de comercio se encuentra en una ciudad específica, y se 1.5 Optimización de rutas de transporte. 39 dispone a visitar una relación de ciudades previamente establecida, en la que se conocen las distancias entre cada una de ellas y el resto. El objetivo del problema es encontrar la ruta óptima que, comenzando y terminando en la misma ciudad, pase una sola vez por cada una de las ciudades a visitar y minimice la distancia recorrida. Aunque se trata de un problema sencillo, desde el punto de vista del modelo simplificado que plantea, ya que apenas considera restricciones en su resolución, su optimización resulta verdaderamente compleja cuando se incrementa el tamaño del problema. De hecho, desde el punto de vista de la teoría de la complejidad computacional, se trata de un problema NPcompleto, véase Karp (1972). Esto significa que es poco probable que podamos encontrar un algoritmo para este problema con un tiempo de ejecución, que aumente como mucho polinómicamente con el tamaño del problema. La persona interesada en profundizar sobre el tema, dispone de una extensa bibliografía para el estudio, dentro de la cual se encuentran obras de referencia como Applegate et al. (2011)yGutin y Punnen (2002). 1.5.3. Múltiples viajantes de comercio (m-TSP). El problema de los m-viajantes de comercio (m-TSP), se obtiene a partir de una generalización del modelo del viajante de comercio (Traveling Salesman Problem - TSP), donde mes un entero mayor a 1. En este problema, se construye una ruta para cada uno de los mviajantes de comercio (o vehículos), de tal forma que puedan ser visitadas nciudades en total, (donde n > m). Al igual que en el TSP, cada cliente debe ser visitado exactamente una vez. Igualmente, cada ruta debe ser un camino cerrado en el que no se repite ninguna ciudad, o más genéricamente denominado vértice o nodo, a excepción de la primera que aparece dos veces como principio y fin de la ruta. La función objetivo es la minimización del coste o distancia total de 40 Introducción. las mrutas. Dada la relación entre el problema múltiple (m-TSP) y el problema básico (TSP), algunos trabajos sobre la materia resuelven el problema mediante una transformación del primero al segundo. Uno de los primeros trabajos en utilizar esta metodología, fue el publicado por Bellmore y Hong (1974), en el cual se pasaba de un problema m-TSP con nciudades o nodos a un problema TSP conteniendo m+n ciudades. Generalmente esta simplificación se realiza basándose en la metodología de dos fases, en la que primero se agrupan o asignan las ciudades y después se generan las rutas, comúnmente denominada cluster-first-route-second. Al tratarse de una variante más completa o generalizada del problema del viajante de comercio, se adapta mejor a la resolución de casos reales o situaciones prácticas. En este sentido, el artículo de Bekta¸s (2006) hace una revisión de aplicaciones prácticas del m-TSP, así como de los métodos o procedimientos de resolución propuestos en la biografía publicada sobre la materia. 1.5.4. Problemas de rutas de vehículos (VRP). Los problemas de rutas de vehículos, denominados generalmente en la literatura científica como Vehicle Routing Problems (VRP), son una generalización de los problemas anteriores. En este caso se trata de un conjunto o flota de vehículos que deben visitar a una relación de clientes geográficamente dispersos. Sin embargo, a diferencia del problema del viajante de comercio, en los problemas de rutas de vehículos se consideran las demandas de los clientes a visitar, es decir, se considera el transporte de mercancías desde los almacenes hasta los clientes. El problema más básico de rutas de vehículos, es el denominado problema de rutas de vehículos con capacidad limitada, conocido generalmente por sus siglas en inglés CVRP, Ca- 1.5 Optimización de rutas de transporte. 41 pacitated Vehicle Routing Problem. Este problema fue descrito formalmente por primera vez en el artículo de Dantzig y Ramser (1959), quienes describieron una aplicación real de distribución de combustible a las estaciones de servicio. En términos generales, el problema de rutas de vehículos con capacidad limitada (CVRP) consiste en generar un conjunto de rutas, usando una flota de vehículos homogénea con capacidad limitada, con el fin de suministrar la demanda de unos clientes. De tal manera que la demanda total de los clientes a servir en cada ruta, no supere la capacidad del vehículo que la realiza. Al igual que en el TSP, cada cliente sólo puede ser visitado una vez, teniendo presente que los vehículos deben comenzar y terminar sus respectivas rutas en el mismo lugar, denominado generalmente depósito o almacén. El objetivo de la solución al problema es la minimización del costo de la distribución subyacente, en la que dicho costo está normalmente relacionado directamente con la distancia total recorrida por la flota de vehículos. En la figura 1.5.1 se muestra un ejemplo ilustrativo de una solución tipo con 3 rutas, 17 clientes y un depósito central desde el que se distribuye la mercancía a los clientes. Por lo tanto, el problema del viajante de comercio (TSP), es un caso particular en el cual sólo existe un vehículo y donde la capacidad de carga del mismo es superior a la demanda total agregada de los clientes a visitar. Partiendo del problema de rutas de vehículos con capacidad limitada (CVRP), se han ido desarrollando una gran cantidad de variantes del VRP. Estas variantes se obtienen mediante una generalización o extensión del problema básico, añadiendo nuevos atributos y restricciones al modelo. De esta forma, las nuevas variantes incorporan en su modelo aspectos relevantes de la realidad del transporte de mercancías, lo que permite abordar cada vez más casos prácticos. Esta evolución del VRP básico hacia problemas más complejos, pero con mayor capacidad para ser aplicados en situaciones reales, supone un enriquecimiento del modelo, con lo que en la literatura, en ocasiones, a estos nuevos tipos de problemas se los denomina Rich 42 Introducción. Figura 1.5.1: Ejemplo descriptivo del problema de rutas de vehículos (VRP). Vehicle Routing Problems. Existen diversos trabajos que realizan una retrospectiva del problema de rutas de vehículos, así como de sus diferentes variantes, entre los que se encuentran los artículos de Laporte (2009) y Laporte et al. (2013), que lo hacen desde una perspectiva más generalista, mientras que el trabajo de Caceres-Cruz et al. (2014) se centra más en las extensiones del VRP con mayor enfoque práctico. Por otra parte, en el caso de una aplicación práctica, se deberá desarrollar un modelo del problema que incluya aquellas extensiones que mejor se adapten a los objetivos y características del caso real a resolver. 1.5 Optimización de rutas de transporte. 43 En la tabla 1.1 se presentan a modo de ejemplo, algunas de las extensiones más importantes del problema de rutas de vehículos (VRP). Queda claro que el número de variantes del problema que se pueden obtener es casi ilimitado, si se considera la combinación de diferentes extensiones en un mismo problema. Características del modelo afectadas Descripción de la variante Condiciones del servicio al cliente Ventanas de tiempo para servir a cada cliente, pudiendo incluir también al depósito. Condiciones del servicio al cliente Los clientes requieren servicios de entrega y recogida de mercancía. Condiciones del servicio al cliente Es posible emplear más de un vehículo para servir la demanda del cliente. Características de las rutas El final de la ruta no tiene porqué ser el depósito (subcontratación del transporte) Características de los vehículos Existe una flota de vehículos heterogénea, con distintas características en cuanto a costes y capacidad. Características de la mercancía y los vehículos Además del peso o volumen total de la mercancía, se consideran sus dimensiones físicas. Depósitos Existe más de un depósito, desde donde salen y regresan los vehículos asignados al mismo. Continúa en la siguiente página 44 Introducción. Características del modelo afectadas Descripción de la variante Naturaleza de la información Algunos datos del problema cambian dinámicamente en el tiempo, pudiéndose generar una nueva solución distinta de la inicial, durante la ejecución del servicio al cliente. Naturaleza de la información Algunos datos del problema tienen una componente de naturaleza estocástica, como la demanda de los clientes o el tiempo empleado en el transporte. Red viaria Las distancias o tiempos de recorrido entre dos nodos, dependen del sentido del trayecto realizado (asimetría de la red viaria). Función objetivo El objetivo del problema incorpora la minimización de la contaminación, el consumo de combustible o los gastos operativos del transporte. (Pollution-Routing Problem). Tabla 1.1: Principales extensiones del VRP. 1.6. Problemas de rutas de vehículos con restricción de carga en dos dimensiones. En este trabajo de investigación se abordan varias extensiones del VRP, partiendo del problema de rutas de vehículos con restricción de carga en dos dimensiones, denominado en la 1.6 Problemas de rutas de vehículos con restricción de carga en dos dimensiones. 45 literatura científica como Two-Dimensional Loading Capacitated Vehicle Routing Problem, (2L-CVRP). Se trata de un problema combinatorio complejo, que tiene su origen en la mezcla de otros dos problemas combinatorios NP-completos: •El problema de rutas de vehículos con capacidad limitada, Capacitated Vehicle Routing Problem (CVRP). •El problema de empaquetado o carga ortogonal en dos dimensiones, Two-Dimensional Orthogonal Packing Problem (2OPP). La introducción de la restricción de carga en dos dimensiones (2L), al problema original CVRP, aumenta la complejidad del problema, reduciendo el espacio de soluciones posibles, al tiempo que aumenta los costes de la solución, (Gendreau et al.,2008b). El problema resultante, 2L-CVRP, básicamente consiste en buscar un conjunto de rutas para la flota de vehículos, de tal forma que se minimice el coste de transporte, cumpliendo las restricciones del problema CVRP, descritas en el apartado 1.5.4, e incluyendo la restricción de carga con limitación en dos dimensiones. En esta variante del VRP, la demanda de los clientes se define como un conjunto de artículos con un peso asociado, así como un ancho y un largo establecido para cada uno de ellos. Es decir, que se trata de artículos con una forma rectangular, que no pueden ser apilados o colocados uno encima del otro, debido a su fragilidad, peso o dimensiones. Teniendo en cuenta que, los artículos asignados a los vehículos no pueden solaparse, ni sobrepasar las dimensiones, largo y ancho, de la superficie rectangular de carga del vehículo. Igualmente, hay que tener presente que, para satisfacer los supuestos del CVRP, todos los artículos solicitados por un mismo cliente deben ser cargados en el mismo vehículo, ya que de otro modo no sería posible completar el pedido del cliente con un solo vehículo. En la figura 1.6.1 se presenta un ejemplo ilustrativo de una solución a un problema rutas de vehículos con limitación de carga en dos dimensiones (2L-CVRP), compuesto por 22 52 Estado del arte. wi≤Wyhi≤H. Cada uno de los rectángulos debe ser situado ortogonalmente, es decir con sus lados paralelos a los lados de la plataforma de carga, esta restricción de carga es conocida en la literatura científica como orthogonal packing pattern. Otra restricción asociada a la carga es la denominada item clustering (Iori et al.,2007), en la cual todos los artículos de un mismo cliente deben estar colocados en el mismo vehículo. Esta condición es necesaria, ya que de lo contrario el cliente tendría que ser visitado por más de un vehículo (split delibery) lo cual incumple una de las restricciones del CVRP. Por lo tanto, el problema consistente en determinar si la carga asignada al vehículo, un conjunto de rectángulos, puede ser colocada dentro del mismo, sobre una superficie rectangular, cumpliendo las restricciones de carga impuestas. Este problema es conocido en investigación operativa como Two-Dimensional Orthogonal Packing Problem (2OPP). Este problema, es a su vez un subproblema de otras dos variantes del problema de empaquetado bidimensional, estas dos variantes son: •Two-Dimensional Bin Packing Problem (2BPP): Se trata de empaquetar un conjunto dado de elementos rectangulares, sin que se solapen, dentro del mínimo número de contenedores (bins), donde cada contenedor tiene el mismo tamaño W×H. En este caso, cuando el número de contenedores es igual a 1, estaríamos en el caso del 2OPP. •Two-Dimensional Strip Packing Problem (2SPP): En el cual se tiene una superficie de carga de ancho Wy longitud ilimitada (strip), y una serie de elementos rectangulares que deben colocarse sobre la superficie de carga, sin solapes y dentro del ancho Wde la misma. La optimización consiste en colocar todos los elementos rectangulares sobre la superficie, consumiendo la menor longitud posible de la plataforma. Para el caso del 2LCVRP, el problema consistiría en comprobar que los artículos a situar sobre la superficie de carga, que se obtiene de la solución propuesta por la parte de la ruta, no superen la longitud disponible del vehículo H, teniendo en cuenta el ancho W. 2.1 El problema de carga en dos dimensiones. 53 Existen algunos artículos que recopilan los trabajos publicados para cada una de estas variantes, entre ellos se pueden destacar los de Lodi et al. (2002) y más recientemente Lodi et al. (2014), para el caso del 2BPP, mientras que el artículo de Riff et al. (2009), hace una revisión del 2SPP. Desde el punto de vista del problema de rutas de vehículos con restricción de carga en dos dimensiones, existen otros conceptos que son relevantes, y que pueden conducir a una serie de restricciones en el patrón de carga de los vehículos, estos conceptos son: •Carga orientada (OL): En este concepto se considera que los rectángulos a cargar tienen una orientación fija, por lo tanto deben ser colocados siguiendo dicha orientación, sin permitir que su rotación. •Carga no orientada (RL): Es el caso contrario al anterior, por lo tanto si es posible rotar los artículos a cargar en ±90º, con lo cual cada rectángulo dispone de dos posibles formas de colocación sobre la plataforma de carga del vehículo. •Carga secuencial (SL): Es un tipo de restricción muy empleado en los problemas de rutas de vehículos con restricción de carga. En la bibliografía se pueden encontrar distintas denominaciones para este concepto, sequential loading, LIFO policy o rear loading son probablemente las más frecuentes. Supone una restricción relacionada con el orden en el que se distribuye la mercancía a los clientes, que depende a su vez del recorrido seleccionado. Es muy frecuente que los vehículos tengan accesible sólo uno de los lados del camión, normalmente la parte trasera, y no es posible o rentable reubicar la carga durante el trayecto. Por lo tanto, es necesario que los artículos solicitados por los clientes sean cargados en orden inverso al que se realiza la ruta de transporte, cargando en primer lugar los artículos del último cliente a visitar y en último lugar los artículos del primer cliente a visitar. Además esta carga debe ser tal que, la descarga de un artículo concreto de un cliente determinado nunca quede bloqueada por otro artículo de un 54 Estado del arte. cliente diferente. •Carga no restringida (UL): Al contrario que el caso secuencial, corresponde a un tipo de carga en el cual se permite reubicar los artículos durante la ruta, por lo tanto pueden ir colocados en cualquier orden sobre la superficie de carga, sin tener en cuenta la secuencia en la que se realiza la visita a los clientes, durante la ruta de transporte. A partir de los conceptos anteriormente expuestos, relativos a las restricciones de carga, y siguiendo la clasificación realizada por Fuellerer et al. (2009), se obtiene una tipología con cuatro posibles subclases para la configuración de carga en dos dimensiones: 1. Carga orientada secuencial (2|SO|L). 2. Carga orientada no restringida (2|UO|L). 3. Carga no orientada secuencial (2|SR|L). 4. Carga no orientada y no restringida (2|UR|L). Como consecuencia de esta clasificación, aparecen cuatro versiones del problema de rutas de vehículos en dos dimensiones, en función de las cuatro configuraciones de carga descritas anteriormente. Generalmente la mayor parte de los artículos que han tratado el problema 2LCVRP, han tratado las versiones con carga orientada, ya sea carga secuencial o no-restringida, es decir los casos 2|SO|L y 2|UO|L. Según lo expuesto anteriormente, para poder generar una solución completa al problema de rutas de vehículos con restricción de carga en dos dimensiones, se hace necesario chequear la viabilidad de la carga de los artículos sobre la plataforma del vehículo, considerando el peso y las dimensiones de los elementos a transportar. Para chequear la viabilidad de la carga sobre un vehículo, se suelen emplear varios métodos como, cotas inferiores, heurísticas específicas 2.1 El problema de carga en dos dimensiones. 55 o métodos exactos. En los siguientes apartados, se esbozan las características más importantes de cada uno de estos métodos. 2.1.2. Límites inferiores. En los límites inferiores o lower bounds, se calcula una cota inferior para la solución a un problema de carga en dos dimensiones del tipo 2BPP ó 2SPP, considerando el conjunto de rectángulos que vamos a tratar de colocar sobre la plataforma rectangular de carga del vehículo. De esta forma, se pueden descartar de entrada aquellas configuraciones de carga que tengan una cota inferior mayor a uno, para el caso del 2BPP, o superior a Hen el caso de considerar el problema 2SPP. La ventaja de usar un límite o cota inferior, está en la rapidez de cálculo, sin un consumo importante de recursos computacionales, y la posibilidad de descartar configuraciones de carga no factibles, lo que reduce el espacio de búsqueda de soluciones factibles. Algunos de los límites inferiores empleados en el chequeo de carga han sido los desarrollados por Martello y Vigo (1998), Martello et al. (2003)yCarlier et al. (2007) para carga orientada (OL), así como por Dell’Amico et al. (2002) para carga no orientada (UL). El lector interesado puede encontrar en el artículo de Boschetti y Montaletti (2010), una relación de los distintos tipos de límites inferiores para el problema 2SPP, mientras que Serairi y Haouari (2010) hace una recopilación de límites inferiores para el problema 2BPP. 2.1.3. Heurísticas y metaheurísticas aplicadas al chequeo de carga. Existen heurísticas específicas para el 2BPP y el 2SPP, que pueden ser empleadas para para comprobar la viabilidad de la configuración de carga en dos dimensiones (2OPP). Estas 56 Estado del arte. heurísticas pueden ser consideradas como límites o cotas superiores (upper bounds), ya que la solución obtenida siempre será mayor o igual a la óptima. En ocasiones se han empleado metaheurísticas que parten de una solución inicial calculada mediante una de las heurísticas mencionadas en el apartado anterior, para llegar a una solución mejorada. Principalmente se han empleado Algoritmos Genéticos (GA), aunque también se han usado la Búsqueda Tabú (TS) o Recocido Simulado (SA), véase por ejemplo el artículo publicado por Bortfeldt (2006). Para una revisión y comparativa de distintas heurísticas y metaheurísticas aplicadas al problema de empaquetado en dos dimensiones, es posible acudir a los trabajos de Hopper y Turton (2001a)yHopper y Turton (2001b). Generalmente a efectos de establecer un sistema de coordenadas que permita identificar la posición de los rectángulos sobre la superficie de almacenamiento, se parte de unos ejes cartesianos X−Y, donde el ancho de la plataforma de carga Wcoincide con el eje X, mientras que el borde lateral izquierdo coincide con el eje Y. De este modo el punto (0,0) corresponde con la esquina inferior-izquierda de la superficie de carga. En los siguientes apartados, se describen algunas de las heurísticas más conocidas y empleadas en los problemas de carga en dos dimensiones asociadas al 2L-CVRP. Sin embargo, existen muchas más heurísticas y variantes de las mismas. En el trabajo de Jylänki (2010), por ejemplo, se hace una recopilación y comparativa de las distintas heurísticas empleadas en la resolución del 2BPP. 2.1.3.1. Bottom-Left (BL). Introducida por Baker et al. (1980), es probablemente la heurística más conocida y una de las más empleadas hasta el momento. El algoritmo Bottom-Left (BL) utiliza como entradas el listado ordenado de los rectángu- 2.1 El problema de carga en dos dimensiones. 57 los a colocar sobre la superficie de almacenamiento, y coloca secuencialmente cada rectángulo sobre dicha superficie según el orden considerado. La estrategia de colocación sitúa primero el rectángulo en la posición superior-derecha de la superficie de carga y a continuación realiza movimientos sucesivos desplazando el rectángulo lo más abajo y a la izquierda posible. Un límite superior para este algoritmo respecto a los posibles patrones de carga, suponiendo un número nde rectángulos, y permitiendo su rotación, puede llegar a 2·n·n!, aunque en la práctica algunos de estos posibles patrones de carga son iguales (Jakobs,1996). La dificultad del problema es manifiesta, ya que la magnitud del espacio de búsqueda de este problema es mayor incluso a la del problema del viajante (TSP). Otra característica importante, es que si se ordena de mayor a menor ancho los rectángulos a colocar, donde el ancho wies paralelo al eje X, la longitud de plataforma obtenida al resolver el algoritmo, es menor o igual a 3 veces el valor óptimo de la longitud para el problema 2SPP. Se han realizado diferentes implementaciones del algoritmo base para mejorar su rendimiento, entre ellas destacan las de Jakobs (1996) y la de Liu y Teng (1999). Dichos artículos utilizan el Bottom-Left dentro de metaheurísticas basadas en algoritmos genéticos. El trabajo de Liu y Teng (1999) mejoró el algoritmo de Jakobs (1996), dando prioridad al movimiento descendente sobre el movimiento hacia la izquierda. Además, es importante señalar que, a diferencia del método de Jakobs (1996), este algoritmo asegura que para al menos una secuencia de ordenamiento de los rectángulos de todas las posibles, se puede llegar al óptimo. Este algoritmo tiene una complejidad de tiempo de orden O(N2). 2.1.3.2. Bottom-Left-Fill (BLF). Es una versión modificada de la heurística de colocación Bottom-Left. Esta heurística fue propuesta por primera vez por Chazelle (1983). Este algoritmo a diferencia del BL, almacena 58 Estado del arte. un listado con las posiciones posibles para el siguiente rectángulo a colocar, según un orden fondo-izquierda (Bottom-Left). Al colocar un nuevo rectángulo, el algoritmo trata de colocarlo en la posición más baja y a la izquierda disponible, y posteriormente comprueba si se produce algún solape con cualquier otro rectángulo colocado anteriormente. Si existe algún solape, se pasa a la siguiente posición disponible hasta que no exista ninguna superposición. Este algoritmo, a diferencia de BL, es capaz de llenar los huecos que se generan durante el proceso de carga con rectángulos que se colocan posteriormente debido a que mantiene las posiciones disponibles almacenadas. Es importante reseñar que tanto, BL como BLF son algoritmos que están influenciados de manera decisiva por la forma en la que se ordena la secuencia de rectángulos a colocar, y que para una misma secuencia de entrada siempre se obtiene el mismo resultado de configuración de carga. Según Hopper y Turton (2001a), BLF supera en rendimiento a BL hasta en un 25%, e incluso, si se ordenaba la secuencia de rectángulos según un ancho decreciente o un largo decreciente, el rendimiento de ambos algoritmos aumentaba hasta un 10% comparado con una ordenación aleatoria. Es importante destacar, que BLF tiene un orden de tiempo O(N3), superior por lo tanto a BL. Probablemente, Bottom-Left-Fill junto con Touching Perimeter Algorithm son los algoritmos más usados hasta el momento, como heurísticas de comprobación de carga en el problema 2L-CVRP. 2.1.3.3. Best Fit (BF). Esta heurística desarrollada por Burke et al. (2004), a diferencia de BL y BLF, no sigue un orden de colocación secuencial, por el contrario selecciona dinámicamente el próximo rectángulo a colocar que mejor se ajusta al espacio disponible que se encuentra más al fondo. De 2.1 El problema de carga en dos dimensiones. 59 esta forma no está influenciado por el orden de la secuencia de entrada de los rectángulos a colocar. Este algoritmo va dejando únicamente los huecos que no puede ir rellenando con los rectángulos disponibles, pero a diferencia de BLF, estos huecos que no pueden ser rellanados se pueden “olvidar”. Otra característica importante de Best Fit, respecto de BL y BLF, es que no requiere comprobar para cada rectángulo colocado las posibles superposiciones que se pudieran producir. Por todo lo anterior, este algoritmo obtiene generalmente mejores resultados que BL ó BLF, e incluso que algunas metaheurísticas. Una implementación mejorada del algoritmo Best Fit fue realizada por Imahori y Yagiura (2010), haciendo uso de árboles de búsqueda binarios y de estructuras especiales para el almacenamiento de la información, consiguiendo un orden de complejidad de tiempo O(n·logn) donde nes el número de rectángulos a colocar. 2.1.3.4. Touching Perimeter. Este heurística originalmente propuesta por Lodi et al. (1999), sitúa cada rectángulo en una posición factible que maximice la fracción del perímetro en contacto con otros rectángulos o con los bordes de la superficie de carga. Como se comentó anteriormente, este algoritmo y alguna de sus variantes han sido empleadas en diversas ocasiones como heurística para la comprobación de la viabilidad de la carga. 2.1.4. Métodos Exactos. Los métodos exactos han sido menos usados que los algoritmos heurísticos o metaheurísticos, para resolver el problema de carga ortogonal en dos dimensiones (2OPP), entre ellos destacan los de Clautiaux et al. (2007b), Fekete et al. (2007) y Côté et al. (2014). Con ellos se pueden obtener soluciones exactas, hasta un cierto tamaño de instancias, a costa de un mayor 60 Estado del arte. consumo de recursos computacionales. Generalmente se suelen usar los métodos de Ramificación y Acotamiento (Branch and Bound), o Ramificación y Corte (Branch and Cut), aunque en ocasiones se combinan con límites inferiores o métodos heurísticos, que se ejecutados primero, para reducir el esfuerzo de cálculo. En el caso del 2BPP, se han propuesto diferentes métodos exactos como, por ejemplo, en los artículos de Martello y Vigo (1998)yClautiaux et al. (2007a). También existen diversos trabajos realizados para el 2SPP, basados en métodos exactos, entre los que se encuentran los publicados por Kenmochi et al. (2009), donde se analizan las dos variantes con y sin rotación, así como Boschetti y Montaletti (2010). 2.2. El problema de rutas de vehículos con restricción de carga en dos dimensiones. En los últimos años, las nuevas variantes del problema de rutas de vehículos (VRP), que combinan restricciones clásicas con otras extraídas de casos reales, han atraído un creciente interés de la comunidad científica, en esta línea los trabajos de Caceres-Cruz et al. (2014) y Lahyani et al. (2015) recopilan muchos de los artículos publicados con un mayor énfasis en situaciones reales. Algunas de estas nuevas variantes incluyen incluso cuestiones ambientales, véanse por ejemplo los artículos de Bekta¸s y Laporte (2011), Demir et al. (2014) y Juan et al. (2014). Otras variantes han aparecido a partir de la inclusión de restricciones de carga, al problema básico o alguna de sus extensiones. En la publicación realizada por Wang et al. (2009), se hace un repaso a los principales trabajos sobre problemas de rutas de vehículos con restricciones de carga. También es posible encontrar una visión sistemática del problema VRP combinado con 2.2 El problema de rutas de vehículos con restricción de carga en dos dimensiones. 61 restricciones de carga, en el artículo de Iori y Martello (2010) Una de estas nuevas extensiones, con grandes posibilidades de aplicación práctica, es el problema ruta de vehículos con restricción de carga en dos dimensiones, conocido por las siglas 2L-CVRP. Esta nueva variante fue abordada por primera vez en Iori (2004), véase el apartado 1.6 para una introducción al 2L-CVRP. Posteriormente, Iori et al. (2007) publicaron el primer artículo sobre la materia, en el cual se propone un método exacto para resolver el problema. En este trabajo, se resuelve solamente el caso de la variante secuencial orientada (sin rotación), 2|SO|L, empleando el método de Ramificación y Corte (Branch-and-Cut) para minimizar el coste del problema de rutas considerando las restricciones de carga. Este método se apoya en una heurística constructiva específica, para mejorar el rendimiento global de la parte del algoritmo correspondiente a las rutas. Sin embargo, para resolver el problema de carga bidimensional (2OPP), se utilizan distintas herramientas, ejecutadas de forma secuencial, siguiendo un orden de menor a mayor consumo de recursos computacionales. En primer lugar se emplea una cota inferior (Martello y Vigo,1998), un límite superior mediante obtenido a partir de una heurística basada en el algoritmo bottom-left (BL), y si ambos límites no son efectivos para el chequeo de la carga, se ejecuta un método exacto del tipo Ramificación y Acotamiento (Branch-and-Bound). En este mismo trabajo se propusieron un conjunto de instancias a resolver para el 2LCVRP, a partir de instancias clásicas del CVRP. Además se definieron 5 clases, en función de la forma en la que se generan los artículos asociados con cada cliente, véase tabla 2.1. La clase 1, está compuesta únicamente por artículos con forma de cuadrado de lado 1. Para el resto de clases se crearon tres tipos de formas, cada una de ellas dispone de un rango de posibles valores para el ancho y el largo. A cada artículo individual de las clases 2 a 5, se le asignó uno de los tres tipos de forma, cada uno de ellos con la misma probabilidad. Una vez escogida la tipología, se generan las dimensiones del artículo en cuestión, tomando un 68 Estado del arte. estudiado. En el estudio realizado por Baldacci et al. (2008) se propone una clasificación de estos problemas de acuerdo con el número de vehículos disponibles, ya sea limitado (HVRP) o ilimitado (FSM), y los costes considerados por tipo de vehículo, fijos (F), variables (D), o ambos (FD). Salhi y Osman (1996) y Ochi et al. (1998a,b) propusieron un algoritmo de Búsqueda Tabú (TS) y Búsqueda Dispersa (Scatter Search), respectivamente, para resolver el problema FSM-F. La Búsqueda Tabú también es utilizada por Lee et al. (2008)yGendreau et al. (1999), para resolver las versiones del problema de flota heterogénea FSM-D y FSM-F. En cuanto a la versión FSM-FD, en Lima et al. (2004) se describe un algoritmo de tipo memético que permite abordar este problema, mientras que Liu et al. (2009) propusieron un algoritmo genético para esta misma variante. Con respecto a la versión con un número limitado de vehículos, en el trabajo de Gendreau et al. (1999) se emplea un algoritmo de Búsqueda Tabú, con diferentes costes variables para cada tipo de vehículo. En Taillard (1999) se utiliza una heurística basada en la Generación de Columnas y en la Búsqueda Tabú. La versión HVRP-D, fue abordada por Tarantilis y Kiranoudis (2002) mediante una metodología denominada Backtracking Adaptive Threshold Accepting (BATA). Tarantilis et al. (2003) resuelven el problema HVRP-D, haciendo uso de un algoritmo de umbrales de aceptación basado en listas, en el cual solo se acepta un empeoramiento de la solución si está dentro de un determinado umbral de aceptación. Posteriormente, en Tarantilis y Kiranoudis (2007) se presenta un algoritmo de dos fases llamado GEROCA (GEneralized ROute Construction Algorithm), que incluye una memoria de adaptación flexible, y que se aplica en dos casos reales modelados como un problema HVRP-FD. Finalmente, Tarantilis et al. (2008) utilizaron una Búsqueda Tabú Guiada (GTS), para solventar el problema de flota heterogénea con un número limitado de vehículos. También se han usado métodos exactos, como los propuestos por Baldacci y Mingozzi (2009), empleando un algoritmo basado en el problema de partición de conjuntos (Set- 2.3 Problema de rutas de vehículos con restricción de carga en dos dimensiones y flota de vehículos heterogénea. 69 Partitioning), y Pessoa et al. (2009) usando un algoritmo basado en el método de ramificación y corte con generación de columnas, Branch-Cut-and-Price (BCP). En la literatura científica también se han abordado otras variantes del VRP con flota heterogénea. Por ejemplo, existen extensiones del VRP con flota heterogénea que incluyen: ventanas de tiempo (Liu y Shen,1999), múltiples depósitos (Salhi y Sari,1997), incertidumbre en la demanda de los clientes (Couillard y Martel,1990), subcontratación del transporte (Bolduc et al.,2007), viajes múltiples (Prins,2002), etc. El problema de rutas de vehículos asimétrico con flota de vehículos heterogénea, Asymmetric and Heterogeneous Vehicle Routing Problem (AHVRP), es otra de las extensiones en la cual se consideran los costes asociados a distancias asimétricas entre los distintos nodos del problema. Recientemente, Herrero et al. (2014) propusieron una metodología híbrida para resolver el problema AHVRP. Su método combina una versión probabilista de una heurística clásica basada en el criterio del ahorro con algunas búsquedas locales, específicamente adaptadas para manejar los costes asociados a distancias asimétricas. En algunas obras que tratan sobre las extensiones del VRP con flota heterogénea, los costes variables y fijos son ignorados (Oppen et al.,2010;Rieck y Zimmermann,2010;Vallejo et al.,2012). Sin embargo, también hay otros estudios que incluyen modelos de costes avanzados. Así, por ejemplo, Tavakkoli-Moghaddam et al. (2007) asumen que los costes dependen del número de vehículos usados, así como de la capacidad total no utilizada. Por último, se pueden encontrar dos excelentes trabajos de recopilación sobre el VRP con flota heterogénea, en Baldacci et al. (2008) y Hoff et al. (2010). Del mismo modo, algunas aplicaciones reales del VRP con flota heterogénea se ilustran en Golden et al. (2001). 70 Estado del arte. 2.4. Problema de rutas de vehículos con restricción de carga en dos dimensiones incluyendo la entrega y recogida agrupadas. Se trata de una nueva extensión del problema de rutas de vehículos, que hasta el momento presente no ha sido resuelta en la literatura científica. El problema de rutas de vehículos con restricción de carga en dos dimensiones incluyendo la entrega y recogida agrupada, que denominaremos de ahora en adelante con las siglas 2L-VRPB, integra dos problemas de optimización combinatoria: El problema de rutas de vehículos con restricción de carga en dos dimensiones (2L-CVRP) y el problema de rutas de vehículos con entrega y recogida agrupadas, Vehicle Routing Problem with Backhaul (VRPB). En relación a este problema, sólo existe un estudio teórico previo, realizado por Malapert et al. (2008), donde se analizaba la combinación de ambos problemas. Dichos autores proponían un modelo de programación de restricciones, que integra componentes tanto de la ruta como de la carga, basado en un enfoque de planificación. Sin embargo, este modelo no permite la rotación de los artículos durante la etapa de carga. Por otra parte, los autores no reportan ningún resultado computacional, ni proponen ninguna instancia a resolver. Tanto el VRPB como el 2L-CVRP han recibido mucha más atención por separado. Se han propuesto varios métodos exactos y heurísticos para resolver el VRPCB. El trabajo de Parragh et al. (2008) proporciona un estudio exhaustivo sobre los distintos enfoques que se han desarrollado para hacer frente a las variantes del problema general de recogida y entrega, Pickup and Delibery Problem (PDP), donde se incluye el problema VRPB como uno de sus cuatro sub-tipos. Los métodos exactos realizan una búsqueda sistemática a lo largo del espacio de solu- 2.4 Problema de rutas de vehículos con restricción de carga en dos dimensiones incluyendo la entrega y recogida agrupadas. 71 ciones, devolviendo la mejor solución posible. Sin embargo, requieren elevados tiempos de ejecución, por lo que su aplicación suele estar relegada a las instancias de menor tamaño. El primer método exacto empleado en la resolución del VRPB, fue introducido por Yano et al. (1987). Los autores desarrollan un algoritmo de Ramificación y Acotamiento basado en un problema de cubrimiento de conjuntos, desarrollado para la logística de una cadena de tiendas. En la solución se planifican rutas óptimas con hasta cuatro clientes con entrega de mercancía (linehaul), y cuatro clientes con recogida de mercancía (backhaul), por ruta. Nuevamente se emplea un algoritmo de Ramificación y Acotamiento en el trabajo realizado por Toth y Vigo (1997), en el que además se utilizan diferentes relajaciones para calcular cotas inferiores. Estos límites inferiores son ajustados progresivamente mediante el uso de planos de corte. El algoritmo desarrollado genera soluciones óptimas a la mayoría de las instancias de referencia para el VRPB (Goetschalckx y Jacobs-Blecha,1989;Toth y Vigo,1996). En el estudio de Mingozzi et al. (1999) se propone una formulación de programación lineal y se desarrolla también un algoritmo Ramificación y Acotamiento. Además se resuelve el problema en forma reducida. El método empleado fue capaz de resolver de forma óptima las instancias propuestas, llegando hasta casos con 100 clientes. El primer enfoque heurístico para resolver el VRPB fue propuesto por Deif y Bodin (1984). En este trabajo, los autores desarrollaban una extensión de la heurística clásica basada en ahorros de Clarke y Wright (1964), lo que les permitía resolver instancias de hasta 300 clientes. En la obra de Goetschalckx y Jacobs-Blecha (1989), se desarrolla una heurística de dos fases. En su método, tanto la fase de agrupamiento como la fase de creación de rutas se resuelven haciendo uso de un enfoque de curvas de llenado del espacio (Space-Filling Curves). Toth y Vigo (1996) propusieron y posteriormente extendieron Toth y Vigo (1999) un algoritmo del tipo primero agrupar y segundo generar rutas. Los autores desarrollaban un método de agrupación que extrae la información contenida dentro de una solución de un VRPB relajado, seguido de un procedimiento de búsqueda de coincidencias e inserción entre las agrupaciones, 72 Estado del arte. junto con una fase de mejora dentro de cada ruta. En cuanto a las metaheurísticas, en la literatura científica existen muchos ejemplos de implementación para el VRPB. El primer enfoque metaheurístico fue propuesto por Potvin et al. (1996). Su algoritmo está basado en un Algoritmo Genético (GA) combinado con una heurística de construcción de rutas, en la cual los clientes primero se ordenan y después se van añadiendo a las rutas en la mejor posición disponible. Osman y Wassan (2002) propusieron una Búsqueda Tabú Reactiva en la que los períodos tabú se ajustan dinámicamente para controlar las fases de diversificación e intensificación. Más tarde, Wassan (2007) combina una Búsqueda Tabú Reactiva con una memoria adaptativa, lo que garantiza una convergencia más rápida. El autor presentó un buen número de nuevas mejores soluciones para varias las instancias de referencia. Otra metaheurística empleada en la resolución del CVRPB, es la Búsqueda Tabú de Múltiples Fases, desarrollada por Brandão (2006). El autor aplica dos procedimientos para obtener la solución inicial, el primero basado en la resolución de dos problemas VRP abiertos, uno para los clientes que requieren entrega y otro para los que requieren recogida, en tanto que el segundo método basado en límites inferiores del problema VRP. Este último autor utilizó una estrategia estática, mientras que Osman y Wassan (2002) y Wassan (2007) utilizaron una estrategia dinámica que se adaptaba en función de la eficacia de la búsqueda. Otro estudio de interés, es el realizado por Ropke y Pisinger (2006), en dicho artículo se presenta un modelo unificado para la solución de muchas variantes del VRP, incluyendo el VRPB. Transforman estas diferentes variantes en un problema de entrega y recogida enriquecido con ventanas de tiempo (Rich PDPTW), que luego se resuelve por medio de un algoritmo de Búsqueda en Entornos Amplios (LNS) mejorado con mecanismos de aprendizaje. La metaheurística basada en Colonia de Hormigas, es usada por Gajpal y Abad (2009), empleando un sistema con dos tipos de hormigas: el primer tipo es utilizado para asignar a los clientes a los vehículos y el segundo tipo para resolver el problema de generación de rutas. En Zachariadis y Kiranoudis (2012) se presenta una metaheurística de búsqueda local que explora entornos compuestos 2.4 Problema de rutas de vehículos con restricción de carga en dos dimensiones incluyendo la entrega y recogida agrupadas. 73 creados a partir de intercambios de longitud variable en la secuencia de los clientes. Los autores introdujeron el concepto de “prometedor” para diversificar la búsqueda y escapar de mínimos locales. En cada iteración, las secuencias de los clientes que aparecen en la solución, son marcadas con un valor que refleja lo prometedoras que resultan respecto al coste de la solución. Estos valores prometedores se utilizan para descartar movimientos de baja calidad que implican las mismas secuencias para los clientes. Cuervo et al. (2014) emplearon un algoritmo de Búsqueda Local Iterativa (ILS) con una heurística de búsqueda local oscilante, que explora una amplia estructura del entorno en cada iteración y permite transiciones entre las regiones factibles y no factibles del espacio de soluciones. Finalmente, García-Nájera et al. (2015) presentaron un enfoque evolutivo multi-objetivo para hacer frente al VRPB. Los autores definieron el número de vehículos, el costo total del viaje, y el número de viajes de regreso sin recogida de mercancía, como los objetivos a minimizadas en su propuesta. Además, utilizaron un proceso de selección basado en la similitud de un VRPB específico para generar un conjunto de soluciones que proporcionen un mejor equilibrio entre todas las posibilidades. Capítulo 3 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. 3.1. Introducción. En este trabajo se propone un algoritmo eficiente, con un número reducido de parámetros, para resolver el problema de rutas de vehículos con restricción de carga en 2 dimensiones (2L-CVRP). Este problema combina dos de los problemas más importantes en logística, es decir, la generación óptima de rutas de vehículos y el problema de optimización de la carga del vehículo. Este algoritmo contempla carga no restringida (no secuencial), incluyendo la posibilidad de aplicar rotaciones de 90º a los artículos, mientras se realiza la carga del vehículo, que es una hipótesis realista raramente considerada en la literatura existente. El algoritmo utiliza un enfoque multi-arranque, que está diseñado para evitar que el algoritmo quede atrapado en mínimos locales. En cada reinicio, se emplea una metodología basada en una asignación de probabilidad sesgada aplicada sobre una heurística clásica de generación de rutas de vehículos, así como sobre un algoritmo efectivo de empaquetado bidimensional, para producir soluciones 76 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. factibles pseudo-óptimas para el 2L-CVRP. El algoritmo propuesto ha sido probado en instancias clásicas para dos configuraciones de carga del 2L-CVRP, es decir, con y sin posibilidad de rotación de los artículos. Los resultados experimentales muestran que el algoritmo propuesto mejora algunas de las mejores soluciones conocidas obtenidas en trabajos anteriores, tanto en calidad como en recursos computacionales. 3.2. Formulación del problema. Ya que el 2L-CVRP combina un problema de rutas de vehículos con un problema de carga del vehículo, su formulación incluirá restricciones de ambos problemas de investigación. Por lo tanto, como un problema de rutas de vehículo con capacidad limitada (CVRP), el 2LCVRP asume la existencia de una flota de vehículos homogénea situados inicialmente en un depósito o almacén central. Estos vehículos deben distribuir un conjunto de artículos, con el fin de satisfacer la demanda de los clientes. Luego, el objetivo principal es encontrar una planificación de rutas factible, que minimice los costes de distribución, sin violar ninguna de las restricciones de la ruta, a saber: a) Cada cliente recibe la visita de un solo vehículo, que satisface su demanda total. b) Cada vehículo comienza y termina su recorrido en el depósito (rutas cerradas). c) La demanda total cubierta por un vehículo no supera su capacidad máxima, en peso y dimensiones de carga. En la extensa literatura existente sobre el CVRP, es posible encontrar diferentes modelos matemáticos para este problema, véase por ejemplo Toth y Vigo (2001) y Golden et al. (2008). A continuación, se presenta una formulación basada en la Programación Lineal Entera (PLE) que adapta los modelos presentados en las obras mencionadas, para el caso del 2L-CVRP. Se 3.2 Formulación del problema. 77 considera un grafo completo no dirigido G= (N,E), donde: •N={0,1,...,n}, es un conjunto de n+1 nodos, representando el depósito central (nodo 0) y los nclientes a los que se debe suministrar (nodos 1 a n). •E={(i,j)|i,j∈N con i =j}es un conjunto de arcos que conectan los nodos iyj. •Para todos los i,j∈N con i =j,ci j =cji >0 son los costes asociados con el transporte entre cualquier par de nodos. Nótese por lo tanto, que los costes de transporte se consideran simétricos. •Para cada cliente i(i∈N con i >0),mi≥0 es el número de artículos solicitados por el cliente i. •Para cada artículo l(1≤l≤mi),dil representa el peso del artículo lsolicitado por el cliente i. De tal modo que, el peso total (demanda) asociada con cada cliente ipuede ser expresada como di, donde di= mi ∑dil l=1. •Se dispone de una flota de K>1 vehículos con idénticas características (flota homogénea). •El número real D>0, representa la máxima capacidad de carga (peso útil a transportar) de cada vehículo. •La variable binaria zi jk toma el valor 1 si el vehículo kes usado para ir del nodo ial nodo j, mientras que es igual a 0 en caso contrario. De esta forma, el problema de rutas de vehículos se puede expresar como: Función objetivo: Minimizar :∑ (i,j)∈E ci j K ∑ k=1 zi jk (3.2.1) 84 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. diferentes. Si, y sólo si, estas dos rutas se pueden combinar sin violar ninguna de las restricciones del problema, entonces se lleva a cabo la fusión de ambas rutas. Con el fin de comprobar la viabilidad de la carga en el camión, el algoritmo emplea nuevamente un método del tipo multi-arranque combinado con una versión modificada de la heurística Best-Fit (Burke et al., 2004), mediante la asignación de una probabilidad asimétrica en el orden de colocación de los artículos durante la carga. Este proceso de aleatoriedad sesgada es similar al anterior. En este caso, sin embargo, la aleatoriedad sesgada se aplica sobre la lista de elementos a cargar. Una vez más, se emplea una distribución geométrica con un solo parámetro, β(0<β<1). Un nuevo parámetro, (maxPackIter), controla el número máximo de veces que la heurística BestFit modificada se ejecutará antes de asumir que los artículos no se pueden cargar en un único vehículo, sin incumplir con las restricciones de carga, con lo cual no será posible combinar las dos rutas propuestas. Cuando se termina con el listado completo de arcos, generalmente, se dispone de una nueva solución factible. Dicha solución puede ser mejorada, mediante el uso de las técnicas de memoria caché y división del problema original en subproblemas, según se describe en Juan et al. (2011). La técnica de la memoria caché es un proceso de búsqueda local rápida que compara cada una de las rutas de la solución actual, con las mejores rutas obtenidas anteriormente, y sustituye las rutas actuales por otras que contienen los mismos clientes pero con un coste menor. La técnica de división del problema en subproblemas, constituye un proceso de local-búsqueda aún más interesante. Esta estrategia sigue la máxima de divide y vencerás, realizando de forma secuencial básicamente los siguientes pasos: 1. A partir de la nueva solución obtenida, se divide el problema original en diferentes subproblemas disjuntos. Para seleccionar el conjunto de clientes y vehículos que formarán parte de cada subproblema, se elige un conjunto de rutas de acuerdo con algunas reglas de proximidad geométrica. Para cada una de estos subproblemas, se disuelven las rutas 3.4 Pseudocódigo del algoritmo MS-BR. 85 asociadas y se extraen los clientes y vehículos asociados, para construir los datos de entrada en el nuevo subproblema 2L-CVRP. 2. Comienza un proceso iterativo en el que se repite, para cada subproblema, la metodología mencionada anteriormente para el problema principal, durante un número de iteraciones controlado por el parámetro denominado (maxSplitIter), con el fin de obtener una solución “local” mejorada del subproblema correspondiente. 3. Finalmente, se unen todas las soluciones "locales" en una nueva solución "global" mejorada. 3.4. Pseudocódigo del algoritmo MS-BR. En esta sección se presenta una descripción con mayor detalle del algoritmo propuesto. El algoritmo 3.1 muestra el pseudo-código correspondiente al procedimiento principal MultiStart-BiasedRand (MS-BR). Este procedimiento requiere, al menos, cuatro parámetros, según lo especificado en el apartado anterior: •Dos están relacionados con las distribuciones de probabilidad, el primero, α, está asociado a la distribución geométrica empleada durante el proceso de asignación de probabilidad asimétrica a la lista de arcos. Mientras que el segundo, β, está asociado a la distribución geométrica utilizada durante el proceso asignación de probabilidad sesgada a la lista de artículos a cargar. •Los otros dos están relacionados con el control del flujo del algoritmo, uno de ellos, (maxPackIter), limita el número máximo de intentos realizados por el procedimiento encargado de comprobar la viabilidad de la carga. En tanto que, el otro, (maxSplitIter), 86 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. controla el número iteraciones que se ejecutará el procedimiento de división y resolución de subproblemas. El algoritmo, como es lógico, también requiere de los datos de entrada (inputs): Las coordenadas cartesianas de cada nodo (clientes y depósito) o, en su defecto, la matriz de costes de transporte entre nodos, las demandas de los clientes, la capacidad máxima del vehículo, las dimensiones del vehículo, así como las dimensiones de cada artículo de forma rectangular. En primer lugar, siguiendo la lógica de la heurística basada en ahorros de Clarke y Wright (1964), el procedimiento genera lista de arcos y ahorros correspondientes, así como una solución trivial (líneas 1 y 2). Esta solución trivial se obtiene asignando, a cada cliente una ruta de ida y vuelta desde el depósito al susodicho cliente. A continuación, se construye una solución de referencia utilizando el procedimiento packAndRoute (línea 3), el cual básicamente combina la heurística clásica basada en ahorros y la conocida heurística de empaquetado Best-Fit, con la metodología basada en la asignación de probabilidad asimétrica. Tras lo cual, se inicia un proceso multi-arranque (líneas 5-15). Este proceso multi-arranque es particularmente útil por dos razones: (i) que permite que el algoritmo escape de mínimos locales; y (ii) facilita una posible ejecución en paralelo del algoritmo aleatorio. De hecho, el algoritmo puede ser ejecutado en paralelo, asignando a cada ejecución una semilla diferente obtenida a partir del generador de números pseudo-aleatorios. Estas ejecuciones se pueden implementar sobre varios hilos, núcleos o equipos. En cada iteración del proceso multi-arranque, se obtiene una nueva solución factible (línea 7). Esta nueva solución es proporcionada por el procedimiento packAndRoute, tras la ordenación al azar de la lista de arcos basada en una distribución de probabilidad asimétrica positiva, en función del ahorro que se obtiene con cada arco (línea 6). A continuación, se aplica un proceso de búsqueda local basada en una memoria rápida (línea 8). Esta búsqueda local intenta actualizar cada ruta en la nueva solución, mediante una ruta mejor que cubre el mismo conjunto de nodos y fue obtenida en iteraciones anteriores. Por otra parte, si la solución se puede considerar como “prometedora”, se aplica otro procedimiento de 3.4 Pseudocódigo del algoritmo MS-BR. 87 Algoritmo 3.1 Pseudo-código del procedimiento principal del algoritmo MSBR. procedure MultiStart-BiasedRand(inputs, α , β , maxPackIter, maxSplitIter) 01 dummySol <- calcDummySol(inputs) % generar una solución trivial 02 savings <- calcSortedSavingsList(inputs) % calcular la lista de arcos orden(ahorros) 03 cwsSol <- packAndRoute(dummySol, savings, β , maxPackIter, inputs) % solución referencia 04 bestSol <- cwsSol 05 while {condición final no alcanzada} do % tiempo o límite de iteraciones 06 randSavings <- biasedRand(savings, α )% nuevo orden aleatorio sesgado 07 newSol <- packAndRoute(dummySol, randSavings, β , maxPackIter, inputs) % nueva sol. aleat. 08 newSol <- cache(newSol) % búsqueda local mediante memoria-caché 09 if {newSol es una 'sol prometedora'} then % p.ej. cost(newSol) < cost(cwsSol) % búsqueda local mediante división en subproblemas 10 newSol <- splitting(newSol, α , inputs, maxSplitIter) 11 end if 12 if {cost(newSol) < cost(bestSol)} then 13 bestSol <- newSol 14 end if 15 end while 16 return bestSol end procedure búsqueda local, que se describe más adelante con mayor detalle. Este procedimiento se basa en estrategias de división en problemas de menor tamaño más fáciles de abordar (líneas 9-11). Si la nueva solución, reduce el coste de la mejor solución obtenida hasta el momento, entonces se guarda esta última solución como la mejor (líneas 12-14). Finalmente, el algoritmo devolverá la mejor solución encontrada (línea 15), hasta alcanzar la condición limite, generalmente un tiempo máximo (línea 5). Uno de los elementos clave en el algoritmo propuesto es la generación de nuevas soluciones con cierta aleatoriedad, teniendo como objetivo la minimización del coste total cumpliendo las restricciones de capacidad y dimensiones de la carga. Los detalles de este proceso constructivo se pueden encontrar en el pseudo-código incluido en el algoritmo 3.2. Usando la solución trivial inicial como punto de partida, comienza un proceso constructivo de combinación de rutas (líneas 2-16). En este proceso, los nuevos arcos son seleccionados de la lista de arcos previamente ordenados al azar, mediante una asignación de probabilidad sesgada en función de los ahorros. Tras lo cual, las rutas asociadas a cada arco seleccionado se combinarán siempre que sea posible, (líneas 8-15), es decir, si no se incumple ninguna restricción, especialmente las correspondientes a la carga. Téngase en cuenta que es posible emplear cual- 88 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. Algoritmo 3.2 Pseudo-código del procedimiento para generar nuevas soluciones aleatorias factibles. procedure packAndRoute(dummySol, randSavings, β , maxPackIter, inputs) 01 newSol <- dummySol 02 while {savings list is not empty} do 03 nextEdge <- extractNextEdge(randSavings) 04 iR <- getRoute(origin(nextEdge)) 05 jR <- getRoute(end(nextEdge)) 06 newRoute <- merge(iR, jR) 07 demand <- calcDemand(newRoute) % aquí la demanda es calculada en términos de peso 08 if {demand <= vehicleCapacity} then 09 if {routeRectanglesArea < vehicleLoadingSurface} then % Aplicar Best-Fit con rotación de artículos 10 reqLength <- bestFit(routeRectangles, β , maxPackIter, vehWidth, vehLength) 11 if {reqLength <= vehLength} then 12 newSol <- updateRoute(iR, jR, newRoute) 13 end if 14 end if 15 end if 16 end while 17 return newSol end procedure quier algoritmo eficiente de empaquetado bidimensional en la línea 10, con el fin de verificar la viabilidad de la carga en el vehículo (líneas 11-13). Como resultado, al final de cada proceso constructivo, se obtiene una solución factible generada con cierta aleatoriedad (línea 17). Por supuesto, la calidad de la solución aleatoria obtenida depende del modo en el cual han sido seleccionados los arcos, es decir, del tipo de criterio y probabilidad empleado. Aquí es donde las distribuciones de probabilidad asimétricas positivas, como por ejemplo la distribución geométrica, pueden ser muy útiles. En otras palabras, si se empleara una distribución de probabilidad uniforme en lugar de una distribución de probabilidad geométrica, los resultados obtenidos no serían competitivos en absoluto, ya que la lógica que sustenta la heurística original se perdería. Procedimiento para la búsqueda local mediante división en subproblemas, algoritmo 3.3 es otra herramienta valiosa para la mejora de las soluciones obtenidas. En términos generales, dada una nueva solución factible, se divide dicha solución en varias subsoluciones disjuntas, mediante la selección de distintos conjuntos de rutas. A continuación, se obtienen los subproblemas asociados a las subsoluciones seleccionadas, extrayendo los datos de entrada asociados a cada subsolución. Estos subproblemas, se vuelven a resolver de forma individual siguien- 3.5 Experimentos computacionales. 89 do la misma metodología descrita anteriormente, basada en la modificación de las heurísticas mencionadas anteriormente mediante la asignación de probabilidad sesgada durante el procedimiento constructivo de las soluciones. Este enfoque se beneficia en gran medida de dos hechos: •Debido a su naturaleza combinatoria, una reducción del tamaño, facilita la optimización de los subproblemas respecto del problema completo original. •La mejora de cualquiera de las subsoluciones disjuntas mejorará la solución global. En particular, como se discute en Juan et al. (2011), existe una amplia variedad de políticas basadas en las propiedades geométricas del problema, que pueden ser utilizadas para dividir el problema global original en subproblemas disjuntos. Hay que tener en cuenta que si las distancias entre un grupo de rutas son relativamente pequeñas, entonces algunos de los nodos en estas rutas pueden ser transferidos de una ruta a otra sin un incremento significativo de los costes de transporte. En consecuencia, la idea principal es simple: utilizar la solución factible actual para agrupar rutas que están relativamente próximas en el plano euclideo. Así, por ejemplo, una política de división Norte-Sur podría resumirse como: (a) Considerar el centro geométrico del problema, (x0,y0), así como el centro geométrico asociado a cada ruta i, (xi,yi); y a continuación, (b) dividir las rutas en dos grupos, los que tienen xi≥x0(rutas Norte) y aquellos con xi<x0(rutas Sur). De manera similar, otras políticas se pueden definir, como por ejemplo, entre Este y Oeste, NE-NO-SE-SO, etc. 3.5. Experimentos computacionales. El algoritmo descrito anteriormente ha sido implementado como una aplicación Java. En el núcleo de esta implementación, se incluyó la biblioteca SSJ proporcionada en L’Ecuyer et al. 90 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. Algoritmo 3.3 Pseudo-código del procedimiento para la búsqueda local mediante división en subproblemas. procedure splitting(newSol, α , inputs, maxSplitIter) 01 globalSol <- empty 02 subSols <- split(newSol) % dividir la nueva solución en subsoluciones disjuntas 03 for each {sol in subSols} do 04 bestSol <- sol 05 inputs <- getInputs(sol) % datos de entrada del nuevo subproblema 06 dummySol <- calcDummySol(inputs) % generar una solución trivial 07 savings <- calcSortedSavingsList(inputs) % calcular la lista de arcos 08 iter <- 1 09 while {iter <= maxSplitIter} do 10 randSavings <- biasedRand(savings, α )% nuevo orden aleatorio sesgado 11 newSol <- packAndRoute(dummySol, randSavings, inputs) % nueva sol. aleat. 12 newSol <- cache(newSol) % búsqueda local mediante memoria-caché 13 if {cost(newSol) < cost(bestSol)} then 14 bestSol <- newSol 15 end if 16 iter <- iter + 1 17 end while 18 globalSol <- add(bestSol, globalSol) 19 end for 20 return globalSol end procedure (2002) y, en particular, el generador de números pseudo-aleatorios LFSR113. Para realizar la pruebas experimentales y obtener los resultados que se presentan en este apartado, se utilizó un ordenador portátil Intel®Core™ 2 Duo a 2,4 GHz y 4 GB de RAM, haciendo uso de un solo núcleo. Mientras que la plataforma de desarrollo empleada fue Netbeans, sobre un sistema operativo Windows 7. Con el fin de comparar la bondad del algoritmo propuesto para las dos configuraciones de carga no restringidas, 2|UO|L y 2|UR|L, se seleccionaron algunas de las instancias de referencia clásicas del 2L-CVRP, propuestas en la literatura1. En el caso de la configuración de carga no orientada y no restringida, 2|UR|L, se ensayaron todas las instancias y clases. En tanto que, en el caso de carga orientada y no restringida, 2|UO|L, un subconjunto de instancias del conjunto completo fueron seleccionadas al azar. Estas instancias de referencia consideran la existencia de una flota de vehículos homogénea y limitada, cada uno de ellos dispone de una superficie de carga de 40×20 unidades cuadradas y tiene una capacidad máxima de peso específica. Cada cliente tiene una demanda que consiste en un conjunto de artículos bidimen1Estas instancias están accesibles en la web: www.or.deis.unibo.it/research.html 3.5 Experimentos computacionales. 91 sionales y forma rectangular, con unas medidas y pesos concretos. Por otra parte, para cada una de estas instancias se consideran cinco clases diferentes de tipología de artículos. Como se describe en Iori et al. (2007)yGendreau et al. (2008b), estas clases se diferencian por el número y tamaño de sus artículos, en la tabla 2.1 se describen en mayor detalle las características más importantes de cada clase. En la tabla 3.1 se presentan las principales características de las instancias de referencia que van a ser ensayadas. Hay que tener en cuenta que la clase 1 es realmente un problema CVRP, ya que cada cliente demanda un sólo artículo de dimensiones 1×1, por lo que el problema no se ve afectado por las limitaciones de carga. Para cada combinación de instancia y clase, se lanzaron diez réplicas independientes, utilizando una semilla diferente en el generador de números pseudo-aleatorios. 3.5.1. Ensayos para el 2L-CVRP con rotación de los artículos. En este caso se resuelven las instancias considerando una configuración de carga no orientada y no restringida (2|UR|L). Es decir, se permite la rotación de los artículos durante el proceso de carga, y no se considera la restricción secuencial en el orden de colocación de los artículos. Para cada instancia y clase, se registra tanto la mejor solución encontrada en las 10 réplicas ensayadas (BEST10), así como el valor medio de las soluciones generadas (AVG10). Estos valores BEST10 y AVG10 se compararon con los resultados obtenidos con el algoritmo de Optimización de Colonia de Hormigas (ACO) desarrollado por Fuellerer et al. (2009), ya que, hasta donde alcanza nuestro conocimiento, es el único artículo publicado hasta el momento que contempla la configuración de carga con posibilidad de rotación de los artículos. En dicho trabajo los autores también realizaron 10 ensayos por instancia y clase utilizando un tiempo máximo de 3 horas para cada réplica. En el caso de nuestros ensayos, sin embargo, cada réplica se ejecutó durante un tiempo máximo de 500 segundos. El algoritmo ACO fue codificado en C++, y todas sus ensayos se realizaron en un Pentium®4 a 3,2 GHz bajo el 92 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. Núm. Nº Clientes Clase 1 Clase 2 Clase 3 Clase 4 Clase 5 Instancia Nº Art. Nº Veh. Nº Art. Nº Veh. Nº Art. Nº Veh. Nº Art. Nº Veh. Nº Art. Nº Veh. 1 15 15 3 24 3 31 3 37 4 45 4 2 15 15 5 25 5 31 5 40 5 48 5 3 20 20 4 29 5 46 5 44 5 49 5 4 20 20 6 32 6 43 6 50 6 62 6 5 21 21 4 31 4 37 4 41 4 57 5 6 21 21 6 33 6 40 6 57 6 56 6 7 22 22 3 32 5 41 5 51 5 55 6 8 22 22 5 29 5 42 5 48 5 52 6 9 25 25 8 40 8 61 8 63 8 91 8 10 29 29 3 43 6 49 6 72 7 86 7 11 29 29 4 43 6 62 7 74 7 91 7 12 30 30 9 50 9 56 9 82 9 101 9 13 32 32 3 44 7 56 7 78 7 102 8 14 32 32 4 47 7 57 7 65 7 87 8 15 32 32 5 48 6 59 6 84 8 114 8 16 35 35 11 56 11 74 11 93 11 114 11 17 40 40 14 60 14 73 14 96 14 127 14 18 44 44 4 66 9 87 10 112 10 122 10 19 50 50 5 82 11 103 11 134 12 157 12 20 71 71 4 104 14 151 15 178 16 226 16 21 75 75 7 114 14 164 17 168 17 202 17 22 75 75 8 112 15 154 16 198 17 236 17 23 75 75 10 112 14 155 16 179 16 225 16 24 75 75 14 124 17 152 17 195 17 215 17 25 100 100 8 157 21 212 21 254 22 311 22 26 100 100 10 147 19 198 20 247 20 310 20 27 100 100 14 152 19 211 22 245 22 320 22 28 120 120 7 183 23 242 25 299 25 384 25 29 134 134 7 197 24 262 26 342 28 422 28 30 150 150 12 225 29 298 30 366 30 433 30 31 199 199 16 307 38 402 40 513 42 602 42 32 199 199 17 299 38 404 39 497 39 589 39 33 199 199 17 301 37 407 41 499 41 577 41 34 240 240 22 370 46 490 49 604 50 720 50 35 252 252 27 367 45 507 50 634 50 762 50 36 255 255 14 387 47 511 51 606 51 786 51 Tabla 3.1: Principales características de las instancias de referencia para el problema 2LCVRP. 3.5 Experimentos computacionales. 93 sistema operativo Linux. En el sitio web http://prolog.univie.ac.at/research/VRPandBPP/ se pueden encontrar en detalle los resultados obtenidos por el algoritmo ACO, para todas las instancias y clases en las cuatro configuraciones de carga posibles para el problema 2L-CVRP. Las comparaciones entre los resultados obtenidos por el algoritmo ACO y nuestro algoritmo MS-BR se resumen en las tablas 3.2 a3.6. La diferencia entre los resultados obtenidos por ambos algoritmos se miden en las columnas denominadas Gap, en la que los valores negativos se corresponden con mejoras, expresadas en tanto por ciento, del MS-BR sobre el algoritmo ACO, mientras que los valores positivos representan el caso contrario. La comparación de los resultados obtenidos por ambos algoritmos, muestra que la metaheurística propuesta, MS-BR, obtiene unos resultados bastante competitivos, mostrando mejoras, diferencias negativas para la mayoría de los casos, con respecto a los resultados publicados por Fuellerer et al. (2009). La figura 3.5.1 muestra, para cada clase, un cuadro-gráfico con las diferencias entre el valor BEST10 alcanzado por el algoritmo ACO y el algoritmo MS-BR. Las diferencias negativas muestran que el algoritmo propuesto obtiene resultados ligeramente mejores para todas las clases en el promedio, y también para la mayor parte de las instancias a nivel individual, especialmente para las clases 3, 4 y 2. 3.5.2. Ensayos para el 2L-CVRP sin rotación de los artículos. Como se mencionó en la sección 2.2, existen varios algoritmos propuestos para resolver la variante de carga en dos dimensiones orientada y no restringida, 2|UO|L, en la cual no se permite la rotación de los artículos. Con el fin de comprobar la eficacia de nuestro enfoque en este escenario, se comparan los resultados obtenidos usando nuestro algoritmo MS-BR con los publicados en la literatura. En particular, se seleccionaron los siguientes algoritmos: 1. Búsqueda Tabú Guiada y Extendida (EGTS), desarrollado por Leung et al. (2011). 100 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. CLASE 1 Instance EGTS (1) SA (2) ACO (3) GRASPxELS (4) MS-BR (5) BKS (6) BSol Gap BSol Gap BSol Gap BSol Gap BSol Time (s) Gap (1)-(6) (2)-(6) (3)-(6) (4)-(6) (5)-(6) 1 278,73 0,00% 278,73 0,00% 278,73 0,00% 278,73 0,00% 278,73 0 0,00% 278,73 2 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0 0,00% 334,96 8 568,56 0,00% 568,56 0,00% 568,56 0,00% 568,56 0,00% 568,56 0 0,00% 568,56 12 610 0,00% 610 0,00% 610 0,00% 610 0,00% 610 4 0,00% 610 14 837,67 0,00% 837,67 0,00% 837,67 0,00% 837,67 0,00% 837,67 1 0,00% 837,67 17 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 39 0,00% 861,79 21 687,8 0,03% 693,56 0,87% 690,2 0,38% 687,6 0,00% 687,6 11 0,00% 687,6 26 819,56 0,00% 819,56 0,00% 819,56 0,00% 819,56 0,00% 819,56 1 0,00% 819,56 36 586,58 0,00% 603,69 2,92% 616,69 5,13% 592,87 1,07% 612,99 469 4,50% 586,58 Promedio 0,00% 0,42% 0,61% 0,12% 0,50% Tabla 3.7: Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la clase 1. que estos últimos son lenguajes compilados. Sin embargo, Java permite un desarrollo rápido de proyectos, independientes de la plataforma, así como de prototipos orientados a objetos que pueden ser usados para probar el potencial de un algoritmo. Como se puede observa en las referidas tablas de resultados, el algoritmo MS-BR es capaz de proporcionar resultados competitivos, en particular para las clases 2, 4 y 5, donde obtiene los valores promedios más bajos con respecto a las mejores soluciones conocidas (BKS). Finalmente, en la figura 3.5.2 muestra una comparativa entre los diferentes algoritmos considerados en este análisis. Todas las instancias y clases seleccionadas han sido consideradas en este gráfico. Como se puede apreciar, la metaheurística propuesta MSBR, ofrece el mejor resultado promedio y también las mejores soluciones para la mayor parte de las instancias. El algoritmo GRASPxELS de Duhamel et al. (2011) también ofrece soluciones de gran calidad relativa, ejecutando 10 réplicas por instancia y clase, con un máximo 1,5 horas por réplica, empleando un Opteron a 2,1 GHz. 3.5 Experimentos computacionales. 101 CLASE 2 Instance EGTS (1) SA (2) ACO (3) GRASPxELS (4) MS-BR (5) BKS (6) BSol Gap BSol Gap BSol Gap BSol Gap BSol Time (s) Gap (1)-(6) (2)-(6) (3)-(6) (4)-(6) (5)-(6) 1 304,79 9,35% 285,50 2,43% 284,52 2,08% 284,42 2,04% 278,73 3 0,00% 278,73 2 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0 0,00% 334,96 8 718,20 6,47% 718,18 6,47% 709,39 5,16% 674,55 0,00% 674,55 3 0,00% 674,55 12 629,42 3,09% 621,28 1,75% 610,57 0,00% 610,57 0,00% 610,57 27 0,00% 610,57 14 1.116,43 7,55% 1.078,10 3,85% 1.038,68 0,06% 1.038,09 0,00% 1.038,77 140 0,07% 1.038,09 17 863,66 0,00% 870,86 0,83% 870,86 0,83% 870,86 0,83% 870,86 63 0,83% 863,66 21 1.060,04 6,77% 1.050,05 5,76% 1.013,49 2,08% 992,83 0,00% 998,78 58 0,60% 992,83 26 1.346,82 4,81% 1.330,00 3,50% 1.298,02 1,01% 1.285,01 0,00% 1.291,38 172 0,50% 1.285,01 36 1.832,73 6,11% 1.776,71 2,87% 1.787,01 3,46% 1.782,99 3,23% 1.727,21 311 0,00% 1.727,21 Promedio 4,90% 3,05% 1,63% 0,68% 0,22% Tabla 3.8: Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 2. CLASE 3 Instance EGTS (1) SA (2) ACO (3) GRASPxELS (4) MS-BR (5) BKS (6) BSol Gap BSol Gap BSol Gap BSol Gap BSol Time (s) Gap (1)-(6) (2)-(6) (3)-(6) (4)-(6) (5)-(6) 1 299,70 5,34% 299,70 5,34% 296,87 4,34% 284,52 0,00% 284,52 3 0,00% 284,52 2 355,65 0,99% 353,48 0,37% 352,16 0,00% 352,16 0,00% 352,16 1 0,00% 352,16 8 748,83 1,41% 748,83 1,41% 740,85 0,33% 738,43 0,00% 738,43 53 0,00% 738,43 12 611,99 0,33% 610,00 0,00% 610,00 0,00% 610,00 0,00% 610,00 7 0,00% 610,00 14 1.087,16 9,31% 1.037,83 4,35% 1.018,75 2,43% 996,25 0,16% 994,61 119 0,00% 994,61 17 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 39 0,00% 861,79 21 1.183,91 5,64% 1.174,10 4,77% 1.148,02 2,44% 1.121,84 0,10% 1.120,68 132 0,00% 1.120,68 26 1.405,45 4,52% 1.411,41 4,96% 1.384,75 2,98% 1.344,66 0,00% 1.378,63 202 2,53% 1.344,66 36 1.906,69 5,49% 1.906,05 5,45% 1.891,90 4,67% 1.834,97 1,52% 1.807,51 316 0,00% 1.807,51 Promedio 3,67% 2,96% 1,91% 0,20% 0,28% Tabla 3.9: Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 3. 102 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. CLASE 4 Instance EGTS (1) SA (2) ACO (3) GRASPxELS (4) MS-BR (5) BKS (6) BSol Gap BSol Gap BSol Gap BSol Gap BSol Time (s) Gap (1)-(6) (2)-(6) (3)-(6) (4)-(6) (5)-(6) 1 296,75 4,88% 296,75 4,88% 282,95 0,00% 282,95 0,00% 282,95 1 0,00% 282,95 2 342,00 2,10% 342,00 2,10% 342,00 2,10% 334,96 0,00% 334,96 0 0,00% 334,96 8 718,18 3,71% 723,65 4,50% 692,47 0,00% 692,47 0,00% 692,47 16 0,00% 692,47 12 618,23 0,65% 614,24 0,00% 614,24 0,00% 614,23 0,00% 614,23 4 0,00% 614,23 14 992,83 1,16% 986,84 0,55% 985,01 0,37% 981,90 0,05% 981,42 26 0,00% 981,42 17 863,27 0,17% 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 29 0,00% 861,79 21 1.008,15 3,51% 1.012,80 3,99% 1.001,14 2,79% 978,82 0,50% 973,96 151 0,00% 973,96 26 1.487,09 5,80% 1.468,02 4,44% 1.451,71 3,28% 1.405,57 0,00% 1.409,42 294 0,27% 1.405,57 36 1.759,36 3,47% 1.764,13 3,75% 1.771,31 4,17% 1.728,69 1,67% 1.700,35 492 0,00% 1.700,35 Promedio 2,83% 2,69% 1,41% 0,25% 0,03% Tabla 3.10: Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 4. CLASE 5 Instance EGTS (1) SA (2) ACO (3) GRASPxELS (4) MS-BR (5) BKS (6) BSol Gap BSol Gap BSol Gap BSol Gap BSol Time (s) Gap (1)-(6) (2)-(6) (3)-(6) (4)-(6) (5)-(6) 1 280,60 0,67% 278,73 0,00% 278,73 0,00% 278,73 0,00% 278,73 2 0,00% 278,73 2 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0,00% 334,96 0 0,00% 334,96 8 621,86 1,96% 621,85 1,96% 621,85 1,96% 609,90 0,00% 609,90 11 0,00% 609,90 12 610,23 0,04% 610,23 0,04% 610,23 0,04% 610,23 0,04% 610,00 3 0,00% 610,00 14 925,56 0,45% 925,56 0,45% 922,58 0,12% 921,45 0,00% 921,44 38 0,00% 921,44 17 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 0,00% 861,79 37 0,00% 861,79 21 903,20 2,07% 921,66 4,16% 897,55 1,44% 884,84 0,00% 891,18 251 0,72% 884,84 26 1.256,59 1,80% 1.266,66 2,61% 1.250,41 1,30% 1.234,39 0,00% 1.234,39 270 0,00% 1.234,39 36 1.549,28 0,66% 1.575,60 2,37% 1.570,81 2,06% 1.572,49 2,17% 1.539,05 495 0,00% 1.539,05 Promedio 0,85% 1,29% 0,77% 0,25% 0,08% Tabla 3.11: Comparación de los mejores resultados obtenidos por el algoritmo MS-BR con respecto a diferentes metaheurísticas para la versión 2|UO|L, clase 5. 3.5 Experimentos computacionales. 103 Figura 3.5.2: Diagrama de cajas comparando las diferencias respecto a las mejores soluciones conocidas, BKS, obtenidas por los distintos algoritmos considerados, para el 2|UO|L. 3.5.3. Evolución de la calidad de las soluciones con el tiempo y número de réplicas. Finalmente, las figuras 3.5.3 y3.5.4 muestran dos ejemplos de cómo la calidad de la solución aportada por nuestro algoritmo, evoluciona a medida que aumenta el tiempo de computación y el número de réplicas consideradas. Estos ejemplos corresponden a dos casos diferentes: •Instancia 36 y clase 5 del 2|UO|L. •Instancia 21 y clase 3 del 2|UR|L. Nótese que en ambos casos la calidad de la solución mejora con el tiempo, desde 10 a 500 segundos, de manera progresiva. Además, la calidad de la mejor solución obtenida, mejora a medida que el número de réplicas aumenta, desde 1 a 10. Incluso para pequeños tiempo de cálculo (por ejemplo, 10 segundos), es posible alcanzar soluciones de buena calidad mediante 104 Algoritmo MS-BR para el 2L-CVRP con y sin rotación de artículos. Figura 3.5.3: Evolución de la mejor solución encontrada cuando aumenta el tiempo de computación y el número de réplicas, tomando como ejemplo la instancia 36 clase 5, (2|UO|L). el aumento del número de réplicas, que apoya la idea de que nuestro enfoque puede beneficiarse de las técnicas de computación-paralela para proporcionar buenas soluciones prácticamente en tiempo real, para problemas de complejidad moderada. 3.5 Experimentos computacionales. 105 Figura 3.5.4: Evolución de la mejor solución encontrada cuando aumenta el tiempo de computación y el número de réplicas, tomando como ejemplo la instancia 21 clase 3, (2|UR|L). Capítulo 4 Algoritmo MS-BR para el 2L-HFVRP no restringido. 4.1. Introducción. En este capítulo se analiza el problema de rutas de vehículos con restricción de carga en dos dimensiones y flota heterogénea, denominado en la literatura como heterogeneous fleet vehicle routing problems with two-dimensional loading constraints (2L-HFVRP), resolviendo las variantes de carga no restringidas, con y sin rotación de carga. Esta nueva variante, generaliza el modelo del problema de rutas de vehículos con restricción de carga en dos dimensiones (2L-CVRP), mediante la posibilidad de utilizar una flota de vehículos heterogénea. Dicha flota de vehículos heterogénea comprende unidades de diferentes capacidades, tamaños, costes fijos y costes variables. A pesar de que las flotas heterogéneas son frecuentes en las empresas logísticas o de transporte, existe una carencia de trabajos publicados en la literatura científica sobre el problema 2L-HFVRP, véase la sección 2.3. Tal es así, que hasta donde alcanza nuestro conocimiento ningún trabajo previo, exceptuando Domínguez et al. (2014a) y Domín- 108 Algoritmo MS-BR para el 2L-HFVRP no restringido. guez et al. (2014b), tratan el problema 2L-HFVRP, para las versiones de carga no orientadas (con rotación). Este capítulo se corresponde con el trabajo publicado en el primero de los dos artículos anteriores, mientras que el próximo capítulo se corresponde con el segundo. Para resolver este tipo de problema se propone nuevamente un algoritmo del tipo multi-arranque sobre la base de la aleatoriedad sesgada aplicada a las heurísticas de generación de rutas y carga de vehículos. Un conjunto de experimentos computacionales contribuyen a ilustrar el alcance de nuestro enfoque, así como para mostrar su eficiencia. 4.2. Descripción del problema. El 2L-HFVRP es una nueva extensión del problema de rutas de vehículos con restricción de carga en dos dimensiones, en el cual se admite la existencia de una flota de vehículos heterogénea. El modelo del problema 2L-HFVRP tiene una descripción similar a la expuesta en la sección 3.2, con las siguientes diferencias: •El transporte de la mercancía se realiza mediante una flota heterogénea de Ptipos diferentes de vehículos, inicialmente localizados en el depósito. •El número de vehículos disponibles de cada tipo no está limitado. •Cada tipo de vehículo t(t=1,2, ..., P)tiene las siguientes características: Costes fijos (Ft), costes variables por unidad de distancia recorrida (Vt), capacidad máxima de carga, (máximo peso de la carga a transportar), de cada vehículo Qty un área de carga At= Wt×Ht. Además, se asume que cuanto mayor es la capacidad de carga de un tipo de vehículo, mayores son los costes fijos y variables asociados al mismo. De tal forma que, el costes fijo correspondiente a una ruta Rusando un vehículo del tipo tserá Ft, mientras que el coste variable de la ruta se calcula como VRt =Vt×∑ (i,j)∈E ci j ·zi jR, donde zi jR es 4.3 Principales características del algoritmo propuesto. 109 una variable binaria que toma el valor 1 si el arco (i,j)forma parte de la ruta R, o cero en caso contrario. En este caso, el coste asociado al arco (i,j), que aparece en la expresión del coste variable de la ruta como ci j, se obtiene a partir de la distancia que hay que recorrer para ir del nodo ial nodo j. Por lo tanto, a diferencia del problema 2L-CVRP, en la extensión 2L-HFVRP, se debe buscar la configuración de vehículos y rutas factibles que minimice el coste total de la solución. Nuevamente se consideran las configuraciones de carga no secuenciales, ya que la colocación de los artículos en los vehículos no está condicionada por el orden en el que se visitan los clientes en la ruta. Por consiguiente se tratan dos versiones de carga: •Orientada y no restringida (2L-UO). •No orientada y no restringida (2L-UR). 4.3. Principales características del algoritmo propuesto. El algoritmo propuesto para resolver el 2L-HFVRP, es una evolución de la metaheurística MS-BR descrita en el capítulo anterior cuando se abordó el problema 2L-CVRP. Esta nueva versión del algoritmo MS-BR, vuelve a emplear la aleatoriedad sesgada sobre una heurística clásica aplicada al problema de rutas de vehículos, según la propuesta realizada por Juan et al. (2011), con dos heurísticas empleadas en los problemas de empaquetado bidimensional, modificadas mediante la asignación de probabilidad con asimetría positiva. Estas dos heurísticas son Best-Fit (Burke et al.,2004) y Touching Perimeter (Lodi et al.,1999). Tal y como se detalla en Juan et al. (2013), emplear la aleatoriedad sesgada (Biased Randomization) sobre una heurística, requiere el uso de distribuciones de probabilidad con asimetría positiva, con el fin de transformar dicha heurística en un algoritmo probabilista multi-arranque. 116 Algoritmo MS-BR para el 2L-HFVRP no restringido. Instancia CLASE 1 SA_HLS t(s) MS-BR t(s) Gap (1) (1) (2) (2) (1)-(2) 1 596,07 33,59 596,07 0,01 0,00% 2 679,18 32,01 670,30 0,01 -1,31% 3 745,51 54,24 745,51 0,01 0,00% 4 694,33 18,36 694,87 0,01 0,08% 5 761,19 26,99 758,47 0,01 -0,36% 6 809,56 25,65 809,56 0,03 0,00% 7 3.211,53 29,76 3.211,53 0,11 0,00% 8 3.184,45 24,30 3.184,45 0,05 0,00% 9 1.029,95 40,28 1.053,74 0,01 2,31% 10 5.149,51 25,88 4.932,34 0,02 -4,22% 11 5.119,40 26,47 4.932,34 0,02 -3,65% 12 1.658,56 92,80 1.655,73 0,02 -0,17% 13 14.655,40 32,18 14.579,87 0,21 -0,52% 14 10.019,00 73,21 9.097,52 0,02 -9,20% 15 10.151,70 55,29 9.097,52 0,02 -10,38% 16 1.292,58 76,92 1.276,22 0,04 -1,27% 17 1.770,83 225,59 1.764,32 0,10 -0,37% 18 3.140,55 35,35 3.169,76 0,11 0,93% 19 1.553,11 107,81 1.492,27 14,90 -3,92% 20 1.956,97 71,57 1.752,35 4,82 -10,46% 21 2.567,18 195,66 2.456,08 7,22 -4,33% 22 2.605,90 174,72 2.456,08 7,15 -5,75% 23 2.643,84 239,29 2.456,08 7,14 -7,10% 24 2.555,41 156,41 2.456,08 7,11 -3,89% 25 2.972,59 253,09 2.731,55 14,31 -8,11% 26 4.049,64 180,23 3.477,44 3,92 -14,13% 27 3.561,58 230,49 2.731,55 14,30 -23,31% 28 6.858,35 161,05 4.068,89 18,20 -40,67% 29 9.695,00 142,63 9.093,97 55,54 -6,20% 30 5.663,33 259,83 3.950,27 36,66 -30,25% 31 8.054,90 483,44 5.391,01 59,96 -33,07% 32 8.408,61 410,86 5.392,79 56,46 -35,87% 33 8.555,58 486,25 5.395,41 51,69 -36,94% 34 5.536,63 425,80 4.264,63 35,88 -22,97% 35 4.444,59 401,58 3.911,70 59,87 -11,99% 36 3.669,89 605,31 2.849,46 57,51 -22,36% Promedio 4.167,29 164,30 3.571,05 14,26 -9,71% Tabla 4.2: Comparación de resultados entre SA_HLS y MS-BR - Clase 1. 4.4 Experimentos computacionales. 117 Instancia CLASE 2 SA_HLS MS-BR t(s) MS-BR t(s) Gap Gap UO (1) UO (2) (2) UR (3) (3) (1)-(2) (1)-(3) 1 602,88 604,26 0,01 604,26 0,01 0,23% 0,23% 2 702,45 702,45 0,03 698,41 0,04 0,00% -0,58% 3 769,13 769,13 0,10 765,80 0,12 0,00% -0,43% 4 697,06 697,06 0,09 694,87 0,05 0,00% -0,31% 5 762,92 762,92 0,04 762,92 0,15 0,00% 0,00% 6 827,60 824,60 0,01 824,60 0,07 -0,36% -0,36% 7 6.343,55 6.251,37 0,03 5.952,09 0,04 -1,45% -6,17% 8 5.071,52 5.169,27 0,15 4.804,14 0,04 1,93% -5,27% 9 1.029,95 1.029,95 0,13 1.029,95 0,19 0,00% 0,00% 10 8.401,68 7.709,91 10,69 7.424,84 6,29 -8,23% -11,63% 11 8.465,67 7.886,43 8,76 7.790,53 4,98 -6,84% -7,98% 12 1.674,56 1.674,56 0,14 1.674,56 0,12 0,00% 0,00% 13 27.842,80 26.913,82 0,17 25.501,45 2,27 -3,34% -8,41% 14 10.979,30 10.637,71 0,50 10.328,26 1,19 -3,11% -5,93% 15 11.160,20 10.738,77 10,85 10.730,47 34,97 -3,78% -3,85% 16 1.285,83 1.285,83 0,04 1.280,90 0,23 0,00% -0,38% 17 1.763,63 1.766,50 2,22 1.766,50 1,98 0,16% 0,16% 18 6.017,02 5.748,70 10,53 5.554,81 14,64 -4,46% -7,68% 19 4.510,52 4.393,53 56,45 4.040,26 53,35 -2,59% -10,43% 20 6.311,25 5.808,38 50,05 5.413,21 56,48 -7,97% -14,23% 21 8.745,10 8.268,79 27,61 7.371,44 58,86 -5,45% -15,71% 22 9.041,16 9.198,72 30,59 8.013,74 44,54 1,74% -11,36% 23 9.280,84 9.156,06 52,05 8.411,75 50,00 -1,34% -9,36% 24 4.941,33 4.701,69 52,29 4.493,00 55,85 -4,85% -9,07% 25 12.822,20 12.563,60 58,28 11.475,80 59,33 -2,02% -10,50% 26 11.993,00 11.323,88 49,85 11.145,73 53,58 -5,58% -7,06% 27 5.683,65 5.415,02 42,67 5.163,56 41,02 -4,73% -9,15% 28 23.463,50 22.115,28 58,89 21.098,96 59,81 -5,75% -10,08% 29 22.243,80 20.369,78 58,39 19.670,54 59,13 -8,42% -11,57% 30 16.752,30 15.968,32 53,99 15.190,20 57,10 -4,68% -9,32% 31 21.906,60 20.650,46 59,05 19.312,19 59,10 -5,73% -11,84% 32 21.729,60 21.141,37 59,61 19.485,90 57,46 -2,71% -10,33% 33 21.971,70 20.875,43 58,27 19.611,24 59,11 -4,99% -10,74% 34 15.115,50 14.691,04 59,40 13.843,60 59,80 -2,81% -8,41% 35 8.765,86 8.276,98 57,05 8.020,38 59,33 -5,58% -8,50% 36 4.475,44 4.270,30 59,26 4.132,65 57,58 -4,58% -7,66% Promedio 9.004,20 8.621,16 27,45 8.168,99 29,69 -2,98% -6,78% Tabla 4.3: Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - Clase 2. 118 Algoritmo MS-BR para el 2L-HFVRP no restringido. Instancia CLASE 3 SA_HLS MS-BR t(s) MS-BR t(s) Gap Gap UO (1) UO (2) (2) UR (3) (3) (1)-(2) (1)-(3) 1 589,15 597,04 0,01 597,04 0,01 1,34% 1,34% 2 730,22 728,24 0,03 728,24 0,05 -0,27% -0,27% 3 790,74 777,60 0,05 754,87 1,60 -1,66% -4,54% 4 697,06 697,06 0,04 697,06 0,05 0,00% 0,00% 5 833,68 772,53 0,03 769,91 0,12 -7,33% -7,65% 6 836,09 827,60 0,01 827,60 0,03 -1,02% -1,02% 7 5.216,26 5.189,41 0,51 5.070,70 0,02 -0,51% -2,79% 8 6.820,56 6.672,52 0,40 6.400,11 0,02 -2,17% -6,16% 9 1.029,95 1.029,95 0,09 1.029,95 0,21 0,00% 0,00% 10 6.853,97 6.284,57 24,79 5.925,85 57,37 -8,31% -13,54% 11 8.751,56 8.230,31 7,20 7.719,58 1,16 -5,96% -11,79% 12 1.681,51 1.681,51 0,37 1.681,51 0,04 0,00% 0,00% 13 25.454,10 24.687,08 0,39 24.448,62 3,45 -3,01% -3,95% 14 11.176,90 10.804,18 6,14 10.737,55 10,50 -3,33% -3,93% 15 11.227,40 10.894,05 14,87 10.519,56 8,11 -2,97% -6,30% 16 1.300,95 1.294,93 0,21 1.288,07 0,09 -0,46% -0,99% 17 1.787,84 1.766,50 7,93 1.766,50 14,50 -1,19% -1,19% 18 5.680,14 5.206,82 29,09 5.019,95 31,53 -8,33% -11,62% 19 4.371,60 4.280,52 22,92 4.001,16 31,80 -2,08% -8,47% 20 6.334,52 5.783,64 59,44 5.477,57 59,34 -8,70% -13,53% 21 9.917,98 9.294,17 46,31 8.042,12 59,29 -6,29% -18,91% 22 9.323,96 8.764,02 37,76 7.914,22 52,42 -6,01% -15,12% 23 8.809,96 8.495,50 34,98 7.315,59 59,19 -3,57% -16,96% 24 4.558,84 4.296,08 31,45 4.122,86 55,94 -5,76% -9,56% 25 11.576,60 10.597,80 58,12 9.917,37 59,59 -8,45% -14,33% 26 12.337,50 10.752,45 34,50 10.265,71 48,85 -12,85% -16,79% 27 6.109,92 5.700,16 47,68 5.574,34 49,47 -6,71% -8,77% 28 24.720,80 22.280,38 56,67 20.123,38 59,96 -9,87% -18,60% 29 21.060,20 19.752,62 58,50 19.384,87 57,20 -6,21% -7,95% 30 17.092,60 16.324,01 59,43 15.223,04 49,74 -4,50% -10,94% 31 21.905,90 20.948,29 59,97 19.884,37 59,45 -4,37% -9,23% 32 20.896,30 19.540,20 56,11 17.581,63 59,66 -6,49% -15,86% 33 23.063,20 21.471,96 56,39 19.348,47 59,73 -6,90% -16,11% 34 15.374,20 14.449,21 59,69 13.824,59 60,00 -6,02% -10,08% 35 9.412,89 8.758,88 58,17 8.580,96 54,75 -6,95% -8,84% 36 4.689,83 4.461,00 54,18 4.338,14 58,90 -4,88% -7,50% Promedio 8.972,64 8.363,69 27,35 7.969,53 31,23 -4,49% -8,39% Tabla 4.4: Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - Clase 3. 4.4 Experimentos computacionales. 119 Instancia CLASE 4 SA_HLS MS-BR t(s) MS-BR t(s) Gap Gap UO (1) UO (2) (2) UR (3) (3) (1)-(2) (1)-(3) 1 614,99 596,07 0,01 596,07 0,01 -3,08% -3,08% 2 684,99 695,91 0,01 695,91 0,01 1,59% 1,59% 3 765,74 754,87 0,06 754,87 0,01 -1,42% -1,42% 4 703,76 698,30 13,48 698,30 1,15 -0,78% -0,78% 5 788,78 781,31 0,06 776,08 0,10 -0,95% -1,61% 6 837,00 827,81 0,20 827,81 1,58 -1,10% -1,10% 7 5.574,00 5.255,76 45,41 5.136,24 0,92 -5,71% -7,85% 8 6.538,33 6.097,00 0,47 6.033,76 1,58 -6,75% -7,72% 9 1.052,62 1.052,62 15,61 1.052,62 16,70 0,00% 0,00% 10 8.072,01 7.621,86 11,70 7.589,82 37,25 -5,58% -5,97% 11 9.699,32 9.035,06 13,00 8.479,54 58,60 -6,85% -12,58% 12 1.683,02 1.680,01 0,27 1.680,01 0,46 -0,18% -0,18% 13 27.585,40 26.596,69 2,34 25.251,74 26,48 -3,58% -8,46% 14 10.809,90 10.465,36 53,41 10.147,48 3,48 -3,19% -6,13% 15 11.900,50 11.490,16 3,94 11.394,41 43,07 -3,45% -4,25% 16 1.299,81 1.290,00 0,31 1.290,00 0,61 -0,75% -0,75% 17 1.788,18 1.766,50 7,23 1.766,50 14,55 -1,21% -1,21% 18 6.283,94 5.954,06 37,97 5.881,43 53,76 -5,25% -6,41% 19 4.781,83 4.582,99 38,30 4.387,02 44,60 -4,16% -8,26% 20 6.655,06 5.976,26 57,43 5.638,19 54,78 -10,20% -15,28% 21 8.393,49 8.057,81 51,31 7.500,34 59,46 -4,00% -10,64% 22 9.301,88 8.654,23 51,16 7.818,67 51,28 -6,96% -15,95% 23 8.727,79 8.273,54 56,99 7.999,03 37,40 -5,20% -8,35% 24 4.698,84 4.425,70 31,32 4.363,45 58,55 -5,81% -7,14% 25 12.784,20 11.718,31 48,63 11.022,61 53,48 -8,34% -13,78% 26 13.039,90 12.342,35 58,56 11.432,15 60,00 -5,35% -12,33% 27 5.689,62 5.441,33 49,95 5.341,49 24,66 -4,36% -6,12% 28 23.517,90 22.030,55 59,73 20.503,71 59,87 -6,32% -12,82% 29 23.039,10 21.377,86 46,84 21.048,35 53,08 -7,21% -8,64% 30 17.144,30 16.925,87 60,00 16.064,26 57,69 -1,27% -6,30% 31 23.197,60 21.947,18 59,58 21.135,03 56,42 -5,39% -8,89% 32 21.835,80 20.797,44 54,78 20.517,22 60,00 -4,76% -6,04% 33 23.267,20 22.719,36 58,61 21.693,24 59,05 -2,35% -6,76% 34 15.347,00 15.135,76 59,30 14.914,08 59,74 -1,38% -2,82% 35 9.594,11 9.204,65 58,71 9.044,45 58,86 -4,06% -5,73% 36 4.425,41 4.245,69 48,85 4.169,09 49,99 -4,06% -5,79% Promedio 9.225,65 8.792,12 32,10 8.462,36 33,87 -3,87% -6,38% Tabla 4.5: Comparación de resultados entre SA_HLS orientado, MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - Clase 4. 120 Algoritmo MS-BR para el 2L-HFVRP no restringido. Instancia CLASE 5 SA_HLS MS-BR t(s) MS-BR t(s) Gap Gap UO (1) UO (2) (2) UR (3) (3) (1)-(2) (1)-(3) 1 596,07 596,07 0,01 596,07 0,01 0,00% 0,00% 2 679,18 670,30 0,01 670,30 0,01 -1,31% -1,31% 3 754,87 754,87 0,01 754,87 0,01 0,00% 0,00% 4 694,87 694,87 0,02 694,87 0,03 0,00% 0,00% 5 761,97 758,47 0,09 758,47 0,20 -0,46% -0,46% 6 824,60 824,60 0,03 822,69 0,10 0,00% -0,23% 7 5.386,27 4.866,88 0,28 4.681,61 0,87 -9,64% -13,08% 8 3.979,98 3.949,42 1,03 3.864,36 0,02 -0,77% -2,91% 9 1.029,95 1.029,95 0,04 1.029,95 0,04 0,00% 0,00% 10 7.172,52 6.391,70 1,95 6.065,00 5,00 -10,89% -15,44% 11 6.402,22 6.101,67 0,60 6.017,59 43,40 -4,69% -6,01% 12 1.685,18 1.686,77 0,02 1.677,52 0,11 0,09% -0,45% 13 23.032,40 22.540,44 11,84 22.503,82 15,78 -2,14% -2,29% 14 10.510,20 9.970,89 57,21 9.970,89 57,21 -5,13% -5,13% 15 11.672,30 11.243,55 20,10 11.244,08 31,72 -3,67% -3,67% 16 1.280,90 1.280,90 0,07 1.280,90 0,11 0,00% 0,00% 17 1.766,50 1.767,66 39,91 1.767,66 17,13 0,07% 0,07% 18 4.723,56 4.313,61 31,96 4.313,61 31,96 -8,68% -8,68% 19 3.305,97 3.195,72 54,64 3.056,16 31,65 -3,33% -7,56% 20 5.312,39 4.263,70 50,23 4.127,08 32,67 -19,74% -22,31% 21 5.826,53 5.692,32 57,50 5.419,26 38,16 -2,30% -6,99% 22 6.630,77 5.739,94 52,87 5.539,41 59,78 -13,43% -16,46% 23 6.447,68 6.055,01 59,89 5.393,45 57,35 -6,09% -16,35% 24 3.992,34 3.814,56 34,66 3.689,41 39,99 -4,45% -7,59% 25 8.288,69 7.340,14 53,83 6.974,77 58,88 -11,44% -15,85% 26 9.755,44 9.131,06 59,94 8.229,76 59,39 -6,40% -15,64% 27 5.297,72 5.143,84 59,54 5.058,02 58,66 -2,90% -4,52% 28 18.741,70 16.358,42 59,19 15.670,84 59,90 -12,72% -16,39% 29 21.161,60 20.102,77 58,26 19.878,63 58,68 -5,00% -6,06% 30 12.183,20 10.536,81 59,13 10.432,91 57,10 -13,51% -14,37% 31 17.491,70 15.329,76 59,77 14.906,75 59,18 -12,36% -14,78% 32 15.981,00 13.641,17 59,40 13.159,35 56,63 -14,64% -17,66% 33 17.376,30 15.349,92 59,50 13.455,74 59,50 -11,66% -22,56% 34 12.101,40 11.306,81 58,20 10.227,84 59,97 -6,57% -15,48% 35 8.075,70 7.714,55 58,54 7.673,25 59,57 -4,47% -4,98% 36 3.952,45 3.842,74 57,72 3.835,63 50,31 -2,78% -2,96% Promedio 7.357,67 6.777,83 32,72 6.542,76 32,25 -5,58% -8,00% Tabla 4.6: Comparación de resultados entre SA_HLS (orientado), MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - Clase 5. 4.4 Experimentos computacionales. 121 Instancia Promedio CLASES 2 a 5 SA_HLS (UO) MS-BR (UO) MS-BR (UR) Gap Gap t(s) (1) t(s) (2) t(s) (3) (1)-(2) (1)-(3) 1 30 0 0 -0,40% -0,40% 2 33 0 0 0,00% -0,14% 3 34 0 0 -0,78% -1,63% 4 30 3 0 -0,20% -0,27% 5 28 0 0 -2,29% -2,54% 6 43 0 0 -0,62% -0,68% 7 31 12 0 -4,25% -7,46% 8 30 1 0 -2,33% -5,84% 9 59 4 4 0,00% 0,00% 10 43 12 26 -8,17% -11,46% 11 53 7 27 -6,20% -9,94% 12 167 0 0 -0,02% -0,16% 13 70 4 12 -3,06% -5,98% 14 78 29 18 -3,68% -5,27% 15 92 12 29 -3,47% -4,51% 16 111 0 0 -0,31% -0,53% 17 191 14 12 -0,55% -0,55% 18 89 27 33 -6,52% -8,52% 19 180 43 40 -3,05% -8,75% 20 175 54 51 -11,30% -16,08% 21 292 46 54 -4,77% -13,84% 22 317 43 52 -5,66% -14,61% 23 358 51 51 -3,87% -12,46% 24 289 37 53 -5,24% -8,37% 25 474 55 58 -7,15% -13,37% 26 363 51 55 -7,59% -12,84% 27 282 50 43 -4,74% -7,21% 28 614 59 60 -8,47% -14,43% 29 495 55 57 -6,74% -8,60% 30 812 58 55 -5,41% -9,91% 31 1115 60 59 -6,66% -10,96% 32 969 57 58 -6,62% -12,06% 33 858 58 59 -6,14% -13,50% 34 1596 59 60 -4,07% -8,85% 35 1214 58 58 -5,28% -7,06% 36 112 55 54 -4,12% -6,09% Promedio 354 30 32 -4,17% -7,36% Tabla 4.7: Comparación de resultados entre SA_HLS (orientado), MS-BR orientado y MS-BR no orientado (con posibilidad de rotación) - promedio Clases 2 a 5. 122 Algoritmo MS-BR para el 2L-HFVRP no restringido. http://dpcs.uoc.edu/joomla/index.php/software. 4.5. Análisis de los resultados. Un vistazo inicial a las tablas de la 4.2 ala4.7 permite concluir lo siguiente: •Para el escenario no orientada, (2|UO|L), el algoritmo MS-BR es capaz de mejorar la mayoría de los resultados individuales, así como en los resultados promedio, obtenidos por el algoritmo SA_HLS, con diferencias medias individuales que van desde -2,98% (Clase 2) a -9,71% (Clase 1), y una diferencia promedio total para las clases 2 a 5 de -4,17%. •Las diferencias son lógicamente mayores cuando se comparan con la versión no orientada, ya que se aumenta el espacio de soluciones para el problema de carga cuando se permite la rotación de los artículos en las clases 2 a 5. •Los resultados indican que el algoritmo propuesto requiere menores recursos computacionales que el algoritmo SA_HLS. Considerando dichos recursos computacionales a partir de los tiempos y los medios informáticos empleados. La figura 4.5.1 permite comparar, para cada clase, los costes totales (incluyendo costes fijos y variables) asociados con la mejor solución provista por cada algoritmo: SA-HLS (UO), MS-BR (UO) y MS-BR (UR). Observándose que: •La clase 1 es la que muestra los costes más bajos. •Dentro de cada clase, los costes medios generados con nuestro algoritmo MS-BR son siempre inferiores a los generados con el algoritmo SA_HLS. 4.5 Análisis de los resultados. 123 Figura 4.5.1: Diagrama de cajas representando los costes totales por algoritmo y clase. Figura 4.5.2: Diagrama de cajas de diferencias (Gaps) por clase. 124 Algoritmo MS-BR para el 2L-HFVRP no restringido. Figura 4.5.3: Diferencias entre las versiones de carga orientada (UO) y no orientada (UR), según instancia y clase, para el algoritmo MS-BR. La figura 4.5.2 permite la comparación de diferencias entre los resultados obtenidos por cada par de algoritmos y en cada clase. En particular, se puede constatar que: •Al comparar el algoritmo SA_HLS con el MS-BR, para la versión de carga orientada no restringida, 2|UO|L, las mayores diferencias son los relacionados con las clases 1 y 5. •Cuando se compara el algoritmo MS-BR en las dos variantes de carga, orientada (UO) y no orientada (UR), para las Clases 2 a 5, existe una reducción de costes debidos a la posibilidad de rotar los artículos durante el proceso de carga. La posibilidad de rotar los artículos a cargar, permite aumentar el espacio de soluciones de carga y con ello, el espacio de soluciones del problema completo, ruta más carga. Este crecimiento del espacio de soluciones factibles de carga, permite llegar a soluciones del problema de rutas con menor coste total. Esta mejora del resultado, para el conjunto de las clases 2 a 5, y a nivel promedio se sitúa en torno al 3%, cobrando una mayor importancia en las clases 2 y 3. 4.5 Análisis de los resultados. 125 Finalmente, la figura 4.5.3 muestra en mayor detalle las diferencias porcentuales a nivel de costes totales, comentadas anteriormente, entre la versión de carga orientada y no orientada. Para cada instancia y clase, se presenta la reducción de costes obtenida al permitir la rotación de los artículos durante la fase de carga. Como se puede observar, la disminución del coste total entre ambas configuraciones de carga, varía en función de: •La instancia considerada, siendo de poca importancia en algunas, véase por ejemplo las cinco primeras, o de gran importancia en otras como por ejemplo las instancias 21, 22 y 23. •La clase de instancia, ya que como se puede apreciar en la gráfica, la influencia es generalmente menor en las clases 4 y 5, mientras que en las clases 2 y 3 se pueden alcanzar diferencias significativas superiores al 10%. 132 Algoritmo ILS-BR para el 2L-HFVRP secuencial. Figura 5.3.1: Esquema general de nuestro algoritmo ILS-BR. En el algoritmo MS-BR se realizaba un reinicio completo de la solución inicial en cada iteración, sin embargo, en el caso del algoritmo ILS-BR se trabaja con una solución base que se va modificando durante las diferentes iteraciones. Dicha solución base se actualiza en cada iteración en la cual se cumple el criterio de aceptación establecido. Mantener una solución base en cada iteración, supone partir de una solución de calidad en lugar de una nueva solución aleatoria generalmente de menor calidad, lo cual implica normalmente un menor grado de diversificación y un mayor grado de intensificación del algoritmo ILS-BR respecto al MS-BR. La técnica de división en subproblemas se utiliza durante la etapa de perturbación para extraer un subconjunto de rutas de la solución base, para posteriormente centrar los esfuerzos de mejora en el subproblema asociado, dejando sin modificar el otro subproblema restante. Lógicamente, una mejora del subproblema seleccionado supone una mejora del problema global. 5.4 Detalle a bajo nivel mediante pseudo-código. 133 Obsérvese que a diferencia del MS-BR, donde se resolvían todos los subproblemas resultantes de la división, en el ILS-BR se generan dos subproblemas y se trata sólo la mejora de uno de ellos. La sistemática descrita en los capítulos anteriores relativa a la modificación de las heurísticas especificadas, usadas en el problema de rutas y de carga de los vehículos, mediante la generación aleatoria de soluciones usando una asignación de probabilidad con distribución asimétrica positiva, vuelve a ser utilizada dentro de la etapa de perturbación de la solución base. Posteriormente, se realiza la etapa de búsqueda local mediante el uso de la técnica de memoria-caché de soluciones, previamente detallada en capítulos anteriores. Finalmente, la mejor de las soluciones base obtenidas será la mejor solución cuando se alcance la condición de parada. 5.4. Detalle a bajo nivel mediante pseudo-código. El algoritmo 5.1 muestra el pseudo-código asociado con el procedimiento principal de la metaheurística ILS-BR. Una vez que las entradas del problema, (datos de los clientes, características de los vehículos disponibles, así como los tamaños y pesos de los artículos solicitados), se han cargado en el programa, se genera una solución base inicial mediante el procedimiento Pack-And-Route (el proceso de generación se explica más adelante en detalle). Esta solución base inicial también se establece como la mejor solución hasta el momento (líneas 1 y 2). A continuación, el algoritmo comienza un procedimiento de Búsqueda Local Iterativa (ILS) (líneas 4 a 21), que tiene por objeto reducir el coste de la mejor solución obtenida mediante la combinación de una etapa de construcción-destrucción (perturbación) de la solución base 134 Algoritmo ILS-BR para el 2L-HFVRP secuencial. Algoritmo 5.1 Pseudo-código del procedimiento principal del ILS-BR. Procedure ILS-BR(inputs, α , maxPackIter, β ) 01 baseSol <- packAndRoute(inputs, α , β )% aleatoriedad sesgada 02 bestSol <- baseSol 03 delta <- 0 % variable auxiliar 04 while {condición final no alcanzada} do % tiempo o límite de iteraciones 05 subSol <- extractRoutesAtRandom(baseSol) % fase de destrucción 06 subInptus <- getSubProblem(subSol) 07 newSubSol <- packAndRoute(subInputs, α , maxPackIter, β )% resolución del subproblema 08 newSubSol <- applyCache(newSubSol) % búsqueda local memoria-caché 09 newSol <- merge(baseSol, newSubSol) % fase de reconstrucción 10 delta <- cost(newSol)  cost(baseSol) 11 if {delta < 0} then % mejora de baseSol 12 credit <- (-delta) 13 baseSol <- newSol 14 if {cost(newSol) < cost(bestSol)} then 15 bestSol <- newSol 16 end if 17 else if {0 < delta < credit} then % criterio de aceptación 18 credit <- 0 19 baseSol <- newSol 20 end if 21 end while 22 return bestSol end procedure con una etapa de búsqueda local (líneas 5 a 9). La perturbación y las etapas de búsqueda local se basan en técnicas de división y de memoria-caché ya descritas en capítulos anteriores. En la etapa de perturbación, un conjunto de rutas adyacentes se extrae de la solución base utilizando un proceso de selección al azar de una ruta base y una serie de rutas adyacentes (fase de destrucción). De este conjunto de rutas se obtienen los datos de entrada del subproblema 2L HVRP secuencial, de menor tamaño que el original (línea 6) y, por lo tanto, más fácil de resolver de manera eficiente. A continuación, el subproblema se resuelve mediante el procedimiento Pack-And-Route (línea 7), y la subsolución resultante se combina con las rutas no extraídas (línea 9) para generar una nueva solución global para el problema original (fase de reconstrucción). De hecho, antes de que ocurra este proceso de fusión, se completa una búsqueda local rápida basada en una memoria-caché de rutas previamente obtenidas (línea 8). Después de la búsqueda local, el coste de la nueva solución se compara con el coste de la solución de base (línea 10). Siempre que la primera sea inferior a la segunda, la solución base se actualiza (línea 13). Un proceso de 5.4 Detalle a bajo nivel mediante pseudo-código. 135 actualización similar se realiza con la mejor solución encontrada (línea 15). Bajo algunas circunstancias, la solución base se actualiza con la nueva solución, incluso si esta última muestra un coste más elevado (línea 19). Esta degradación de la solución base se lleva a cabo de vez en cuando, con el fin de disminuir la probabilidad de que el algoritmo quede atrapado en un mínimo local. Concretamente, para aceptar esta pérdida en el resultado de la solución base se utiliza el siguiente criterio basado: •El aumento del coste tiene que ser inferior a la mejora obtenida en la última actualización (representado en el pseudocódigo por la variable credit). •Tras una degradación de la solución base, no se admite una segunda degradación consecutiva (esto se logra al estableciendo la variable credit a 0 cada vez que se degrada la solución base). El procedimiento Pack-And-Route, que se muestra en el pseudo-código 5.2, se corresponde básicamente con la misma metodología descrita en el capítulo anterior pero incluyendo la restricción secuencial que no había sido abordada anteriormente. Dicha restricción afecta a la solución de carga, por lo que es gestionada dentro del procedimiento checkPacking, cuyo pseudo-código aparece en 5.3. Tras algunos ensayos se establecen los valores de αyβ, para el algoritmo propuesto. El parámetro αse fija en esta ocasión al valor 0,3, mientras que el parámetro βtoma un valor aleatorio entre 0,06 y 0,24, en cada llamada a la heurística de carga. Como se puede observar en el pseudo-código del procedimiento checkPacking, la restricción secuencial de carga requiere un control sobre el orden de visita a los clientes durante la ruta. Este orden es extraído mediante el procedimiento getCustomerOrder, y almacenado en la variable custOrder (línea 3). A diferencia del algoritmo MS-BR, en esta nueva propuesta se ha incluido una memoria-caché, (con estructura de datos del tipo hash map), para almacenar las 136 Algoritmo ILS-BR para el 2L-HFVRP secuencial. Algoritmo 5.2 Pseudo-código del procedimiento Pack-And-Route. Procedure packAndRoute(subInputs, α , maxPackIter, β ) 01 sol <- genDummySol(inputs) % generar solución trivial usando el vehículo de menor tamaño 02 savingsList <- buildSavingsList(inputs) 03 savingsList <- biasedRandSort(savingsList, α )% % calcular la lista de arcos orden(ahorros) 04 while {savingsList is not empty} do 05 nextEdge <- extractNextEdge(savingsList) 06 iNode <- getOriginNode(nextEdge) 07 jNode <- getDestinyNode(nextEdge) 08 iRoute <- getRoute(iNode, sol) 09 jRoute <- getRoute(jNode, sol) 10 vehType <- selectSmallestWeightCapableVehType(iRoute, jRoute) 11 isPackingFeasible <- false 12 isMergeAnImprovement <- false 13 while {veh in vehType has not been checked} do 14 isMergeAnImprovement <- checkIfMergeImprovesSol(iRoute, jRoute, veh) 15 if {isMergeAnImprovement is true} do 16 isPackingFeasible <- checkPacking(iRoute, jRoute, vehType, maxPackIter, β ) 17 if {isPackingFeasible is false} then 18 if {vehType is not the largest type of vehicle} do 19 vehType <- selectNextLargerTypeOfVehicle(vehType) 20 else 21 exit while% referido al anidado 22 end if 23 end if 24 end if 25 end while 26 if {isMergeAnImprovement} and {isPackingFeasible} then 27 newRoute <- merge(iRoute, jRoute, veh) 28 sol <- update(iRoute, jRoute, newRoute) 29 end if 30 end while 31 return sol end procedure soluciones factibles de carga obtenidas junto con el tipo de vehículo empleado, de esta forma se reduce el esfuerzo computacional en la resolución del problema de carga. Esta memoria de soluciones de carga factibles, es consultada mediante el procedimiento checkPackingCache (línea 6), y actualizada cuando se obtiene una nueva solución de carga (líneas 12 y 17). Cuando no existe una solución previa en la memoria, el problema de carga secuencial es tratado mediante dos metodologías distintas aplicadas sobre cada una de las heurísticas de empaquetado utilizadas Best-Fit y Touching Perimeter, descritas en el capítulo anterior. Dando lugar, en este caso a cuatro variantes de empaquetado que se aplican secuencialmente, dos variantes para cada heurística: 1. La primera metodología consiste en cargar el vehículo siguiendo el criterio LIFO, es 5.4 Detalle a bajo nivel mediante pseudo-código. 137 Algoritmo 5.3 Pseudo-código del procedimiento checkPacking. Procedure checkPacking(iRoute, jRoute, vehType, maxPackIter, β ) 01 isPackingFeasible <- false 02 itemsList <- getItems(iRoute, jRoute) 03 custOrder <- getCustomerOrder(iRoute, jRoute) % orden de visita a los clientes 04 packingSol <- emptySol 05 if {items total area ≤ vehicle loading surface} then 06 packingSol <- checkPackingCache(custOrder, vehType) % buscar en memoria de sol. de carga 07 if {packingSol is not emptySol} then 08 isPackingFeasible <- true % solución factible de carga encontrada en memoria 09 else % aplicación de la aleatoriedad sesgada sobre la heurística Touching Perimeter 10 packingSol <- biasedRandTP(itemsList, custOrder, vehType, maxPackIter, β ) 11 if {requestedLength(packingSol) <= length(vehType)} then 12 update packing cache with packingSol 13 isPackingFeasible <- true 14 else % aplicación de la aleatoriedad sesgada sobre la heurística Best-Fit 15 packingSol <- biasedRandBF(itemsList, custOrder, vehType, maxPackIter, β ) 16 if {requestedLength(packin,gSol) ≤ length(vehType)} then 17 update packing cache with packingSol 18 isPackingFeasible <- true 19 end if 20 end if 21 end if 22 end if 23 return isPackingFeasible end procedure decir, se carga el vehículo en orden inverso al que se visitan los clientes, empezando con el último cliente a visitar en la ruta y terminando con el primero. Luego para cada ciclo de carga correspondiente al cliente en cuestión, para la posición a ocupar por el siguiente artículo a cargar sólo se consideran los artículos pendientes de colocar del cliente actual. Cuando hay posibilidad de colocar más de un ítem, se realizará una selección aleatoria dando mayor probabilidad al que obtenga el mejor encaje según los criterios de cada heurística Best-Fit o Touching Perimeter. Este método en principio nos asegura el cumplimiento de la restricción secuencial. 2. En la segunda metodología, sin embargo, tanto en la heurística Best-Fit como en la Touching Perimeter, cuando hay más de un elemento que encaje en la posición analizada en cada momento, se realiza una selección aleatoria de cualquiera de estos artículos, pero dando mayor probabilidad en la selección a los elementos que pertenecen a clientes visitados al final de la ruta. De esta forma, se aumenta la probabilidad de selección de los artículos, en función de la posición que ocupa el cliente correspondiente en la ruta. 138 Algoritmo ILS-BR para el 2L-HFVRP secuencial. Para asignar esta probabilidad haciendo uso de la aleatoriedad sesgada, se utiliza un factor de ganancia para cada heurística de tal modo que: a) En el caso del Touching Perimeter el valor del perímetro de contacto obtenido, (puntuación), para cada artículo del cliente i, en la posición considerada, se multiplica por 1+ρ(i)2, donde ρ(i)es la posición del cliente ien la ruta, empezando por ρ(i) = 1 para el primer cliente a visitar. La puntuación obtenida tras multiplicar el valor del perímetro por la ganancia, se ordena de mayor a menor. Además el chequeo de la restricción secuencial se realiza después de colocar un nuevo elemento. En caso de no cumplir la condición secuencial se interrumpe el proceso de colocación y se comienza otro nuevo. b) En el caso del Best-Fit, la variable que determina el orden de prioridad en la selección de los elementos, para cada posición, es la diferencia entre el espacio libre de carga y la dimensión correspondiente del rectángulo que es menor o igual al espacio disponible, menor diferencia es mejor encaje, véase Burke et al. (2004). En este caso, para favorecer la selección de los elementos pertenecientes a clientes que se visitan al final de la ruta, el valor de esta diferencia se multiplica nuevamente por un factor de ganancia 1−ρ(i)2. La puntuación resultante permite ordenar los artículos de menor a mayor valor, y aplicar posteriormente la asignación de probabilidad asimétrica sobre la lista ordenada de artículos para la posición considerada. El parámetro maxPackIter, controla el número de intentos que se realizan con cada heurística y método para lograr una solución de carga viable. Para ajustar el número de intentos a la dificultad del problema, este parámetro toma como valor la suma total de artículos a cargar en el vehículo. 5.5 Experimentos computacionales. 139 5.5. Experimentos computacionales. El algoritmo descrito en este capítulo se ha implementado como una aplicación Java. Se utilizó, para realizar todas las pruebas, un sólo núcleo de un procesador Intel®Core™ i72670QM a 2,2 GHz y 4 GB de RAM, que se ejecutan directamente en la plataforma Netbeans, instalado sobre un sistema operativo Windows 7. Con el fin de probar nuestro algoritmo, nuevamente se recurre a las instancias de referencia propuestas por Leung et al. (2013), detalladas en la sección 4.4. Usando el algoritmo ILS-BR, las 180 instancias-clases se resolvieron, excepto la clase 1, bajo dos escenarios diferentes: 1. Carga orientada secuencial (2|SO|L). 2. Carga no orientada secuencial (2|SR|L). Para cada escenario y cada combinación de instancia y clase, se ejecutan cinco réplicas de nuestro algoritmo, cada uno de ellos utilizando una semilla diferente para la generación aleatoria. Cada réplica se ejecutó durante un tiempo máximo de 1 minuto, es decir, se permitió un tiempo máximo de 5 minutos para cada combinación de instancia y clase. Para el escenario orientado secuencial, (sin rotación de los artículos), se comparan nuestros resultados con el Recocido Simulado con una Búsqueda Local Heurística, Simulated Annealing with Heuristic Local Search (SA_HLS), al igual que en el capítulo anterior. Recordemos que el SA_HLS fue implementado en C++ y ejecutado en una computadora con un procesador Core 2 Duo a 2,2 GHz y 2 GB de RAM en Windows 7. Para la versión de carga no orientada secuencial, (2|SR|L), hasta donde llega nuestro conocimiento, no hay resultados previos publicados con los que comparar el algoritmo propuesto. Por esa razón, se vuelve a comparar nuestros resultados para los escenarios orientado y no orientado, como una forma de estimar la reducción de los costes derivados de la posibilidad 140 Algoritmo ILS-BR para el 2L-HFVRP secuencial. de rotar los artículos. Las tablas 5.1 a5.6 muestran los resultados obtenidos para los tres enfoques mencionados anteriormente: SA_HLS (orientado), nuestra mejor solución para el escenario orientado (ILS-BR SO), y nuestra mejor solución para el escenario con rotación (ILS-BR SR). El tiempo que aparece en las tablas, corresponde a los segundos transcurridos hasta encontrar la mejor solución. Con respecto a la Clase 1, ya que todos sus artículos son de forma cuadrada, los resultados de esta clase son los mismos independientemente de si se permite o no la rotación de artículos. Por último, también se realiza una comparativa entre el algoritmo MS-BR propuesto en el capítulo anterior frente al ILS-BR, para la versión de carga orientada y no restringida, 2|UO|L. En la tabla 5.7 se muestra la referida comparativa para los resultados promedio de las clases 2 a 5. En este caso, se elimina la restricción de carga secuencial, para facilitar la confrontación de resultados. Ambos algoritmos fueron ejecutados empleando los mismos recursos informáticos, ya especificados anteriormente. Una vez más, se incluye la mejor solución obtenida para las cinco réplicas, el tiempo de CPU transcurrido y el porcentaje de mejora, gap negativo, del ILS-BR respecto al MS-BR. 5.6. Análisis de los resultados. Para el caso secuencial, los resultados de las tablas 5.1 a5.6, nos permiten concluir lo siguiente: •Para el escenario orientado secuencial, el algoritmo ILS-BR es capaz de mejorar la mayoría de los resultados individuales, así como el promedio en los resultados proporcionados por el algoritmo SA_HLS, con diferencias medias individuales que van desde -2,00% (clase 4) a -9,71% (Clase 1), y una diferencia promedio total para las clases 2 a 5 de -3,01%. 5.6 Análisis de los resultados. 141 Instancia CLASE 1 SA_HLS t(s) ILS-BR t(s) Gap (1) (1) (2) (2) (1)-(2) 1 596,07 29,78 596,07 0,00 0,00% 2 679,18 5,05 670,30 0,00 -1,31% 3 745,51 12,39 745,51 0,01 0,00% 4 694,33 6,15 694,33 1,88 0,00% 5 761,19 5,62 758,47 0,02 -0,36% 6 809,56 4,77 809,56 0,07 0,00% 7 3.211,53 3,67 3.211,53 0,35 0,00% 8 3.184,45 3,21 3.184,45 0,17 0,00% 9 1.029,95 7,39 1.029,95 0,01 0,00% 10 5.149,51 6,97 4.932,34 0,87 -4,22% 11 5.119,40 6,97 4.932,34 0,88 -3,65% 12 1.658,56 35,80 1.655,73 0,31 -0,17% 13 14.655,40 1,93 14.579,87 0,15 -0,52% 14 10.019,00 13,51 9.097,52 0,09 -9,20% 15 10.151,70 5,49 9.097,52 0,08 -10,38% 16 1.292,58 17,94 1.276,22 0,01 -1,27% 17 1.770,83 38,88 1.764,32 0,03 -0,37% 18 3.140,55 13,54 3.169,76 0,95 0,93% 19 1.553,11 32,56 1.490,28 0,18 -4,05% 20 1.956,97 56,00 1.776,44 1,28 -9,23% 21 2.567,18 75,00 2.470,47 51,80 -3,77% 22 2.605,90 76,39 2.470,47 51,52 -5,20% 23 2.643,84 93,99 2.470,47 51,73 -6,56% 24 2.555,41 63,98 2.470,47 49,51 -3,32% 25 2.972,59 129,04 2.728,40 6,91 -8,21% 26 4.049,64 88,09 3.477,26 1,44 -14,13% 27 3.561,58 159,20 2.728,40 6,58 -23,39% 28 6.858,35 125,60 4.065,70 46,85 -40,72% 29 9.695,00 139,73 9.105,07 45,26 -6,08% 30 5.663,33 242,15 3.946,79 42,46 -30,31% 31 8.054,90 325,51 5.370,31 59,79 -33,33% 32 8.408,61 379,53 5.370,34 59,99 -36,13% 33 8.555,58 368,50 5.377,08 48,82 -37,15% 34 5.536,63 323,50 4.263,78 44,12 -22,99% 35 4.444,59 324,64 3.911,17 59,44 -12,00% 36 3.669,89 555,13 2.847,02 55,05 -22,42% Promedio 4.167,29 104,93 3.570,71 19,13 -9,71% Tabla 5.1: Comparación de resultados entre SA_HLS y ILS-BR - Clase 1.