En este trabajo se describe la influencia de las fibras de acero en el diseño de coste mínimo de puentes de carretera de vigas prefabricadas con sección transversal en doble U pretensadas y vanos isostáticos. Para ello se utiliza un algoritmo memético con una búsqueda en entornos variable (MA-VDNS) para optimizar el coste de estas estructuras contando las fases de fabricación, transporte y construcción del puente. El problema implica 41 variables de diseño discretas que definen la geometría de la viga y de la losa, los materiales en ambos elementos, las armaduras pasiva y activa y la resistencia residual a tracción de las fibras. El uso de las fibras disminuye el peso medio de la viga en un 1,72% y reduce el número medio de tendones en un 3,59%; sin embargo, incrementa un 8,71% de media la armadura pasiva necesaria. Por último, y a pesar del mayor coste del hormigón con fibras, se comprueba que su uso es económicamente viable, pues se consigue una diferencia relativa media de coste respecto al hormigón sin fibras, inferior al 0,19%.
Resultados interesantes:
A pesar del mayor coste económico del hormigón con fibras y de que el estado de decompresión del hormigón no ocurre en ninguna fibra de la sección de la viga por el pretensado, el hormigón con fibras es competitivo económicamente respecto al no uso de fibras, puesto que la diferencia relativa es inferior al 5,36% en el peor de los casos.
El estudio paramétrico realizado indica una buena correlación del coste, canto y peso de la viga y número de tendones respecto a la luz del puente. Esto permite un predimensionamiento ajustado.
Se ha comprobado que las fibras reducen de media un 3,59% el número de tendones necesarios, lo cual significa que su uso puede compensar parte del pretensado necesario.
Sorprende comprobar que el uso de fibras incrementa de media un 8,71% la armadura necesaria por unidad de superficie de losa. Esto se puede explicar debido a que la carestía del hormigón con fibras hace que el algoritmo intente disminuir su volumen, lo cual se compensa con el incremento de armadura pasiva.
En el caso de las estructuras óptimas, se ha encontrado una reducción del 6% del peso de las vigas realizadas con fibras, lo cual puede ser relevante para el transporte e izado de los elementos.
Referencia:
MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2015). A memetic algorithm approach to designing of precast-prestressed concrete road bridges with steel fiber-reinforcement.Journal of Structural Engineering ASCE, 141(2): 04014114. DOI:10.1061/(ASCE)ST.1943-541X.0001058 , 04014114.
Abstract
This paper describes the influence of steel fiber-reinforcement on the design of cost-optimized, prestressed concrete, precast road bridges, with a double U-shaped cross-section and isostatic spans. A memetic algorithm with variable-depth neighborhood search (MA-VDNS) is applied to the economic cost of these structures at different stages of manufacturing, transportation and construction. The problem involved 41 discrete design variables for the geometry of the beam and the slab, materials in the two elements, active and passive reinforcement, as well as residual flexural tensile strength corresponding to the fibers. The use of fibers decreases the mean weight of the beam by 1.72%, reduces the number of strands an average of 3.59%, but it increases the passive reinforcement by 8.71% on average, respectively. Finally, despite the higher cost of the fibers, their use is economically feasible since the average relative difference in cost is less than 0.19%.
Resumen–El artículo se ocupa de la optimización económica de los tableros de los pasos superiores de carreteras formados por una losa de hormigón ejecutada in situ y dos vigas artesa prefabricadas de hormigón pretensado autocompactable. Se comprueba la eficacia de las distintas metaheurísticas aplicadas en la optimización: “descent local search” (DLS), “simulated annealing” (SA), “threshold accepting” (TA), “genetic algoritms” (GA) y “memetic algorithms” (MA). Los cálculos de las tensiones y de sus envolventes, son programados en lenguaje fortran directamente por los autores. Los algoritmos de optimización heurística se aplican a un tablero de 35 m de luz y 12 m de ancho. Los parámetros que definen la forma de la sección de la viga se adaptan a los moldes de una instalación de prefabricados. El ejemplo que se analiza consta de 59 variables discretas. El módulo de la evaluación incluye los estados límite último y de servicio que se aplican comúnmente para estas estructuras: flexión, cortante, torsor, fisuración, flechas, etc. Los algoritmos SA y TA se han calibrado previamente a partir del DLS, y el MA a partir del GA y del SA. Cada heurística se procesa nueve veces, obteniéndose información estadística sobre el valor mínimo, el medio y las desviaciones. Se realiza un análisis del rendimiento de las distintas heurísticas, basado en un estudio de las soluciones Pareto-óptimas entre tiempo de ejecución y rendimiento. Los mejores resultados se obtienen para el SA y el TA, siendo el coste mínimo de 108008 €, correspondiente al SA. Finalmente, entre las principales conclusiones de este estudio, destaca que las soluciones y los tiempos de proceso computacional son tales, que estos métodos se pueden aplicar de un modo práctico a casos reales, y que el conocimiento derivado del uso de estos algoritmos permiten recomendar rangos de valores para emplearlos en el diseño optimizado de estas estructuras y en su aplicación para los predimensionados de las variables.
Palabras clave—Optimización, metaheurística, puentes, pasos superiores, diseño de estructuras.
Referencia: MARTÍ, J.V.; YEPES, V.; GARCÍA-SEGURA, T. (2015). Aplicación de metaheurísticas en la optimización de pasos superiores de carreteras. X Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados – MAEB 2015, 4-6 de febrero, Mérida, pp. 241-247. ISBN: 978-84-697-2150-6.
A veces la Naturaleza nos sorprende cada día más. ¿Es posible que el comportamiento de las hormigas pueda servirnos para optimizar estructuras complejas, como por ejemplo un puente? Pues vamos a ver que sí. Este post es continuación de otros anteriores donde hablamos de la posibilidad de optimizar estructuras de hormigón. La optimización por colonia de hormigas (ant colony optimization) va a ser una metaheurística que nos va a permitir realizar este tipo de operaciones. A continuación vamos a contar los fundamentos básicos y en las referencias os dejo, incluso, algunos artículos donde hemos podido utilizar esta técnica de forma exitosa.
Colorni, Dorigo y Maniezzo (1991) sugirieron la idea de imitar el comportamiento de los insectos para encontrar soluciones a los problemas de optimización combinatoria. El principio de la metaheurística denominada como “Ant System Optimization, ACO” se basa en el comportamiento colectivo de las hormigas en la búsqueda de alimentos para su subsistencia, que son capaces de encontrar el camino más corto entre una fuente de comida y su hormiguero. Primero las hormigas exploran el entorno de su hormiguero de forma aleatoria. Tan pronto como un individuo encuentra una fuente de comida, evalúa su cantidad y calidad y transporta un poco al hormiguero. Durante el regreso, la hormiga deja por el camino una señal odorífera, depositando una sustancia denominada feromona, para que las demás puedan seguirla. Después de un tiempo, el camino hacia el alimento se indicará por un rastro oloroso que crece con el número de hormigas que pasen por él, y que va desapareciendo en caso contrario. El resultado final es la optimización del trabajo de todo el hormiguero en su búsqueda de comida.
En la Figura se muestra cómo las hormigas encuentran el camino más corto. En a) las hormigas deben decidir un camino; en b) se toma uno al azar; en c), dado que la velocidad de una hormiga se considera aproximadamente constante, las que llegan antes vuelven eligiendo el camino con más acumulación de feromona. En d), se circula por el camino más corto, desapareciendo por evaporación el rastro en el camino más largo.
Las hormigas y el camino más corto
La analogía a una metaheurística de optimización puede establecerse de la siguiente forma:
La búsqueda de alimento por las hormigas es equivalente a la exploración de soluciones factibles de un problema combinatorio.
La cantidad de alimento hallada en un lugar es similar al valor de la función objetivo.
El rastro de feromona es la memoria adaptativa del método.
Un esquema básico de la metaheurística sería el siguiente:
Iniciar un rastro de feromona.
Mientras no se encuentre un criterio de parada:
Para cada hormiga artificial, construir una nueva solución usando el rastro actual y evaluar la solución que está siendo construida.
Actualizar el rastro de feromona.
El componente más importante de un Sistema de Hormigas es la gestión de las huellas odoríferas. En su versión estándar, los rastros se usan en relación con la función objetivo para construir nuevas soluciones. Una vez se ha construido, éstos se actualizan de la siguiente forma: primero todos los rastros se debilitan para simular la evaporación del feronoma; después aquellos que corresponden a los elementos que se han empleado para la construcción, se refuerzan teniendo en cuenta la calidad de la solución.
El siguiente vídeo os puede ayudar a comprender el comportamiento de las hormigas. Espero que os guste.
Referencias:
COLORNI, A.; DORIGO, M.; MANIEZZO, V. (1991). Distributed optimization by ant colonies, in VARELA, F.J.; BOURGINE, P. (eds.) Proceedings of the First European Conference on Artificial Life (ECAL-91). The MIT Press: Cambrige, MA, 134-142.
MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; ALCALÁ, J. (2011). Design of tall bridge piers by ant colony optimization. Engineering Structures, 33:2320-2329.
MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections. Computers & Structures, 88: 375-386. ISSN: 0045-7949. (link)
YEPES, V. (2003). Apuntes de optimización heurística en ingeniería. Editorial de la Universidad Politécnica de Valencia. Ref. 2003.249. Valencia, 266 pp. Depósito Legal: V-2720-2003.
Abstract: This paper presents a multiobjective optimization of post-tensioned concrete road bridges in terms of cost, CO2 emissions, and overall safety factor. A computer tool links the optimization modulus with a set of modules for the finite-element analysis and limit states verification. This is applied for the case study of a three-span continuous post-tensioned box-girder road bridge, located in a coastal region. A multiobjective harmony search is used to automatically search a set of optimum structural solutions regarding the geometry, concrete strength, reinforcing and post-tensioned steel. Diversification strategies are combined with intensification strategies to improve solution quality. Results indicate that cost and CO2 emissions are close to each other for any safety range. A one-euro reduction, involves a 2.34 kg CO2 emissions reduction. Output identifies the best variables to improve safety and the critical limit states. This tool also provides bridge managers with a set of trade-off optimum solutions, which balance their preferences most closely, and meet the requirements previously defined.
Keywords
Multiobjective optimization;
CO2 emissions;
Safety;
Post-tensioned concrete;
Box-girder bridge;
Multiobjective harmony search
Highlights
A multiobjective optimization of post-tensioned concrete road bridges is presented.
A computer tool combines finite-element analysis and limit states verification.
Output provides a trade-off between cost, CO2 emissions, and overall safety factor.
Near the optima, a one-euro reduction represents a 2.34 kg CO2 emissions reduction.
Results show the cheapest and most eco-friendly variables for improving safety.
Reference:
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. DOI: 10.1016/j.engstruct.2016.07.012.
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.
Analogía entre la improvisación musical y la optimización en ingeniería. Fuente: http://www.hindawi.com/journals/jam/2012/147950/fig1/
El proceso de improvisación musical supone una organización coherente de los sonidos y los silencios que da los parámetros fundamentales de la música, que son la melodía, la armonía y el ritmo. La simulación del proceso de improvisación musical puede servir a los calculistas de estructuras como inspiración en el diseño de algoritmos que permitan optimizar, por ejemplo, un puente. En esta comparación, el conjunto de músicos se podría asimilar a las variables de decisión; el rango de afinación, al rango de valores; la armonía; la estética, a la función objetivo; la práctica, a la iteración y la experiencia, a la matriz de memoria. A este algoritmo heurístico se le denomina harmony search.
En este post os dejo el resumen, la referencia y el enlace a un artículo que acaban de publicarnos en la revista Engineering Structures donde aplicamos esta metodología en la optimización sostenible del diseño de una pasarela peatonal formada por una viga cajón postesada. Esta investigación está financiada dentro del Proyecto HORSOST (BIA2011-23602) financiado por el Ministerio de Ciencia e Innovación.
Resumen: Este artículo tiene como objetivo el diseño sostenible de puentes viga peatonales de hormigón postesado de sección en cajón. Para ello se utiliza un algoritmo heurístico híbrido de búsqueda armónica (hybrid harmony search) con la aceptación por umbrales para encontrar la geometría y los materiales necesarios para que la suma de los costos y la huella de carbono sea lo más baja posible, cumpliendo con todas las restricciones de seguridad estructural y durabilidad. Para ajustar los parámetros del algoritmo se utilizó la metodología del diseño de experimentos. Se realizó asimismo un estudio paramétrico en pasarelas de 90 a 130 m de luz. Los resultados encontrados indican que la optimización con ambas funciones objetivo conducen a resultados similares en coste, si bien con soluciones diferentes. Los resultados sugieren que la reducción en las emisiones de CO2 conllevan mayores cantos, más pretensado y menores resistencias características del hormigón empleado. La metodología presentada supone una propuesta detallada de las reglas de predimensionamiento de este tipo de estructuras teniendo en cuenta un enfoque medioambiental.
¿Cuándo empieza realmente la optimización de las estructuras? Difícil pregunta a resolver. Si bien los aspectos básicos relacionados con la optimización matemática se establecieron en los siglos XVIII y XIX con los trabajos de Lagrange o Euler, hay que esperar hasta los años 40 del siglo XX para que Kantorovich y Dantzing desarrollaran definitivamente los principios de la programación matemática. Es a partir de la revolución informática de los años 70 cuando estas herramientas empiezan a ser empleadas habitualmente en numerosas aplicaciones en las ciencias, las ingenierías y los negocios. Sin embargo, el progreso de técnicas de optimización que no requieran derivadas y que se generen a través de reglas heurísticas, ha supuesto una auténtica revolución en el campo de la optimización de los problemas reales. En efecto, los métodos aproximados pueden utilizarse allí donde el elevado número de variables en juego impiden la resolución en un tiempo de cálculo razonable de los problemas mediante la programación matemática. A estos algoritmos de optimización aproximada, cuando su uso no está restringido a un solo tipo de problemas, la comunidad científica en el ámbito de la inteligencia artificial y la investigación operativa les ha dado el nombre de metaheurísticas. Este grupo incluye una amplia variedad de procedimientos inspirados en algunos fenómenos naturales, tales como los algoritmos genéticos, el recocido simulado o la optimización por colonias de hormigas . Liao et al. [1] presentan una revisión de la aplicación de los métodos heurísticos en el campo de la gestión del proyecto y de la construcción.
En relación con la optimización de las estructuras, si bien la información más antigua se remonta al siglo XV con los trabajos de Leonardo da Vinci y de Galileo Galilei sobre la disminución del peso de estructuras de madera, hay que esperar al siglo XIX con Maxwell y Levy, y a comienzos del siglo XX con Mitchell, para ver las primeras aportaciones en el diseño de mínimo peso de estructuras de arcos y cerchas metálicas. En 1994, Cohn y Dinovitzer [2] realizaron una amplia revisión de los métodos empleados en la optimización de estructuras, comprobando que la inmensa mayoría de las investigaciones llevadas a cabo hasta entonces se basaban en la programación matemática y en problemas más bien teóricos, con una preponderancia abrumadora de las estructuras metálicas frente a las estructuras de hormigón. Así, la aplicación de métodos heurísticos a la ingeniería estructural se remonta a los años 70 y 80 [3-5], siendo la computación evolutiva, y en especial los algoritmos genéticos, los métodos que más se han utilizado. La revisión de Kicinger et al. [6] proporciona un completo estado del arte de los métodos evolutivos aplicados al diseño estructural. Por otro lado, nuestro grupo de investigación, a través de su proyecto de investigación HORSOST, y más recientemente con el proyecto BRIDLIFE, ha presentado trabajos recientes de diseño automático y optimización de estructuras de hormigón armado con algoritmos genéticos [7] y con otras técnicas heurísticas [8-13], así como trabajos de optimización con hormigón pretensado [14,15] o de la optimización de las infraestructuras lineales [16].
Os dejo a continuación un vídeo tutorial donde se realiza una pequeña introducción al diseño optimización estructural. Espero que os sea de interés. Por cierto, si alguien se anima a hacer su tesis doctoral con nuestro grupo de investigación, será bien recibido.
Referencias:
[1] T.W. Liao, P.J. Egbelu, B.R. Sarker, S.S. Leu, Metaheuristics for project and construction management – A state-of-the-art review, Automation in Construction 20 (2011) 491-505.
[2] M.Z. Cohn, A.S. Dinovitzer, Application of structural optimization, ASCE Journal of Structural Engineering 120 (1994) 617-649.
[3] A. Hoeffler, U. Leysner, J. Weidermann, Optimization of the layout of trusses combining strategies based on Mitchel’s theorem and on biological principles of evolution, Proceedings of the Second Symposium on Structural Optimization (1973).
[4] M. Lawo, G. Thierauf, Optimal design for dynamic stochastic loading: a solution by random search, en: Optimization in structural design, University of Siegen, 1982, pp. 346-352.
[5] D.E. Goldberg, M.P. Samtani, Engineering optimization via genetic algorithms, Proceedings of the Ninth Conference on Electronic Computation ASCE (1986) 471-482.
[6] R. Kicinger, T. Arciszewski, K. De Jong, Evolutionary computation and structural design: A survey of the state-of-the-art, Computers & Structures 83 (2005) 1943-1978.
[7] F.J. Martinez, F. González-Vidosa, A. Hospitaler, V. Yepes, Heuristic optimization of RC bridge piers with rectangular hollow sections, Computers & Structures 88 (2010) 375-386.
[8] I. Paya-Zaforteza, V. Yepes, F. González-Vidosa, A. Hospitaler, On the Weibull cost estimation of building frames designed by simulated annealing, Meccanica 45 (2010) 693-704.
[9] V. Yepes, F. González-Vidosa, J. Alcala, P. Villalba, CO2-Optimization design of reinforced concrete retaining walls based on a VNS-Threshold acceptance strategy, Journal of Computing in Civil Engineering ASCE 26 (2012) 378-386.
[10] C. Perea, V. Yepes, J. Alcala, A. Hospitaler, F. González-Vidosa, A parametric study of optimum road frame bridges by threshold acceptance, Indian Journal of Engineering & Materials Sciences 17 (2010) 427-437.
[11] A. Carbonell, V. Yepes, F. González-Vidosa, Búsqueda exhaustiva por entornos aplicada al diseño económico de bóvedas de hormigón armado, Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería 27 (2011) 227-235.
[12] A. Carbonell, F. González-Vidosa, V. Yepes, Design of reinforced concrete road vaults by heuristic optimization, Advances in Engineering Software 42 (2011) 151-159.
[13] T. García-Segura, V. Yepes, J.V. Martí, J. Alcalá, Optimization of concrete I-beams using a new hybrid glowworm swarm algorithm. Latin American Journal of Solids and Structures, 11(7) (2014) 1190 – 1205.
[14] J.V. Martí, F. González-Vidosa, Design of prestressed concrete precast pedestrian bridges by heuristic optimization, Advances in Engineering Software 41 (2010) 916-922.
[15] J.V. Martí, F. González-Vidosa, V. Yepes, J. Alcalá, Design of prestressed concrete precast road bridges with hybrid simulated annealing, Engineering Structures 48 (2013) 342-352.
[16] C. Torres-Machí, A. Chamorro, C. Videla, E. Pellicer, V. Yepes. An interative approach for the optimization of pavement maintenance mangement at the network level, The Scientific World Journal ID 524329 (2014).
[17] T. García-Segura, V. Yepes, J. Alcalá, E. Pérez-López. Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges. Engineering Structures 92 (2015) 112-122.
[18] J.V. Martí, V. Yepes, F. González-Vidosa. Memetic algorithm approach to designing of precast-prestressed concrete road bridges with steel fiber-reinforcement. Journal of Structural Engineering ASCE 141(2) (2015) 04014114.
[19] V. Yepes, J.V. Martí, T. García-Segura. Cost and CO2 emission optimization of precast-prestressed concrete U-beam road bridges by a hybrid glowworm swarm algorithm. Automation in Construction49 (2015) 123-134.
[20] V. Yepes, T. García-Segura, J.M. Moreno-Jiménez. A cognitive approach for the multi-objective optimization of RC structural problems. Archives of Civil and Mechanical Engineering, 15(4) (2015) 1024-1036.
[21] A. Luz, V. Yepes, F. González-Vidosa, J.V. Martí. Diseño de estribos abiertos en puentes de carretera obtenidos mediante optimización híbrida de escalada estocástica. Informes de la Construcción, 67(540) (2015), e114.
[22] T. García-Segura, V. Yepes, J. Alcalá, E. Pérez-López. Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges. Engineering Structures, 92 (2015) 112-122.
[23] J.V. Martí, T. García-Segura, V. Yepes.Structural design of precast-prestressed concrete U-beam road bridges based on embodied energy. Journal of Cleaner Production, 120 (2016) 231-240.
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).
Acabamos de recibir la agradable noticia de que nuestra compañera Cristina Torres Machí ha sido elegida como ganadora de la categoría Tesis Doctoral del Premio Abertis Chile, patrocinada por la Cátedra Abertis de la Pontificia Universidad Católica de Chile. La tesis, denominada “Optimización heurística multiobjetivo para la gestión de activos de infraestructura de transporte terrestre” se defendió el 30 de marzo de 2015, optando brillantemente a la doble titulación de doctorado, tanto de la Universitat Politècnica de València (UPV) como de la Pontificia Universidad Católica de Chile (PUC). Los directores de tesis han sido la doctora Marcela Alondra Chamorro Gine (PUC), Eugenio Pellicer Armiñana (UPV) y Víctor Yepes Piqueras (UPV). La calificación fue la máxima posible, de sobresaliente “cum laude” por unanimidad.
TORRES-MACHÍ, C.; CHAMORRO, A.; YEPES, V.; PELLICER, E. (2014). Current models and practices of economic and environmental evaluation for sustainable network-level pavement management.Revista de la Construcción, 13(2): 49-56. http://dx.doi.org/10.4067/S0718-915X2014000200006
TORRES-MACHÍ, C.; CHAMORRO, A.; VIDELA, C.; PELLICER, E.; YEPES, V. (2014). An iterative approach for the optimization of pavement maintenance management at the network level.The Scientific World Journal, Volume 2014, Article ID 524329, 11 pages, http://dx.doi.org/10.1155/2014/524329 (link)
TORRES-MACHÍ, C.; CHAMORRO, A.; PELLICER, E.; YEPES, V.; VIDELA, C. (2015). Sustainable pavement management: Integrating economic, technical, and environmental aspects in decision making.Transportation Research Record, 2523:56-63. DOI:10.3141/2523-07
YEPES, V.; TORRES-MACHÍ, C.; CHAMORRO, A.; PELLICER, E. (2016). Optimal pavement maintenance programs based on a hybrid greedy randomized adaptive search procedure algorithm.Journal of Civil Engineering and Management, 22(4):540-550. DOI: 10.3846/13923730.2015.1120770
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.
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.
