La Metodología de la Superficie de Respuesta (RSM) es un conjunto de técnicas matemáticas y estadísticas utilizadas para modelar y analizar problemas en los que una variable de interés es influenciada por otras. El propósito inicial de estas técnicas es diseñar un experimento que proporcione valores razonables de la variable respuesta y, a continuación, determinar el modelo matemático que mejor se ajusta a los datos obtenidos. El objetivo final es establecer los valores de los factores que optimizan el valor de la variable respuesta. Esto se logra al determinar las condiciones óptimas de operación del sistema.
La diferencia entre (RSM) y un diseño experimental corriente estriba en que un diseño experimental por si solo tiene como objetivo localizar el tratamiento «ganador» entre todos aquellos que se han probado. En cambio, RSM pretende localizar las condiciones óptimas de operación del proceso. Ello supone un reto para el investigador, requiere una estrategia más completa e incluye la posibilidad de efectuar varios experimentos secuenciales y el uso de técnicas matemáticas más avanzadas.
Os dejo a continuación un vídeo explicativo que espero os aclare la metodología.
Otro vídeo complementario al anterior es el siguiente:
Referencias:
Box, G. E. P., Wilson, K. G. (1951), On the experimental attainment of optimum conditions,Journal of the Royal Statistical Society, B 13, 1-45
Cornell, John A. (1984), How to apply Response Surface Methodology, American Society for Quality Control, Milwaukee, WI.
Kuehl, Robert O. (2001) Diseño de Experimentos, 2a. Edición, Thomson Learning.
Melvin T. A. Response Surface Optimization using JMP Software, < http://www2.sas.com/proceedings/sugi22/STATS/PAPER265.PDF>
Montgomery, D. C. (2002), Diseño y Análisis de Experimentos, Editorial Limusa, Segunda Edición.
Figura. Fases en la ejecución de una PHD. Fuente: http://tracksonhorizontaldrilling.com.au/directional-drilling-presents-top-solution/
La instalación propiamente dicha de las tuberías o los conductos se realiza en varias fases. Primero se perfora un taladro piloto; a continuación se ensancha dicha perforación de forma concéntrica en sentido contrario al de la perforación piloto. En ese momento la máquina tira y la tubería se engancha al escariador para alojarla en su posición definitiva.
La perforación piloto constituye la siguiente fase del proceso tras los estudios previos y el emplazamiento de la maquinaria. Se trata de perforar con un cabezal direccionable con un varillaje especial que admite cambios de orientación. Su diámetro dependerá de la maquinaria utilizada y está relacionada con el tamaño de las barras de perforación y de las brocas de perforación. Los aspectos más relevantes a considerar son las posibles obstrucciones y los radios de curvaturas. Un sistema de navegación guía la cabeza de perforación. Lo habitual es que el varillaje permita la entrada de lodos, que pueden inyectarse a presión para mejorar la perforación. Los lodos arrastran el detritus hacia el exterior. En el caso de terrenos duros se puede utilizar un motor de lodos (mud-motor) que acciona el cabezal de perforación.
Tras la perforación piloto se realiza la operación de ensanche, normalmente en sentido inverso, tirando de un escariador. El agrandamiento puede hacerse de una vez o en fases sucesivas hasta alcanzar el diámetro necesario. Es habitual que el diámetro final sea el doble del de la tubería a instalar. Un aspecto clave es el terreno y su estabilidad, pues va a condicionar el uso del ensanchador. Así, en terrenos blandos se emplean ensanchadores tipo flycutter o barriles, mientras que en terrenos duros o roca se necesitan ensanchadores especiales con protecciones de carburo de tunsgteno. Existen escariadores cortadores, que corta trozos pequeños de material que se mezclan con el fluido de perforación; el escariador compactador, donde los recortes se compactan; y los mixtos, donde los recortes se compactan y se mueven.
Figura. Cabeza de perforación. Imágen de Catalana de PerforacionsFigura. Escariador. Imagen de Catalana de Perforacions
Por último, la tubería se alinea y se fija justo detrás del ensanchador y se introduce, de una sola vez, en el interior de la perforación tirando de ella. Para facilitar la operación los lodos lubrican las paredes de la perforación para reducir el rozamiento. Cuando se recoge el varillaje, la instalación ya está terminada.
Las recomendaciones generales para la ejecución de PHD pasarían por normalizar los métodos de trabajos para aumentar rendimientos y reducir costes, establecer sistemas de control que garanticen la seguridad y la calidad de los trabajos y establecer un sistema capaz de rechazar, corregir o aceptar las desviaciones que se puedan dar.
A continuación os dejo un vídeo explicativo al respecto del procedimiento constructivo del PHD.
Referencias:
IbSTT Asociación Ibérica de Tecnología SIN Zanja (2013). Manual de Tecnologías Sin Zanja.
Yepes, V. (2014). Maquinaria para sondeos y perforaciones. Apuntes de la Universitat Politècnica de València, Ref. 209. Valencia, 89 pp.
Yepes, V. (2015). Aspectos generales de la perforación horizontal dirigida. Curso de Postgrado Especialista en Tecnologías Sin Zanja, Ref. M7-2, 10 pp.
Al igual que ocurre con cualquier procedimiento constructivo, la PHD tiene sus etapas de planificación, ejecución y control (Pellicer et al., 2014). El proceso de instalación de una tubería o canalización mediante PHD comienza con un estudio previo con el objeto de elegir la mejor máquina y útiles para un caso concreto. Se incluye la topografía de la zona y un estudio geotécnico que determine el tipo de terreno. No menos importante es detectar con precisión los servicios existentes en el subsuelo mediante un georadar e incluso analizar rutas alternativas. A continuación se debe adecuar la zona de trabajo para el emplazamiento de los equipos, tanto en el inicio de la perforación como en la salida. No se debe subestimar la planificación. Por cada día de trabajo de campo debería dedicarse un mínimo de dos días de planificación.
La etapa de estudios previos debería centrarse en dos aspectos que se consideran fundamentales:
1. La naturaleza intrínseca del proceso de construcción que implica:
El corte de las formaciones del suelo y su incorporación a los fluidos de perforación
El mantenimiento continuo y estable de las paredes de la perforación
El transporte del detritus suspendido en la mezcla para permitir la instalación de la tubería
2. El trazado de la perforación, que deberá centrarse en el obstáculo a cruzar, considerando especialmente las condiciones geotécnicas e hidrológicas (ver Figura), así como identificar el radio de curvatura de las barras de perforación y los esfuerzos máximos admisibles.
Os dejo a continuación un vídeo explicativo que espero sea de vuestro interés.
Referencias:
IbSTT Asociación Ibérica de Tecnología SIN Zanja (2013). Manual de Tecnologías Sin Zanja.
Pellicer, E., Yepes, V., Teixeira, J.C., Moura, H.P., and Catalá, J. (2014). Construction Management. Wiley Blackwell, 316 pp.
Yepes, V. (2014). Maquinaria para sondeos y perforaciones. Apuntes de la Universitat Politècnica de València, Ref. 209. Valencia, 89 pp.
Yepes, V. (2015). Aspectos generales de la perforación horizontal dirigida. Curso de Postgrado Especialista en Tecnologías Sin Zanja, Ref. M7-2, 10 pp.
La Perforación Horizontal Dirigida PHD (HDD, de su acrónimo en inglés Horizontal Directional Drilling) para colocar nuevas tuberías sin zanja surgió de la fusión de las tecnologías empleadas en la captación de agua y del petróleo. Resulta sorprendente descubrir que Leonardo da Vinci inventó, en el siglo XV, la primera máquina de perforación horizontal que servía para introducir tuberías de madera. La primera instalación con PHD se realizó en 1971 con una tubería de acero de 180 mm para cruzar el río Pájaro cerca de Watsonville, California. Hoy es una técnica que se ha generalizado para franquear obstáculos como ríos, carreteras y zonas complicadas de atravesar mediante una excavación convencional. También se utiliza en las obras municipales para las conducciones de agua potable, gas natural, fibra óptica, cableados eléctricos, alcantarillado y similares cuando hay que cruzar edificios o calles.
Figura. Máquina de perforación horizontal ideada por Leonardo da Vinci, antes de 1495. Fuente: http://trenchless-australasia.com/
Lubrecht (2012) analiza las ventajas medioambientales de las técnicas PHD usadas en la descontaminación de suelos. Sin embargo, Ariaratnam y Proszek (2006) recuerdan los desorbitantes costes legales por daños a terceros en los que están incurriendo contratistas negligentes, tanto de PHD como de excavación tradicional. Ello obliga a sistemas muy precisos para detectar obstáculos y otras conducciones para evitar accidentes y explosiones (Jaganathan et al., 2011).
El movimiento de perforación habitualmente se realiza en un plano horizontal que contiene longitudinalmente a la línea de perforación, formada por la cabeza y la sarta de perforación. Al principio, con la técnica PHD en desarrollo, sólo se instalaban tuberías a presión y conductos de cables, sin que la inclinación fuera un parámetro crítico. Hoy las perforadoras cuentan con sistemas de guiado de alta precisión que permiten colocar tuberías de gravedad.
Se podría decir que la PHD es una técnica a medio camino entre la perforación de topo de percusión (impact moling) y el microtunelado. PHD proporciona un creciente número de opciones de instalación, pues la trayectoria de la perforación se puede cambiar en cualquier momento para sortear obstáculos superficiales o subterráneos. Las instalaciones habituales utilizan diámetros de 50 a 1200 mm y longitudes de hasta 2000 m. Si bien Allouche et al. (2000) indican que el 72% de las tuberías instaladas con PHD son de diámetros menores o iguales a 100 mm. Los materiales de las tuberías suelen ser de polietileno de alta densidad (PEAD), cloruro de polivinilo (PVC), acero y hierro dúctil. La fuerza de tiro se emplea para clasificar los sistemas PHD, pues está relacionado con el tamaño de máquina necesario, el diámetro del conducto a instalar y la longitud de perforación. Ariaratnam y Allouche (2000) proporcionan un buen compendio de recomendaciones y buenas prácticas relacionadas con esta técnica.
Os dejo a continuación un vídeo explicativo que introduce la técnica de la Perforación Horizontal Dirigida.
Referencias:
Allouche, E., Ariaratnam, S., and Lueke, J. (2000). Horizontal Directional Drilling: Profile of an Emerging Industry. Journal of Construction Engineering and Management, Volume 126, No. 1, pp. 68–76.
Ariaratnam, S. T., and Allouche, E. N. (2000). Suggested practices for installations using horizontal directional drilling. Practice Periodical on Structural Design and Construction, Volume 5, No. 4, pp. 142-149.
Ariaratnam, S. T., and Proszek, J. (2006). Legal consequences of damages to underground facilities by horizontal directional drilling. Journal of Professional Issues in Engineering Education and Practice, Volume 132, No. 4, pp. 342-354.
IbSTT Asociación Ibérica de Tecnología SIN Zanja (2013). Manual de Tecnologías Sin Zanja.
Jaganathan, A. P., Shah, J. N., Allouche, E. N., Kieba, M., and Ziolkowski, C. J. (2011). Modeling of an obstacle detection sensor for horizontal directional drilling (HDD) operations. Automation in Construction, Volume 20, No. 8, pp. 1079-1086.
Lubrecht, M. D. (2012). Horizontal directional drilling: A green and sustainable technology for site remediation. Environmental Science & Technology, Volume 46, No. 5, pp. 2484-2489.
Yepes, V. (2014). Maquinaria para sondeos y perforaciones. Apuntes de la Universitat Politècnica de València, Ref. 209. Valencia, 89 pp.
Yepes, V. (2015). Aspectos generales de la perforación horizontal dirigida. Curso de Postgrado Especialista en Tecnologías Sin Zanja, Ref. M7-2, 10 pp.
Dentro de las zanjadoras, os presentamos aquí la cortadora de disco con picas. Su equipo de trabajo está formado por un disco de gran diámetro que lleva en su periferia unos segmentos cambiables con cortadores en forma de picas.
La fuerza de penetración del disco sobre el suelo se consigue mediante unos cilindros hidráulicos. Su campo de aplicación habitual es el corte de roca, terrenos congelados, pavimentos, reperfilado de zanjas, tendido de cables, etc.
En el siguiente vídeo podéis ver el funcionamiento de una zanjadora Tesmec 1100, de 35 toneladas, con 10 m de largo, 4 de alto y 2.5 m de ancho. La rueda de corte de acero de 3,5 toneladas mide 4 m de diámetro. Su sierra es capaz de triturar rocas. Espero que os guste.
Referencias:
YEPES, V. (2014). Maquinaria de movimiento de tierras. Apuntes de la Universitat Politècnica de València, Ref. 204. Valencia, 158 pp.
Muchos servicios y canalizaciones se encuentran en zonas urbanas congestionadas. Su instalación, renovación o rehabilitación con métodos tradicionales de apertura de zanjas suponen grandes problemas e inconvenientes a la población. Las tecnologías sin zanja (trenchless) son a menudo económicamente más efectivas que las tecnologías de excavación con zanja (Yepes, 2014). Los plazos más cortos de ejecución, una mayor calidad en la construcción, un menor número de restricciones externas como el tráfico o el medio ambiente y la progresiva reducción de costes, está consolidando y extendiendo la tecnología de construcción sin zanja a nivel mundial. Por ejemplo, Tighe et al. (2002) afirman que la vida de un pavimento flexible se reduce aproximadamente el 30% de si se le abre una excavación. Además, los costes de mantenimiento y rehabilitación de dicho pavimento se incrementan notablemente. Por otra parte, son técnicas de bajo impacto ambiental pues evitan alteraciones en los biotopos naturales y en la afectación de la vida superficial. De hecho, Allouche et al. (2000) consideran que es el segmento de la industria de la construcción de las tecnologías sin zanja que más está creciendo. Cerca del 15% de las nuevas instalaciones subterráneas en Alemania se realizan con técnicas sin zanja (Bayer et al., 2005). Ma y Najafi (2007) explican el acelerado desarrollo de estas técnicas en China.
Os dejo a continuación un vídeo explicativo sobre este tipo de tecnologías, que espero os sea útil.
Referencias:
Allouche, E., Ariaratnam, S., and Lueke, J. (2000). Horizontal Directional Drilling: Profile of an Emerging Industry. Journal of Construction Engineering and Management, Volume 126, No. 1, pp. 68–76.
Bayer, H.J. (Editor) (2005). HDD Practice Handbook. Vulkan-Verlag, Essen, Germany
IbSTT Asociación Ibérica de Tecnología SIN Zanja (2013). Manual de Tecnologías Sin Zanja.
Ma, B., and Najafi, M. (2008). Development and applications of trenchless technology in china. Tunnelling and Underground Space Technology, Volume 23, No. 4, pp. 476-480.
Tighe, S., Knight, M., Papoutsis, D., Rodriguez, V., and Walker, C. (2002). User cost savings in eliminating pavement excavations through employing trenchless technologies. Canadian Journal of Civil Engineering, Volume 29, No. 5, pp. 751–761.
Yepes, V. (2014). Maquinaria para sondeos y perforaciones. Apuntes de la Universitat Politècnica de València, Ref. 209. Valencia, 89 pp.
Yepes, V. (2015). Aspectos generales de la perforación horizontal dirigida. Curso de Postgrado Especialista en Tecnologías Sin Zanja, Ref. M7-2, 10 pp.
Las labores de extracción de material en obras subterráneas y túneles no es una tarea sencilla. Al poco espacio de maniobra hay que añadir los problemas derivados de la ventilación de espacios cerrados y problemas de seguridad y salud que afectan a los trabajadores.
Este tipo de cargadoras se desarrollan para las más duras aplicaciones subterráneas, con objetivos orientados a economizar la producción, incrementar la seguridad y fiabilidad. Este equipo de cargador LHD (load haul dump) es especialmente adecuado para trabajar debajo de condiciones difíciles, como estrechos, de baja altura y lugares de trabajo con lodo.
En este sentido, las cargadoras LHD, de perfil bajo, empleadas en este tipo de obras adquieren características especiales. Su diseño es compacto, tanto en altura como en anchura. Su radio de giro es mínimo (articuladas), lo que le permite una gran maniobrabilidad en zonas estrechas. Son muy productivas en recorridos cortos o medios (hasta 1000 m). Pueden ser de accionamiento eléctrico o mediante motores diésel.
Para distancias inferiores a unos 500 m y túneles de pequeña y mediana sección, se utiliza una pala con un cazo de gran capacidad (3m³) que carga el escombro del frente y lo lleva hasta el exterior. La máquina no gira, sentándose el maquinista de forma lateral para conducir en ambas direcciones. Para distancias mayores se utilizan zonas de acopio intermedio de escombros.
Con marcos optimizados, una fuerza motriz muy potente, avanzada tecnología de transmisión, tracción, controles de dirección articulados y ergonómicos, son extremadamente resistentes, muy maniobrables y excepcionalmente productivas. Estas máquinas presentan una capacidad de 1 a 25 toneladas.
Un cargador SANDVIK LH517. Wikipedia
Os paso varios vídeos para que podáis ver su funcionamiento. Espero que os gusten.
Referencias:
MARTÍ, J.V.; YEPES, V.; GONZÁLEZ, F.; ALCALÁ, J. (2012). Técnicas de voladuras y excavación en túneles. Apuntes de la Universitat Politècnica de València. Ref. 530, 165 pp.
YEPES, V. (2014). Maquinaria de movimiento de tierras. Apuntes de la Universitat Politècnica de València. 148 pp.
Las empresas constructoras cuentan con parques de maquinaria que gestionan las máquinas, equipos y piezas de repuesto. Estos parques varían en función del tamaño y naturaleza de la empresa constructora. Las grandes empresas cuentan con un gran parque central y con parques de zona de menor envergadura. El personal del parque representa entre el 5 y el 10% del total de la empresa, porcentajes que aumentan si se consideran a los operadores y a los maquinistas.
El dimensionamiento, organización y control de las existencias de un parque depende de la demanda de maquinaria por parte de cada obra y del plazo de entrega. Estos factores son conocidos a veces en términos de probabilidad y en otros casos son desconocidos. Los parques de maquinaria se constituyen en «embalses» reguladores que posibilitan el equilibrio entre los flujos reales de entrada y salida.
Figura. Ejemplo de modelo de organización de un parque de maquinaria
La estructura de un parque de maquinaria depende de la organización, dimensión, extensión geográfica, especialización y grado de mecanización de la empresa constructora. Entre las actividades que realiza el parque se encuentran la adquisición de máquinas, su mantenimiento y su enajenación cuando su empleo sea improductivo o innecesario. El parque se encuentra integrado completamente en la organización de algunas empresas, mientras que en otras actúa de forma independiente, pasando cargos a su propia empresa por el uso de la maquinaria.
Un parque de maquinaria se organiza en un conjunto de departamento o secciones que típicamente podrían ser las siguientes:
Adquisiciones y coordinación: planifica la adquisición de máquinas basándose en las necesidades de renovación y en la evolución del mercado de la empresa, sin olvidar las necesidades concretas que surgen con la adjudicación de obras.
Documentación: tiene a su cargo todos los archivos de documentación tanto técnica como económica.
Conservación: planifica y controla los trabajos de mantenimiento de las máquinas tanto en obra como en taller.
Proyecto de instalaciones: el cometido es el estudio y la realización de todas las instalaciones que se precisen para las obras y para las licitaciones.
Inventarios y estadística: actualiza los inventarios de maquinaria.
Métodos: estudia las máquinas nuevas y su aplicación a las obras, los nuevos sistemas de máquinas ya conocidas, las pruebas con máquinas propias, etc.
Matriculaciones: se ocupa de la matriculación de las máquinas y vehículos de la empresa y de todas las gestiones relacionadas con ellos.
Figura. Gestión funcional del parque
Os dejo una mesa redonda sobre la visión de los parques de maquinaria, que espero os guste.
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.
El post de hoy va dedicado a aquellos de vosotros que os dedicáis a la investigación científica. Vamos a hablar de ORCID, que es un proyecto abierto, sin ánimo de lucro, comunitario, que ofrece un sistema para crear y mantener un registro único de investigadores y un método claro para vincular las actividades de investigación y los productos de estos identificadores. ORCID es único por su capacidad de aplicarse a todas las disciplinas, sectores de investigación y fronteras nacionales. Es un centro que conecta a los investigadores y la investigación a través de la incorporación de identificadores ORCID en flujos de trabajo clave, tales como el mantenimiento de los perfiles de investigación, las presentaciones manuscritas, las solicitudes de subvención y las solicitudes de patentes.
En mi caso particular, mis registros de investigador son los siguientes:
La Metodología de la Superficie de Respuesta (RSM) es un conjunto de técnicas matemáticas y estadísticas utilizadas para modelar y analizar problemas en los que una variable de interés es influenciada por otras. El propósito inicial de estas técnicas es diseñar un experimento que proporcione valores razonables de la variable respuesta y, a continuación, determinar el modelo matemático que mejor se ajusta a los datos obtenidos. El objetivo final es establecer los valores de los factores que optimizan el valor de la variable respuesta. Esto se logra al determinar las condiciones óptimas de operación del sistema.
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.
