Gestionar la logística de un operador turístico consiste, en esencia, en intentar imponer orden a un sistema inherentemente caótico. El desafío es monumental: coordinar rutas a 30 destinos distintos desde un centro de operaciones como el de Alicante, con una flota limitada de cuatro aviones y quince tripulaciones, en el que cada asiento cuenta.
En este entorno de baja demanda, los costes son fijos, pero la realidad es volátil: las cancelaciones de última hora y las reservas inesperadas convierten los planes iniciales en papel mojado. ¿Cómo se puede determinar la rentabilidad cuando el escenario cambia cada minuto? La solución más avanzada no proviene de la programación lineal clásica, sino de los principios de la biología evolutiva.
Inspirado en el estudio de Medina y Yepes sobre la aplicación de algoritmos genéticos (AG) al problema de rutas de vehículos con capacidad (CVRP), este análisis desglosa cómo la «supervivencia del más apto» se traduce en una estabilidad financiera sin precedentes para el sector aéreo. Podéis descargar el artículo completo aquí.
La «naturaleza» como el mejor ingeniero de rutas.
En logística avanzada, los métodos deterministas tradicionales se topan con un obstáculo insalvable cuando el número de destinos crece exponencialmente. Calcular la ruta óptima para una red que abarque de Casablanca a Venecia mediante fuerza bruta matemática resulta inmanejable en términos computacionales. Los algoritmos genéticos resuelven este problema emulando la evolución mediante los procesos de selección, cruce y mutación. En lugar de buscar una única respuesta perfecta, el sistema mantiene una «población» de soluciones que compiten entre sí.
Este enfoque permite gestionar restricciones ambiguas o contradictorias, como maximizar la ocupación frente a minimizar el tiempo de vuelo, de una forma que la matemática rígida no puede. El AG no solo busca, sino que también aprende a explorar.
«La característica específica de los AG es la exploración paralela y eficiente del espacio de soluciones, basada en la explotación de soluciones óptimas inducidas por los operadores de cruce y en la exploración de soluciones nuevas forzada por los operadores de mutación».
El poder de los «Tres Padres»: una recombinación genética única.
La gran innovación técnica que se destaca en el estudio es el uso de un operador de recombinación de tres progenitores (three-parent edge-mapped recombination operator). Mientras que en la genética biológica la herencia es dual, en la optimización de redes de distribución tres progenitores ofrecen una mayor riqueza de datos para generar una «descendencia» (una ruta) más robusta.
Este método extrae las mejores conexiones (arcos) de tres soluciones distintas. Si una conexión específica aparece en dos o tres de los «padres», se preserva en el «hijo» porque se considera una pieza de alta eficiencia. Para garantizar la viabilidad de la ruta, el algoritmo incluye una lógica de resolución de conflictos: si tres arcos convergen en un mismo nodo de la descendencia, el sistema elimina aleatoriamente uno de ellos para mantener la estructura de la red. Este enfoque de triple herencia permite alcanzar soluciones óptimas con una velocidad y precisión que superan con creces a los cruces tradicionales de dos progenitores.
De la incertidumbre del 43 % a la estabilidad del 2,7 %.
El impacto real de los AG se mide en la transformación de la volatilidad en previsibilidad. Al modelar la demanda de destinos como Ajaccio, Túnez o Malta mediante estructuras estocásticas, el estudio revela una capacidad asombrosa para absorber la incertidumbre. Con una flota de cuatro aviones de cincuenta asientos y quince tripulaciones, el sistema gestionó un volumen total de aproximadamente ochocientos pasajeros, con métricas de eficiencia envidiables.
Los datos son elocuentes: mientras que la demanda individual por destino presenta un coeficiente de variación del 43 % —una pesadilla operativa—, la optimización diaria reduce la variabilidad del coste por pasajero transportado a un asombroso 2,7 %. En la práctica, esto significa:
Coste medio por pasajero: 118 EUR.
Ocupación media de asientos: 65 %.
Velocidad de crucero optimizada: 240 nudos.
El sistema es tan eficiente a la hora de reorganizar escalas y rutas en función de la demanda real que el impacto financiero final permanece prácticamente inalterado a pesar de las fluctuaciones del mercado.
El «fantasma en la máquina»: el riesgo de la robustez excesiva.
Desde la perspectiva de la transformación digital, los AG presentan una paradoja fascinante: su robustez puede ser su mayor peligro. Diseñado para ofrecer siempre una solución viable, un código con errores profundos puede seguir funcionando y entregando resultados «aparentemente buenos» sin que el sistema se colapse.
El riesgo no es el fallo catastrófico, sino el equilibrio subóptimo. Un error oculto en el algoritmo podría estar dejando sobre la mesa un 5 % o un 10 % de beneficio potencial, camuflado por la capacidad del algoritmo para «sobrevivir» a sus propios defectos de programación. Esto subraya la importancia de la supervisión experta, ya que en los sistemas que evolucionan por sí mismos la validación humana es la única garantía de que no operamos con una ineficiencia invisible pero costosa.
El futuro es la interacción humano-máquina.
Los AGV no son herramientas de reemplazo, sino de colaboración. El estudio subraya la importancia de la interfaz gráfica, que permite al gestor logístico interactuar con el proceso en tiempo real. Un ser humano puede «inyectar» soluciones basadas en su experiencia o en su intuición clínica, y el algoritmo las asimilará y refinará a lo largo de miles de generaciones.
Esta sinergia es fundamental para integrar los «costes virtuales». Mientras la máquina optimiza distancias y consumo de combustible, el ser humano puede definir variables subjetivas pero críticas, como la inconveniencia política de un aeropuerto en tensión o la complejidad social de una escala concreta. Al traducir estas percepciones en valores en la función de coste, el sistema evoluciona hacia una estrategia proactiva capaz de simular escenarios futuros en lugar de simplemente reaccionar ante las cancelaciones diarias.
Conclusión: hacia una logística evolutiva.
El éxito de la red de Alicante, que conecta 30 destinos del Mediterráneo y de Europa occidental, confirma un cambio de paradigma: en la logística moderna, la flexibilidad es más valiosa que la precisión absoluta. Los modelos rígidos se quiebran ante la volatilidad de la demanda, pero los sistemas evolutivos se fortalecen con ella.
En un mercado que no perdona la ineficiencia, la pregunta para los líderes del sector es clara: ¿es mejor buscar una solución «perfecta» una sola vez o diseñar un sistema que evolucione constantemente ante cada nuevo desafío? La respuesta, como demuestran Medina y Yepes, radica en aprender de la naturaleza para conquistar los cielos.
En esta conversación puedes escuchar las ideas más interesantes sobre este tema.
Este vídeo resume los aspectos clave del artículo.
Más allá del GPS: por qué la ruta más corta no siempre es la más rentable.
Para cualquier responsable de operaciones, la intuición dicta una regla aparentemente infalible: cuanto menos kilómetros se recorren, mayores son los márgenes. Sin embargo, ante la complejidad de la última milla contemporánea, esta lógica resulta peligrosamente incompleta. El ahorro en combustible suele verse compensado por penalizaciones por entregas tardías, ineficiencias en el uso de la capacidad de carga o por el coste oculto de ignorar las regulaciones laborales.
El éxito no consiste en reducir la distancia de forma simplista, sino en maximizar la rentabilidad operativa. Es aquí donde el problema de las rutas de vehículos con flotas heterogéneas y ventanas de tiempo flexibles (VRPHESTW,Vehicle Routing Problem with Heterogeneous Fleet and Soft Time Windows) surge como la respuesta científica al caos logístico. Este modelo trasciende el mapa al integrar variables económicas, humanas y temporales en una única ecuación estratégica. Este artículo se basa en uno de los resultados más importantes de mi tesis doctoral, publicada en un trabajo que podéis encontrar al final de las referencias (Yepes y Medina, 2006).
La rentabilidad total sobre la distancia total recorrida: la nueva métrica de éxito.
El enfoque tradicional se limita a minimizar el consumo de kilómetros. No obstante, la logística de alto nivel exige una función con un objetivo económico que considere la operación como un centro de beneficios y no solo de costes. La fórmula es clara:
Beneficio = Ingresos Totales – Costes Operativos – Costes de Penalización por Ventanas de Tiempo.
En este modelo, los ingresos no son una cifra estática, sino que se consideran dos tasas: una fija por servicio y otra variable en función de la distancia y del volumen de la mercancía. La gran innovación es que la satisfacción del cliente se convierte en un activo negociable. Al monetizar los retrasos mediante penalizaciones, el algoritmo decide de forma autónoma si resulta más rentable aceptar una pequeña desviación en el horario de entrega o invertir en un vehículo adicional. La logística moderna, por tanto, no busca el «cumplimiento a cualquier precio», sino el equilibrio óptimo entre el servicio y el margen.
El poder estratégico de una flota «mixta».
Una de las mayores ventajas competitivas del transporte radica en la heterogeneidad. El modelo demuestra que una flota uniforme tiende a ser ineficiente. El algoritmo realiza un arbitraje constante entre distintos tipos de vehículos para encontrar la combinación que minimiza el coste total de propiedad y operación.
En este análisis, la selección de vehículos (categorizados como k = 1, 2 o 3) no solo se basa en el volumen de carga, sino también en un equilibrio sofisticado entre:
Capacidad y velocidad: desde el vehículo pequeño y ágil (k = 1), ideal para zonas urbanas densas, hasta el «pesado» (k = 3), con gran capacidad, pero mayor coste fijo y menor velocidad de maniobra.
Estructura de costes laborales: el sistema evalúa el impacto financiero de pasar de la remuneración por hora legal a las horas extraordinarias y, finalmente, a las severas penalizaciones económicas derivadas del exceso de jornada laboral, protegiendo así la rentabilidad y la seguridad jurídica de la empresa.
Como señala el estudio:
«Los problemas de rutas de vehículos en el mundo real requieren una función objetivo económica para medir la calidad de las soluciones».
Ventanas de tiempo flexibles: el tiempo como variable económica elástica.
En la logística convencional, una ventana de tiempo es un muro infranqueable: llegar un minuto tarde se considera un fallo del sistema. El concepto de «soft time windows» (ventanas de tiempo flexibles) revoluciona esta noción al considerar el tiempo como una variable económica elástica.
En lugar de prohibir las entregas fuera de horario, el modelo establece una penalización económica escalonada en función de la antelación o el retraso. Esta flexibilidad calculada permite que el sistema de optimización identifique rutas que, aunque «incumplen» ligeramente el horario, logran una consolidación de carga tan eficiente que el beneficio neto final es muy superior al de una ruta de cumplimiento rígido. Se pasa así de una logística de obediencia a una logística de resultados.
El hallazgo sorprendente: el valor estratégico del sesgo.
El descubrimiento más disruptivo de la investigación consiste en distinguir entre la función «objetivo» (el beneficio real que queremos obtener) y la función «guía» (las instrucciones que le damos al algoritmo para explorar el mapa).
En un experimento revelador, los investigadores «engañaron» al algoritmo aumentando artificialmente en un 10 % los costes de distancia en la función guía (escenario HES-B). Al evaluar la ruta resultante con los costes reales (escenario HES-A), el beneficio neto aumentó un 6,4 %.
¿Por qué funciona este sesgo estratégico? Al sobreponderar el coste de la distancia durante la fase de búsqueda, se obliga al algoritmo a encontrar clústeres de clientes extremadamente compactos y rutas más robustas que el peso económico estándar pasaría por alto. Este fenómeno demuestra que, para escapar de los «óptimos locales» (soluciones que parecen buenas, pero no lo son), a veces es necesario alterar la topología del problema para forzar al sistema a encontrar la excelencia global.
Un marco de tres pilares para la implementación.
Para ejecutar esta estrategia, se propone un marco de optimización híbrido que integra la exploración creativa y el rigor matemático.
Fase de construcción inteligente (GRASP): no se generan rutas al azar, sino que se inicia el proceso seleccionando clientes «semilla» según criterios de alta rentabilidad y dificultad logística, lo que asegura un punto de partida sólido.
Fase de diversificación global (VNS): el sistema utiliza una «búsqueda de vecindario variable» para desafiar las rutas establecidas. En esta fase se introduce variedad para evitar que la operación se estanque en las soluciones obvias.
Fase de intensificación de precisión (algoritmo de umbral): un pulido final que somete cada ruta a un escrutinio de costes extremo, aceptando incluso soluciones ligeramente peores temporalmente para alcanzar el máximo céntimo de beneficio potencial.
Conclusión: hacia una logística con visión de negocio.
La optimización de rutas ha dejado de ser un problema geográfico para convertirse en una disciplina puramente estratégica de economía. El uso de algoritmos avanzados que integran flotas heterogéneas y ventanas de tiempo flexibles permite a las empresas navegar por la volatilidad de los costes y las exigencias del mercado con una precisión quirúrgica.
Optimizar no consiste solo en llegar antes, sino en comprender el coste exacto de cada minuto y cada kilómetro para decidir, basándose en datos, qué configuración de flota garantiza el crecimiento sostenible del negocio.
Pregunta para reflexionar: En su operación actual, ¿está optimizando para que sus vehículos recorran menos distancia o para que su balance de situación sea más robusto?
Puedes escuchar en esta conversación algunas de las ideas más interesantes sobre este tema.
Este vídeo resume bien los conceptos básicos tratados.
Búsqueda local mejorada por el criterio de aceptación por umbrales
RESUMEN
La ponencia presenta un procedimiento de resolución aproximada en la optimización económica de rutas de reparto con flotas de vehículos heterogéneas y horarios de servicio flexibles VRPHESTW basado en la búsqueda probabilista en entornos variables y en la aceptación por umbrales estocásticos. Se ha ensayado en un problema concreto la eficacia de la búsqueda con múltiples operadores, así como la ventaja del empleo de la aceptación por umbrales. Sin embargo, la introducción de ruidos estocásticos gaussianos en los umbrales no ha representado una mejora significativa del procedimiento.
Referencia:
MEDINA, J.R.; YEPES, V. (2004). Optimización de rutas mediante la búsqueda en entornos variables y aceptación por umbrales estocásticos, en Larrodé, E. y Castejón, L. (Eds.): Infraestructuras de Transporte y Logística como Motor de Desarrollo de las Regiones Europeas. Actas del VI Congreso de Ingeniería del Transporte. Vol. 4, pp. 1985-1992. Zaragoza, 23-25 de junio. ISBN (Vol. 4): 84-609-1364-3.
Puente de Alcántara, icono y foco de peregrinación para los ingenieros civiles. Imagen: V. Yepes, 2016
YEPES, V. (2000). Los itinerarios temáticos como elementos diferenciadores del producto turístico global.Actas del V Congreso Internacional sobre Caminería Hispánica. Tomo II, pp. 1359-1372. AACHE Ediciones. Valencia, 17-22 de julio.
1 INTRODUCCIÓN.
El desarrollo tecnológico en las sociedades de consumo de los países desarrollados ha propiciado en las últimas décadas un aumento de la disponibilidad de tiempo libre para el ocio. Este período sobrante después del trabajo, el sueño y los quehaceres personales y domésticos ha permitido el auge de una gran variedad de actividades recreativas que permiten reparar la fuerza y la vitalidad de las personas y que puede incluir ocupaciones tan diversas como ver la televisión o pasar unas vacaciones en el extranjero (Boniface y Cooper, 1987). El turismo puede representar una de las facetas de las actividades recreativas, aunque también incluye desplazamientos no estrictamente vinculados con el ocio (convenciones, ferias, congresos, negocios, etcétera). Continue reading «Los itinerarios temáticos como elementos diferenciadores del producto turístico global»→
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.
Gestionar la logística de un operador turístico consiste, en esencia, en intentar imponer orden a un sistema inherentemente caótico. El desafío es monumental: coordinar rutas a 30 destinos distintos desde un centro de operaciones como el de Alicante, con una flota limitada de cuatro aviones y quince tripulaciones, en el que cada asiento cuenta.
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.
