Planificación de redes de transporte con baja demanda

La planificación y gestión de redes de distribución de baja demanda exigen contar con técnicas eficientes de optimización de rutas. El sistema de optimización de rutas disponible no solo afecta el desarrollo de operaciones, sino también las decisiones tácticas y estratégicas, como el tamaño óptimo de la flota, la estimación de costes, las políticas de publicidad y la rotura de servicio, etc.  Por ejemplo, es habitual la venta de paquetes turísticos que incluyen el transporte; los precios se fijan mucho antes de que la demanda de transporte sea conocida, siendo frecuentes las cancelaciones de última hora y la llegada de nuevos clientes. Si  el número de pasajeros que deben ser transportados es pequeño, en comparación con la máxima capacidad de carga del vehículo óptimo a la distancia correspondiente, los beneficios o pérdidas del transporte dependen críticamente de la eficiencia del sistema de optimización de rutas. La Figura muestra la influencia de la optimización de operaciones en la planificación y la gestión de redes de distribución de baja demanda.

Redes de baja demanda
Planificación y Gestión de Redes de Distribución de Baja Demanda

Así pues, la planificación y gestión de redes de distribución de baja demanda generan una variedad de problemas de decisión que dependen críticamente de la optimización de operaciones, con espacios de solución muy amplios y, además, crecientes exponencialmente con el número de destinos y el tamaño de la flota. Esta explosión combinatoria de soluciones y la complejidad de las variables a optimizar impiden que la optimización pueda abordarse con técnicas de optimización exactas; por el contrario, las técnicas metaheurísticas y probabilísticas son alternativas siempre viables que, aunque no garantizan alcanzar la solución óptima absoluta, sí pueden proporcionar buenas soluciones a problemas reales complejos (ver Díaz et al., 1996). En este contexto, los sistemas inteligentes son métodos apropiados para resolver problemas complejos de optimización combinatoria como el planteado (ver Goonatilake and Treleaven, 1996, Fayyard et al., 1996 y Medina, 1998). En este artículo, se ha utilizado un algoritmo genético originalmente diseñado para resolver el TSP para abordar problemas más complejos como el CVRP y el SCVRP, utilizando funciones de coste y restricciones muy  variadas.

Por otro lado, el problema de optimización de las operaciones de transporte es crucial para la propia existencia de un cierto nicho de mercado de baja demanda. Si se consigue una distribución muy eficiente, es posible aflorar una demanda latente y satisfacerla con una flota pequeña y un costo razonable. Esta situación se produce en el mercado turístico con destinos poco masificados. En un ejemplo de aplicación presentado por Medina y Yepes (2003), se utiliza un aeropuerto hub, donde tanto para fijar precios como para definir la mejor estrategia comercial resulta imprescindible disponer de un sistema flexible para optimizar la distribución de pasajeros y de modelos estocásticos de simulación de escenarios.

Pantallazo rutas
Salida típica del programa de optimización de rutas

Referencias:

DÍAZ, A., GLOVER, F., GHAZIRI, H.M., GONZÁLEZ, J.L., LAGUNA, M., MOSCATO, P. y TSENG, F.T.(1996). Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería.  Editorial Paraninfo S.A., Madrid (España).

FAYYARD, U.M., PIATETSKI-SHAPIRO, G., SMYTH, P., and UTHURUSAMI, R.(1996). Advances in   Knowledge Discovery and Data Mining. MIT Press.

GOONATILAKE, S. and TRELEAVEN, P. (1996). Intelligent Systems for Finance and Business. John Wiley.

MEDINA, J.R.(1998). Algoritmos genéticos para la optimización de redes de distribución. Actas del X Congreso Panamericano de Ingeniería de Tránsito y Transporte. Santander 1998, Ministerio de Fomento (España), pp. 339-347.

MEDINA, J.R.; YEPES, V. (2003). Optimization of touristic distribution networks using genetic algorithms. Statistics and Operations Research Transactions, 27(1): 95-112.  ISSN: 1696-2281.  (pdf)

Diseño heurístico de puentes de hormigón pretensado como ejemplo de docencia de posgrado

Este artículo describe la impartición de un curso de posgrado en el diseño automatizado y optimización económica de estructuras de hormigón. El contenido forma parte de un Máster en Ingeniería de Hormigón que comenzó en octubre de 2007. El curso aplica los algoritmos heurísticos al diseño práctico de estructuras reales de hormigón, tales como muros, pórticos y marcos de pasos inferiores de carreteras, pórticos de edificación, bóvedas, pilas, estribos y tableros de puentes. Se presentan como casos prácticos dos tableros de puente de hormigón pretensado usados en la obra pública de construcción de carreteras. En primer lugar, se aplica SA a un tablero de un puente peatonal de viga artesa de hormigón prefabricado. El  segundo ejemplo aplica TA a un tablero de losa continua de hormigón postesado. Los casos estudiados indican que la optimización heurística es una buena opción para diseñar   estructuras de hormigón pretensado reduciendo los costes.

Pincha aquí para descargar

¿Cómo decidir cuando tenemos un dilema? El óptimo de Pareto

Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios;  si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado «óptimo de Pareto«. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.

 

 

Optimización económica de redes de transporte

Trascendencia del transporte

La trascendencia económica del sector del transporte genera costos sociales y medioambientales de gran envergadura. Esta actividad supone aproximadamente un sexto del Producto Interno Bruto (PIB) de los países industrializados (ver Yepes, 2002). Un estudio del National Council of Physical Distribution (ver Ballou, 1991) estima que el transporte sumó un 15% del PIB de Estados Unidos en 1978, constituyendo más del 45% de todos los costos logísticos de las organizaciones. En España, según datos del Ministerio de Fomento (ver CTCICCP, 2001), la participación del sector en el valor añadido bruto del año 1997 se situó en un 4.6%. En cuanto al empleo, 613,400 personas se encontraban ocupadas en el año 1999 en el sector de transportes en España, lo cual representa el 3.69% de la población activa. La distribución física representa para las empresas entre la sexta y la cuarta parte de las ventas y entre uno y dos tercios del total de los costos logísticos (Ballou, 1991). Continue reading «Optimización económica de redes de transporte»

¿Qué son las metaheurísticas?

 ¿Cómo se podrían optimizar en tiempos de cálculo razonable problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otro tipo de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que es imposible hacerlo con métodos matemáticos exactos? La respuesta son los métodos aproximados, también denominados heurísticas. Este artículo divulgativo trata de ampliar otros anteriores  donde ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Para más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto, una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al, 2008).

Desde los primeros años de la década de los 80, la investigación de los problemas de optimización combinatoria se centra en el diseño de estrategias generales que sirvan para guiar a las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.

Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.

Las metaheurísticas son susceptibles de agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de memoria que guíe de la exploración del espacio de elecciones posibles permite otro tipo de agrupamiento. En otras circunstancias se emplean perturbaciones de las opciones, de la topología del espacio de soluciones, o de la función objetivo. En la Figura se recoge una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), teniendo en común todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que existen en este momento muchas más técnicas de optimización, pero puede ser dicha clasificación un punto de partida para una mejor taxonomía de las mismas.

 

Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales.
Figura. Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales (Yepes, 2002)

Las  metaheurísticas empleadas en la optimización combinatoria en podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que éste concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los diferentes problemas de optimización combinatoria.

Referencias

GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)

OSMAN, I.H.; KELLY, J.P. (Eds.) (1996). Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers.

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Comunicaciones presentadas en el 2º Congreso EIME

En plena celebración del 2º Congreso Nacional sobre Ensañanza de las Matemáticas en Ingeniería de Edificación, desarrollado los días 18 y 19 de julio de 2013 en la Universitat Politècnica de València, aprovecho para presentar los resúmenes de los trabajos que hemos presentado. Espero que sean de vuestro interés.

Los autores agradecen el aporte financiero realizado para este trabajo por el Ministerio de Ciencia e Innovación (Proyecto de Investigación BIA2011-23602) y por la Universitat Politècnica de València (Proyecto de Investigación PAID-06-12).

BÁRCENA, A.; ALCALÁ, J.; YEPES, V.; MARTÍ, J.V. (2013). Diseño automático de forjados de chapa nervada optimizados con criterios de economía y sostenibilidad. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 159-172. ISBN: 978-84-8363-992-4.

Los forjados mixtos con chapa colaborante son una tipología de estructuras horizontales que está experimentando un crecimiento continuo en las últimas décadas. Su optimización presenta un enorme interés para conseguir diseños más asequibles y sostenibles, que permitan un mejor aprovechamiento de los recursos necesarios. El objetivo de este trabajo es aplicar técnicas heurísticas para este tipo de forjados, permitiendo plantearse el problema de una manera más compleja, utilizando una definición completa del forjado mixto y sus componentes, mientras que al mismo tiempo satisface las restricciones de este tipo de estructuras. Los algoritmos de optimización aplicados a la estructura se basan en tres metaheurísticas: búsqueda local de descenso (DLS), recocido simulado (SA) y el umbral de aceptación (TA). Se muestran las principales características, los parámetros que deben calibrarse y los diferentes modos de selección de dichos parámetros, para cada una de las heurísticas. La comparación de los resultados ha permitido señalar la SA como la mejor heurística de todas ellas. Por último, una vez seleccionado el mejor calibración de la SA, se ha estudiado la sensibilidad del modelo y un estudio paramétrico con diferentes tramos horizontales.

GARCÍA-SEGURA, T.; YEPES, V.; ALCALÁ, J.; MARTÍ, J.V. (2013). Optimización multiobjetivo de viga en I de hormigón armado con criterios sostenibles. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 135-148. ISBN: 978-84-8363-992-4.

Este estudio tiene como objetivo presentar una metodología de diseño de una viga en I de hormigón armado de alta resistencia autocompactable o convencional.  Algoritmos heurísticos como recocido simulado multiobjetivo “Multiobjective Simulated Annealing” (MOSA) son utilizados para buscar dentro del espacio de soluciones factibles aquellas que mejoren criterios como coste, emisiones de CO2 o durabilidad. Se tomará como ejemplo una viga en I biapoyada de 15 m de luz definida por 20 variables. La viga deberá cumplir de acuerdo a la Instrucción de Hormigón Estructural (EHE-08) los requisitos de seguridad estructural, así como aspectos constructivos o geométricos. El análisis comparativo de los objetivos servirá como guía para el diseño sostenible de estructuras de hormigón. Los resultados obtenidos muestran una clara tendencia de diseño de estructuras de hormigón hacia la sostenibilidad.

MARTÍ, J.V.; YEPES, V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Optimización memética de vigas artesa prefabricadas con criterios sostenibles de hormigón con fibras. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 91-104. ISBN: 978-84-8363-992-4.

Esta comunicación describe una metodología heurística empleada para diseñar estructuras bajo criterios sostenibles, con reducción de la emisión de gases de efecto invernadero (CO2) durante la fase de ejecución. La estructura presentada es un tablero de un paso superior de carreteras de vigas artesa  prefabricadas de hormigón reforzado con fibras, empleando para ello un algoritmo memético híbrido, que combina la búsqueda poblacional de soluciones mediante algoritmos genéticos y una búsqueda por entornos variable (VDNS). Este algoritmo se aplica a un tablero formado por dos vigas isostáticas para una luz de 30 m y una losa de 12 m de ancho. La estructura analizada consta de 41 variables discretas. El módulo de la evaluación considera los estados límite último y de servicio que se aplican habitualmente para estas estructuras. El uso del algoritmo memético requiere previamente su calibración. Cada una de las heurísticas se procesa nueve veces, obteniéndose información estadística sobre el valor mínimo, el medio y las desviaciones. El procedimiento presentado permite la aplicación práctica al diseño real y su adaptación al proceso de prefabricación.

MARTÍ, J.V.; YEPES, V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Diseño de vigas en “U” de hormigón con fibras mediante la heurística SA con criterios económicos. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 299-309. ISBN: 978-84-8363-992-4.

Este artículo se ocupa de la optimización económica de los puentes de carreteras formados por tableros constituidos por una losa de hormigón ejecutada in situ y dos vigas artesa de hormigón reforzado con fibras metálicas pretensadas prefabricadas. Se comprueba la eficacia de la optimización heurística por el método del recocido simulado “simulated annealing” (SA). 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 prácticamente a cualquier tipo de molde de una instalación de prefabricados. El ejemplo que se analiza consta de 60 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. El uso del algoritmo SA requiere previamente su calibración. La heurística se procesa 9 veces, obteniéndose información estadística sobre el valor mínimo, el medio y las desviaciones. El mejor resultado obtenido tiene un coste de 109.127 €.  Finalmente, entre las principales conclusiones de este estudio, destaca que económicamente es factible el uso de fibras de acero en el hormigón estructural y que las soluciones y los tiempos de proceso computacional son tales, que este método se puede aplicar de un modo práctico a casos reales.

RODRÍGUEZ-CALDERITA, A.M.; ALCALÁ, J.; YEPES, V.; MARTÍ, J.V. (2013). Optimización heurística aplicada al diseño automático de forjados de losa postesa. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 63-75. ISBN: 978-84-8363-992-4.

En ese trabajo se muestran las características principales de los forjados de losa postesa obtenidos tras aplicar métodos heurísticos de optimización. Estos forjados son ventajosos frente a soluciones más convencionales a partir de ciertas luces. El proceso de diseño de estos forjados se puede plantear como un problema de optimización, que abordado con métodos heurísticos puede ser formulado de un modo totalmente realista. Se pueden encontrar diseños completos de forjados optimizados no solo con criterios de economía, sino también de sostenibilidad, pudiendo comparar ambos casos. Los resultados obtenidos en este trabajo muestran una clara tendencia a disponer cantos muy estrictos en los resultados óptimos. Aplicando criterios de sostenibilidad se tiende a hormigones de mayores resistencias que con criterios económicos. Finalmente se han realizado pruebas de sensibilidad a los precios, que muestran mucha independencia de los forjados óptimos frente a las variaciones de precios ensayadas.

TORRES-MACHÍ, C.; YEPES, V.; PELLICER, E.; CHAMORRO, A. (2013). Optimización en la gestión de activos. Aplicación al mantenimiento de múltiples estructuras de edificación. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp.323-332. ISBN: 978-84-8363-992-4.

En una sociedad desarrollada en la que el nivel de inversión en nuevas infra-estructuras tiende a estabilizarse, su conservación pasa a ser uno de los retos a los que deben enfrentarse sus gestores, de forma que los recursos escasos de los que disponen, sean destinados en la mejor alternativa posible. Sin embargo, la asignación óptima de recursos de conservación es un problema que no tiene una solución directa. De hecho, la resolución del problema de asignación de recursos para el mantenimiento de una infra-estructuras presenta un problema de explosión combinatoria, pues existen ST soluciones factibles para la gestión una infraestructura con S posibles tratamientos de conservación y un periodo de análisis de T años. El objetivo de esta comunicación es presentar un modelo matemático que permite optimizar los recursos asignados al mantenimiento de una infraestructura de edificación, de forma que se maximice el nivel de servicio de la misma, cumpliendo además con unas restricciones presupuestarias y unos niveles mínimos de conservación.

YEPES, V.; ALCALÁ, J.; MARTÍ, J.V.;  GONZÁLEZ-VIDOSA, F. (2013). Cómo predimensionar muros óptimos sin calculadora usando la inteligencia artificial. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 119-134. ISBN: 978-84-8363-992-4.

El trabajo presenta un estudio de diseño automático de muros ménsula de hormigón armado basado en el recocido simulado, dentro de un esquema de búsqueda en entornos variables, como metaheurística de optimización económica. Cada solución se caracteriza por 20 variables de diseño: 4 geométricas relacionadas con el espesor del alzado y de la zapata, así como con las longitudes de la puntera y del talón; 4 tipos de material y 12 variables relacionadas con el armado. El trabajo estudia la importancia relativa de factores tales como el coeficiente de rozamiento suelo-zapata, el ángulo de rozamiento muro-relleno y la limitación de la flecha del alzado. Por último, se presenta un estudio paramétrico de muros de 4 a 10 metros de altura total para diferentes rellenos y condiciones de carga. Se aportan valores medios de costes, volúmenes de hormigón, espesor de alzados y zapatas, longitudes de punteras y talones que pueden ser útiles para el predimensionado económico de muros. Los resultados muestran cómo la inteligencia artificial es capaz de dimensionar de forma automática los muros ménsula de hormigón armado, detectando relaciones aportadas por la experiencia en el cálculo de este tipo de estructuras. Se aporta, como novedad de gran interés práctico, unas reglas sencillas que permiten predimensionar y estimar económicamente de forma rápida este tipo de estructuras.

YEPES, V.; MARTÍ, J.V.; ALCALÁ, J.; GARCÍA-SEGURA, T. (2013). Métodos empleados en el proyecto HORSOST sobre diseño sostenible con hormigón no convencional. 2º Congreso Nacional de la Enseñanza de las Matemáticas en la Ingeniería de Edificación, EIMIE, 18-19 de julio, Valencia, pp. 259-272. ISBN: 978-84-8363-992-4.

El objetivo fundamental del proyecto de investigación HORSOST consiste en establecer pautas de diseño eficiente de estructuras realizadas con hormigón no convencional optimizadas heurísticamente con funciones multiobjetivo relacionadas con la sostenibilidad. Se pretende avanzar en el establecimiento de nuevos diseños que permitan extraer las ventajas que aportan los hormigones especiales, en particular hormigones de alta resistencia, hormigones con fibras, hormigones autocompactantes. Para ello se utiliza el análisis del ciclo de vida de dichas estructuras (elaboración, transporte, procedimientos constructivos, mantenimiento, etc.) considerando aspectos energéticos, medioambientales, sociales y económicos. La optimización heurística permite evaluar los diseños más eficientes, comparar soluciones y generar bases de datos sobre las que aplicar herramientas procedentes de la minería de datos y del aprendizaje automático para extraer información no trivial que permita fórmulas de predimensionamiento. La posibilidad de análisis se debe a que las herramientas matemáticas empleadas presentan un carácter general. Se aplican técnicas como redes neuronales o la teoría del valor extremo además de otras herramientas más habituales como la regresión lineal múltiple o el análisis por componentes principales.

 

Automatic design of concrete vaults using iterated local search and extreme value estimation

La optimización de estructuras reales de hormigón armado constituye un campo de gran interés no solo en la investigación, sino también en la aplicación real en obra. Os paso un artículo reciente que explica una forma de optimizar bóvedas de hormigón empleadas habitualmente en pasos inferiores, como falsos túneles. Los ahorros que se pueden conseguir, en este caso, han sido de un 7% respecto a un diseño tradicional. En el caso de obras lineales de gran longitud, los ahorros pueden ser nada despreciables. La revista Latin American Journal of Solids and Structures es en abierto, de donde podéis descargar este y otros artículos de interés.

Pincha aquí para descargar

 

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.