Los métodos tradicionales empleados para el proyecto de un puente se basan en procedimientos de prueba y error que sirven para mejorar los diseños (Figura 1). Si bien la experiencia del proyectista permite definir “a priori” la geometría de la estructura, el resto de variables se determinan atendiendo al cumplimiento de los diferentes estados límite exigidos por los reglamentos para las situaciones de proyecto consideradas. De esta forma, la solución propuesta, si bien es funcionalmente correcta, no tiene porque ser la óptima. Los métodos de optimización, como pueden ser los algoritmos metaheurísticos o estocásticos, proporcionan una alternativa eficaz a los diseños estructurales basados en la experiencia. Estos algoritmos se caracterizan porque combinan unas reglas de decisión y la aleatoriedad para buscar de forma eficaz soluciones de alta calidad en espacios de soluciones de gran tamaño, tal y como son los originados por los problemas estructurales reales. Además, al explorar una gran cantidad de posibles combinaciones, encuentra soluciones que pueden estar alejadas de las reglas de diseño habituales empleadas por los proyectistas.
Figura 1. Diseño por prueba y error de las estructuras (Yepes, 2017)
Así, por ejemplo, los puentes de sección en cajón constituyen uno de las tipologías más habituales en los puentes continuos, pues presentan ventajas tanto desde la perspectiva de su eficiencia resistente como por su bajo peso propio. Sin embargo, las normas de diseño actuales no siempre contemplan los objetivos y las prioridades de una sociedad cambiante. El informe Brundtland (WCED, 1987) propone una visión a largo plazo para mantener los recursos, que serán necesarios para las necesidades futuras. El desarrollo sostenible requiere una triple visión que equilibre el desarrollo económico y las necesidades ambientales y sociales. Por lo tanto, las preocupaciones por construir un futuro más sostenible obligan a considerar aspectos como el impacto ambiental, la durabilidad y el nivel de seguridad, entre otros. Esto ha llevado al desarrollo de materiales de baja emisión de carbono, la búsqueda de nuevos diseños que reduzcan el impacto ambiental, la planificación de mantenimiento para prolongar la vida útil de las estructuras y la evaluación de su ciclo de vida para contemplar su impacto en su conjunto.
Esta nueva visión implica renovar la metodología de diseño de estructuras de modo que se consideren los criterios de sostenibilidad, que permita el uso de nuevos materiales y que, además, garantice un análisis estructural preciso. En este sentido, la optimización multiobjetivo encuentra soluciones óptimas con respecto a distintos objetivos, algunos de ellos contradictorios entre sí. Los actuales procedimientos de optimización heurística han permitido el diseño automatizado de estructuras óptimas. Sin embargo, existe una tendencia a considerar el diseño inicial y las operaciones de mantenimiento de la estructura como objetivos separados. Es decir, por una parte se estudia el diseño óptimo de una estructura para cumplir con los estados límite últimos y de servicio, y por otra parte, se considera la optimización de las operaciones de mantenimiento del puente durante su vida útil como un objetivo diferente, partiendo de una estructura ya construida, con un determinado estado de seguridad conocido. Como el mantenimiento depende del estado, el diseño inicial debe considerar los aspectos del ciclo de vida que también minimizan el mantenimiento futuro. Por lo tanto, es importante considerar la durabilidad con el fin de diseñar estructuras longevas y reducir los impactos a largo plazo. Es decir, se debe proyectar una estructura considerando todos los aspectos relacionados con su ciclo de vida.
La optimización multiobjetivo (MOO) de las estructuras reales requiere tiempos de cálculo elevados, incluso con la potencia de los actuales ordenadores, debido a la existencia de muchas variables de decisión, al procedimiento de análisis con métodos como el de los elementos finitos y al número de funciones objetivo consideradas. El uso de modelos predictivos tales como las redes neuronales artificiales (Artificial Neural Networks, ANNs) permite reducir el número necesario de evaluaciones exactas de la estructura y sustituir dicho cálculo por predicciones aproximadas. ANN aprende de los datos disponibles y permite predicciones incluso cuando las relaciones son altamente no lineales. Esta característica reduce el elevado coste computacional de las interaciones necesarias en los algoritmos de optimización heurística, al sustituir en dicho proceso una parte de los cálculos exactos por otros aproximados.
MOO conduce a una gama de soluciones óptimas, que se consideran igualmente buenas en función de los mútiples objetivos –la denominada frontera de Pareto-. El proceso de toma de decisiones para elegir la mejor de las opciones tiene lugar a posteriori, donde los expertos eligen la mejor solución en función de sus preferencias utilizando técnicas de toma de decisiones. Sin embargo, la asignación de pesos a cada uno de los objetivos del problema puede estar sujeta a incertidumbres o falta de objetividad. Sobre esta base, este trabajo sugiere una metodología capaz de introducir la información de selección (preferencia) en un proceso de toma de decisiones multicriterio en el que existen incertidumbres asociadas a la comparación de criterios.
Referencias:
García-Segura, T.; Yepes, V.; Alcalá, J.; Pérez-López, E. (2015). Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges.Engineering Structures, 92, 112–122.
García-Segura, T.; Yepes, V. (2016). Multiobjective optimization of post-tensioned concrete box-girder road bridges considering cost, CO2 emissions, and safety.Engineering Structures, 125, 325–336.
García-Segura, T.; Yepes, V.; Frangopol, D.M. (2017a). Multi-objective design of post-tensioned concrete road bridges using artificial neural networks.Structural and Multidisciplinary Optimization, 56(1):139-150.,
Martí, J.V.; García-Segura, T.; Yepes, V. (2016). Structural design of precast-prestressed concrete U-beam road bridges based on embodied energy.Journal of Cleaner Production, 120, 231–240.
Martí, J.V.; González-Vidosa, F.; Yepes, V.; Alcalá, J. (2013). Design of prestressed concrete precast road bridges with hybrid simulated annealing.Engineering Structures, 48, 342–352.
Martí, J.V.; Yepes, V.; González-Vidosa, F. (2015). Memetic algorithm approach to designing precast-prestressed concrete road bridges with steel fiber reinforcement.Journal of Structural Engineering, 141(2), 04014114.
Yepes, V. (2017). Trabajo de investigación. Concurso de Acceso al Cuerpo de Catedráticos de Universidad. Universitat Politècnica de València, 110 pp.
Yepes, V.; García-Segura, T.; Moreno-Jiménez, J.M. (2015a). A cognitive approach for the multi-objective optimization of RC structural problems.Archives of Civil and Mechanical Engineering, 15(4), 1024–1036.
Yepes, V.; Martí, J.V.; García-Segura, T. (2015). Cost and CO2 emission optimization of precast–prestressed concrete U-beam road bridges by a hybrid glowworm swarm algorithm.Automation in Construction, 49, 123–134.
Yepes, V.; Martí, J.V.; García-Segura, T.; González-Vidosa, F. (2017). Heuristics in optimal detailed design of precast road bridges.Archives of Civil and Mechanical Engineering, 17(4), 738-749.
A continuación os dejo un artículo donde se aplica la optimización heurística mediante recocido simulado de ménsulas cortas de hormigón armado, usando para ello elementos finitos con fisuración distribuida.
ROJAS, G.; ROJAS, P.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2012). Heuristic optimization of short corbels by smeared cracking finite element analysis. International Conference on Computer Aided Optimum Design in Engineering, 20-22 june. Computer Aided Optimum Design in Engineering XII. Vol. 125, pp. 71-82. Edited By: S. HERNANDEZ, University of A Coruña, Spain, C.A. BREBBIA, Wessex Institute of Technology, UK and W.P. DE WILDE, Vrije Universiteit Brussel, Belgium. DOI: 10.2495/OP120071 ISSN: 1743-3509 (on line).
Acaban de publicarnos un artículo donde se utilizan cuatro algoritmos heurísticos: Descent Local Search, Threshold Accepting Algorithm with Mutation Operation, Genetic Algorithm y Memetic Algorithm para el diseño automático de puentes pretensados.
YEPES, V.; MARTÍ, J.V.; GARCÍA-SEGURA, T.; GONZÁLEZ-VIDOSA, F. (2017). Heuristics in optimal detailed design of precast road bridges.Archives of Civil and Mechanical Engineering, 17(4):738-749. DOI: 10.1016/j.acme.2017.02.006
Abstract:
This paper deals with the cost optimization of road bridges consisting of concrete slabs prepared in situ and two precast-prestressed U-shaped beams of self-compacting concrete. It shows the efficiency of four heuristic algorithms applied to a problem of 59 discrete variables. The four algorithms are the Descent Local Search (DLS), a threshold accepting algorithm with mutation operation (TAMO), the Genetic Algorithm (GA), and the Memetic Algorithm (MA). The heuristic optimization algorithms are applied to a bridge with a span length of 35 m and a width of 12 m. A performance analysis is run for the different heuristics, based on a study of Pareto optimal solutions between execution time and efficiency. The best results were obtained with TAMO for a minimum cost of 104184 euros. Among the key findings of the study, the practical use of these heuristics in real cases stands out. Furthermore, the knowledge gained from the investigation of the algorithms allows a range of values for the design optimization of such structures and pre-dimensioning of the variables to be recommended.
Para empezar este año 2017, nada mejor que te comuniquen la publicación de un artículo de investigación el mismo día 1. Se trata en este caso de la utilización de algoritmos heurísticos híbridos para optimizar el coste de muros de contrafuertes. Se ha publicado en la revista Engineering Structures.
Podéis acceder a solicitar el artículo en este enlace:
This paper represents an economic optimization of buttressed earth-retaining walls. We explore the optimum solutions using a harmony search with an intensification stage through threshold accepting. The calibration of the resulting algorithm has been obtained as a result of several test runs for different parameters. A design parametric study was computed to walls in series from 4 to 16 m total height. The results showed different ratios of reinforcement per volume of concrete for three types of ground fill. Our main findings confirmed that the most sensitive variable for optimum walls is the wall-friction angle. The preference for wall-fill friction angles different to 0 in project design is confirmed. The type of fill is stated as the main key factor affecting the cost of optimum walls. The design parametric study shows that the soil foundation bearing capacity substantially affects costs, mainly in coarse granular fills (F1). In that sense, cost-optimum walls are less sensitive to the bearing capacity in mixed soils (F2) and fine soils of low plasticity (F3). Our results also showed that safety against sliding is a more influential factor for optimum buttressed walls than the overturning constraint. Finally, as for the results derived from the optimization procedure, a more suitable rule of thumb to dimension the footing thickness of the footing is proposed.
Viaducto St. Cloud, Francia – 2000. http://vslmex.com.mx/
En estos momentos es posible automatizar completamente el diseño óptimo de puentes usando algoritmos heurísticos. A continuación os dejo, en abierto, un capítulo de libro en el que se explica tanto la optimización de un puente de vigas artesas prefabricado como otro construido “in situ” como losa de hormigón postesado. Se trata de un trabajo incluido dentro del proyecto de investigación BRIDLIFE. Este tipo de técnicas acabarán imponiéndose en unos años en los paquetes informáticos de cálculo. Sin embargo, resulta muy importante resaltar que el proyectista es el que tiene la última palabra en el diseño.
Referencia:
Martí, J.V.; Alcalá, J.; García-Segura, T.; Yepes, V. (2016). Heuristic design of a precast-prestressed concrete U-beam and post-tensioned cast-in-place concrete slab road bridges. In: Hernández, S.; Brebbia, C.A.; de Wilde, W.P. (eds.), High Performance and Optimum Design of Structures and Materials II. WIT Transactions on The Built Environment, Vol. 166. WIT Press, pp. 17-28. ISBN: 978-1-78466-143-4.
Esta es la versión post-print de autor. La publicación se encuentra en: http://hdl.handle.net/10251/46928, siendo el Copyright de Elsevier.
El artículo debe ser citado de la siguiente forma:
Martí, JV.; Yepes, V.; Gonzalez-Vidosa, F.; Luz, AJ. (2014). Diseño automático de tableros óptimos de puentes de carretera de vigas artesa prefabricadas mediante algoritmos meméticos híbridos. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería. 30(3):145-154. doi:10.1016/j.rimni.2013.04.010.
El Instituto ICITECH (Instituto de Ciencia y Tecnología del Hormigón) es un Centro de Investigación de la Universidad Politécnica de Valencia creado en 2005, que agrupa a los profesores e investigadores cuya actividad investigadora se centra en el hormigón. Actualmente forman parte del instituto un total de 63 miembros, de los cuales 32 son profesores, 14 son investigadores contratados y el resto personal técnico de apoyo a la investigación y de administración.
La finalidad del Instituto es la investigación del hormigón, tanto desde el punto de vista de los materiales constituyentes como el de las estructuras, en una amplia gama de aspectos como el proceso de fabricación, el comportamiento fisco-químico, mecánico o medioambiental, la sostenibilidad o el comportamiento, diseño, construcción y mantenimiento de las estructuras.
Los objetivos son fomentar y promover la investigación de calidad a través de la realización de proyectos de I+D, potenciar la investigación aplicada, la transferencia de tecnología y de conocimiento a las empresas afines y la participación de socios industriales.
Las instalaciones de ICITECH se ubican en un nuevo edificio que alberga una gran losa de carga de 500 m2 junto con un muro de reacción horizontal en L de 14×6 m y 13 m de altura y con puntos de anclaje tanto en la losa como en el muro de 500 kN situados a un metro de distancia entre sus ejes. Además, dispone de una instalación oleohidráulica constituida por 6 grupos motobomba que proporcionan 250 bares un caudal de 1560 litros/min y dos puentes grúa de 10 t cada uno que permite manejar elementos de hasta 20 t por toda la superficie de la nave. Este conjunto permite realizar ensayos a escala real de estructuras con muy diversas tipologías de carga. Además de esta gran instalación, el edificio incluye laboratorios de química y de materiales con un total de 175 m2, tres cámaras húmedas: una de 117 m3 y dos de 57 m3, central de aire comprimido, gas natural, dióxido de carbono y aire seco.
Os paso a continuación un pequeño dossier que hemos preparado para explicar lo que hace nuestro grupo de investigación sobre optimización heurística relacionado con temas de hormigón (proyecto HORSOST) y con el mantenimiento de activos e infraestructuras. Esta actividad se encuentra enmarcada dentro del ICITECH, del Máster Oficial en Ingeniería del Hormigón (acreditado con el sello EUR-ACE) y del Programa de Doctorado en Ingeniería de la Construcción de la Universidad Politécnica de Valencia (verificado por ANECA).
YEPES, V.; MEDINA, J.R. (2006). Big-Bang: Un nuevo algoritmo aplicado a la optimización de redes de transporte del tipo VRPTW.Actas del VII Congreso de Ingeniería del Transporte CIT-2006. Libro CD, 8 pp. Ciudad Real, 14-16 de junio. ISBN: 84-689-8341-1.
RESUMEN
La ponencia presenta un procedimiento de optimización económica de rutas de reparto con flotas de vehículos heterogéneas y horarios de servicio flexibles VRPHESTW. Para ello se presenta una nueva heurística, denominada “Big-Bang” basada en la modificación gradual de la variable espacial donde se ubican los nodos que representan a los clientes. La simulación de esta heurística de relajación consiste en reducir la velocidad de todos los vehículos, que al principio es muy alta para estabilizarse al final en su verdadera magnitud. El algoritmo emplea para explorar el espacio de soluciones una búsqueda probabilista en entornos variables con una aceptación de máximo gradiente. El algoritmo propuesto encuentra soluciones de elevada calidad, con la ventaja de poder utilizar otros procedimientos de búsqueda local que resulten más eficientes que el de máximo gradiente (algoritmo del solterón, aceptación por umbrales, búsqueda tabú, etc.).
INTRODUCCIÓN
La asignación de rutas de reparto a una flota de vehículos “Vehicle Routing Problem” (VRP) constituye un problema habitual en las empresas dedicadas a la distribución de bienes o personas que conlleva un impacto económico, social y medioambiental importante. Sin embargo, los problemas de optimización que representan numerosas situaciones reales sólo pueden resolverse mediante procedimientos aproximados debido a su elevada complejidad intrínseca (ver Ball et al., 1995).
En las últimas décadas se han aplicado una gran variedad de técnicas para optimizar el problema de las rutas con horarios de servicio “vehicle routing problem with time windows” (VRPTW), tanto con heurísticas de construcción de soluciones (ver Solomon, 1987) o de mejora (ver Potvin y Rousseau, 1995), como metaheurísticas (ver Homberger y Gehring, 2005; Russell y Chiang, 2006). Sin embargo, son escasas las publicaciones que abordan la optimización con modelos más cercanos a la realidad incorporando horarios de servicio flexibles “vehicle routing problem with soft time windows” (VRPSTW) (ver Taillard et al., 1997), flotas heterogéneas de vehículos “vehicle routing problem with a heterogeneous fleet of vehicles” (VRPHE) (ver Gendreau et al., 1999), o ambas “vehicle routing problem with a heterogeneous fleet of vehicles and soft time windows” (VRPHESTW) (ver Yepes y Medina, 2002, 2004, 2006).
Además, los problemas reales de rutas difieren significativamente de los problemas teóricos. En efecto, la optimización jerárquica empleada habitualmente en la literatura (donde las mejores soluciones son las que, en primer lugar, presentan un menor número de rutas; y posteriormente, una menor distancia recorrida por todos los vehículos), no representa adecuadamente los costes reales de las empresas ni sus políticas de tarifas. Yepes (2002) indicó la trascendencia de utilizar una función objetivo de tipo económico para resolver estos problemas ante cambios en los escenarios de tarifas y costes. Asimismo, las restricciones legales y sociales, así como la calidad del servicio también se deben incluir dentro de una función objetivo de tipo económico, que contemple los ingresos y los costes de las operaciones de transporte (Medina y Yepes, 2003).
En la ponencia se presenta una nueva heurística basada en la modificación gradual de la variable espacial donde se ubican los nodos que representan a los clientes, y que se ha denominado “Big-Bang”. Esta estrategia de relajación, a su vez, se anida en una variante de la búsqueda en entornos variables “Variable Neighborhood Search” (VNS) (ver Mladenovic y Hansen, 1997) apoyada en la elección probabilista de un operador distinto en cada movimiento, empleada con éxito en el trabajo de Yepes y Medina (2006). Todo ello se ensaya con un problema de rutas del tipo VRPHESTW donde, además, se emplea una función objetivo de tipo económico, unas jornadas laborables con distintos costes y con tiempos de viaje dependientes del tiempo de acceso y alejamiento a cada nodo (congestión, tráfico, etc.).
EL ALGORITMO BIG-BANG
El algoritmo Big-Bang que se propone parte de la siguiente idea: Si todos los vehículos tuviesen una velocidad mayor a la real, dicho fenómeno se podría interpretar como que los clientes se encuentran en un espacio donde, físicamente, las distancias fuesen menores. Un procedimiento de búsqueda encontraría un óptimo local en este escenario favorable a la reducción del número de vehículos. Si se desciende escalonadamente la velocidad, y en cada caso se encuentra su óptimo local, probablemente el nuevo óptimo sería similar al anterior, siempre que la disminución fuera suficientemente suave. Esta relajación de la velocidad se interrumpiría en el último escalón, donde el óptimo local encontrado satisfaría la velocidad real de los vehículos. El efecto sería un aumento gradual del espacio físico donde se ubican los clientes, efecto por el cual se ha querido llamar a la heurística algoritmo Big-Bang. En la situación inicial las restricciones fundamentales que condicionan el problema son la capacidad de los vehículos y los horarios de servicio. Al final, la lejanía entre los clientes y el almacén central, son condiciones que se han introducido progresivamente al final de la heurística.
En efecto, un vehículo con una velocidad v llega de 0 a 1 en el instante t01 (ver Figura 1). Se supone, sin perder generalidad, que el tiempo de servicio es nulo. Si la velocidad se incrementase a v’, entonces la llegada ocurriría en t01’. Esta situación equivale a suponer que el nodo, en vez de estar en 1 está más cerca de 0, es decir, en 1’ y la velocidad se mantiene en v. Así, la llegada ocurre en el instante t’01, que es igual al t01’. Por tanto, un aumento en la rapidez de los vehículos es equivalente a un acortamiento físico de las distancias. Sin embargo, las ventanas temporales interfieren en el razonamiento anterior. La existencia de esperas provoca que, aunque la velocidad v’ favorece el acortamiento a la distancia 1’, no es posible iniciar el servicio puesto que lo impide la ventana temporal. La situación equivalente es la representada en la Figura 1 cuando el vehículo circula a una velocidad v’’. En este caso, el acortamiento de distancias a 1’ se ve interrumpido por la limitación en el inicio del servicio a la situación 1’’, donde el inicio del servicio s1’ es coincidente con el s1’’. La conclusión es que el aumento de la rapidez de los vehículos permite relajar las restricciones en las distancias, acortando éstas mientras las limitaciones horarias no lo impidan.
Fig. 1 – Incidencia en la variación de la velocidad de un vehículo en el inicio del servicio
Una de las características más interesantes de esta heurística de relajación consiste en la posibilidad de emplear como procedimientos de búsqueda local en cada escalón de velocidad, metaheurísticas más agresivas de búsqueda que la simple aceptación por umbrales (búsqueda tabú, algoritmo del solterón, cristalización simulada, etc.). En la ponencia que se presenta se ha optado por utilizar una búsqueda de máximo gradiente para comprobar la eficacia intrínseca del algoritmo, para no empañarla con la de otras metaheurísticas que por sí solas resultan, muy eficaces para el problema VRPHESTW (ver Yepes y Medina, 2004).
DESCRIPCIÓN DE LA METAHEURÍSTICA PROPUESTA
El método presentado consta de dos fases. En la primera se genera una solución inicial mediante una heurística de construcción de rutas específica. Posteriormente se emplea el algoritmo “Big-Bang” basándose en una versión probabilista de la búsqueda por entornos variables “Variable Neighborhood Search” (VNS) (ver Mladenovic y Hansen, 1997) y un criterio de aceptación de máximo gradiente.
3.1 Fase 1: Heurística económica de construcción secuencial de rutas.
Se ha empleado el método de Yepes y Medina (2006) para generar una solución inicial de elevada calidad al problema VRPHESTW. El procedimiento inicia una ruta seleccionando adecuadamente al primer cliente para posteriormente agregar otros mientras se cumplan las restricciones impuestas. Además, se elige el vehículo de mayor capacidad para disminuir en lo posible el número necesario.
3.2 Fase 2: Algoritmo “Big-Bang” con búsqueda probabilista en entornos variables.
El algoritmo que se propone consta de un número M+1 de ciclos de búsqueda local por entornos. Cada ciclo de búsqueda termina con la obtención de un óptimo relativo correspondiente con unas velocidades de los vehículos fijadas para dicho ciclo. En el primer ciclo, la velocidad de los vehículos se amplifica por un factor de incremento D= D1>1. Este factor debe reducirse progresivamente hasta llegar al último ciclo de búsqueda local, en el cual D =DM+1 =1. Para este trabajo, la reducción de la velocidad ha sido lineal con el número de ciclos; sin embargo, se podría adoptar otro tipo de función reductora.
Como técnica de búsqueda local se ha empleado la metaheurística propuesta por Yepes y Medina (2006) para el problema VRPHESTW, de búsqueda por entornos variables basada en la elección probabilística de 9 operadores distintos y un criterio de aceptación por máximo gradiente. Los movimientos elegidos han sido los siguientes:
Movimientos dentro de una ruta: se emplea el operador relocate (un nodo salta a otro lugar dentro de la ruta) y el swap (dos nodos de la ruta se intercambian entre sí).
Movimientos entre dos rutas: se utiliza el operador CROSS-exchange (Taillard et al., 1997) y dos casos particulares, el movimiento 2-opt* (Potvin y Rousseau, 1995) y el 2-exchange (Osman, 1993).
Movimiento de vehículos: vehicle–swap cambia entre sí los vehículos de dos rutas, y replacement sustituye el vehículo de una ruta por otro de la flota que no está utilizándose.
Reconstrucción de soluciones: R&R0 desconecta un nodo al azar y lo introduce en la posición y ruta más favorable, mientras que R&Rseq rompe la ruta con menor número de nodos, y los reintroduce en la mejor posición y ruta (ver Schirmpf et al., 2000).
La Tabla 1 contiene las probabilidades que tiene cada operador de ser elegido. Dichos valores han ofrecido buenos resultados en experiencias anteriores (ver Yepes, 2002).
Tabla 1 – Probabilidad de elección de los operadores
EJEMPLO DE APLICACIÓN AL PROBLEMA VRPHESTW
Se analiza un problema del tipo VRPHESTW denominado HES-A descrito en Yepes y Medina (2004, 2006). Este caso deriva del ejemplo R103 de Solomon (1987), al cual se incorporan horarios flexibles de entrega, flotas heterogéneas y una función económica caracterizada por unos ingresos y unos costes fijos y variables. El lenguaje código utilizado ha sido Visual Basic 6.0 ejecutándose los ejemplos en un ordenador Pentium IV 3.00 GHz.
En las Figuras 2 y 3 se representa el beneficio obtenido y el tiempo empleado por la heurística descrita cuando se aplica al problema HES-A. El número de iteraciones empleadas para cada escalón de velocidad ha oscilado entre 1000 y 50000. Los escalones de velocidad ensayados varían entre 3 y 100. La mejor solución encontrada se corresponde con un beneficio de 164752, obtenida para un factor inicial de modificación de la velocidad D1=130, así como 30000 iteraciones en cada uno de los 30 escalones de velocidad considerados. Sin embargo, esta solución no atiende a todos los clientes (sólo el 96.70% de la demanda queda cubierta). La mejor solución que atiende toda la demanda se corresponde con un beneficio de 155184, obtenida para un D1=150, así como 50000 iteraciones en 100 escalones de velocidad. Destacamos cómo el algoritmo es capaz de aumentar el beneficio de las operaciones a costa de renunciar al servicio a determinados clientes. La mejor solución no factible sólo precisa 12 vehículos y recorre 1224.71 unidades de distancia total, frente a los 13 vehículos y las 1260.54 unidades de distancia de la mejor solución factible. Si se pretende servir toda la demanda, bastaría endurecer las penalizaciones en la función objetivo.
Fig. 2 – Beneficio obtenido para el problema HES-A con el algoritmo propuesto, analizado por el factor inicial de incremento de velocidadFig. 3 – Beneficio obtenido para el problema HES-A con el algoritmo propuesto, analizado por la factibilidad de la solución
En la Tabla 2 se han recogido los valores óptimos en el sentido de Pareto de las soluciones factibles (ver Voorneveld, 2003). Dichos óptimos se corresponden con los valores de mayor beneficio en el menor tiempo de cálculo posible. Se observa que es favorable el aumento del factor de modificación inicial de la velocidad, del número de escalones y del número de iteraciones. Sin embargo, ello comporta un mayor tiempo de cálculo.
Tabla 2 – Resultados óptimos de Pareto para el problema HES-A, para las soluciones factibles
El mejor resultado obtenido por esta metaheurística (ver Tabla 3) es inferior al encontrado por el algoritmo del solterón propuesto por Yepes y Medina (2004) para un tiempo de cálculo similar. En aquella ocasión se obtuvo un beneficio de 170335, con 13 vehículos que recorrieron un total de 1229.13 unidades de distancia. Esta circunstancia sugiere que la búsqueda local de máximo gradiente empleada podría sustituirse por un algoritmo de búsqueda más agresiva, como el algoritmo del solterón.
Tabla 3 – Resultados obtenidos para el problema HES-A
CONCLUSIONES
Se ha presentado una nueva heurística denominada “Big-Bang” basada en la modificación gradual de la variable espacial donde se ubican los nodos que representan los clientes. Esta estrategia de relajación consiste en reducir progresivamente, de forma escalonada, la velocidad de todos los vehículos, de forma que, al final del proceso, todos dicha velocidad sea la que corresponde con las restricciones del problema. Este procedimiento permite una fuerte tendencia hacia la reducción inicial del número de vehículos necesarios. En la ponencia se ha empleado este procedimiento para la resolución del problema VRPHESTW. Como estrategia de búsqueda local se ha empleado un esquema de búsqueda aleatoria en entornos variables, que emplea de forma probabilista un conjunto de 9 operadores y un criterio de aceptación de nuevas soluciones de máximo gradiente. En los ensayos se ha comprobado que un aumento en el factor de incremento inicial de la temperatura, del número de escalones, y de las iteraciones proporciona un incremento en la calidad de las soluciones, si bien con un mayor tiempo de cálculo. Los resultados obtenidos son de elevada calidad, si bien se sugiere el empleo de procedimientos de búsqueda local más agresivos, como por ejemplo el algoritmo del solterón, que ha dado muy buenos resultados para la resolución de este problema.
AGRADECIMIENTOS
Los autores agradecen el apoyo en este trabajo del Ministerio de Educación y Ciencia y de los fondos FEDER (Proyectos: BIA2005-03197 y REN2002-02951).
REFERENCIAS
BALL, M.O.; MAGNANTI, T.L.; MONNA, C.L.; NEMHAUSER, G.L. (Eds.) (1995). Network Routing, Handbooks in Operations Research and Management Science, vol. 8. North-Holland, Amsterdam.
GENDREAU, M.; LAPORTE, G.; MUSARAGNY, C.; TAILLARD, É.D. (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers and Operations Research 26, pp. 1153-1173.
HOMBERGER, J.; GEHRING, H. (2005). A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research 162, pp. 220-238.
MEDINA, J.R.; YEPES, V. (2003). Optimization of touristic distribution networks using genetic algorithms. Statistics and Operations Research Transactions 27(1), pp. 95-112.
MLADENOVIC, N.; HANSEN, P. (1997). Variable neighborhood search. Computer and Operations Research 24(11) pp. 1097-1100.
OSMAN, I.H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research 41, pp. 421-451.
POTVIN, J.Y.; ROUSSEAU, J.M. (1995). An exchange heuristic for routing problems with time windows. J. Operational Res. Soc. 46(12), pp. 1433-1446.
RUSSELL, R.A.; CHIANG, W.C. (2006). Scatter search for the vehicle routing problem with time windows. European Journal of Operations Research 169, pp.606-622.
SCHIRMPF, G.; SCHENIDER, J.; STAMM-WILBRANDT, H.; DUECK, G. (2000). Record breaking optimization results using the ruin and recreate principle. Journal of Computation Physics 159, pp. 139-171.
SOLOMON, M.M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), pp. 254-265.
TAILLARD, É.; BADEAU, P.; GENDREAU, M.; GUERTIN, F.; POTVIN, J.-Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science 31(2), pp. 170-186.
VOORNEVELD, M. (2003). Characterization of Pareto dominance. Operations Research Letters 31, pp. 7-11.
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis doctoral. Universidad Politécnica de Valencia. 352 pp.
YEPES, V.; MEDINA, J.R. (2002). Criterio económico para la optimización de rutas con flotas heterogéneas VRPHESTW, en Ibeas, A. y Díaz, J.M. (Eds.): Actas del V Congreso de Ingeniería del Transporte. Vol. 2, pp. 693-700. Santander, 11-13 junio.
YEPES, V.; MEDINA, J.R. (2004). Algoritmo del solterón aplicado a la optimización de rutas con flotas heterogéneas VPRHESTW, en Larrodé, E. y Castejón, L. (Eds.): Actas del VI Congreso de Ingeniería del Transporte. Vol. 2, pp. 759-766. Zaragoza, 23-25 de junio.
YEPES, V.; MEDINA, J.R. (2006). Economic heuristic optimization for heterogeneous fleet VRPHESTW. Journal of Transportation Engineering, ASCE 132(4), pp. 303-311.
Ayer 12 de enero de 2016 tuvo lugar la defensa de la tesis doctoral de D. Alejandro José Luz Ivars denominada “Diseño óptimo de estribos abiertos de hormigón armado en puentes de carretera mediante optimización heurística”, dirigida por Fernando González Vidosa y Víctor Yepes Piqueras. La tesis recibió la calificación de “Sobresaliente cum laude” por unanimidad. Presentamos a continuación un pequeño resumen de la misma.
Resumen
La infraestructura de mayor implantación en el territorio es la carretera. Los tramos en puente y en túnel son los más singulares y costosos, aunque los primeros son más numerosos que los segundos. Hoy en día los puentes de paso superior son uno de los más frecuentes en todas las carreteras importantes. El estribo más recomendable y habitual para este tipo de puentes es el abierto porque, se esconde bajo el terraplén, mejorando la visibilidad de los conductores de la vía inferior, y, ahorra materiales respecto al cerrado a partir de una altura de terraplén suficiente. Muchos esfuerzos se han dedicado al cálculo y diseño de los tableros de puente, menos a las pilas, y, aún menos, a los estribos. Esta tesis se ocupa del diseño óptimo de estribos abiertos de hormigón armado en puentes de carretera. Se suma a las investigaciones del Grupo de Investigación, al que pertenece de Procedimientos de la Construcción, Optimización y Análisis de Estructuras (GPRC); que ya ha optimizado tableros (de losa pretensados y de vigas artesa) y pilas (rectangulares huecas), así como, muros, bóvedas y pórticos.
Solución de referencia
Los métodos de optimización más antiguos son los exactos, pero se complican mucho y pierden eficiencia cuando el número de variables es muy alto y las condiciones que deben cumplir las soluciones (comprobaciones resistentes de los materiales) no son lineales. Por el contrario, con ayuda de los ordenadores actuales, los métodos heurísticos están en gran auge, permitiendo, con algoritmos sencillos y “mucho coste” computacional, pero en tiempo razonable, resolver de manera automática, problemas tan complejos como los reales, sin simplificaciones, y no solo optimizando el coste como hasta ahora, sino también, otros criterios o, varios a la vez, con gran facilidad. Los estribos óptimos de la tesis se obtienen mediante estos métodos heurísticos y un programa informático que se ha realizado. Están completamente diseñados para ser construidos, y para ello constan de 40 variables discretas. Los estribos no han sido antes tratados en la bibliografía de optimización. Las funciones objetivo son el coste, la seguridad estructural, la constructibilidad y la sostenibilidad ambiental, tanto de forma aislada como por parejas con el coste (con una optimización multiobjetivo híbrida MOSAMO).
Los estribos así obtenidos son diseños óptimos que no han precisado la experiencia previa de un proyectista de estructuras que proponga, como se ha venido haciendo hasta la actualidad, el diseño inicial a comprobar. Si no cumple alguna comprobación resistente (a efectuar, bien manualmente, bien, como actualmente, mediante uno o varios programas informáticos de estructuras), el diseño inicial se retoca ligeramente por el ingeniero mediante un procedimiento de prueba y error. Los programas actuales aún no incluyen rutinas de optimización como el de la tesis. Por ello la bondad del diseño final depende mucho del proyectista que los maneja y de la bibliografía que conoce. La bibliografía sobre el diseño de estribos es escasa y no completa. Este trabajo la amplía aportando las relaciones geométricas, los órdenes de magnitud y los mecanismos resistentes de los estribos óptimos (criterios de predimensionamiento) y los compara con los de la bibliografía y con los de un estribo de referencia ER. Estribo con una altura de 9 m, realmente construido y proyectado por reconocidos ingenieros, respecto al que se han comprobado ahorros económicos superiores al 18% (fundamentalmente en la zapata). Para este ER se ha realizado un estudio paramétrico obteniendo los estribos óptimos con alturas totales entre 6 y 15 m y para tensiones admisibles entre 0,2 y 0,5 MPa.
Se han empleado con éxito algoritmos heurísticos a los estribos de los dos grandes grupos existentes: por un lado, de Búsqueda Secuencial por Entornos o Hill Climbing; y, por otro, de los llamados Algoritmos Poblacionales o Evolutivos; en ambos casos, tanto con soluciones factibles como infactibles. En esta tesis, mediante una nueva propuesta de penalización de la función objetivo, se consiguen, ahorros del 60% en tiempo de cálculo. Los algoritmos empleados se basan en el recocido simulado (SAMO) y en la aceptación por umbrales (TAMO). Son dos algoritmos híbridos de escalada estocástica con operadores de mutación basados en los algoritmos genéticos. Las diferencias entre ellos no son significativas, menores del 0.2%. Con un ordenador Intel Core 2 Quad CPU Q6600 de 2.4 GHz y con 3.24 GB de memoria RAM se consigue la optimización (con penalizaciones altas) en tan solo una ejecución del algoritmo, como novedad frente a otras investigaciones, de 1 h 35’(38’ con ordenador actual). Dentro del segundo grupo se desarrollan dos nuevas heurísticas HSDLS y HSPDLS basadas en Harmony Search e hibridadas con DLS sin y con penalizaciones (y el mismo operador de mutación primer grupo) con las que se consiguen resultados similares pero con tiempos 9 y 6 veces superiores respectivamente.
Tanto la optimización monobjetivo como la multiobjetivo (MO) ponen de manifiesto la equivalencia de optimizar en coste, en CO₂ o en energía con diferencias menores del 1.5%, si bien es, a costa de un elevado número de armaduras pasivas. La optimización MO (coste barras) ofrece un ahorro medio en barras del 78.4% con un incremento medio de los otros tres criterios de 7.85% siendo el ahorro económico respecto ER todavía de un 12,23%.
Hoy 9 de diciembre de 2015 ha tenido lugar la lectura de la tesis doctoral de D. Ángel Rodríguez-Calderita Facundi denominada “Optimización heurística de forjados de losa postesa”, dirigida por Víctor Yepes Piqueras y Julián Alcalá Gonzalez. La tesis recibió la calificación de “Sobresaliente cum laude” por unanimidad. Presentamos a continuación un pequeño resumen de la misma.
Resumen
El objetivo fundamental de esta tesis consiste en el desarrollo de un nuevo algoritmo de optimización que permita una mayor eficiencia que otros algoritmos empleados en la optimización de estructuras, así como la obtención de reglas de diseño a partir de los resultados de la optimización de forjados de losa postesa.
Los forjados son los elementos estructurales que se repiten constantemente en el diseño de los edificios y que, por tanto, requieren de un grado de atención importante. Por esto su optimización presenta un indudable interés. Los forjados de losa postesa, en particular, suponen una mejora tecnológica respecto a los forjados convencionales, y resultan ventajosos dentro de determinados campos de aplicación.
Del análisis de los trabajos de investigación previamente publicados, se ha podido concluir que la optimización de estructuras de hormigón en general, y de forjados losa en particular, se aborda de forma eficaz mediante el uso de metaheurísticas. El uso de estas técnicas ha demostrado ser ventajoso al hacer posible considerar todos los elementos que conforman el forjado, dando al resultado de la optimización un enfoque muy práctico pues el resultado del proceso es un forjado completamente definido.
A partir de aquí se han implementado tres algoritmos mono-objetivo basados en otras tantas metaheurísticas: el recocido simulado (SA), la aceptación por umbrales (TA) y el algoritmo del solterón, este último con dos variantes (OBA, OBA1). Estos algoritmos han sido debidamente calibrados para mejorar su funcionamiento. La comparación entre ellos muestra que funcionan de un modo muy similar. El que ha proporcionado los mejores resultados ha sido el TA, con losas entre un 0.5% y un 1% más económicas que el resto de algoritmos. El algoritmo que mejores resultados ha obtenido a continuación es casi siempre el OBA 1, pues mejora al OBA, e incluso al TA para parametrizaciones de corta duración de cálculo.
En cualquier caso, el algoritmo TA ha mejorado el coste de una solución de referencia en un 31.63%. Este ahorro tan significativo se justifica por la reducción de canto, lo que reduce la medición de hormigón, y por tanto de peso, por lo que permite reducir también cuantías de acero. Asimismo se ha implementado un algoritmo multiobjetivo (SMOSA), enfrentando dos funciones objetivo que entran en conflicto: el coste económico y la seguridad estructural, evaluada mediante un factor definido como el menor de los factores de seguridad de todos los estados límite examinados. Los resultados indican que un incremento del factor de seguridad envolvente de un 5% sobre el mínimo impuesto por las normas requiere un sobrecoste del 2%, pero esta proporción no se mantiene lineal. Para aumentar la seguridad al doble del valor normativo, el coste se incrementa en un 89.54%.
Con todos estos resultados, y analizando los resultados del algoritmo TA, se ha diseñado un nuevo algoritmo de optimización que se ha denominado Destrucción puntual más reconstrucción guiada (DP+RG). Se trata de un algoritmo inspirado en los algoritmos de destrucción-reconstrucción, con elementos de los algoritmos de búsqueda en entornos amplios. Se basa en emplear movimientos más sofisticados que dirigen la búsqueda no solo en función de la variación en la función objetivo, sino también en la alteración en el cumplimiento de los requisitos estructurales. Aunque se ha aplicado únicamente a este tipo de forjados es totalmente generalizable a la optimización de cualquier estructura de hormigón.
A pesar del requerimiento de memoria del equipo informático, este algoritmo ha resultado ser entre seis y doce veces más rápido que los algoritmos anteriores. También es más robusto, en el sentido de que las ejecuciones consecutivas del algoritmo proporcionan soluciones con una desviación máxima entre ellas del 0.29% en el peor de los casos, frente a valores de hasta el 12.5 % en el TA. Finalmente, los resultados obtenidos llegan a mejorar al TA entre un 1.1 y un 2.3% de media.
El forjado optimo desde el punto de vista económico será aquel que tenga un menor canto para la misma resistencia característica de hormigón, el canto ha resultado la variable más determinante de las analizadas lo que justifica que su ajuste se realice centímetro a centímetro y no en escalones de cinco centímetros que suele ser lo habitual.
YEPES, V.; MEDINA, J.R. (2006). Big-Bang: Un nuevo algoritmo aplicado a la optimización de redes de transporte del tipo VRPTW. Actas del VII Congreso de Ingeniería del Transporte CIT-2006. Libro CD, 8 pp. Ciudad Real, 14-16 de junio. ISBN: 84-689-8341-1.
