UPV



Resultados de la búsqueda By Etiquetas: transporte


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: ,  ,  ,  ,  ,  ,  ,  |  

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: ,  ,  ,  ,  ,  ,  ,  ,  ,  |  

Transporte de aglomerado asfáltico en caliente

Transporte y extendido de aglomerado asfáltico. http://www.madrid.es/

El transporte de las mezclas asfálticas se realiza mediante camiones volquete desde la planta al tajo de extensión. La caja basculante debe estar limpia y ligeramente humedecida con agua jabonosa para evitar que la mezcla se adhiera. La caja debe ser corta y alta, con una capacidad acorde con la tolva de recepción de la extendedora. Además, deben disponerse lonas o cobertores para proteger la mezcla del agua, polvo o de la pérdida de calor por viento. El número de camiones necesario depende de la capacidad de puesta en obra de la extendedora, siempre que no quede limitada por la producción de la planta de fabricación, y de la distancia de transporte. Se aconseja cierto sobredimensionamiento en la flota de camiones para evitar retrasos o prever posibles averías. Un aspecto clave en la puesta en obra de las mezclas asfálticas en caliente es la distancia de transporte. El enfriamiento de la mezcla depende fundamentalmente de la temperatura ambiente y del viento. Con una lona de protección, la pérdida de temperatura de la masa es de pocos grados, enfriándose una pequeña costra superficial, lo que permite distancias máximas de transporte apreciables. Así, en camiones de gran capacidad, se pueden llegar hasta unos 25 km, e incluso en circunstancias excepcionales, a más de 100 km. Otro aspecto importante es la segregación del material, que se evitará minimizando las alturas de descarga la formación de montones cónicos. El material se deberá mover lentamente durante la carga, ayudando manualmente si es necesario la distribución lateral. Durante el transporte se pueden apreciar razones que pueden motivar el rechazo de la mezcla:

  • Temperatura alta: Se detecta cuando la mezcla desprende un humo azulado, en cuyo caso se debe comprobar la temperatura.
  • Temperatura baja: La mezcla presenta un aspecto poco fluido, con los áridos gruesos mal cubiertos. Se debe comprobar la temperatura.
  • Exceso de ligante: Es fácil de detectar si la mezcla fluye o asienta más de lo normal. Se debe tomar una muestra y señalar la zona por si hay que levantarla en el caso de confirmarse el exceso.
  • Defecto de ligante: Falta brillo en la mezcla y los áridos no se encuentran perfectamente recubiertos, con un aspecto suelto del material. Se procederá igual que con el exceso.
  • Falta de uniformidad: Se aprecia el distinto aspecto de la mezcla en distintas zonas.
  • Exceso de árido grueso: El aspecto de la mezcla es parecido al de exceso de ligante, pero una vez extendida la capa, se aprecia una textura más gruesa y abierta de lo normal.
  • Exceso de árido fino: El aspecto es el del defecto de ligante, que se puede comprobar observando la textura superficial de la mezcla una vez extendida, así como su comportamiento al compactarla.
  • Exceso de humedad: Se observa un desprendimiento de vapor al descargarse la mezcla y a veces parece como si tuviera un falso exceso de ligante.
  • Segregación de la mezcla: Se observa una segregación excesiva entre gruesos y finos al extender la mezcla.
  • Contaminaciones: Durante el transporte puede contaminarse la mezcla con gasoil, agua, polvo, restos vegetales, etc.

A continuación os dejo un vídeo del profesor Miguel Ángel del Val, de la Universidad Politécnica de Madrid, que explica el transporte de la mezcla asfáltica hasta su lugar de colocación.

También os paso un vídeo donde se puede ver un camión de transporte de aglomerado en caliente:

Referencias: YEPES, V. (2014). Maquinaria para la fabricación y puesta en obra de mezclas bituminosas. Apuntes Universitat Politècnica de València.

17 febrero, 2016
 
|   Etiquetas: ,  ,  ,  |  

Un problema de cinemática y el transporte de vigas por carreteras

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

 

 

14 enero, 2016
 
|   Etiquetas: ,  ,  ,  ,  ,  |  

Tesis doctoral sobre optimización en la gestión de activos de infraestructuras de transporte terrestre

2015-03-30 12.30.28Hoy 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.

2015-03-30 12.16.50

DSC01886

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

¿Qué es la distancia crítica de transporte?

Aquí nos vamos a ocupar de la distancia crítica de transporte. En un movimiento de tierras, por ejemplo, es aquella distancia en la que el equipo de cargadoras y camiones está equilibrado. Es decir, ni sobran ni faltan camiones o cargadoras. O dicho de otra forma, es la distancia de transporte en la que no existen esperas en las máquinas. Esta es una distancia teórica, puesto que para calcularla debemos conocer todos los datos de antemano, y éstos no son deterministas. Por otra parte, en obra ocurre lo contrario: tenemos una distancia de transporte como dato, pero en este caso se trataría de saber cuántos camiones y cargadoras serían necesarios para que no existiesen demoras. Afortunadamente en obra se puede corregir rápidamente cualquier desfase. Para entender este concepto os paso un laboratorio virtual que usan nuestros alumnos para facilitar la comprensión de este concepto. Espero que os guste.

Para acceder al laboratorio virtual, pinchar aquí: Distancia crítica de transporte

Distancia crítica

Referencias:

YEPES, V. (1995). Maquinaria de movimiento de tierras. Servicio de Publicaciones de la Universidad Politécnica de Valencia. SP.UPV-264. 144 pp.

YEPES, V. (2015). Coste, producción y mantenimiento de maquinaria para construcción. Editorial Universitat Politècnica de València, 155 pp. ISBN: 978-84-9048-301-5.

 

 

16 febrero, 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…)

Planificación de redes de transporte con baja demanda

La planificación y gestión de redes de distribución de baja demanda exige disponer de técnicas eficientes de optimización de rutas. El sistema de optimización de rutas disponible, no sólo afecta el desarrollo de operaciones sino, también las decisiones tácticas y estratégicas como el tamaño óptimo de flota, estimación de costes, políticas de publicidad y 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 debe ser transportado 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 generadas por el transporte dependen críticamente de la eficiencia del sistema de optimización de rutas. La Figura describe la influencia de la optimización de operaciones en la planificación y 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 (más…)

6 agosto, 2014
 
|   Etiquetas: ,  ,  ,  ,  ,  |  

El funicular

Funicular en Valparaiso (Chile). Wikipedia.

Se denomina funicular a un sistema de transporte por cable utilizado para salvar grandes pendientes. Se emplean para transportar cargas a intervalos regulares. Circula sobre raíles y normalmente dispone de dos cabinas enlazadas por un cable de acero sobre una vía de ferrocarril, a modo de ascensor inclinado, de tal forma que mientras un vehículo sube el otro baja, lo que permite aprovechar la energía potencial del que queda en la parte superior para subir el inferior a la vez que se frena el que está bajando.

Se pueden superar pendientes de hasta un 70%. Los carretones de elevación suelen ser dispositivos tipo skip, permaneciendo en un plano horizontal para no verter la carga. Con pequeñas rampas, la velocidad de subida llega a 1 m/s y las cargas oscilan entre 10 y 20 t. Con fuertes pendientes, se alcanzan hasta 5 t y 0,5 m/s.

Los vagones suelen compartir la misma vía salvo en el punto medio, donde se bifurca para que puedan pasar a la vez. Los vehículos carecen de motorización propia, ya que el movimiento lo imprime un motor que acciona una gran polea, que a su vez mueve el cable de tracción. No obstante, los vehículos van dotados de varios sistemas de frenado, tanto de servicio como de urgencia, este último en caso de fallo en las instalaciones (rotura o disensión del cable, etc.) o en los vehículos.

Este medio de transporte se creó alrededor del Siglo XIX como una alternativa a la vías del ferrocarril, como medio de vencer grandes pendientes. El primer funicular del mundo, accionado por una máquina de vapor, fue el que unía Rue Terme con Croix Rousse y fue inaugurado en Lyon en el año 1862.

A continuación os dejo un vídeo del funicular suizo de Gelmer, que es el más empinado del mundo, con un 106,6% de pendiente. Está situado a unos 80 km de la capital helvética. Este funicular es fruto de la adaptación al uso turístico de un antiguo remonte usado para la construcción del Embalse de Gelmer. Espero que os guste.

16 diciembre, 2013
 
|   Etiquetas: ,  ,  ,  |  

¿Por qué son tan complicados los problemas de distribución física?

Aspecto de diversas soluciones al problema de rutas

Aspecto de diversas soluciones al problema de rutas

Los problemas de distribución física consisten básicamente en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías. Los clientes se localizan en puntos o arcos y a su vez pueden presentar horarios de servicio determinados; el problema consiste en establecer secuencias de clientes y programar los horarios de los vehículos de manera óptima. Los problemas reales de transporte son extraordinariamente variados. Yepes (2002) propone una clasificación que contiene un mínimo de 8,8·109 combinaciones posibles de modelos de distribución. Si alguien fuese capaz de describir en un segundo cada uno de ellos, tardaría cerca de 280 años en enunciarlos todos. La investigación científica se ha centrado, por tanto, en un grupo muy reducido de modelos teóricos que además tienden a simplificar excesivamente los problemas reales. Son típicos problemas de optimización matemática combinatoria. (más…)

30 noviembre, 2013
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  |  

Previous Posts

Universidad Politécnica de Valencia