Métodos heurísticos para resolver un problema de gran escala de reasignación de contenedores entre terminales de un hub portuario

J Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Métodos heurísticos para resolver un problema de gran escala de reasignación de contenedores entre terminales de un hub portuario Autor: Andrés González Gómez Tutor: Alejandro Escudero Santana Dpto. Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 3 Trabajo Fin de Grado Grado en Ingeniería de Organización Industrial Métodos heurísticos para resolver un problema de gran escala de reasignación de contenedores entre terminales de un hub portuario Autor: Andrés González Gómez Tutor: Alejandro Escudero Santana Profesor Contratado Doctor Dpto. de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 Trabajo Fin de Grado: Métodos heurísticos para resolver un problema de gran escala de reasignación de contenedores entre terminales de un hub portuario Autor: Andrés González Gómez Tutor: Alejandro Escudero Santana El tribunal nombrado para juzgar el Trabajo arriba indicado, compuesto por los siguientes miembros: Presidente: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2019 El secretario del Tribunal 5 A mi familia y amigos por todo su apoyo. 7 Agradecimientos Agradecer a mi familia su apoyo incondicional durante todo el grado, incluso cuando en algunos momentos ni yo mismo creía en mí. A todos mis amigos y en general a todos los que han confiado en mí en algún momento. Dar las gracias sobre todo a Alejandro Escudero por darme la oportunidad de realizar este trabajo que tanto me ha enriquecido, por su paciencia y consejos. Andrés González Gómez Sevilla, 2019 9 Resumen En este trabajo se resuelve un problema particular del movimiento de contenedores entre las terminales de un puerto “Hub” intermodal. Mediante el desarrollo y aplicación de una heurística se pretende optimizar el tiempo y/o costes de las rutas seguidas por los camiones durante una jornada de trabajo. Los resultados obtenidos son comparados con los de una heurística desarrollada en el artículo Ki Ho Chung et al., 2007. Desde los años ochenta hasta hace relativamente poco tiempo, se encuentran los puertos de tercera generación. Aumentaron los graneles y la carga general, así pasaron a funcionar como una plataforma logística, ampliando el movimiento de contenedores. El puerto pasó a ser un punto de intercambio de distribución de la carga, abriendo nuevos canales de información y apareciendo nuevos conceptos de puertos. En esta generación se consigue un aumento de la calidad de los servicios. La cuarta y quinta generación se está produciendo en la actualidad y desarrollándose en un futuro próximo con la modernización de los puertos y su adaptación a los mercados. Mediante el uso de un sistema de información e integrando todos los factores y servicios anteriores, se puede obtener una personalización de los servicios, convirtiendo al contenedor en transporte por excelencia. Los de la cuarta generación se caracterizan por un aumento en las nuevas tecnologías aplicadas a la gestión y explotación portuaria y los puertos de nueva generación van un poco por delante en logística, en tecnología de información y en la gestión de la demanda. Las características de las distintas generaciones de puertos se encuentran en la tabla 1: 17 Primera Generación Segunda Generación Tercera Generación Cuarta Generación Quinta Generación Periodo de desarrollo Hasta 1960 Después de 1960 Después de 1980 Actualidad Futuro Carga principal Carga general Carga general, carga seca/líquida y carga a granel Carga a granel y carga contenerizada Carga a granel y carga contenerizada Carga a granel y carga contenerizada Actitud y estrategia de desarrollo portuario Conservadora. Punto de conexión de modos de transporte Expansionista. Centro de transporte industrial y comercial Orientación comercial. Centro de transporte integrado y plataforma logística para el comercio internacional Orientación comercial en red. Puerto en red dentro de una comunidad portuaria Logística colaborativa. Nodo logístico en la malla competenciacolaboración Ámbito de actividades Carga y descarga de mercancías, almacenamiento, servicios a la navegación. Muelles y zonas junto al mar Carga y descarga de mercancías, almacenamiento, servicios a la navegación. Muelles y zonas junto al mar. Transformación de la carga, servicios industriales y comerciales destinados al buque. Ampliación de la zona portuaria Carga y descarga de mercancías, almacenamiento, servicios a la navegación. Muelles y zonas junto al mar. Transformación de la carga, servicios industriales y comerciales destinados al buque. Ampliación de la zona portuaria. Distribución de la carga e información, actividades logísticas Todos los servicios anteriores y Servicios logísticos integrados Todos los anteriores y Semantic Web Característica s de producción Corriente de carga. Servicios industriales sencillos. Bajo valor añadido Corriente de carga. Transformación de la carga. Servicios combinados. Aumento del valor añadido. Corriente de carga e información. Distribución de carga e información. Conjunto de servicios múltiples. Alto valor añadido. Especialización Tecnologías de la información. Alto valor añadido Especialización. Globalización de la información. Factores decisivos Trabajo/capital Capital Tecnología/conoci mientos Intercambio de información Aprendizaje colaborativo Tabla 1: Evolución de los puertos. Fuente: Tesis César Moreno Martínez ¨Metodología para maximizar…” 2.2. Evolución del transporte marítimo La curiosidad del ser humano junto con la necesidad por alcanzar cualquier parte del mundo para intercambiar productos, materias primas o satisfacer necesidades, llevó al desarrollo de rutas marítimas. Hay evidencias de la existencia del transporte marítimo siglos antes de Cristo. Los primeros barcos que existieron fueron las balsas de palma de los egipcios, motivados por el interés comercial. Prácticamente de forma paralela al comienzo de la navegación de los propios egipcios, se desarrolló en la Isla de Creta un imperio marítimo que, con sus barcos, fueron capaces de conectar con las grandes civilizaciones de aquella época. El comercio se acentuó con la Edad de Bronce, llegando a definir un tipo de economía y el descubrimiento y posterior establecimiento de itinerarios marítimos. De los cretenses aprendieron los fenicios y los griegos. Estos aprovecharon tanto las rutas marítimas, como sus técnicas de navegación. Posteriormente, los romanos bebieron de los métodos que habían mejorado los fenicios, siendo estos los que desarrollaron los puertos en cuanto a infraestructura con grandes obras marítimas que no pudieron igualarse en los siguientes 1500 años, quedando hoy en día numerosos restos. Los propios romanos construyeron y promovieron la construcción de faros en las costas atlánticas y mediterráneas. En la Edad Media se produce un estancamiento, es un periodo de recesión en cuanto al comercio marítimo y a la navegación. No es hasta los siglos X y XI cuando comienza el resurgir, apareciendo nuevas rutas como las del Mediterráneo, que sirvió para proveer de alimentos a los griegos o rutas como las que se lograron al aventurarse a cruzar el actual Estrecho de Gibraltar (antiguas Columnas de Hércules) y explorar el Atlántico. Siguiendo con la dinámica de la aventura, el descubrimiento de América o el descubrimiento del oro llevaron consigo el descubrimiento de nuevas rutas, la construcción de muelles y la evolución de los barcos con la máquina de vapor en el siglo XIX, aumentando su carga y tamaño. A principios del siglo XX, los barcos seguían descargándose individualmente. Malcom P. Mclean llegó a adquirir una empresa de camiones que transportaba productos como algodón desde Nueva Jersey hasta el muelle de Hooken donde la American Export Line los llevaba hasta Estambul. Él tenía muchas aspiraciones de crecimiento, pero la problemática del descargue de la mercancía “fardo a fardo” le hacía perder tiempo y dinero. Compró una empresa de transporte marítimo con el objetivo de encontrar una forma de carga y descarga más rápida. Debido a la ley antimonopolio, decidió vender la empresa de camiones para conseguir alcanzar su principal inquietud. Tenía que desarrollar un contenedor grande, ligero y estable. En 1956 zarpa el primer barco, el Ideal X (ver figura 1), cargado de contenedores. Para crecer necesitaba el apoyo del resto de transportadoras marítimas. Mediante el traslado de contenedores entre algunas rutas, Mclean fue perfeccionándolo. 19 Figura 1:Plano del Ideal X Gracias a los problemas logísticos de EE. UU en su guerra contra Vietnam, la idea de Mclean consigue desarrollarse y no es hasta 1967 cuando llega a Europa. En menos de diez años ya había navieras que construían sus propios contenedores. El movimiento de contenedores fue cada vez mayor, tanto que en 2015 y, como se muestra en la figura 2, el tráfico mundial de contenedores fue de aproximadamente 651 millones, creciendo un 1.8% con respecto al año anterior, mientras que en España el movimiento de contenedores fue de 13,1 millones, aproximadamente. Figura 2: Datos sobre el movimiento de contenedores Fuente icontainers 3. Conceptos básicos de una terminal de contenedores En una terminal de contenedores marítima se produce el transbordo entre buques y vehículos terrestres como trenes y camiones o producirse el intercambio de forma inversa. Necesitará de unas infraestructuras tanto para su carga y descarga, como para el almacenaje de las mercancías. En esta sección se verán los diferentes conceptos referentes a dichas terminales, así como los tipos y subsistemas en los que se puede dividir. 3.1. Mercancías manejadas en los puertos La existencia de los puertos se debe al movimiento de mercancías, por eso es necesario hacer una clasificación de estas. Arango et al. (2010) y el propio Ministerio de Fomento, clasifica las mercancías principales en tres tipos: graneles sólidos, graneles líquidos y mercancías diversas. ➢ Graneles Sólidos: Representan el mayor conjunto de la carga mundial, siendo aproximadamente 5200 millones de toneladas en 2018 (entorno al 60%). Los graneles secos mayores más transportados son el mineral de hierro, cemento, carbón y cereales. Los graneles menores son productos como el acero o productos semielaborados. ➢ Graneles Líquidos: Representados principalmente por los hidrocarburos, constituyen aproximadamente el 40% de la carga mundial. Los principales productos dentro de los hidrocarburos son el petróleo (entorno al 72% de los hidrocarburos), productos petroleros (entorno al 22%) y gas (entorno al 6%). ➢ Mercancías diversas: La mayoría se presenta en contenedores. Este mercado continúa creciendo y se distingue por la necesidad de especificación del servicio marítimo. 3.2. Tipos de terminales de contenedor En la actualidad se pueden diferenciar dos tipos de terminales de contenedores: la terminal de contenedores portuaria y el puerto seco. No todas las terminales de contenedores realizan los procesos siguiendo la misma metodología, por eso, la maquinaria debe ser escogida con el objetivo de alcanzar la máxima eficiencia posible, aunque las características principales son comunes para todas. 3.2.1. Puerto seco Según la UNCTAD (United Nations Conference for Trade and Development), un puerto seco es “una instalación no costera de uso público, distinta de un Puerto y de un Aeropuerto, aprobada por un organismo competente, equipada con instalaciones fijas y ofreciendo servicios para manipular y almacenar temporalmente cualquier clase de mercancías incluyendo contenedores". La peculiaridad de este tipo de puertos es que se encuentran alejados de las 21 costas y están conectados con puertos costeros mediante el transporte ferroviario. Permiten mejorar el servicio a las ciudades del interior de los países. En la figura 3 se puede observar el puerto seco de Antequera. Figura 3:Puerto seco de Antequera Fuente: Málaga Hoy 3.2.2. Terminal de contenedores portuaria (TCP) Una terminal de contenedores portuaria se define como una instalación o instalaciones que sirven para el intercambio del transporte marítimo a cualquier otro tipo de transporte, como el ferroviario o por carretera. Una TCP se caracteriza por tener una maquinaria especializada para el movimiento de contenedores y por poseer una capacidad de almacenamiento usada para regular los distintos ritmos de llegada. Las terminales de contenedores portuarias pueden tener un alto nivel de sistematización gracias a la estandarización de los contenedores. Un ejemplo de TCP se puede ver en la figura 4, en la que se muestra la TCP del puerto de Huelva. Figura 4: TCP de Huelva Fuente: www.puertodehuelva.com 3.2.2.1. Zonas dentro de una terminal de contenedores portuaria Una terminal de contenedores suele tener cuatro zonas principales: ➢ Zona de operación: Zona en los muelles donde se realizan las actividades de carga y descarga de los contenedores a los buques. ➢ Zona de almacenamiento: Zona destinada al almacenamiento de contenedores. ➢ Zona de cambio de modo de transporte: Destinada a la realización de las actividades de carga y descarga de contenedores a camiones y/o trenes. ➢ Zona de servicio: En esta zona suelen encontrarse otros servicios portuarios como las oficinas de control, talleres, aduanas, etc. 3.3. Subsistemas de una terminal de contenedores Anteriormente se han descrito las zonas físicas que se pueden encontrar en una terminal de contenedores portuaria. En estas zonas, o en la frontera de unas con otras, se pueden llevar a cabo distinto tipos de procesos conocidos como subsistemas. El hecho de dividir la terminal en distintos procesos permite optimizarlas de forma particular para la toma decisiones. La literatura sobre optimización de terminales (Hennessey, 2004) distingue cuatro tipos de procesos, tal y como se muestra en la figura 5. Figura 5: Subsistemas de una terminal de contenedores 23 3.3.1. Subsistema Conexión buque-muelle En este proceso se realiza una serie de operaciones que se podrían resumir a grandes rasgos como las actividades de carga y descarga. Los procesos en el muelle involucran la participación de los buques, obligando la intervención de agentes como los armadores, los navieros y sobre todo los consignatarios (intermediario o agente que actúa en nombre del propietario del buque). El proceso de importación comienza cuando el buque está atracado en el muelle. En este momento, las grúas proceden a descargar los diferentes contenedores para que el resto de los mecanismos y maquinarias como los straddle carriers, lo lleven a su destino final. Esta tarea requiere de la organización de todos los agentes para conseguir la mayor productividad posible, evitando que durante el instante de tiempo que la grúa está descargando contenedores, haya maquinaria parada. El proceso de exportación es el mismo proceso descrito anteriormente, pero realizado de forma inversa. En este caso, en la búsqueda de la productividad, se debe organizar la maquinaria de tal forma que la grúa no esté parada esperando la llegada de contenedores. Además, a la hora de cargar el buque se debe tener en cuenta la estabilidad de este y es por eso por lo que los contenedores más pesado se deben cargar primero. Figura 6: Muelle de Lezo Fuente: Pasaia Port 3.3.2. Subsistema de Almacenaje Este subsistema se encuentra entre el subsistema de conexión buque-muelle y el subsistema de recepción y entrega. Abarca la mayor parte de la terminal y responde a la necesidad de tener una zona para el almacenaje de contenedores en proporción con la demanda de estos. El almacenamiento de contenedores es uno de los problemas que se intenta resolver continuamente debido al aumento de estos cada año, aunque el objetivo principal de este subsistema sea proporcionar una forma eficaz para atender las distintas variaciones que existen entre la importación y la exportación y la recepción y entrega de las mercancías desde o hacia los distintos modos de transporte. Dependiendo de la maquinaria y los medios que se dispongan para el almacenaje, el diseño de este subsistema puede variar. El subsistema de almacenaje permite el apilado y una posible automatización. El número de filas, columnas o contenedores apilados uno encima de otro dependerá de las características de las máquinas que posea la terminal, como las grúas, los straddle carriers, etc. Los contenedores que salen o entran a la zona de almacenaje pueden estar marcados con las siguientes características: exportación, importación, vacíos, llenos, frigoríficos, larga distancia, etc. Por lo tanto, la distribución y transferencia se debe realizar en el menor tiempo posible y de la mejor forma posible. Existen tres estrategias para almacenar contenedores y son las siguientes: ➢ Ubicación de los contenedores de importación cerca de las puertas que dan acceso a los camiones y los de exportación más cerca del muelle para facilitar los movimientos y acelerar el proceso ➢ Ubicación de los contendores de importación cerca del muelle y los de exportación cerca de la zona de acceso terrestre. ➢ Los contenedores pueden estar ubicados en cualquier parte de la zona de campa. Figura 7: Zona de almacenaje Fuente: www.archcontainers.com 3.3.3. Subsistema de interconexión y transferencia de contenedores Este subsistema asegura el transporte de contenedores entre todos los subsistemas. En él influye tanto la información para la gestión, como el propio movimiento de contenedores. Las decisiones estratégicas como la selección del tipo de conexiones tienen una gran importancia. ➢ Usando AGV se pueden obtener soluciones tecnológicas con alta automatización. ➢ Si el subsistema de almacenamiento posee carretillas pórtico, elevadoras o plataformas, estas se pueden usar para la interconexión. 25 3.3.4. Subsistema de recepción y entrega Está formado por las entradas, equipos e instalaciones necesarias para controlar y manipular las cargas que llegan y salen mediante transporte ferroviario y/o mediante camiones. Se puede dividir a su vez en otros dos subsistemas: ➢ El primero involucra la llegada de camiones y trenes generando colas a la entrada y tiempos de servicio, tiempo que se dedica a las labores administrativas, inspecciones, instrucciones sobre dónde deben recoger o entregar la carga, etc. Para evitar conflictos, la entrada de camiones es distinta que la salida de camiones. También puede ocurrir que la entrada y la salida sea la misma, pero destinando un número de puertas para cada flujo. ➢ El segundo está formado por las operaciones que se realizan desde que el camión entra, es cargado y sale de la terminal. El tiempo total incluye el tiempo de espera, el tiempo que tarda en ser cargado y el tiempo de servicio. La zona de espera de camiones puede tener dos configuraciones, tal y como se muestra en la figura 8: Figura 8: Zona de carga en paralelo y cuarto de círculo Además de en la zona de entrega (figura 9), los procesos de carga y descarga se pueden producirse en la zona de almacenaje (figura 10): Figura 9: Esquema general de carga y descarga Por último, se enumeran los principales fabricantes de buques portacontenedores del mundo actualmente: ➢ Stocznia Pólnocna en Polonia. ➢ Fincantieri en Italia. ➢ Odense Steel Shipyard en Dinamarca. ➢ Samsung Heavy Industries en Corea del Sur. ➢ Hyundai Heavy Industries en Corea del Sur. ➢ Daewoo Heavy Industries en Corea del Sur. 3.7. Equipos de manipulación de una terminal de contenedores La carga y descarga de contenedores no sería posible sin un conjunto de grúas y vehículos. Con el paso del tiempo se pretende alcanzar un cierto nivel de operaciones realizadas de forma automática y eso ha llevado a pensar en el desarrollo de un tipo de maquinaria diferente. A continuación, se describen los tipos de máquinas que más se usan en las terminales de contenedores: 3.7.1. Grúas Pórtico Es el principal elemento en una terminal de contenedores portuaria, debido a que es la única capaz de realizar las operaciones de carga y descarga de los buques. Su funcionamiento marca el ritmo de trabajo de toda la terminal. Las primeras grúas se diseñaron para cargar hasta 22,7 toneladas elevables a una altura de 15,6 metros y un alcance de 23,8 metros. Las diferentes grúas se pueden resumir en la tabla 2, en la que se recoge la evolución y la adaptación de las grúas a los diferentes tipos de buques. Su cambio físico se puede apreciar en la figura 17: Tipo Feeder Panamax Post Panamax Súper Post- Panamax Alcance delantero en contenedores 10 13 16 22 Altura bastidor telescópico (Spreader) 25 m 30.50 m 33 m 40 m Distancia entre carriles 15.24 m 15.24 m 30.48 m 30.48 m Capacidad bajo Spreader Hasta 40 t Hasta 50 t Hasta 65 t Hasta 65 t Translación del pórtico 30 m/min 45 m/min 45 m/min 45 m/min Spreader telescópico 20’/40’/45’ 20’/40’/45’ 20’/40’/45’ 20’/40’/45’ Tabla 2: Resumen de características de las grúas pórtico 33 En la figura 16 se puede ver una grúa pórtico para contenedores Super Post-Panamax. Figura 16: Grúa pórtico en el puerto de Cartagena . Fuente: nautiexpo.com En la figura 17 se muestra las diferentes medidas que puede tener las distintas partes de una grúa de pórtico. Figura 17: Evolución de la grúa pórtico Fuente: cadenadesuministro.com, 2013 3.7.2. Grúas pórtico de almacenamiento Dependiendo del grado de automatización de las terminales, el manejo de la entrada y salida de contenedores para colocarlos en bloques, estibas o pilas lo harán mediante grúas RTG (Grúas pórtico sobre neumáticos) o grúas RMG (grúas pórtico sobre rieles). Las grúas RTG requieren de un operador en la cabina. Tienen un tamaño de entre 5 y 8 contenedores de ancho y de entre 3 y 4 contenedores de alto. Su función principal es descargar camiones cogiendo los contenedores de los bloques y viceversa, tal y como se puede ver en la figura 18. Figura 18: Grúa RTG Fuente: mundoportuario.wordpress.com Las grúas RMG son más altas y anchas que las RTG. Funcionan totalmente con electricidad y los requisitos para la comunicación de datos es mayor debido a la automatización de funciones. Un ejemplo de grúa RMG se puede apreciar en la figura 19, esta viaja por los rieles para levantar y apilar contenedores de 20 y 40 pies. El contenedor se levanta mediante un esparcidor telescópico conectado a cables. Figura 19: Grúa RMG Fuente: conductix.us 3.7.3. Carretilla Pórtico o Straddle Carriers Esta máquina se encarga de mover los contenedores que previamente otro equipo ha colocado en tierra. Pueden cargar dos contenedores de un TEU o un contenedor de dos TEUs y son capaces de apilar hasta una altura de cuatro contenedores. En la figura 20 se puede ver una carretilla pórtico trasladando un contenedor. Figura 20: Puerto de Rotterdam. Straddle Carrier de Liebherr en el Delta Terminal ECT (Países Bajos) Fuente: Liebherr.com 3.7.4. Grúas polivalentes Tiene diferentes funciones y entre ellas cabe destacar que permite manejar varios tipos de carga y, por lo tanto, contenedores. Su presencia es cada vez menor (se encuentran aún en puertos poco desarrollados o con poca capacidad para hacerlo). En la figura 21 se puede apreciar una grúa polivalente ubicada en el puerto de Málaga. Figura 21: Grúa polivalente en el puerto de Málaga Fuente: Noatum maritime 37 3.7.5. Equipos de manipulación frontal Sirven para cargar, descargar y transportar contenedores por la terminal. Se pueden diferenciar entre camión puente (Reach Stacker) y carretilla elevadora de carga frontal (Front Lift Truck). ➢ Reach Stacker: Consta de un bastidor de gran altura y de un bastidor telescópico. Sirve para manejar contenedores de entre 20 y 40 pies y pueden llegar a formar largas filas apilando entre 3 y 4 contenedores de altura como se aprecia en la figura 22. Figura 22: Reach stacker Fuente: Liebherr.com ➢ Front Lift Truck: Tienen la misma configuración que las carretillas normales. Pueden llevar el bastidor telescópico sobre los carriles del mástil, sobre las horquillas de carga o sobre el tablero porta horquillas. Pueden manejar contenedores de entre 20 y 40 pies, apilando entre 3 y 4 alturas si están cargados y entre 5 o 6 si están vacíos. Figura 23: Front Lift Truck en el puerto de Johannesburgo Fuente: junkmail.com.za 3.7.6. Cabezas tractoras con plataformas Los camiones son máquinas muy requeridas en las terminales para el transporte horizontal de contenedores, ya que son más rápidos que los equipos comentados en la sección 3.7.5. Son capaces de transportar más de un contenedor dependiendo del número de plataformas que posea como se puede apreciar en la figura 24. Figura 24: Camión con plataformas Fuente: Tesis Carlos Arango 3.7.7. Vehículos Auto guiados Estos vehículos se han incorporado a las terminales de contenedores hace relativamente poco tiempo. Existen dos tipos de vehículos auto guiados: ➢ AGV (Automated Guided Vehicles): Es un robot capacitado para moverse de forma autónoma realizando tareas como el transporte de objetos pesados (ver figura 25) ➢ ALV (Automated Lift Vehicles): Permite cargar y descargar el contenedor sin necesidad de otro equipo de manipulación (a diferencia de los AGV). Pueden realizar el mismo trabajo que los camiones con remolques de autocarga o las carretillas pórtico, pero de forma automática. Figura 25: Vehículo AGV Fuente: nauticexpo.es 39 3.7.8. Remolques portacontenedor autocarga Remolques con un sistema para cargar y descargar contenedores sin ningún tipo de ayuda. Pueden apilar contenedores a una o dos alturas. Figura 26: Remolque portacontenedor autocarga Fuente: DPWORLD, 2014 3.8. Operativas de terminales de contenedores portuarias Para planificar y tratar de garantizar una explotación eficiente de las terminales portuarias se debe cambiar el modo de funcionamiento para que se asemeje lo máximo posible a un flujo continuo de producción, compuesto por una serie de fases formando una cadena. Cada eslabón de dicha cadena debe optimizarse individualmente, ya que como afirman muchos autores, “es imposible obtener buenos resultados si se optimiza una terminal de contenedores portuaria como un conjunto, debido a la diversidad de máquinas de manipulación existente”. La mayor parte del tiempo que se consume en un puerto está asociado a las operaciones de carga y descarga. Por ello, se deben planificar las operaciones desde la asignación de muelles, los tiempos de atraque hasta la planificación de las grúas y el orden de la carga y/o descarga. El encargado de descargar una zona del barco debe poseer información sobre la bodega del buque en la que se encuentran los contenedores. También se debe tener en cuenta la coordinación de las grúas pórtico con el resto de maquinaria en la terminal para que no haya interferencias. Las distintas operativas de una terminal de contenedores portuaria son: operativa de buque, del almacenado y apilado y de transferencia. 3.8.1. Operativa de buque La llegada de un buque a una terminal de contenedores portuaria supone la búsqueda de soluciones a tres problemas para minimizar el tiempo que los buques están atracados: ➢ La asignación de muelles. ➢ El plan maestro del muelle o planificación de la estiba. ➢ La programación de grúas. 3.8.1.1. Plan maestro del muelle Tanto las navieras como las terminales de contenedores portuarias elaboran su plan de estiba para cada TCP y buque, respectivamente. Esto ocasiona en algunos casos que dichos planes no coincidan, ya que las navieras buscan maximizar la utilización del buque y minimizar el tiempo de atraque, mientras que las TCP buscan minimizar las relocalizaciones. Se plantea la resolución de un problema multi objetivo para contentar a sendas partes. 3.8.1.2. Programación de grúas La asignación de grúas trata de minimizar el tiempo de atraque de los barcos y, en consecuencia, el tiempo de carga y descarga de los contenedores. Para resolver este problema se debe tener en cuenta: • Cantidad de grúas que atenderán a cada buque. • Tiempo de cada grúa asignada a cada sección de los buques. • Secuencia de carga y descarga a seguir por la grúa. • Distribución de grúas a cada sección. Si se gestiona correctamente las grúas podrán estar disponible lo antes posible para atender a otro buque. 3.8.2. Operativa de almacenaje y apilado El espacio en los puertos es un recurso cada vez más escaso, obligando a cambiar la estrategia de patio dependiendo de cada terminal en busca de la optimización de dicho recurso. El problema se divide en dos decisiones: la asignación de cada contenedor a una zona y la ubicación en una posición dentro de la zona. • Localización de contenedores en la zona de almacenamiento: Una vez que el contenedor llega a la terminal requiere de una grúa o carretilla para ser movido y de un espacio. Ambos recursos son limitados y eso acarrea un problema. El almacenamiento se puede hacer siguiendo diferentes criterios según el servicio (según el medio en el que saldrán los contenedores), por cliente, por destino, etc. • Relocalización de contenedores: Son movimientos no deseados que causan pérdidas de tiempo y dinero. Principalmente son causados por una colocación que no se corresponde con las fechas de salida, ubicación por pesos, etc. 41 3.8.3. Operativa de transferencia En una terminal de contenedores portuaria hay dos tipos de transporte: el transporte horizontal que moviliza los contenedores a través de toda la terminal. Este, a su vez, se divide en dos según la zona de la TCP en la que se lleve a cabo los desplazamientos, entre la zona de almacenaje y la zona de muelle y entre la zona de llegada de trenes y camiones y la zona de almacenaje. El otro tipo de movimientos es el vertical para apilar los contenedores. Esta operativa se divide en tres, debido a su complejidad: 3.8.3.1. Gestión del transporte en los muelles Para cargar y descargar hay que llevar los contenedores desde la zona de almacenaje (los diferentes bloques de contenedores) hasta las grúas asignadas a cada buque y viceversa. Esta zona se conoce como buffer y sirve para: ➢ Sincronizar vehículos de transporte con las grúas pórtico, evitando tiempos ociosos y cuellos de botella. ➢ Diseñar rutas para eliminar atascos en los muelles. ➢ Asignar de forma óptima los vehículos de transporte horizontal para conseguir un buen plan de funcionamiento general. Entre los muelles y la zona de almacenaje cada vez se hace más uso de operaciones automatizadas llevadas a cabo por los AGV y los ALV. 3.8.3.2. Gestión del transporte terrestre Se planifican todos los movimientos de contenedores en una terminal de contenedores portuaria, tanto los movimientos en la zona de almacenaje y la llegada de camiones, como los de aduanas, reubicación de contenedores vacíos, etc. 3.8.3.3. Gestión y programación de grúas Se usan grúas continuamente (tanto RTG como RMG) para: ➢ Relocalizar contenedores en la explanada. ➢ Recepción de contenedores que entran a la terminal para exportación. ➢ Recepción y entrega de contenedores a las máquinas de manipulación terrestre. El principal objetivo de la programación de las grúas en explanadas (Yard Crane Scheduling Problem) es reducir los tiempos de espera en las diferentes maquinarias de la terminal más minimizar el tiempo de operaciones del buque e incrementar el flujo total de contenedores manipulados en la terminal. [3] ∑𝑋0𝑗 𝑘 ≤ 𝑗∈𝑁 1 ∀ 𝑘∈𝐾 [4] 𝑋𝑖𝑗 𝑘=1 → 𝑡𝑖𝑗 𝑘= 𝑡𝑗𝑘 ∀ 𝑖∈𝑁, ∀ 𝑗∈𝑁 [5] 𝑡0 𝑘= 0 ∀ 𝑘∈𝐾 [6] 𝑡𝑖𝑘 ≤ 𝑇 ∀ 𝑘∈𝐾, ∀ 𝑖∈𝑁 [7] 𝑋𝑖𝑗 𝑘 ∈ {0,1} ∀ 𝑖∈𝑁, ∀ 𝑗∈𝑁, ∀ 𝑘∈𝐾 La restricción [1] establece que el nodo i debe ser visitado por un único camión. La restricción [2] indica la conservación del flujo, es lo mismo ir con un vehículo desde el nodo i al nodo j que hacerlo de forma inversa. La restricción [3] recoge que cualquier vehículo que se use solo puede empezar en un nodo a lo sumo. La restricción [4] se lleva a cabo si el vehículo k se mueve directamente del nodo i al j y, entonces la hora del nodo j es la hora que empieza el trabajo i más el tiempo en ir vacío del nodo i al nodo j. La restricción [5] aclara que el tiempo en el que comienza a usarse un camión es cero. La restricción [6] limita el tiempo de operación al máximo permitido por vehículo al día y, por último, la restricción [7] indica que dicha variable es booleana, adoptando el cero o el uno. 4.3.2. Multi-commodity problem En el mundo real, tanto los contenedores de 20 pies como los de 40 pies, deben transportarse de una forma diferente a la que se plantea en el problema básico. En este problema aparecerán los tres tipos de chasis con los que cuenta los diferentes camiones: para transportar un contenedor de 20 pies, para transportar un contenedor de 40 pies o el de tipo “combined” que permite transportar un contenedor de 40 pies o dos contenedores de 20 pies. El problema ¨multicommodity” pretende encontrar un conjunto de rutas de vehículos que satisfaga todas las órdenes de transporte a la vez que minimiza el coste total. En la resolución del problema todos los camiones poseen chasis tipo combined, ya que a priori son los más eficientes. 49 Para el modelado de dicho problema, se le asignará dos nodos a cada contenedor, uno que representa el nodo de recogida y otro que representa el nodo de entrega. Suponiendo que se tiene n contenedores {1,2, …, n} este conjunto representará el punto de partida de cada contenedor y los puntos de entrega serán representados por el conjunto {n+1, n+2, …, 2n} La notación utilizada para la formulación del modelo es: - 𝑁1={1,2,…,𝑛}: Conjunto de nodos de recogida. - 𝑁2={𝑛+1,𝑛+2,...,2𝑛}: Conjunto de nodos de entrega. - 𝑁=𝑁1+𝑁2+0 - 𝐾1: Conjunto de vehículos con chasis para un contenedor de 20 pies. - 𝐾2: Conjunto de vehículos con chasis “combined” para un contenedor de 40 pies o dos de 20 pies. - 𝐾3: Conjunto de vehículos con chasis para un contenedor de 40 pies - 𝐾= 𝐾1 + 𝐾2 + 𝐾3 - 𝑠𝑗: Pedido de recogida o entrega para el nodo j. Si un contenedor de 20 pies está cargado en el nodo j adopta el valor de 1. Si un contenedor de 40 pies está cargado en el nodo j, toma el valor de 2. Si un contenedor de 20 pies está descargado en el nodo j tomará el valor de -1 y si es un contenedor de 40 pies el que está descargado tomará el valor de -2. - 𝑇: Tiempo máximo de operación de un vehículo por día. - 𝑡𝑖𝑗: Tiempo de carga o descarga más el tiempo de viajar del nodo i al nodo j - 𝑐𝑖𝑗 𝑘: Coste de transportar desde el nodo i al nodo j con el vehículo k - 𝑋𝑖𝑗 𝑘: Adoptará el valor del 1 si el vehículo k viaja desde el nodo i al nodo j - 𝑡𝑖𝑘: hora de llegada del vehículo k al nodo i - 𝑤𝑖𝑘: Tamaño de los contenedores dejados en el vehículo k cuando este abandona el nodo i (nodo de recogida). La función objetivo se formula como la minimización del coste total de transporte con los tres tipos de vehículos disponibles para el movimiento de contenedores: Minimizar ∑∑∑𝑐𝑖𝑗 𝑘 ∙ 𝑘∈𝐾𝑗∈𝑁𝑖∈𝑁 𝑋𝑖𝑗 𝑘 s.a: [9] ∑∑𝑋𝑖𝑗 𝑘 = 1 ∀ 𝑖∈𝑁 𝑘∈𝐾𝑗∈𝑁 [10] ∑𝑋𝑖𝑗 𝑘 = ∑𝑋𝑗𝑖 𝑘 𝑗∈𝑁+ 𝑗∈𝑁+ ∀ 𝑘∈𝐾, ∀ 𝑖∈𝑁 [11] ∑𝑋0𝑗 𝑘 ≤ 𝑗∈𝑁 1 ∀ 𝑘∈𝐾 [12] ∑𝑋𝑖𝑗 𝑘 𝑗∈𝑁 =1 → 𝑡𝑖𝑘+𝑡𝑖𝑗 = 𝑡𝑛+𝑖 𝑘 ∀ 𝑖∈𝑁1, ∀ 𝑘∈𝐾 [13] 𝑋𝑖𝑗 𝑘=1 → 𝑡𝑖𝑗 𝑘≤ 𝑡𝑗𝑘 ∀ 𝑖∈𝑁, ∀ 𝑗∈𝑁, ∀ 𝑘∈𝐾, 𝑗≠𝑛+ 𝑖 [14] 𝑡0 𝑘= 0 ∀ 𝑘∈𝐾 [15] 𝑡𝑖𝑘 + 𝑡𝑖0 ≤ 𝑇 ∀ 𝑘∈𝐾, ∀ 𝑖∈𝑁2 [16] 𝑋𝑖𝑗 𝑘 = 1→ 𝑤𝑖𝑘 + 𝑠𝑗 ≤ 𝑤𝑗𝑘 ∀ 𝑖∈𝑁, ∀ 𝑗∈𝑁, ∀ 𝑘∈𝐾 [17] 𝑤0𝑘= 0 ∀ 𝑘∈𝐾 [18] 𝑤𝑖𝑘 {≤1 ∀ 𝑖∈𝑁, ∀ 𝑘∈𝐾1 ≤2 ∀ 𝑖∈𝑁, ∀ 𝑘∈𝐾2 =0 𝑜 =2 ∀ 𝑖∈𝑁, ∀ 𝑘∈𝐾3 [19] 𝑋𝑖𝑗 𝑘 ∈ {0,1} ∀ 𝑖∈𝑁, ∀ 𝑗∈𝑁, ∀ 𝑘∈𝐾 51 [20] 𝑡𝑖𝑘≥0,𝑤𝑖𝑘≥0 ∀ 𝑖∈𝑁, ∀ 𝑘∈𝐾 La restricción [9] indica que el nodo i debe ser visitado por solo un tipo de vehículo. La restricción [10] muestra la conservación del flujo, es lo mismo ir con un vehículo desde el nodo i al nodo j que hacerlo de forma inversa. La restricción [11] recoge que cualquier vehículo que se use solo puede empezar en un nodo como máximo. La restricción [12] muestra la relación entre el tiempo de realización de la recogida más el tiempo de viaje al punto de entrega y este debe ser menor o igual que el tiempo en el que se vaya a entregar. La restricción [13] se lleva a cabo si el vehículo k se mueve directamente del nodo i al j y, entonces la hora del nodo j es la hora que empieza el trabajo i más el tiempo en ir vacío del nodo i al nodo j. La restricción [14] y [15] indican tanto la limitación de tiempo de los vehículos y que se empieza a computar en cero. Desde la restricción [16] hasta la [18] lo que se indica es la compatibilidad entre las rutas y las cargas, así como las capacidades. El resto de las restricciones indican el tipo de variables y cómo deben ser sus valores. 5. Revisión de las metodologías de resolución Este tipo de problemas es de naturaleza NP-Hard y, por lo tanto, su resolución matemática mediante algún software implicaría un tiempo desorbitado de computación. Para resolverlo se pretende aplicar la heurística descrita en Ki Ho Chung et al. 2007 y se comparan sus resultados con el desarrollo de una nueva heurística propia. En este apartado se presentarán diferentes métodos para resolver problemas de transporte acompañados de una breve descripción. Seguidamente se desarrollará en profundidad la heurística del artículo y la heurística elegida para su resolución. 5.1. Métodos de resolución de problemas de transporte El problema de transporte o distribución es un problema de redes especial en programación lineal que se fundamenta en la necesidad de llevar unidades desde un punto de origen hacia un punto de destino. El nombre con el que se conoce a este tipo de problemas es el de Vehicle Routing Problem (VRP) o problema de ruteo de vehículos en español. El VRP es difícil de optimizar, ya que su objetivo es minimizar el coste asociado al transporte por las rutas de reparto y esto, a su vez, depende de diferentes características y restricciones que no pueden ser obviadas. Este problema aparece en muchos ámbitos de la logística, el transporte y la distribución y se caracteriza por tener distintas variantes: ➢ VRP con flota heterogénea: Vehículos diferentes entre sí. ➢ VRP con ventanas de tiempo: Los pedidos se deben entregar en un horario concretado. ➢ VRP con rutas abiertas: Los vehículos no vuelven al punto de inicio. ➢ VRP con pick up and delivery. Debido a que el VRP tiene origen en el problema de viajante (TSP: travelling salesman problema) en la tabla 3 se muestra una clasificación desde este punto de vista: Tabla 3: Clasificación de los problemas VRP Fuente: Solution of the vehicle routing problem for the potatoe distribution in Colombia 53 Su alta complejidad complica la obtención de soluciones óptimas y, por tanto, los problemas de este tipo se suelen resolver mediante la aplicación de heurísticas y metaheurísticas. 5.1.1. Algoritmos exactos Necesitan ser formulados como modelos de programación lineal enteros o muy parecidos. Pueden ser resueltos con métodos cuya forma de trabajar es ir acotando soluciones factibles hasta que alcanzan una solución factible final. Estas técnicas son apropiadas si se tiene un modelo matemático que representa la realidad a estudiar. Son búsquedas exhaustivas y, por lo tanto, ineficientes con problemas de un tamaño considerado. Son los llamados algoritmos Branch & Bound. Estos métodos siguen el llamado “Modelo de árbol”, donde el problema inicial sería la raíz y se van enumerando soluciones a través de una división del espacio en busca de subconjuntos de soluciones. Una vez acotado el problema, se exploran los subconjuntos de soluciones para descartar las ramas que proporcionan soluciones peores a la encontrada hasta el momento. Las ramas que superan la exploración vuelven a dividirse repitiendo el proceso. Existen numerosas variantes de formulación del problema VRP, ya que los algoritmos de “Modelo de árbol” se desarrollan adaptándose a la formulación de cada problema. Estas variantes han sido propuestas en libros de autores como Toth y Vigo [1] y de forma más reciente y actualizada en J.F Corderau et al. [2]. Además, se propusieron métodos como el Branch & cut que también se puede apreciar en publicaciones de G. Laporte, A. Campbell, entre otros. Se basa en el método de ramificación y poda (Branch and bound), pero incorpora planos de corte. Se empieza resolviendo el problema lineal sin restricciones enteras. Al obtener una solución óptima con un valor no entero para una variable que ha de serlo, mediante el uso de planos de corte se busca una restricción lineal de forma que se cumpla para todos los puntos factibles enteros y que no se cumpla por la solución óptima no entera obtenida. Si se puede encontrar dicha restricción, se incorpora al problema lineal, llegando a una nueva solución. Se repite este proceso hasta que se encuentre una solución entera y se pueda demostrar que es óptima o hasta que no se encuentren más planos de corte. A partir de entonces, se aplica el algoritmo de ramificación y poda. 5.1.2. Metaheurísticas Un gran número de problemas no pueden ser resueltos de forma óptima con los métodos convencionales debido a la complejidad de dichos problemas. Para obtener buenas soluciones en un espacio de tiempo razonable, se recurre a métodos aproximados. Por esta razón, en los últimos años se han ido desarrollando y validando un conjunto de metodologías conocidas como metaheurísticas. Las metaheurística tratan de guiar una heurística subordinada y combina métodos para explorar adecuadamente el espacio de soluciones. El Diccionario de la Real Academia de la Lengua lo define como una “técnica de la indagación y del descubrimiento”; o como “la manera de buscar la solución de un problema mediante métodos no rigurosos, es decir, reglas empíricas” Las metaheurísticas no garantizan la obtención del óptimo global, pero permiten encontrar soluciones de alta calidad. Parten de una solución inicial y, mediante iteraciones del algoritmo, se consiguen otras de las que una que cumpla unos criterios y/o restricciones será la elegida. A partir de esa solución se vuelve a iterar hasta alcanzar la condición de parada previamente establecida. Algunas de las metaheurísticas más usadas son: ➢ Algoritmos genéticos: Son metaheurísticas muy robustas basadas en población. Se basan en crear soluciones, evaluarlas y reutilizar las buenas para generar descendencia. Los algoritmos genéticos se fundamentan en tres principios que explican la evolución: la herencia, la codificación genética y la supervivencia del más fuerte y se puede diferenciar entre: o Algoritmos genéticos generacionales: Para pasar de una población a otra se escogen soluciones de forma aleatoria en base a una determinada probabilidad proporcional fitness. Las soluciones se cruzan y mutan para dar lugar a otros hijos que formarán la siguiente generación. o Algoritmos genéticos régimen permanente: De una generación a otra únicamente un individuo se modifica (por cruce o mutación) y forma parte de la siguiente generación entrando por el peor de los individuos. ➢ Iterated local search: Es una metaheurística basada en vecindad que parte de una solución inicial a la que se le realiza una búsqueda local para hallar un óptimo local. Una vez encontrado se aplica una perturbación (un movimiento de mayor magnitud que hace que se aleje del valle en el que se encuentra, moviéndose hacia otro cercano. Hay que tener cuidado de no realizar una perturbación demasiado grande como para que se sitúe en una solución aleatoria) para alejarse del óptimo local y alcanzar otro valle donde se aplica de nuevo búsqueda local para llegar a otro óptimo local. Así sucesivamente hasta alcanzar la condición de parada. La búsqueda local es una rutina de mejora que parte de una solución inicial y estudia sus vecinos (soluciones cercanas que se obtienen mediante movimientos a los que se le asocia una variación de la función objetivo que determina si la nueva solución es mejor que la de partida). ➢ Grasp: Es una metaheurística basada en vecindad que se caracteriza por ser un método miope y aleatorio. Se desarrolla en P iteraciones, cada una de ellas compuestas por una fase constructiva y una fase de mejora, alcanzándose un óptimo local en cada iteración. Al realizar las P iteraciones, se escoge el mejor de los óptimos locales obtenidos. o La fase constructiva parte de una “hoja en blanco” y se lleva a cabo en T pasos. En cada paso se tendrá una solución parcial a la que hay que añadirle el siguiente elemento. Los elementos que no han sido incorporados aún a la solución parcial se encuentran en una lista de candidatos con un índice de greedy cada uno (muestra lo ventajoso que es añadir ese elemento a la solución parcial). Para que el método tenga aleatoriedad no se añade a la solución el elemento con mayor índice, sino que se genera la lista de candidatos restringida en la que entran aleatoriamente los elementos que tienen un índice de greedy dentro del umbral. Finalmente se añade a la solución parcial el mejor elemento de la lista restringida de candidatos y se pasa al siguiente paso hasta obtener una solución completa. o La fase de mejora consiste en aplicar una rutina para mejorar la solución obtenida en la fase constructiva. Normalmente se aplica búsqueda local. 55 ➢ Búsqueda en vecindad variable: Es una familia de metaheurísticas basadas en vecindad cuya característica principal es el uso de diferentes tipos de vecindades para la fase de búsqueda del óptimo local. o VND: Se parte de una solución inicial y se definen N niveles de vecindades distintos. Se aplica la primera vecindad a la solución de partida y se buscará en la vecindad al completo, pudiéndose dar dos casos: encontrar una solución mejor en esa vecindad, por lo que se actualizaría la solución de partida a esa encontrada o no encontrar una solución mejor en esa vecindad y se pasaría a explorar en el segundo tipo de vecindad definido, pudiéndose dar otra vez los dos casos. El método no garantiza optimalidad, pero asegura que la solución es simultáneamente óptimo local de N tipos de vecindades diferentes. o RVNS: Se parte de una solución inicial y se definen en N diferentes vecindades. Se aplica la primera vecindad a la solución de partida, pero solo se buscará un vecino, pudiéndose dar los dos casos citados en la variante VND. El método termina cuando se cumple la condición de terminación que suele estar marcada por el un número de iteraciones y/o tipos de vecindades definidas. ➢ Simulated Annealing (recocido simulado): Metaheurística basada en vecindad que se fundamenta en los principios que rigen el enfriamiento de los metales. Se parte de una solución a la que se le aplica la rutina de búsqueda local hasta llegar a un óptimo local al que se le aplica posteriormente una perturbación. Esta metaheurística acepta empeoramientos de la función objetivo con una determinada probabilidad en la que existe un parámetro T que simula la temperatura de enfriamiento de los metales. A medida que se realizan iteraciones, T va descendiendo y se aceptarán soluciones peores. Fijada una T inicial, se harán L iteraciones hasta que esta sea modificada. Cuando L tiende a infinito se puede obtener el óptimo, pero si no se realizan infinitas iteraciones, los resultados que se obtienen son muy buenos en ocasiones y muy malos en otros. ➢ Scatter Search: Es una metaheurística basada en población que genera soluciones de forma sistemática para mejorar las anteriores y que pasen a la siguiente generación. Primero se define un método que genere soluciones de forma sistemática y a cada solución se le aplica un método de mejora. Posteriormente se tiene una población inicial, se le extrae un número de soluciones que forman el conjunto “Refset” a la que se le aplica otro método sistemático, pero esta vez para generar subconjuntos. Estos subconjuntos se cruzan y a las soluciones obtenidas se les aplica otro método de mejora y se actualiza el conjunto “Refset”, si procede. ➢ Búsqueda tabú: Parte de una solución aleatoria inicial y se pretende encontrar otra que mejore la función objetivo. En cada iteración se van almacenando las posibles soluciones y se marcan como tabú para que el algoritmo no entre en bucle provocando que no pueda escapar de los óptimos locales. ➢ Colonia de hormigas: Método basado en la naturaleza. Por el hecho de que las hormigas dejan huella mediante la segregación de feromonas cuando exploran distintas direcciones del espacio de soluciones factibles, ayuda a otras hormigas a conocer dichas direcciones para ser exploradas y que no caigan en un óptimo local. En cada iteración las feromonas van disminuyendo. 5.1.3. Métodos heurísticos El concepto de heurística tiene una definición difícil de acotar. Newel, Shaw y Simon en 1963 dijeron que era “un proceso que puede resolver un problema dado, pero que no ofrece garantías de que lo hará”. La idea consiste en concentrar toda la información entorno a la función de evaluación heurística. Esta función asocia a cada estado del espacio de estados una cierta cantidad numérica para evaluar de alguna forma cómo de prometedor es ese estado para acceder a un estado objetivo. Las heurísticas se caracterizan porque no garantizan optimalidad. Si encuentran una solución, no se garantiza que reúna las mejores propiedades y en algunas ocasiones (aunque no se puede determinar de antemano) encontrarán una solución aceptablemente buena en un tiempo razonable. Las heurísticas para el problema VRP se clasificaron por Toth y Vigo en 2002 dependiendo de su labor: • Constructivas: van formando una solución de forma evolutiva, incorporando el elemento que cumpla con mejor valor el criterio establecido. Dentro de este tipo destaca el algoritmo de ahorros de Clarke and Wright. o Fue definida en 1964, tratándose de la heurística más significativa para resolver problemas VRP. Se tiene una serie de vehículos limitados y un depósito general para abastecer a n clientes de forma que las rutas que se obtengan sean las de menor coste. El depósito se denota 0 y los clientes van desde 1 hasta n. Los costes de ir desde el depósito a cada cliente (c0j) y los costes de desplazamiento entre cada pareja de clientes (Cij) son conocidos y simétricos. Los pasos que sigue el algoritmo son los siguientes: ▪ 1. Se crean n rutas, una por cada cliente, de la forma (0, i, 0). Los vehículos parten del depósito, realizan la entrega a un cliente y vuelven al depósito. ▪ 2. Se calcula el ahorro para cada unión de clientes como: ▪ 3. Se ordenan los resultados de forma decreciente. ▪ 4. Se escoge la pareja de clientes que han dado lugar al ahorro de mayor valor y, si se cumplen todas las restricciones, se unen, introduciéndose el arco (i, j) y eliminándose los arcos (i, 0) y (j, 0). ▪ 5. Se repite el paso anterior hasta que no se encuentren más uniones factibles. • De mejora: la solución se obtiene a partir de una solución factible. Intentan mejorar cada posible solución mediante la prueba de intercambiar la secuencia de vértices dentro o fuera de las rutas. • Técnicas de relajación: guardan una estrecha relación con la programación lineal entera. La más conocida de todas es la Relajación Lagrangiana, que consiste en descomponer un modelo lineal entero en un conjunto de restricciones difíciles y otras más fáciles, relajando las primeras, al pasarlas a la función objetivo multiplicándolas por un factor que penaliza, de forma análoga a lo que se hacía con el método de los multiplicadores de Lagrange. 57 6. Heurística de resolución propuesta 6.1. Interpretación 1 Tanto el problema básico como el Multi-commodity problem son de clase NP-hard. Por dicho motivo, para la resolución se ha propuesto un algoritmo basado en una heurística de inserción (Rosenkrantz et al., 1977) descrita en Ki Ho Chung et al., 2007. Como ya se citó anteriormente, el problema básico es un problema MTSP que se puede resolver de forma relativamente fácil, debido a que es un problema muy estudiado y existen numerosas metodologías para resolverlo, aun así, a dicho problema también se le aplicará la heurística. Suponiendo que se tiene un vehículo k que pertenece a K, tal que sigue una ruta del tipo (0, …, p, p+1, …, q, q+1, …, 0), si se debe recoger un contenedor en el nodo i y entregarlo en el nodo n+i, existen dos formas de inserción de la recogida y entrega del contenedor i en la ruta actual del vehículo k, tal y como se muestra a continuación. 1. El vehículo k debe ir de p a p+1 y en ese trayecto podría coger el contenedor i e ir hacia p+1, continuando con su ruta que pasa por q en dirección a q+1. En ese trayecto podría dejar el contenedor i en su nodo de entrega n+i (ver figura 29). Figura 29: Primera forma de inserción Fuente: Elaboración propia 2. Si el vehículo k debe ir de p a p+1 podría “desviarse” para recoger al contenedor i y llevarlo directamente a su punto de entrega n+i para posteriormente seguir con su ruta de forma normal (ver figura 30). Figura 30: Segunda forma de inserción Fuente: Elaboración propia 8. Conclusiones Cuando se tiene un problema con un gran número de variables y restricciones, la aplicación de métodos exactos posee mucha complejidad y su resolución conlleva mucho tiempo. Por ello, las metaheurísticas y heurísticas, como en este caso, asumen un papel muy importante en la obtención de una solución relativamente buena en un tiempo de resolución mucho menor. La realización de dicho problema se ha realizado por el gran interés que presenta el movimiento de contenedores en las terminales portuarias, ya que este sector está en continuo crecimiento y mediante la optimización del transporte en dichas terminales se pueden ahorrar numerosos costes. Con el desarrollo y posterior codificación de la heurística mediante Python, se ha conseguido la minimización de tiempos y/o costes de los camiones necesarios para realizar todas las órdenes de trabajo teniendo en cuenta los tiempos de carga y descarga de los contenedores. Optimizando dichas rutas se consigue descongestionar los patios en los que se encuentran los contenedores, cuyo espacio es limitado y acarrea tantos problemas. El proyecto consta de dos problemas, uno básico y otro con el chasis del camión distinto a lo que es habitual. En el artículo seleccionado no se lleva a cabo la aplicación de la heurística para el problema básico, por lo que no se pueden comparar los resultados que se han obtenido con la heurística propia. Como se ha comentado anteriormente y, debido a que la capacidad de cada camión es de un contenedor, se necesitarían 110 camiones, 60 con chasis tipo 2 (transporta un contenedor de 40 pies) y 50 con chasis de tipo 1(transporta un contenedor de 20 pies). El problema básico se ha intentado realizar con la heurística descrita en el artículo Ki Ho Chung et al., 2007, pero el tiempo de computación es demasiado grande debido al procesador del ordenador en el que se ha realizado la compilación. Sin embargo, gracias al desarrollo de la heurística propia, se ha podido obtener una solución en un tiempo de computación inferior a dos segundos. No se sabe si los resultados obtenidos con dicha heurística son muy buenos, ya que el artículo no posee una solución de referencia, pero se obtiene una posible solución en muy poco tiempo. En cuanto al problema con los camiones que poseen el chasis tipo 3 o “combined” la heurística descrita en el artículo comenta que, tras su aplicación, se necesitan93 camiones trabajando durante una media de 7.845 horas, mientras que con la heurística propia se necesitarían 86 camiones trabajando durante una media de 7.58817 horas. El código de este trabajo se ha pretendido realizar de la forma más limpia y estructurada en funciones para que el tiempo de compilación se redujera lo máximo posible, aunque quizás se puede depurar más. Para la ejecución del programa se han cargado una serie de constantes como el coste de usar cada tipo de camión, el número de horas de trabajo de los camioneros, el coste por unidad de distancia y el garaje de donde parten y a donde deben llegar los camiones. Todas estas constantes pueden ser cambiadas dependiendo de las características del problema, pudiendo obtener distintos resultados que permitirían comparar y decidir. 65 9. Bibliografía P. Tot y D. Vigo. The Vehicle Routing Problem (Monographs on Discrete Mathematics and Applications), Philadelphia, PA, 2002. WY. Yap y JSL. Lam (2004) An interpretation of inter-container port relationships from the demand perspective. Maritime Policy and Management, 31: 337–355. F. Alonso, M.J. Álvarez y J.E. Beasley (2007). A Tabu Search Algorithm for the Periodic Vehicle Routing Problem with Multiple Vehicle Trips and Accessibility Restrictions”, Journal of the Operational Research Society, 59: 5-11 S. Ashour, J. Vega y R.G. Parker (1972). A heuristic for travelling salesman problems, Transportation Research, 6: 187-195. R. Baldacci, P. Toth y D. Vigo (2007). Recent advances in vehicle routing exact algorithms, 4OR A Quarterly Journal of Operations Research, 5: 269-298. R. Baldacci Y A. Mingozzi (2009). A unified exact method for solving different classes of vehicle routing problems, Mathematical Programming Serie A, 2: 347-380 J.E. Beasley y N. Christofides (1997). Vehicle routing with a sparse feasibility graph, European Journal of Operational Research, 98: 499-511 J.E. Bell, P.R. McMullen: (2004). Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics.18: 41-48 H. Min. The multiple vehicle routing problem with simultaneous delivery and pick up points, Transportation Research, vol. 23, n° 5. pp. 377-386, 1989. G. Berbeglia, J.F. Cordeau, I. Gribkovskaia, y G. Laporte, Statics pickup and delivery problems. Sociedad de Estadística e Investigación Operativa, Springer, 2007, pp. 1-31. G. Berbeglia, J. F. Cordeau, y G. Laporte, Dynamic pick up and delivery problems, European Journal of Operational Research- ELSEVIER. pp. 8-15, 2009. N. Liu, X Li, B. Mi, y H. Ma Zhang (2010). Improvement research on vehicle routing problem with simultaneous delivery and pickup with time windows for barreled water, Industrial Engineering and Engineering Management- IEEE, pp. 1347-1350, 2010. L. Chun-Hua, Z. Hong, y Z. Jian. (2009). Vehicle routing problem with time window and simultaneous pickups and deliveries, Industrial Engineering and Engineering Management, IE&EM '09, 16th International Conference on 2009, pp. 685-689. Y. Qu y J. F. Bard, The heterogeneous pickup and delivery problem with configurable vehicle capacity, European Journal of Operational Research-ELSEVIER Transportation Research. Part C. Emerging Technologies, pp. 1-20, 2013. T. E. Tzoreff, D. Granot, F. Granot, y G. Sosic. (2002). The vehicle routing problem with pickups and deliveries on some special graphs, European Journal of Operational Research- ELSEVIER, pp. 193-229, 2002. H. N. Psaraftis. (2011). A multi-commodity, capacitated pickup and delivery problem: The single and two vehicle cases, European Journal of Operational Research-ELSEVIER, pp. 572-580, 2011. G. Mosheiov. (1998). Vehicle routing with pickup and delivery: tour partitioning heuristics, European Journal of Operational Research-ELSEVIER, vol. 34, n°. 3, pp. 669-684, 1998. R. Dondo y J. Cerdá. (2013). A sweep heuristic based formulation for the vehicle routing problem with cross-docking. European Journal of Operational Research-ELSEVIER, Part B 40, pp. 293-311. W. Nanry and J. W. & Barnes (2000). Solving the pickup and delivery problem with time windows using reactive tabu search, European Journal of Operational Research-ELSEVIER, Part B 34, pp. 107-121, 2000. AENOR. UNE 117101:2003 Contenedores de la serie I. Clasificación, dimensiones y masas brutas máximas. UNCTAD. El transporte marítimo 2017. UNCTAD. El transporte marítimo 2013. F.H. Cullen, J.J. Jarvis Y H.D. Ratliff (1981). Set partitioning based heuristics for interactive routing. Networks, 11, 125–143. Y. Dumas, J. Desrosiers, y F. Soumis (1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54, 7–22. H.N. Psaraftis (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 14, 130–154. H.N. Psaraftis (1983). An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transportation Science, 17, 351–357. D. Rosenkrantz, R. Sterns y P. Lewis (1977). An analysis of several heuristics for the traveling salesman problem SIAM. Journal of Computing, 6, 563–581. 67 ANEXO 1 SOLUCIÓN CAMIONES CHASIS TIPO 1 - Camión 1 (490€): - 4p5p4p5p4p5p4p5p4p5p4p5p4p5p4p5p4p5p4p5p7p4p5p7p4p5p7p4p54 en 470 min. 28 de 483 p. - Camión 2 (480€): 4p5p7p4p5p7p4p5p7p4p6p4p6p4p6p4p6p4p6p4p6p4p6p3p4p64 en 460 min. 53 de 483 p. - Camión 3 (500€): 4p6p3p4p6p3p4p6p3p4p6p3p4p6p3p4p6p3p4 en 480 min. 71 de 483p. - Camión 4 (500€): 4p6p3p4p6p3p4p6p3p4p7p4p7p4p7p4p7p4p7p4p7p4 en 480 min. 92 de 483p. - Camión 5 (500€): 4p7p4p7p4p7p4p7p4p7p4p7p4p7p4p7p4p7p4p7p4p7p5p74 en 480 min. 115 de 483 p. - Camión 6 (500€): 4p7p5p7p5p7p5p7p5p7p5p7p5p7p5p7p5p7p5p74 en 480 min. 134 de 483 p. - Camión 7 (440€): 4p3p4p3p4p3p4p0p4p0p4p0p4 en 420 min. 146 de 483 p. - Camión 8 (485€): 4p0p7p5p7p5p7p5p7p5p7p5p7p5p7p5p7p54 en 465 min. 163 de 483 p. - Camión 9 (455€): 4p0p7p5p7p5p7p5p7p5p7p2p7p2p74 en 435 min. 177 de 483 p. - Camión 10 (465€): 4p0p7p2p7p2p7p2p7p2p7p2p74 en 445 min. 189 de 483 p. - Camión 11 (465€): 4p0p7p2p7p2p7p2p7p2p7p2p74 en 445 min. 201 de 483 p. - Camión 12 (480€): 4p0p7p2p7p2p4p0p7p2p4p04 en 460 min. 212 de 483 p. - Camión 13 (500€): 4p0p7p2p4p0p7p2p4p0p7p2p4 en 480 min. 224 de 483 p. - Camión 14 (475€): 4p0p7p2p5p7p2p5p2p5p2p54 en 455 min. 235 de 483 p. - Camión 15 (460€): 4p0p7p2p5p2p5p2p5p2p54 en 440 min. 245 de 483 p. - Camión 16 (500€): 4p1p4p1p4p1p4p1p3p4p1p3p4 en 480 min. 257 de 483 p. - Camión 17 (500€): 4p1p3p4p1p3p4p1p3p4p1p3p4 en 480 min. 269 de 483 p. - Camión 18 (500€): 4p1p3p4p1p3p4p1p3p4p1p3p4 en 480 min. 281 de 483 p. - Camión 19 (450€): 4p1p3p4p1p3p4p1p3p4p14 en 430 min. 291 de 483 p. - Camión 20 (470€): 4p1p0p7p2p56p3p4p1p0p74 en 450 min. 301 de 483 p. - Camión 21 (480€): 4p1p0p7p2p56p3p4p2p56p3p64 en 460 min. 312 de 483 p. - Camión 22 (440€): 4p2p56p3p6p3p64p2p57p2p54 en 420 min. 322 de 483 p. - Camión 23 (495€): 47p2p57p2p57p2p57p2p57p2p54 en 475 min. 332 de 483 p. - Camión 24 (440€): 43p63p63p63p63p63p63p64 en 420 min. 339 de 483 p. - Camión 25 (495€): 47p0p7p0p1p0p1p0p14 en 475 min. 347 de 483 p. - Camión 26 (465€): 47p0p1p0p1p0p1p04 en 445 min. 354 de 483 p. - Camión 27 (465€): 47p0p1p0p1p0p1p04 en 445 min. 361 de 483 p. - Camión 28 (465€): 47p0p1p0p1p0p1p04 en 445 min. 368 de 483 p. - Camión 29 (465€): 47p0p1p0p1p0p1p04 en 445 min. 375 de 483 p. - Camión 30 (465€): 47p0p1p0p1p0p1p04 en 445 min. 382 de 483 p. - Camión 31 (465€): 47p0p1p0p1p0p1p04 en 445 min. 389 de 483 p. - Camión 32 (480€): 47p0p1p0p12p57p0p14 en 460 min. 396 de 483 p. - Camión 33 (495€): 47p0p12p57p0p12p57p04 en 475 min. 403 de 483 p. - Camión 34 (495€): 47p0p12p57p0p12p57p04 en 475 min. 410 de 483 p. - Camión 35 (495€): 47p0p12p57p0p12p57p04 en 475 min. 417 de 483 p. - Camión 36 (445€): 47p0p17p0p17p0p14 en 425 min. 423 de 483 p. - Camión 37 (445€): 47p0p17p0p17p0p14 en 425 min. 429 de 483 p. - Camión 38 (445€): 47p0p17p0p17p0p14 en 425 min. 435 de 483 p. - Camión 39 (435€): 47p0p13p13p13p14 en 415 min. 440 de 483 p. - Camión 40 (410€): 43p13p13p10p14 en 390 min. 444 de 483 p. - Camión 41 (470€): 40p10p10p10p14 en 450 min. 448 de 483 p. - Camión 42 (470€): 40p10p10p10p14 en 450 min. 452 de 483 p. - Camión 43 (470€): 40p10p10p10p14 en 450 min. 456 de 483 p. - Camión 44 (470€): 40p10p10p10p14 en 450 min. 460 de 483 p. - Camión 45 (470€): 40p10p10p10p14 en 450 min. 464 de 483 p. - Camión 46 (470€): 40p10p10p10p14 en 450 min. 468 de 483 p. - Camión 47 (470€): 40p10p10p10p14 en 450 min. 472 de 483 p. - Camión 48 (470€): 40p10p10p10p14 en 450 min. 476 de 483 p. - Camión 49 (470€): 40p10p10p10p14 en 450 min. 480 de 483 p. - Camión 50 (360€): 40p10p10p14 en 340 min. 483 de 483 p. SOLUCIÓN CAMIONES CHASIS TIPO 2 - Camión 1 (500€): 4P5P4P5P4P5P4P5P4P5P4P5P4P5P4P5P4P5P4P5P7P4P5P7P4P5P7P4P54 en 470 min. 28 de 679 P. - Camión 2 (500€): 4P5P7P4P5P7P4P5P7P4P5P7P4P5P7P4P5P7P4P5P7P4P5P74 en 470 min. 51 de 679 P. - Camión 3 (500€): 4P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P54 en 470 min. 70 de 679 P. - Camión 4 (500€): 4P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P54 en 470 min. 89 de 679 P. - Camión 5 (510€): 4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4 en 480 min. 121 de 679 P. - Camión 6 (510€): 4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4 en 480 min. 153 de 679 P. - Camión 7 (470€): 4P6P4P6P4P6P4P6P4P6P4P6P4P6P3P4P6P3P4P6P3P4P64 en 440 min. 175 de 679 P. - Camión 8 (500€): 4P6P3P4P6P3P4P6P3P4P6P3P4P7P5P7P5P7P54 en 470 min. 193 de 679 P. - Camión 9 (510€): 4P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P5P74 en 480 min. 212 de 679 P. - Camión 10 (440€): 4P7P5P7P5P7P2P7P2P7P2P7P2P74 en 410 min. 225 de 679 P. - Camión 11 (510€): 4P3P4P3P4P3P4P3P4P3P4P3P4P3P4P3P4 en 480 min. 241 de 679 P. - Camión 12 (500€): 4P3P4P3P4P3P65P7P0P4P3P65P7P04 en 470 min. 254 de 679 P. - Camión 13 (495€): 4P3P65P7P0P7P0P7P0P7P0P74 en 465 min. 265 de 679 P. - Camión 14 (500€): 4P3P64P3P64P3P64P3P64P3P64P3P64P34 en 470 min. 278 de 679 P. - Camión 15 (460€): 4P3P64P3P64P3P1P4P3P1P4P34 en 430 min. 289 de 679 P. - Camión 16 (485€): 4P3P1P4P3P1P4P3P1P4P0P74 en 455 min. 300 de 679 P. - Camión 17 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 310 de 679 P. - Camión 18 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 320 de 679 P. - Camión 19 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 330 de 679 P. - Camión 20 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 340 de 679 P. - Camión 21 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 350 de 679 P. - Camión 22 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 360 de 679 P. 69 - Camión 23 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 370 de 679 P. - Camión 24 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 380 de 679 P. - Camión 25 (510€): 4P0P7P0P7P0P7P0P1P4P04 en 480 min. 390 de 679 P. - Camión 26 (450€): 4P0P1P4P0P1P4P0P1P4 en 420 min. 399 de 679 P. - Camión 27 (450€): 4P0P1P4P0P1P4P0P1P4 en 420 min. 408 de 679 P. - Camión 28 (450€): 4P0P1P4P0P1P4P0P1P4 en 420 min. 417 de 679 P. - Camión 29 (450€): 4P0P1P4P0P1P4P0P1P4 en 420 min. 426 de 679 P. - Camión 30 (450€): 4P0P1P4P0P1P4P0P1P4 en 420 min. 435 de 679 P. - Camión 31 (510€): 4P1P4P1P4P1P4P1P4P1P4P1P4 en 480 min. 447 de 679 P. - Camión 32 (495€): 4P1P4P1P4P2P7P0P1P4P2P74 en 465 min. 458 de 679 P. - Camión 33 (470€): 4P2P7P0P1P4P2P7P0P1P4 en 440 min. 468 de 679 P. - Camión 34 (505€): 4P2P7P0P1P4P2P74P2P74P2P74 en 475 min. 479 de 679 P. - Camión 35 (435€): 4P2P74P2P4P2P4P2P4P2P4 en 405 min. 489 de 679 P. - Camión 36 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 501 de 679 P. - Camión 37 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 513 de 679 P. - Camión 38 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 525 de 679 P. - Camión 39 (500€): 4P2P4P2P4P2P4P2P5P23P1P4 en 470 min. 536 de 679 P. - Camión 40 (450€): 4P23P1P4P23P1P4P23P1P4 en 420 min. 545 de 679 P. - Camión 41 (450€): 4P23P1P4P23P1P4P23P1P4 en 420 min. 554 de 679 P. - Camión 42 (450€): 4P23P1P4P23P1P4P23P1P4 en 420 min. 563 de 679 P. - Camión 43 (450€): 4P23P1P4P23P1P4P23P1P4 en 420 min. 572 de 679 P. - Camión 44 (510€): 4P23P1P45P23P1P3P1P3P14 en 480 min. 581 de 679 P. - Camión 45 (510€): 45P23P1P3P1P3P1P3P1P34 en 480 min. 590 de 679 P. - Camión 46 (490€): 45P23P1P3P1P3P1P35P24 en 460 min. 598 de 679 P. - Camión 47 (480€): 45P21P35P21P35P21P34 en 450 min. 604 de 679 P. - Camión 48 (480€): 45P21P35P21P35P21P34 en 450 min. 610 de 679 P. - Camión 49 (480€): 45P21P35P21P35P21P34 en 450 min. 616 de 679 P. - Camión 50 (480€): 45P21P35P21P35P21P34 en 450 min. 622 de 679 P. - Camión 51 (480€): 45P21P35P21P35P21P34 en 450 min. 628 de 679 P. - Camión 52 (480€): 45P21P35P21P35P21P34 en 450 min. 634 de 679 P. - Camión 53 (480€): 45P21P35P21P35P21P34 en 450 min. 640 de 679 P. - Camión 54 (480€): 45P21P35P21P35P21P34 en 450 min. 646 de 679 P. - Camión 55 (480€): 45P21P35P21P35P21P34 en 450 min. 652 de 679 P. - Camión 56 (510€): 45P25P25P25P25P25P24 en 480 min. 658 de 679 P. - Camión 57 (480€): 45P25P25P20P1P0P14 en 450 min. 664 de 679 P. - Camión 58 (510€): 40P1P0P1P0P1P0P14 en 480 min. 671 de 679 P. - Camión 59 (510€): 40P1P0P1P0P1P0P14 en 480 min. 678 de 679 P. - Camión 60 (150€): 41P04 en 120 min. 679 de 679 P. SOLUCIÓN CAMIONES CON CHASIS TIPO 3 O “COMBINED” - Camión 1 (500€): 4pp5pp4pp5pp4pp5pp4pp5pp4pp5pp7pp4pp5pp7pp4pp5pp7pp4 en 470 min. 34 de 483 p. 0 de 679 de P. - Camión 2 (490€): 4pp5pp7pp4pp6pp4pp6pp4pp6pp4pp6pp3pp4pp6pp3pp4 en 460 min. 64 de 483 p. 0 de 679 de P. - Camión 3 (480€): 4pp6pp3pp4pp6pp3pp4pp6pp3pp4pp7pp4pp7pp4 en 450 min. 90 de 483 p. 0 de 679 de P. - Camión 4 (480€): 4pp7pp4pp7pp4pp7pp4pp7pp4pp7pp4pp7pp5pp7pp5P4 en 450 min. 118 de 483 p. 1 de 679 de P. - Camión 5 (500€): 4pp7pp5pp7pp5pp7pp5pp7pp5pp7pp5pp7pp5pp7P4 en 470 min. 144 de 483 p. 2 de 679 de P. - Camión 6 (505€): 4pp3pp4pp0pp4pp0pp7pp5pp7pp5pp7pp5P4 en 475 min. 166 de 483 p. 3 de 679 de P. - Camión 7 (490€): 4pp0pp7pp2pp7pp2pp7pp2pp7pp2P4 en 460 min. 184 de 483 p. 4 de 679 de P. - Camión 8 (500€): 4pp0pp7pp2pp7pp2pp7pp2pp7pp2pp4 en 470 min. 204 de 483 p. 4 de 679 de P. - Camión 9 (490€): 4pp0pp7pp2pp4pp0pp7pp2pp5pp7P4 en 460 min. 222 de 483 p. 5 de 679 de P. - Camión 10 (470€): 4pp0pp7pp2pp5pp2pp5pp2pp5P4 en 440 min. 238 de 483 p. 6 de 679 de P. - Camión 11 (430€): 4pp1pp4pp1pp3pp4pp1pp3pp4 en 400 min. 254 de 483 p. 6 de 679 de P. - Camión 12 (480€): 4pp1pp3pp4pp1pp3pp4pp1pp3pp4 en 450 min. 272 de 483 p. 6 de 679 de P. - Camión 13 (470€): 4pp1pp3pp4pp1pp0pp7pp2pp5P4 en 440 min. 288 de 483 p. 7 de 679 de P. - Camión 14 (470€): 4pp1pp0pp1pp0pp1pp0P4 en 440 min. 300 de 483 p. 8 de 679 de P. - Camión 15 (470€): 4pp1pp0pp1pp0pp1pp0p4 en 440 min. 313 de 483 p. 8 de 679 de P. - Camión 16 (455€): 4pp2pp5P4P5P4P5P4P5P4P5P4P5P7pp2pp5P7P4 en 425 min. 321 de 483 p. 21 de 679 de P. - Camión 17 (500€): 4P5P7pp2pp5P7pp0pp1pp0pp1P4 en 470 min. 333 de 483 p. 25 de 679 de P. - Camión 18 (435€): 4P5P7pp0pp1pp0pp1pp04 en 405 min. 343 de 483 p. 27 de 679 de P. - Camión 19 (435€): 4P5P7pp0pp1pp0pp1pp04 en 405 min. 353 de 483 p. 29 de 679 de P. - Camión 20 (500€): 4P5P7pp0pp1P4P5P7pp0pp1P4P5P7P4 en 470 min. 361 de 483 p. 38 de 679 de P. - Camión 21 (500€): 4P5P7pp0pp1P4P5P7pp0pp1P4P5P7P4 en 470 min. 369 de 483 p. 47 de 679 de P. - Camión 22 (500€): 4P5P7pp0pp1P4P5P7pp0pp1P4P5P7P4 en 470 min. 377 de 483 p. 56 de 679 de P. - Camión 23 (500€): 4P5P7pp0pp1P4P5P7pp0pp1P4P5P7P4 en 470 min. 385 de 483 p. 65 de 679 de P. - Camión 24 (500€): 4P5P7pp0pp1P4P5P7pp0pp1P4P5P7P4 en 470 min. 393 de 483 p. 74 de 679 de P. - Camión 25 (500€): 4P6pp3pp4P6pp3pp4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4 en 470 min. 401 de 483 p. 94 de 679 de P. - Camión 26 (510€): 4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4 en 480 min. 401 de 483 p. 126 de 679 de P. - Camión 27 (500€): 4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P4P6P3P4 en 470 min. 401 de 483 p. 155 de 679 de P. - Camión 28 (510€): 4P6P3pp6P3pp6P3pp6P3pp6P3pp6P3P4 en 480 min. 411 de 483 p. 163 de 679 de P. - Camión 29 (510€): 4P6p+4p3pp1P4P64P64P64p65p4P7pp0pp1P4P7P4 en 480 min. 421 de 483 p. 172 de 679 de P. - Camión 30 (510€): 4P7P4P3pp1P4P3pp1P4P3P4P3P4P3P4 en 480 min. 425 de 483 p. 184 de 679 de P. 71 - Camión 31 (510€): 4P3P4P3P4P3P4P3P4P3P4P3P4P3P4P3P4 en 480 min. 425 de 483 p. 200 de 679 de P. - Camión 32 (495€): 4P3P4P3P4P3P4P3P4P3P65P7P5P7P5P7P54 en 465 min. 425 de 483 p. 216 de 679 de P. - Camión 33 (505€): 4P3P65P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P54 en 475 min. 425 de 483 p. 234 de 679 de P. - Camión 34 (505€): 4P3P65P7P5P7P5P7P5P7P5P7P5P7P5P7P5P7P54 en 475 min. 425 de 483 p. 252 de 679 de P. - Camión 35 (455€): 4P3P65P7P5P7P5P7P5P7P5P7P5P2pp54 en 425 min. 427 de 483 p. 265 de 679 de P. - Camión 36 (500€): 4P3P64P3P64P3P64P3P64P3P64P3P64P34 en 470 min. 427 de 483 p. 278 de 679 de P. - Camión 37 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 433 de 483 p. 284 de 679 de P. - Camión 38 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 439 de 483 p. 290 de 679 de P. - Camión 39 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 445 de 483 p. 296 de 679 de P. - Camión 40 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 451 de 483 p. 302 de 679 de P. - Camión 41 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 457 de 483 p. 308 de 679 de P. - Camión 42 (480€): 4P0pp1P4P0pp1P4P0pp1P4 en 450 min. 463 de 483 p. 314 de 679 de P. - Camión 43 (495€): 4P0pp1P4P0P7P5P2pp5P2pp54 en 465 min. 469 de 483 p. 321 de 679 de P. - Camión 44 (450€): 4P0P7P5P2pp5P2pp5P2P7P54 en 420 min. 473 de 483 p. 329 de 679 de P. - Camión 45 (460€): 4P0P7P5P2P7P5P2P7P5P2P7P54 en 430 min. 473 de 483 p. 341 de 679 de P. - Camión 46 (510€): 4P0P7P5P2P7P2P7P2P7P2P7P2P74 en 480 min. 473 de 483 p. 354 de 679 de P. - Camión 47 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 473 de 483 p. 364 de 679 de P. - Camión 48 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 473 de 483 p. 374 de 679 de P. - Camión 49 (485€): 4P0P7P0P7P0P7P0P7P0P74 en 455 min. 473 de 483 p. 384 de 679 de P. - Camión 50 (510€): 4P1P4P1P4P1P4P1P4P1P4P1P4 en 480 min. 473 de 483 p. 396 de 679 de P. - Camión 51 (455€): 4P1P4P1P4P2P7P0P7P0P74 en 425 min. 473 de 483 p. 406 de 679 de P. - Camión 52 (475€): 4P2P7P0P7P0P7P0P7P0P74 en 445 min. 473 de 483 p. 416 de 679 de P. - Camión 53 (475€): 4P2P7P0P7P0P7P0P7P0P74 en 445 min. 473 de 483 p. 426 de 679 de P. - Camión 54 (475€): 4P2P7P0P7P0P7P0P7P0P74 en 445 min. 473 de 483 p. 436 de 679 de P. - Camión 55 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 473 de 483 p. 448 de 679 de P. - Camión 56 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 473 de 483 p. 460 de 679 de P. - Camión 57 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 473 de 483 p. 472 de 679 de P. - Camión 58 (510€): 4P2P4P2P4P2P4P2P4P2P4P2P4 en 480 min. 473 de 483 p. 484 de 679 de P. - Camión 59 (465€): 4P2P5P2p+1p4P2p+0p7P0P74 en 435 min. 477 de 483 p. 490 de 679 de P. - Camión 60 (485€): 4P23P64p0P7P0P7P0P7P0P74 en 455 min. 478 de 483 p. 499 de 679 de P. - Camión 61 (450€): 4P23P1P4P23P1P4P23P1P4 en 420 min. 478 de 483 p. 508 de 679 de P. - Camión 62 (480€): 4P23P1P4P23P1P4P23P1P34 en 450 min. 478 de 483 p. 517 de 679 de P. - Camión 63 (500€): 4P23P1P3P1P3P1P3P1P34 en 470 min. 478 de 483 p. 526 de 679 de P. - Camión 64 (500€): 4P23P1P3P1P3P1P3P1P34 en 470 min. 478 de 483 p. 535 de 679 de P. - Camión 65 (500€): 4P23P1P3P1P3P1P3P1P34 en 470 min. 478 de 483 p. 544 de 679 de P. - Camión 66 (500€): 4P23P1P3P1P3P1P3P1P34 en 470 min. 478 de 483 p. 553 de 679 de P. - Camión 67 (500€): 4P23P1P3P1P3P1P3P1P34 en 470 min. 478 de 483 p. 562 de 679 de P. - Camión 68 (465€): 4P23P1P3P1P3P1P37p24 en 435 min. 479 de 483 p. 569 de 679 de P. - Camión 69 (450€): 4P24P24P24P24P24p24 en 420 min. 480 de 483 p. 574 de 679 de P. - Camión 70 (475€): 45P27P0P7P0P7P0P7P0P74 en 445 min. 480 de 483 p. 583 de 679 de P. - Camión 71 (475€): 45P27P0P7P0P7P0P7P0P74 en 445 min. 480 de 483 p. 592 de 679 de P. - Camión 72 (460€): 45P27P0P7P0P7P0P1P34 en 430 min. 480 de 483 p. 600 de 679 de P. - Camión 73 (455€): 45P27P0P1P37P0P1P34 en 425 min. 480 de 483 p. 607 de 679 de P. - Camión 74 (455€): 45P27P0P1P37P0P1P34 en 425 min. 480 de 483 p. 614 de 679 de P. - Camión 75 (510€): 45P27p0P1P35P21P35P24 en 480 min. 481 de 483 p. 620 de 679 de P. - Camión 76 (480€): 45P21P35P21P35P21P34 en 450 min. 481 de 483 p. 626 de 679 de P. - Camión 77 (480€): 45P21P35P21P35P21p34 en 450 min. 482 de 483 p. 631 de 679 de P. - Camión 78 (510€): 45P25P25P25P25P25P24 en 480 min. 482 de 483 p. 637 de 679 de P. - Camión 79 (510€): 45P25P25P25P25P25P24 en 480 min. 482 de 483 p. 643 de 679 de P. - Camión 80 (430€): 45P25P25P25P25p24 en 400 min. 483 de 483 p. 647 de 679 de P. - Camión 81 (510€): 40P1P0P1P0P1P0P14 en 480 min. 483 de 483 p. 654 de 679 de P. - Camión 82 (510€): 40P1P0P1P0P1P0P14 en 480 min. 483 de 483 p. 661 de 679 de P. - Camión 83 (500€): 40P1P0P1P0P10P14 en 470 min. 483 de 483 p. 667 de 679 de P. - Camión 84 (480€): 40P10P10P10P14 en 450 min. 483 de 483 p. 671 de 679 de P. 73 - Camión 85 (480€): 40P10P10P10P14 en 450 min. 483 de 483 p. 675 de 679 de P. - Camión 86 (480€): 40P10P10P10P14 en 450 min. 483 de 483 p. 679 de 679 de P. Realización de la interpretación 1 1. import time 2. 3. from cte import ( 4. LOAD_UNLOAD_PKG, 5. MAX_DRIVER_MIN, 6. PRIZE_TIME, 7. PRIZE_TRUCK_TYPE1, 8. PRIZE_TRUCK_TYPE2, 9. PRIZE_TRUCK_TYPE3, 10. TRUCK_START, 11. TRUCK_TYPE1, 12. TRUCK_TYPE2 13. ) 14. from utils import ( 15. create_order_time_dict, 16. extract_orders, 17. extract_time 18. ) 19. 20. 21. start = time.time() 22. 23. 24. def search_best_way(ords, start): 25. """ 26. Buscar el mejor camino desde un terminal a otro donde el camión transporte 27. un paquete en menos tiempo: 28. ords(dict): diccionario con órdenes pendientes 29. start(str): terminal de comienzo 30. 31. return: Una lista con el mejor orden basado en tiempo y el tiempo (sin 32. contar carga y descarga) 33. """ 34. best = '' 35. t = MAX_DRIVER_MIN * 1 36. for order in list(filter(lambda x: x[0][0] != start and (x[1][0] >= 1 or x[1][1] >= 1), ords.items())): 37. way = start + order[0][0] 38. ts = order[1][2] + ords[way][2] 39. if ts < t: 40. t = ts * 1 41. best = order[:] 42. return (best, t) if best else None 43. 44. 45. def search_special_way(ords, start): 46. """ 47. Buscar un camino especial donde se lleve un contenedor del punto X al punto Y, 48. pasando por un punto intermedio Z donde se recoge un contenedor para llevar 49. al punto Y, así se optimiza y se aprovecha que se lleva un camión de 50. tipo 3. 51. ords(dict): diccionario con órdenes pendientes 52. start(str): terminal de comienzo 81 53. 54. return: Una lista con los mejores órdenes basado en tiempo y el tiempo 55. (sin contar carga y descarga) 56. """ 57. best = '' 58. t = MAX_DRIVER_MIN * 1 59. for order1 in list(filter(lambda x: start == x[0][0] and x[1][0] >= 1, ords.items())): 60. for order2 in list(filter(lambda x: order1[0] != x[0] and order1[0][1] == x[0][1] and x[1][0] >= 1, ords.items())): 61. way = 'p+{}p{}'.format(order2[0][0], order2[0][1]) 62. ts = ords[order1[0][0] + order2[0][0]][2] + order2[1][ 2] 63. if ts < t: 64. t = ts * 1 65. best = order1, order2 66. return (best, t) if best else None 67. 68. def search_best_travel_t3(ords, start=str(TRUCK_START)): 69. """ 70. Buscar el mejor camino para un camión de tipo 3 con las órdenes dadas. 71. ords(dict): diccionario con órdenes pendientes 72. start(str): terminal de comienzo, el camión comenzará y terminará aquí 73. 74. return: Una lista con lo siguiente: 75. way(str): camino para un camión 76. t(int): tiempo total para dicho camión 77. ords(dict): órdenes pendientes 78. """ 79. def rm_ords(ooo, rms): 80. for key, values in rms.items(): 81. if not values: 82. continue 83. for v in values: 84. ooo[v][key] -= 1 85. return ooo 86. 87. t = 0 88. res = start[:] 89. tsig = 0 90. tend = 0 91. prev_tend = 0 92. prev_rend = '' 93. prev_oend = {} 94. n = n1 = n2 = n3 = n4 = n5 = None 95. 96. while True: 97. ini = res[-1] 98. osig = {0: [], 1: []} 99. oend = {0: [], 1: []} 100. 101. # En este problema se usa varias búsquedas diferentes, en concreto, 102. # se utiliza 5 para intentar hallar el camino más eficiente 103. n = list(filter(lambda x: x[0][0] == ini and x[1][0] >= 2, ords.items())) 104. if not n: 105. 106. n2 = list(filter(lambda x: x[0][0] == ini and x[1][1] >= 1, ords.items())) 107. if not n2: 108. n3 = search_special_way(ords, ini) 109. if not n3: 110. n4 = list(filter(lambda x: x[0][0] == ini and x[1][0] >= 1, ords.items())) 111. if not n4: 112. n5 = search_best_way(ords, ini) 113. 114. # La primera opción será buscar el camino más corto donde se lleve dos 115. # paquetes pequeños a la vez, así se ahorra tiempo y se mueve los 116. # mayores paquetes posibles 117. if n: 118. sol = sorted(n, key=lambda x: x[1][2])[0] 119. pkg = 0 120. tsig = sol[1][2] + LOAD_UNLOAD_PKG * 4 121. rsig = 'pp' + sol[0][1] 122. osig[pkg].append(sol[0]) 123. osig[pkg].append(sol[0]) 124. # La segunda opción, en caso de no ser posible llevar dos paquetes 125. # pequeños, se sigue con los paquetes grandes de la forma más eficiente, 126. # buscando los caminos más cortos desde el punto actual 127. elif n2: 128. sol = sorted(n2, key=lambda x: x[1][2])[0] 129. pkg = 1 130. tsig = sol[1][2] + LOAD_UNLOAD_PKG * 2 131. rsig = 'P' + sol[0][1] 132. osig[pkg].append(sol[0]) 133. # La tercera opción, será buscar un camino especial como se le ha 134. # llamado en la función search_special_way 135. elif n3: 136. sol, tn3 = n3 137. pkg = 0 138. osig[pkg].append(sol[0][0]) 139. osig[pkg].append(sol[1][0]) 140. sol = sol[1] 141. tsig = tn3 + LOAD_UNLOAD_PKG * 4 142. rsig = 'p+{}p{}'.format(sol[0][0], sol[0][1]) 143. # La cuarta opción será llevar paquetes pequeños en solItario, sin poder 144. # recoger otro pequeño de camino y optimizar ya que quedarán pocos 145. # paquetes donde elegir 146. elif n4: 147. sol = sorted(n4, key=lambda x: x[1][2])[0] 148. pkg = 0 149. tsig = sol[1][2] + LOAD_UNLOAD_PKG * 2 150. rsig = 'p' + sol[0][1] 151. osig[pkg].append(sol[0]) 152. # Por último, en caso de no existir paquetes a mover desde el punto 153. # actual, se tiene que buscar un camino donde se llegue a un punto que 154. # si se pueda mover un paquete y moverlo de la forma más rápida posible 83 155. 156. elif n5: sol, tn5 = n5 157. 158. if sol[1][1] >= 1: 159. pkg = 1 160. pkg_name = 'P' 161. else: 162. pkg = 0 163. pkg_name = 'p' 164. tsig = tn5 + LOAD_UNLOAD_PKG * 2 165. rsig = '{}{}{}'.format(sol[0][0], pkg_name, sol[0][1]) 166. osig[pkg].append(sol[0]) 167. 168. # Se comprueba que el camión llega al punto de partida 169. is_end = res[0] == sol[0][1] 170. if is_end: 171. tend = 0 172. rend = '' 173. else: 174. last = ords[sol[0][1] + res[0]] 175. if last[0] >= 1 or last[1] >= 1: 176. pkg_name = 'P' if last[1] >= 1 else 'p' 177. pkg = 1 if last[1] >= 1 else 0 178. tend = last[2] + LOAD_UNLOAD_PKG * 2 179. rend = pkg_name + res[0] 180. oend[pkg].append(sol[0][1] + res[0]) 181. else: 182. tend = last[2] 183. rend = res[0] 184. 185. # Se comprueba los tiempos máximos de un conductor para terminar o seguir 186. # buscando un camino 187. if t + tsig + tend > MAX_DRIVER_MIN: 188. t += prev_tend 189. res += prev_rend 190. ords = rm_ords(ords, prev_oend) 191. break 192. elif t + tsig + tend == MAX_DRIVER_MIN: 193. t += tsig + tend 194. res += rsig + rend 195. ords = rm_ords(ords, osig) 196. ords = rm_ords(ords, oend) 197. break 198. else: 199. t += tsig 200. res += rsig 201. ords = rm_ords(ords, osig) 202. remaining = list(filter(lambda x: x[1][0] >= 1 or x[1][1] >= 1, ords.items())) 203. if not remaining or (len(remaining) == 1 and remaining[0][0] == res[-1] + res[0]): 204. t += tend 205. res += rend 206. ords = rm_ords(ords, oend) 207. break 208. prev_tend = tend * 1 209. prev_rend = rend[:] 210. prev_oend = oend.copy() 211. 212. return res, t, ords 213. 214. 215. print("""La solución del camino de cada camión será del estilo: 4pp0P1p+2p34, esto significa lo siguiente: 216. 217. * Camión parte de Terminal 4 y va a Terminal 0, con 2 paquetes de 20' 218. * Camión parte de Terminal 0 y va a Terminal 1, con 1 paquete de 40' 219. * Camión parte de Terminal 1 y va a Terminal 2, con 1 paquete de 20', pero no lo suelta 220. * Camión parte de Terminal 2 y va a Terminal 3, con 2 paquete de 20' (uno que recoge y el anterior) 221. * Camión parte de Terminal 3 y va a Terminal 4, sin paquete, y finaliza """) 222. 223. print("\nSOLUCIÓN CAMIONES TIPO 3") 224. times = extract_time('times.csv') 225. orders = extract_orders('orders.csv') 226. dorders = create_order_time_dict(orders, times) 227. current_orders = {'20': 0, '40': 0} 228. trucks = 0 229. while list(filter(lambda x: x[1][0] + x[1][1] > 0, dorders.items())): 230. res, t, dorders = search_best_travel_t3(dorders, start=str(TRU CK_START)) 231. current_orders['20'] += res.count('p') 232. current_orders['40'] += res.count('P') 233. trucks += 1 234. print('Camión {}: {} en {} min. {} de {} p. {} de {} de P.'.format(trucks, 235. res, t, current_orders['20'], orders['t20'], current_order s['40'], orders['t40'])) 236. 237. print("TIME: {}s".format(time.time() - start))