UPV



Resultados de la búsqueda By Etiquetas: algoritmo


Optimización heurística mediante aceptación por umbrales

En algunos posts anteriores hemos comentado lo que es un modelo matemático de optimización, qué son las metaheurísticas, o cómo poder optimizar las estructuras de hormigón. A continuación os presentamos un Polimedia donde se explica brevemente cómo podemos optimizar siguiendo la técnica de optimización heurística mediante aceptación por umbrales. Podréis comprobar cómo se trata de un caso similar a la famosa técnica de la cristalización simulada. Espero que os sea útil. (En el caso de que no funcione el vídeo, el enlace es el siguiente: https://www.youtube.com/watch?v=ha5fiRsVPZM)

Podéis consultar, a modo de ejemplo, algunos artículos científicos que hemos escrito a ese respecto en las siguientes publicaciones:

  • CARBONELL, A.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2011). Heuristic optimization of reinforced concrete road vault underpasses. Advances in Engineering Software, 42(4): 151-159. ISSN: 0965-9978.  (link)
  • 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.; MEDINA, J.R. (2006). Economic Heuristic Optimization for Heterogeneous Fleet VRPHESTW. Journal of Transportation Engineering, ASCE, 132(4): 303-311. (link)

 

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

16 noviembre, 2017
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  ,  |  

¿Qué es la optimización por cristalización simulada?

La cristalización simulada (también llamado recocido simulado)  “Simulated Annealing, SA” constituye una de las estrategias a las que se recurre en la resolución de los problemas de optimización combinatoria. Kirkpatrick, Gelatt y Vecchi la propusieron por primera vez en 1983 y Cerny en 1985 de forma independiente. Estos autores se inspiraron en los trabajos sobre Mecánica Estadística de Metrópolis et al. (1953). La metaheurística despliega una estructura que se inserta cómodamente en la programación, mostrando además una considerable habilidad para escapar de los óptimos locales. Fue una técnica que experimentó un auge considerable en la década de los 80 para resolver los modelos matemáticos de optimización.

La energía de un sistema termodinámico se compara con la función de coste evaluada para una solución admisible de un problema de optimización combinatoria. En ambos casos se trata de evolucionar de un estado a otro de menor energía o coste. El acceso de un estado metaestable a otro se alcanza introduciendo “ruido” con un parámetro de control al que se denomina temperatura. Su reducción adecuada permite, con una elevada probabilidad, que un sistema termodinámico adquiera un mínimo global de energía. Conceptualmente es un algoritmo de búsqueda por entornos, que selecciona candidatos de forma aleatoria. La alternativa se aprueba si perfecciona la solución actual (D menor o igual que cero); en caso contrario, será aceptada con una probabilidad  (e(-D/T) si D>0, donde T es el parámetro temperatura) decreciente con el aumento de la diferencia entre los costes de la solución candidata y la actual. El proceso se repite cuando la propuesta no es admitida. La selección aleatoria de soluciones degradadas permite eludir los mínimos locales. La cristalización simulada se codifica fácilmente, incluso en problemas complejos y con funciones objetivo arbitrarias. Además, con independencia de la solución inicial, el algoritmo converge estadísticamente a la solución óptima (Lundy y Mees, 1986). En cualquier caso, SA proporciona generalmente soluciones valiosas, aunque no informa si ha llegado al óptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque sí comparable, ante otros específicos que aprovechan información adicional del problema. El algoritmo es lento, especialmente si la función objetivo es costosa en su tiempo de computación. Además, la cristalización simulada pierde terreno frente a otros métodos más simples y rápidos como el descenso local cuando el espacio de las soluciones es poco abrupto o escasean los mínimos locales.

Os dejo un vídeo explicativo: https://www.youtube.com/watch?v=wtw_B_3lrjE

Referencias

CERNY, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm. Journal of Optimization Theory and Applications, 45: 41-51.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

LUNDY, M.; MEES, A. (1986). Convergence of an Annealing Algorithm. Mathematical programming, 34:111-124.

METROPOLIS, N.; ROSENBLUTH, A.W.; ROSENBLUTH, M.N.; TELLER, A.H.; TELER, E. (1953). Equation of State Calculation by Fast Computing Machines. Journal of Chemical Physics, 21:1087-1092.

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)

¿Es fácil optimizar estructuras de hormigón?

Es más, ¿es posible que un ordenador sea capaz de diseñar de forma automática estructuras óptimas sin darle ninguna pista o información previa? Estoy convencido que a la vuelta de un par de años, todos los programas comerciales tendrán paquetes de optimización estructural que permitirán reducciones de coste en torno al 5-15% respecto a los programas actuales. Ya os adelanto que esta nueva tecnología va a traer consigo nuevas patologías en las estructuras de hormigón, que con la optimización se parecen más a las estructuras metálicas. Con el tiempo habrá que introducir capítulos o restricciones en las futuras versiones de la EHE o de los Eurocódigos. En este post vamos a continuar comentando aspectos relacionados con la modelización matemática, la optimización combinatoria, las metaheurísticas y los algoritmos.

Toda esta aventura la empezamos en el año 2002, con el primer curso de doctorado sobre optimización heurística en la ingeniería civil, que luego hemos ido ampliando y mejorando en el actual Máster Oficial en Ingeniería del Hormigón. Ya tenemos varias tesis doctorales y artículos científicos al respecto para aquellos de vosotros curiosos o interesados en el tema. Para aquellos que queráis ver algunas aplicaciones concretas, os recomiendo el siguiente capítulo de libro que escribimos sobre la optimización de distintas estructuras con un algoritmo tan simple como la cristalización simulada. Para aquellos otros que tengáis más curiosidad, os dejos algunas publicaciones de nuestro grupo de investigación en el apartado de referencias.

Os paso, para abrir boca, una forma sencilla de optimizar a través de este Polimedia. Espero que os guste.

Referencias:

  • MOLINA-MORENO, F.; MARTÍ, J.V.; YEPES, V. (2017). Carbon embodied optimization for buttressed earth-retaining walls: implications for low-carbon conceptual designs. Journal of Cleaner Production, 164:872-884. https://authors.elsevier.com/a/1VLOP3QCo9NDzg 
  • GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M.; YANG, D.Y. (2017). Lifetime Reliability-Based Optimization of Post-Tensioned Box-Girder Bridges. Engineering Structures, 145:381-391. DOI:10.1016/j.engstruct.2017.05.013 OPEN ACCESS
  • GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M. (2017). Multi-Objective Design of Post-Tensioned Concrete Road Bridges Using Artificial Neural Networks. Structural and Multidisciplinary Optimization, 56(1):139-150. doi: 10.1007/s00158-017-1653-0
  • 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
  • MOLINA-MORENO, F.; GARCÍA-SEGURA; MARTÍ, J.V.; YEPES, V. (2017). Optimization of Buttressed Earth-Retaining Walls using Hybrid Harmony Search Algorithms. Engineering Structures, 134:205-216. DOI: 10.1016/j.engstruct.2016.12.042
  • 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.
  • 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. DOI: 10.1016/j.jclepro.2016.02.024
  • 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. DOI: 10.1016/j.engstruct.2015.03.015 (link)
  • LUZ, A.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; MARTÍ, J.V. (2015). 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), e114. DOI: 10.3989/ic.14.089
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2015). 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 (descargar versión autor)
  • YEPES, V.; GARCÍA-SEGURA, T.; MORENO-JIMÉNEZ, J.M. (2015). A cognitive approach for the multi-objective optimization of RC structural problems. Archives of Civil and Mechanical Engineering, 15(4):1024-1036. doi:10.1016/j.acme.2015.05.001
  • 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. DOI: 10.1016/j.autcon.2014.10.013 (link)
  • GARCÍA-SEGURA, T.; YEPES, V.; MARTÍ, J.V.; ALCALÁ, J. (2014). Optimization of concrete I-beams using a new hybrid glowworm swarm algorithm. Latin American Journal of Solids and Structures,  11(7):1190 – 1205. ISSN: 1679-7817. (link)
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; LUZ, A. (2013). 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, DOI: http://dx.doi.org/10.1016/j.rimni.2013.04.010.
  • TORRES-MACHÍ, C.; YEPES, V.; ALCALA, J.; PELLICER, E. (2013). Optimization of high-performance concrete structures by variable neighborhood search. International Journal of Civil Engineering, 11(2):90-99 . ISSN: 1735-0522. (link)
  • MARTÍNEZ-MARTÍN, F.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2013). A parametric study of optimum tall piers for railway bridge viaducts. Structural Engineering and Mechanics45(6): 723-740. (link)
  • MARTINEZ-MARTIN, F.J.; GONZALEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2012). Multi-objective optimization design of bridge piers with hybrid heuristic algorithms. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering, 13(6):420-432. DOI: 10.1631/jzus.A1100304. ISSN 1673-565X (Print); ISSN 1862-1775 (Online).  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; YEPES, V.; ALCALÁ, J. (2013). Design of prestressed concrete precast road bridges with hybrid simulated annealing. Engineering Structures48:342-352. DOI:10.1016/j.engstruct.2012.09.014. ISSN: 0141-0296.(link)
  • YEPES, V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J.; VILLALBA, P. (2012). CO2-Optimization Design of Reinforced Concrete Retaining Walls based on a VNS-Threshold Acceptance Strategy. Journal of Computing in Civil Engineering ASCE, 26 (3):378-386. DOI: 10.1061/(ASCE)CP.1943-5487.0000140. ISNN: 0887-3801. (link)
  • CARBONELL, A.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2011). 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(3):227-235.  (link) [Global best local search applied to the economic design of reinforced concrete vauls]
  • CARBONELL, A.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2011). Heuristic optimization of reinforced concrete road vault underpasses. Advances in Engineering Software, 42(4): 151-159. ISSN: 0965-9978.  (link)
  • MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2011). Estudio paramétrico de pilas para viaductos de carretera. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 27(3):236-250. (link)
  • 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.
  • PEREA, C.; YEPES, V.; ALCALÁ, J.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2010). A parametric study of optimum road frame bridges by threshold acceptance. Indian Journal of Engineering & Materials Sciences, 17(6):427-437. ISSN: 0971-4588.  (link)
  • PAYÁ-ZAFORTEZA, I.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2010). On the Weibull cost estimation of building frames designed by simulated annealing. Meccanica, 45(5): 693-704. DOI 10.1007/s11012-010-9285-0. ISSN: 0025-6455.  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F. (2010). Design of prestressed concrete precast pedestrian bridges by heuristic optimization. Advances in Engineering Software, 41(7-8): 916-922. http://dx.doi.org/10.1016/j.advengsoft.2010.05.003
  • 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)
  • PAYÁ, I.; YEPES, V.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2009). CO2-Efficient Design of Reinforced Concrete Building Frames. Engineering Structures, 31: 1501-1508. ISSN: 0141-0296. (link)
  • YEPES, V.; ALCALÁ, J.; PEREA, C.; GONZÁLEZ-VIDOSA, F. (2008). A Parametric Study of Optimum Earth Retaining Walls by Simulated Annealing. Engineering Structures, 30(3): 821-830. ISSN: 0141-0296.  (link)
  • PEREA, C.; ALCALÁ, J.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2008). Design of Reinforced Concrete Bridge Frames by Heuristic Optimization. Advances in Engineering Software, 39(8): 676-688. ISSN: 0965-9978.  (link)
  • PAYÁ, I.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2008). Multiobjective Optimization of Reinforced Concrete Building Frames by Simulated Annealing. Computer-Aided Civil and Infrastructure Engineering, 23(8): 596-610. ISSN: 1093-9687.  (link)
  • PAYÁ, I.; YEPES, V.; CLEMENTE, J.J.; GONZÁLEZ-VIDOSA, F. (2006). Optimización heurística de pórticos de edificación de hormigón armado. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 22(3): 241-259. [Heuristic optimization of reinforced concrete building frames]. (link)
26 julio, 2017
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  |  

¿Las hormigas nos pueden enseñar a optimizar puentes?

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. (más…)

15 agosto, 2016
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  ,  ,  ,  |  

Big-Bang: Un nuevo algoritmo aplicado a la optimización de redes de transporte del tipo VRPTW

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.).

  1. 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.).

  1. 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

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).

  1. 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: vehicleswap 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

Tabla 1 – Probabilidad de elección de los operadores

  1. 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 velocidad

Fig. 2 – Beneficio obtenido para el problema HES-A con el algoritmo propuesto, analizado por el factor inicial de incremento de velocidad

Fig. 3 – Beneficio obtenido para el problema HES-A con el algoritmo propuesto, analizado por la factibilidad de la solución

Fig. 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

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

Tabla 3 – Resultados obtenidos para el problema HES-A

  1. 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.

8 abril, 2016
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  ,  ,  ,  |  

Aplicación en la docencia posgrado de algoritmos heurísticos en la optimización de estructuras: Muros nervados

MARTÍ, J.V.; YEPES, V. (2015). Aplicación en la docencia posgrado de algoritmos heurísticos en la optimización de estructuras: Muros nervados. XIII Jornadas de Redes de Investigación en Docencia Universitaria, 2 y 3 de julio, Alicante, 15 pp.

Descargar (PDF, 470KB)

7 julio, 2015
 
|   Etiquetas: ,  ,  ,  ,  |  

Los algoritmos genéticos

Charles Darwin en una fotografía tomada por J.M. Cameron en 1869.

Resulta fascinante comprobar cómo aplicando los mecanismos básicos de la evolución ya descrita por Darwin en su obra fundamental, El origen de las especies por medio de la selección natural, o la preservación de las razas preferidas en la lucha por la vida, publicada en 1859, se pueden generar algoritmos capaces de optimizar problemas complejos. Este tipo de metaheurísticas inspiradas en la Naturaleza ya se comentaron en posts anteriores cuando hablamos de la optimización por colonias de hormigas o de la cristalización simulada. Aunque es un algoritmo ampliamente conocido por la comunidad científica, voy a intentar dar un par de pinceladas con el único afan de divulgar esta técnica. La verdad es que las implicaciones filosóficas que subyacen tras la teoría de Darwin son de una profundidad difícil de entender cuando se lleva a sus últimos extremos. Pero el caso es que estos algoritmos funcionan perfectamente en la optimización de estructuras de hormigón, problemas de transporte y otros problemas difíciles de optimización combinatoria.

Para aquellos interesados, os paso en las referencias un par de artículos donde hemos aplicado los algoritmos genéticos para optimizar rutas de transporte aéreo o pilas de puente huecas de hormigón armado. (más…)

¿Qué es la optimización combinatoria?

Los problemas de optimización en los que las variables de decisión son enteras, es decir, donde el espacio de soluciones está formado por ordenaciones o subconjuntos de números naturales, reciben el nombre de problemas de optimización combinatoria. En este caso, se trata de hallar el mejor valor de entre un número finito o numerable de soluciones viables. Sin embargo la enumeración de este conjunto resulta prácticamente imposible, aún para problemas de tamaño moderado.

Las raíces históricas de la optimización combinatoria subyacen en ciertos problemas económicos: la planificación y gestión de operaciones y el uso eficiente de los recursos. Pronto comenzaron a modelizarse de esta manera aplicaciones más técnicas, y hoy vemos problemas de optimización discreta en diversas áreas: informática, gestión logística (rutas, almacenaje), telecomunicaciones, ingeniería, etc., así como para tareas variadas como el diseño de campañas de marketing, la planificación de inversiones, la división de áreas en distritos políticos, la secuenciación de genes, la clasificación de plantas y animales, el diseño de nuevas moléculas, el trazado de redes de comunicaciones, el posicionamiento de satélites, la determinación del tamaño de vehículos y las rutas de medios de transporte, la asignación de trabajadores a tareas, la construcción de códigos seguros, el diseño de circuitos electrónicos, etc. (Yepes, 2002). La trascendencia de estos modelos, además del elevado número de aplicaciones, estriba en el hecho de que “contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución” (Garfinkel, 1985). En Grötschel y Lobas (1993) se enumeran otros campos en los cuales pueden utilizarse las técnicas de optimización combinatoria.

REFERENCIAS

GARFINKEL, R.S. (1985). Motivation and Modeling, in LAWLER, E.L.; LENSTRA, J.K.; RINNOOY KAN, A.H.G.; SHMOYS, D.B. (eds.) The Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization. Wiley. Chichester.

GRÖTSCHEL, M.; LÓVASZ, L. (1993). Combinatorial Optimization: A Survey. Technical Report 93-29. DIMACS, May.

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)

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.

18 julio, 2014
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  ,  ,  ,  |  

Optimización y programación matemática

George Bernard Dantzig

George Bernard Dantzig (1914-2005), “padre de la programación lineal”

Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.

La programación matemática constituye un campo amplio de estudio que se ocupa de la teoría, aplicaciones y métodos computacionales para resolver los problemas de optimización condicionada. En estos modelos se busca el extremo de una función objetivo sometida a un conjunto de restricciones que deben cumplirse necesariamente. Las situaciones que pueden afrontarse con la programación matemática se suelen presentar en ingeniería, empresas comerciales y en ciencias sociales y físicas.

Con carácter general, un programa matemático (ver Minoux, 1986) consiste en un problema de optimización sujeto a restricciones en  de la forma:

 

(más…)

5 junio, 2014
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  |  

Previous Posts

Universidad Politécnica de Valencia