Figura 1. Las generaciones futuras tendrán que pagar por unas infraestructuras deterioradas
En esta entrada, vamos a justificar cómo ciertas estrategias de gestión del mantenimiento y conservación de las carreteras pueden aumentar significativamente los costos para los usuarios. Para lograrlo, en primer lugar, definiremos las diferentes estrategias disponibles, y posteriormente analizaremos cuál de ellas tiene un impacto negativo en los costos que deben asumir los usuarios.
Si bien es cierto que estas nuevas infraestructuras nacen con un periodo de vida relativamente largo, no menos cierto es que una parte significativa de dicha infraestructura está empezando a notar el paso del tiempo; es más, parece que podemos vivir dentro de un horizonte no tan lejano, un verdadero colapso en los niveles de servicio prestados por estos activos. Lo peor de todo ello es que estas infraestructuras se financiaron a largo plazo y la siguiente generación (Figura 1) se encontrará con la sorpresa de tener que pagar por infraestructuras con niveles de servicio pésimos. Es lo que en otro artículo califiqué como la “crisis de las infraestructuras”. Todo esto nos lleva a la cuestión central del problema: la necesidad urgente de contar con un plan racional y recursos suficientes para mantener las infraestructuras básicas de un país.
En la Figura 2 podemos ver una gráfica donde se representa no solo la degradación del estado o de las prestaciones de la carretera, sino las distintas estrategias que se tienen al alcance para modificar dicho deterioro.
Figura 2. Estrategias de conservación (Clemente, 2012)
Así, la estrategia preventiva o proactiva tiene como objetivo mantener en el tiempo el estado físico del elemento en un nivel adecuado, evitando que alcance elevados niveles de deterioro que puedan afectar a su funcionalidad y disparar los costes de reparación. Estas actuaciones son normalmente de alcance y coste limitado y se realizan con cierta periodicidad en función de la evolución observada o incluso de manera programada antes de que el defecto se llegue a manifestar. La estrategia correctiva o reactiva es la que deja al elemento que se deteriore al límite, en cuyo momento se efectúan intervenciones de gran calado, como por ejemplo grandes rehabilitaciones integrales o estructurales, que lo devuelven, o lo intentan devolver, a su estado original. Sin embargo, son actuaciones de mayor coste, aunque más separadas en el tiempo. Por último, se podría optar por un deterioro controlado hasta la retirada. En este caso se pasa directamente a retirar el elemento cuando se ha alcanzado su vida útil de servicio y se sustituye por otro similar. Durante este periodo no se interviene, o se hace mínimamente para no afectar la funcionalidad.
Por tanto, la estrategia óptima no es evidente, pues depende tanto de factores endógenos (características constructivas de la carretera, edad, etc.) y exógenos (condiciones del clima, nivel de tráfico, etc.) y en consecuencia no se pueden generalizar las conclusiones. Este problema, por consiguiente, es uno de los focos más importantes de nuestro grupo de investigación. Os he puesto referencias de algunas de nuestras publicaciones.
Pero el problema se hace más complejo cuando se tienen en cuenta los costes de los usuarios. En efecto, las características de la carretera y el nivel y la composición de la demanda de tráfico influyen en los costes de los usuarios. Un mal estado del pavimento, incrementa claramente el coste soportado por el usuario. Y lo que es peor, un estado subóptimo de la infraestructura debido a una estrategia de conservación reactiva, tiene como consecuencia el incremento del riesgo de accidentes, la reducción de la velocidad de los vehículos, las restricciones de paso y la elección por los usuarios de itinerarios alternativos con mayor tiempo de recorrido. Insisto en este punto. Una conservación deficiente genera mayores costes a los usuarios relacionados con el valor del tiempo de viaje, con el vehículo y con los accidentes de tráfico.
En la Figura 3 se puede ver que existe un hipotético nivel de conservación óptimo que minimiza los costes totales del transporte, teniendo en cuenta el coste del usuario, el coste de conservación y el coste de construcción. Sin una estrategia clara de conservación, los responsables de una red de carreteras suelen realizar una conservación correctiva, que tiene un aparente ahorro económico en el corto plazo, pero que traslada al futuro unos costes que pueden ser muy elevados tanto para los contribuyentes que sufragan la inversión como para los usuarios.
CLEMENTE, J.J. (2012). La toma de decisión en el marco de la gestión de activos de infraestructuras de transporte terrestre. Trabajo de investigación. Universitat Politècnica de València.
SALAS, J.; YEPES, V. (2019). MS-ReRO and D-ROSE methods: assessing relational uncertainty and evaluating scenarios’ risks and opportunities on multi-scale infrastructure systems. Journal of Cleaner Production, (accepted, in press).
SIERRA, L.A.; PELLICER, E.; YEPES, V. (2017). Method for estimating the social sustainability of infrastructure projects. Environmental Impact Assessment Review, 65:41-53.
SIERRA, L.A.; YEPES, V.; GARCÍA-SEGURA, T.; PELLICER, E. (2018). Bayesian network method for decision-making about the social sustainability of infrastructure projects. Journal of Cleaner Production, 176:521-534.
SIERRA, L.A.; YEPES, V.; PELLICER, E. (2017). Assessing the social sustainability contribution of an infrastructure project under conditions of uncertainty. Environmental Impact Assessment Review, 67:61-72.
SIERRA, L.A.; YEPES, V.; PELLICER, E. (2018). A review of multi-criteria assessment of the social sustainability of infrastructures. Journal of Cleaner Production, 187:496-513.
TORRES-MACHÍ, C. (2015). Optimización heurística multiobjetivo para la gestión de activos de infraestructuras de transporte terrestre. Tesis doctoral. Universitat Politècnica de València – Pontificia Universidad Católica de Chile.
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.
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.
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.
TORRES-MACHI, C.; PELLICER, E.; YEPES, V.; CHAMORRO, A. (2017). Towards a sustainable optimization of pavement maintenance programs under budgetary restrictions. Journal of Cleaner Production, 148:90-102.
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.
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.
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)
Preservar las infraestructuras en un estado mínimamente adecuado de conservación y mantenimiento es una necesidad de primer orden en cualquier sociedad. Sin embargo, por motivos que a veces son estructurales y otras coyunturales, los responsables de esta tarea no prestan la atención y los recursos necesarios para este cometido. Parece que la inversión en conservación de los activos siempre ha sido insuficiente incluso en países desarrollados.
En efecto, parece evidente que el desarrollo económico que tuvo lugar en países como el nuestro en la última parte del siglo XX se centró, en el caso por ejemplo de las carreteras, en ampliar la red para apoyar dicho desarrollo. Si bien es cierto que estas nuevas infraestructuras nacen con un periodo de vida relativamente largo, también es cierto que una parte nada desdeñable de dicha infraestructura está empezando a notar el paso del tiempo, y lo que es peor, parece que podemos vivir dentro de un horizonte no tan lejano, a un verdadero colapso en los niveles de servicio prestados por estos activos. Lo peor de todo ello es que estas infraestructuras se financiaron a largo plazo y la siguiente generación se va a encontrar con la sorpresa de tener que pagar Continue reading “La “crisis” de las infraestructuras”→
No resulta nada fácil realizar el mantenimiento de una red de carreteras durante un horizonte, digamos de 20 años, cuando los presupuestos son muy restrictivos. Las consecuencias son nefastas para la calidad del servicio prestado por dicha infraestructura. El problema deriva del hecho de tener que elegir la mejor opción de mantenimiento, en el momento adecuado, con un presupuesto mínimo, de forma que todo ello permita maximizar la condición de servicio de la infraestructura. ¡Un problema nada fácil!
Para solucionar este tipo de problemas hemos propuesto un algoritmo heurístico novedoso capaz de generar soluciones óptimas en casos tan complicados como el que se presenta.
Os dejo el resumen, las palabras clave y la referencia por si queréis citar el artículo.
Abstract. Insufficient investment in the public sector together with inefficient maintenance infrastructure programs lead to high economic costs in the long term. Thus, infrastructure managers need practical tools to maximize the Long-Term Effectiveness (LTE) of maintenance programs. This paper describes an optimization tool based on a hybrid Greedy Randomized Adaptive Search Procedure (GRASP) considering Threshold Accepting (TA) with relaxed constraints. This tool facilitates the design of optimal maintenance programs subject to budgetary and technical restrictions, exploring the effect of different budgetary scenarios on the overall network condition. The optimization tool is applied to a case study demonstrating its efficiency to analyze real data. Optimized maintenance programs are shown to yield LTE 40% higher than the traditional programs based on a reactive strategy. To extend the results obtained in this case study, a set of simulated scenarios, based on the range of values found in the real example, are also optimized. This analysis concludes that this optimization algorithm enhances the allocation of maintenance funds over the one obtained under a traditional reactive strategy. The sensitivity analysis of a range of budgetary scenarios indicates that the funding level in the early years is a driving factor of the LTE of optimal maintenance programs.
Alcoy (Alicante) es la ciudad de los puentes. Es, posiblemente, uno de los pueblos donde han nacido más ingenieros de caminos, entre los que me incluyo. El post de hoy va dedicado a una obra de ingeniería fallida, la línea de ferrocarril entre Alicante y Alcoy. El proyecto de esta línea de ferrocarril corrió a cargo del ingeniero de caminos José Roselló Martí , destinado en 1927 a la 3ª jefatura de Estudios y Construcciones de Ferrocarriles del Sureste de España, donde se encargó de la redacción del proyecto del viaducto sobre el rio Polop y los de los barrancos de Siete Lunas, Barchell, Uxola y Zinc, en Alcoy.
A finales de los años 20 del siglo XX se pudo materializar, tras no pocas dificultades, el trazado de la línea férrea que uniría Alicante y Alcoy. El último proyecto lo redactó Roselló el 13 de julio de 1929. De esta línea destacan los numerosos puentes y túneles que se tuvieron que hacer y que hoy sirven como ruta verde para el turismo de interior en estas comarcas.
La mayor parte de los viaductos se construyeron con tres elementos: arcos de medio punto de hormigón armado de 30 m de luz, arcos de hormigón en masa de 12 m de luz y vigas rectas de hormigón armado de 17,60 m. El más grande y espectacular de los viaductos es el que salva el río Polop, situado al pie del Parque Natural de la “Font Roja”. Posee 230 m. de longitud y una altura máxima sobre el cauce de 46 m. Consta de cinco arcos de 30 m. de luz de hormigón armado y tres arcos de avenida de 12 m. de luz, más pequeños, de hormigón en masa. Las bóvedas tienen todas 3,60 m de anchura, 0,90 m de espesor en la clave y 1,40 m. en los arranques. Los tímpanos están aligerados por arquillos de 4 m. y arriostrados transversalmente por tirantes del mismo material. Dispone de miradores en los arcos pares.
Se utilizaron cerchas semirrígidas para el armado de los arcos, pues aún no se habían publicado los modelos oficiales de puentes para ferrocarril. Consistía este sistema en el empleo de estructuras rígidas de acero, dimensionadas para sostener el peso propio de la bóveda durante la construcción. Colgado de las cerchas, y bien sujeto a las cabezas inferiores de las mismas, se colocaba un encofrado de madera siguiendo el intradós de la bóveda. Se complementaba este entablonado con unas paredes laterales de madera hasta la altura del trasdós, quedando así establecido el encofrado de las bóvedas, pudiendo de este modo suprimirse costosas cimbras y andamios. A esta armadura se le añadía las armaduras en aquellas zonas necesarias para resistir la flexión que ocasionaban las sobrecargas móviles de servicio del puente.
Asistimos, en las primeras décadas del siglo XX, al predominio de los puentes de hormigón armado en España, que poco a poco fueron desplazando a los puentes metálicos por su mayor economía frente al alto precio del acero y menores gastos de mantenimiento. El predominio del hormigón fue posible al desarrollo en nuestro país de la técnica con figuras como Juan Manuel Zafra o José Eugenio Ribera.
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.
Cuando se trata de construir un puente con vigas prefabricadas, uno de los problemas a resolver es el transporte por carretera de este tipo de elementos. Debido a las características técnicas de la carga, que exceden en dimensiones, masa y carga por eje de las máxima autorizadas, se requiere de una Autorización Complementaria de Circulación que expedirá el Organismo competente en materia de tráfico. Las unidades de transporte son camiones semirremolques que se denominan habitualmente “dollys”.
A continuación os paso varios vídeos explicativos y un vídeo tutorial de Javier Luque donde se aplica el concepto de Centro Instantáneo de Rotación para el cálculo de velocidades lineales en función de condicionantes iniciales de la velocidad angular. Un buen problema de física que tiene su aplicación en el transporte de vigas de gran tamaño. Espero que os sean útiles los vídeos.
El puente Canal de Magdeburgo, sobre el río Elba. Wikipedia
El puente Canal de Magdeburgo (Alemania) es famoso por ser el acueducto navegable más largo del mundo, con una longitud total de 918 m. Este puente conecta el canal Elbe-Havel con el canal de Mittelland, que atraviesa el río Elba y sobre el que discurre el canal navegable de Magdeburgo. El objetivo es acortar kilómetros de navegación y favorecerla cuando los calados del río son excesivamente bajos.
Su construcción comenzó en 1997 y abrió sus puertas en octubre de 2003. Su coste aproximado fue de 500 millones de euros y es famoso por ser el acueducto navegable más largo del mundo. Posee una longitud total de 918 m, una anchura de 34 m y una profundidad del canal de 4,25 m. El puente tiene una luz máxima de 106 m y se construyó con cerca de 68 000 m³ de hormigón y 24 000 t de acero.
Fuente: http://discoverytumundo.blogspot.com.es/
Os dejo un par de vídeos sobre el acueducto, el primero de ellos de licitacivil. Espero que os gusten.
Podéis ampliar la información en algunos de los siguientes enlaces:
Hoy lunes 30 de marzo de 2015 se ha defendido con éxito la tesis doctoral de la profesora Cristina Torres Machí denominada “Optimización heurística multiobjetivo para la gestión de activos de infraestructuras de transporte terrestre”, que optaba 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 ha sido la máxima posible, de sobresaliente “cum laude” por unanimidad.
Os paso el resumen de la tesis:
“A pesar de la importancia de las infraestructuras en el desarrollo económico y social, los recursos disponibles para su conservación suelen ser insuficientes, generando un deterioro acelerado de las mismas. En este contexto surge la disciplina de gestión de activos de infraestructura, que busca optimizar la asignación de recursos para la gestión, operación y conservación de la infraestructura mediante un análisis de su ciclo de vida.
Los criterios tradicionalmente empleados para evaluar las alternativas de conservación han sido los técnicos y económicos. Si bien, recientemente, se han realizado esfuerzos para cuantificar el impacto ambiental; los modelos actuales carecen de un enfoque integrado. Surge así la oportunidad de desarrollar una evaluación sostenible que integre los aspectos técnicos, económicos y ambientales en el ciclo de vida de la infraestructura.
En relación a la asignación óptima de recursos, los métodos mayoritariamente empleados son los de programación matemática y los métodos de optimización aproximada. Dentro de estos últimos, las aplicaciones de algoritmos heurísticos resultan escasas, limitándose a resolver el problema a nivel de proyecto. Estos métodos, sin embargo, han sido exitosamente aplicados para resolver problemas de optimización combinatoria en otros campos de investigación. A esto hay que añadir que las aplicaciones desarrolladas se centran, mayoritariamente, en la optimización de un único objetivo; obviando la naturaleza multiobjetivo del problema real. Se detecta, por tanto, la oportunidad de desarrollar una herramienta de optimización heurística multiobjetivo que, considerando una evaluación sostenible de alternativas, mejore la asignación actual de recursos.
A la vista de estos antecedentes, el objetivo principal de esta investigación consiste en desarrollar una herramienta para la evaluación de alternativas de conservación y la optimización heurística multiobjetivo, que permita una asignación más sostenible y eficiente de los recursos disponibles para la conservación de redes de activos de infraestructura de transporte terrestre. La herramienta propuesta se aplica a un caso de estudio real que consiste en la gestión de una red de pavimentos urbanos en Chile.
De la aplicación de la herramienta de optimización al caso de estudio se concluye que los algoritmos heurísticos basados en búsquedas por entornos resultan poco eficientes para resolver el problema de asignación de recursos de conservación. Ante esta limitación, se desarrolla un nuevo método híbrido que considera los algoritmos GRASP (Greedy Randomized Adaptative Search Procedure), GLS (Guided Local Search) y GFB (Greedy First Best). Además, el método propuesto permite evaluar las alternativas de conservación considerando, de forma integrada, criterios técnicos, económicos y ambientales.
El algoritmo híbrido propuesto diseña programas de conservación con una efectividad media un 9% superior a la obtenida con el algoritmo de búsqueda por entornos más eficaz, requiriendo para ello un menor esfuerzo computacional. En la aplicación al caso de estudio chileno, se observa que el algoritmo híbrido mejora la gestión actual, aumentando en un 22% la condición media de la red y reduciendo, además, las emisiones de CO2 en un 12%.
En términos prácticos, los programas óptimos consideran una política proactiva, en la que los pavimentos se tratan cuando la condición de los mismos aún es buena. Por último, la herramienta propuesta mejora la planificación temporal de los recursos. En base a las evidencias demostradas en el caso de estudio, se concluye que la distribución temporal del presupuesto es un factor clave en el desempeño técnico y ambiental de la red”.
Palabras Clave: Sostenibilidad; sustentabilidad; análisis del ciclo de vida; gestión de infraestructura; conservación; preservación.
Preservar las infraestructuras en un estado mínimamente adecuado de conservación y mantenimiento es una necesidad de primer orden en cualquier sociedad. Sin embargo, por motivos que a veces son estructurales y otras coyunturales, los responsables de esta tarea no prestan la atención y los recursos necesarios para este cometido. Parece que la inversión en conservación de los activos siempre ha sido insuficiente incluso en países desarrollados.
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.
