💻 computer science

Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

Este artículo presenta una metaheurística de Búsqueda de Vecindad Variable reducida cooperativa (rVNS) para optimizar el complejo Problema de Enrutamiento y Programación de Vehículos con Capacidad de Múltiples Viajes y Ventanas de Tiempo con Descansos para Comidas (MTCVRSPTW-MB) para operaciones de catering aeroportuario, demostrando su eficiencia superior y reducción de kilometraje sobre los métodos exactos en instancias de la vida real en el Aeropuerto Internacional de San Francisco.

Autores originales: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Publicado 2026-07-07

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un aeropuerto concurrido como un rompecabezas gigante de alto riesgo. Por un lado, tienes cientos de aviones llegando y saliendo, cada uno necesitando que se le cargue o descargue comida. Por el otro, tienes una flota de camiones y conductores, cada uno con habilidades específicas, tiempo limitado y reglas estrictas sobre cuándo pueden tomar su descanso para almorzar.

El objetivo es simple: alimentar a cada avión a tiempo utilizando la menor cantidad de millas recorridas por los camiones. Pero la matemática detrás de esto es increíblemente compleja. Si intentas resolverlo con un programa de computadora estándar, es como intentar encontrar un grano de arena específico en una playa revisando cada grano uno por uno: toma demasiado tiempo.

Este artículo presenta una forma más inteligente y rápida de resolver este rompecabezas utilizando un método llamado rVNS (Búsqueda de Vecindad Variable reducida). Así es como funciona, desglosado en conceptos cotidianos:

1. El Problema: El "Tetris" de la comida del aeropuerto

Imagina al equipo de asistencia en tierra del aeropuerto jugando una partida de Tetris de alta velocidad.

Los Bloques: Estas son las tareas (cargar un avión, descargar un avión).
Los Espacios: Estos son los conductores y los camiones.
Las Reglas: Un conductor solo puede conducir un camión específico; un camión solo puede transportar cierta cantidad de comida; un conductor debe tomar un descanso de 30 minutos entre las 4 y las 5 horas después de comenzar; y un avión debe ser alimentado dentro de un intervalo de tiempo específico.

En el pasado, los investigadores intentaron dos formas de resolver esto:

La forma "Perfecta" (Método Exacto): Intentar calcular cada una de las posibilidades para encontrar la solución absoluta. Esto es como intentar leer todos los libros de una biblioteca para encontrar la mejor historia. Es preciso, pero tarda demasiado.
La forma "Rápida" (Heurística Voraz): Tomar la mejor decisión disponible en el momento exacto. Esto es como agarrar el libro más cercano sin mirar los demás. Es rápido, pero a menudo conduce a un resultado mediocre.

2. La Solución: El "Barajado Inteligente" (rVNS)

El nuevo método, rVNS, es como un maestro de los rompecabezas que sabe que, a veces, tienes que romper un buen arreglo para crear uno mejor.

En lugar de intentar construir el rompecabezas perfecto desde cero, el algoritmo comienza con un arreglo decente y luego juega un juego de "Barajar y Cambiar".

El Barajado: Selecciona aleatoriamente algunos grupos de tareas (bloques) y los elimina del horario, colocándolos en una "sala de espera".
El Cambio: Luego intenta volver a colocar esas tareas, pero esta vez intenta encajarlas en diferentes lugares o intercambiarlas con otras tareas para ver si la imagen general mejora.

¿Por qué "Reducida"?
Normalmente, estos algoritmos intentan barajar grandes fragmentos del rompecabezas, lo cual es lento. Este nuevo método baraja fragmentos pequeños, pero lo hace de forma muy rápida y repetitiva. Es como un chef que prueba una sopa y añade una pizca de sal, y luego la prueba de nuevo, en lugar de intentar reescribir toda la receta cada vez.

3. La Salsa Secreta: Dos Estrategias Diferentes

El algoritmo es lo suficientemente inteligente como para saber cuándo enfocarse en qué. Tiene dos modos:

Modo A (El "Rellenador"): Su objetivo principal es asegurar que ninguna tarea se quede atrás. Baraja el horario para garantizar que cada avión sea alimentado.
Modo B (El "Ahorrador de Millas"): Una vez que la mayoría de las tareas han sido asignadas, cambia su enfoque a ahorrar combustible. Busca formas de reorganizar los camiones para que conduzcan menos millas entre aviones.

4. La "Reunión de Equipo" (Paralelización)

Para hacer esto aún más rápido, los investigadores no solo usaron un cerebro de computadora; usaron un equipo. Imagina a un grupo de detectives tratando de resolver un crimen. En lugar de que una sola persona revise cada pista, dividieron el trabajo:

El Equipo de Detectives 1 trabaja en el horario del turno de la mañana.
El Equipo de Detectivos 2 trabaja en el horario del turno de la tarde.
Cada 10 segundos, se reúnen, comparten sus mejores ideas y combinan sus hallazgos.

Esto asegura que no se queden estancados en un "callejón sin salida" (un óptimo local) donde creen haber encontrado la mejor solución, pero en realidad se han perdido una mejor.

5. Los Resultados: Más Rápidos, Mejores y Más Fluidos

Cuando probaron este nuevo método con datos reales del Aeropuerto Internacional de San Francisco (SFO):

Tasa de Éxito: Los métodos antiguos lograban asignar aproximadamente entre el 80% y el 89% de las tareas. El nuevo método rVNS asignó del 99% al 99.8% de las tareas. Casi nunca deja un avión sin alimentar.
Ahorro de Combustible: Debido a que reorganiza el horario de manera más eficiente, los camiones recorrieron entre un 20% y un 30% menos de millas que antes.
Velocidad: Encontró estas soluciones casi perfectas en menos de un minuto, lo cual es lo suficientemente rápido para ser utilizado en operaciones en tiempo real.

Resumen

En resumen, este artículo presenta un nuevo algoritmo de "barajado inteligente" que ayuda a los gestores de aeropuertos a asignar tareas de entrega de alimentos a conductores y camiones. Al dividir el problema en piezas más pequeñas, barajándolas aleatoriamente para encontrar mejores encajes y utilizando un equipo de computadoras para trabajar juntas, el sistema garantiza que casi todos los aviones sean alimentados mientras se recorren significativamente menos millas que con los métodos anteriores. Convierte un rompecabezas caótico e imposible de resolver en una rutina diaria manejable y eficiente.

Resumen Técnico: Asignación y Optimización de Operaciones de Asistencia en Tierra de Aeropuertos mediante rVNS

Definición del Problema
El estudio aborda la compleja optimización combinatoria de las operaciones de asistencia en tierra de los aeropuertos, centrándose específicamente en los servicios de catering. El problema central se modela como el Problema de Enrutamiento y Programación de Vehículos con Capacidad y Múltiples Viajes con Ventanas de Tiempo y Descansos para Comidas (MTCVRSPTW-MB), extendido para dar cabida a una flota heterogénea de camiones y conductores con diversas cualificaciones y patrones de carga.

El objetivo es doble:

Primario: Maximizar el número de tareas de catering (carga/descarga de aeronaves) asignadas a los conductores y camiones disponibles.
Secundario: Minimizar el kilometraje total requerido para ejecutar estas tareas.

El problema está limitado por estrictas reglas operativas, que incluyen:

Restricciones del Conductor: Horarios de turno, descansos obligatorios de 30 minutos para comidas (que ocurren 4–5 horas después del inicio del turno) y requisitos de cualificación para tipos específicos de aeronaves y aerolíneas.
Restricciones del Camión: Límites de capacidad, tipos de camión específicos (14FT, 16FT, 22FT) y disponibilidad diaria limitada.
Restricciones de la Tarea: Ventanas de tiempo para la ejecución, compatibilidad entre el camión/conductor y la aeronave/aerolínea específica, y requisitos de volumen.
Restricciones de la Misión: Reglas que rigen las misiones de múltiples tareas, tales como prohibir descargas nacionales después de cargas internacionales dentro de la misma misión, asegurar un tiempo de viaje suficiente entre tareas y requerir que todas las misiones comiencen y terminen en la unidad principal de catering.

El estudio utiliza datos reales del Aeropuerto Internacional de San Francisco (SFO) de marzo de 2023, que involucran aproximadamente 350 tareas diarias, 80 conductores y 40 camiones. Un requisito crítico es que las soluciones deben generarse en un minuto para ser operativamente viables.

Metodología
Los autores proponen una metaheurística de Búsqueda de Vecindad Variable reducida cooperativa (rVNS). Este enfoque se seleccionó sobre la Búsqueda de Vecindad Variable (VNS) tradicional y la Búsqueda de Vecindad Grande Adaptativa (ALNS) para equilibrar la eficiencia computacional con la calidad de la solución.

Los componentes clave de la metodología incluyen:

Marco de rVNS (Reduced VNS):
- A diferencia de la VNS clásica que varía los tamaños de paso, la rVNS emplea un tamaño de paso pequeño y fijo.
- El algoritmo opera mediante un ciclo de deconstrucción y reconstrucción: desasigna un número fijo de tareas ( $n$ ) de la solución actual e intenta reasignarlas aleatoriamente.
- Para compensar el tamaño de paso fijo, el algoritmo aprovecha la alta simetría del problema de programación. Al explorar soluciones "equivalentes" (diferentes programas con puntuaciones idénticas) mediante intercambios aleatorios, la búsqueda se diversifica sin necesidad de pasos grandes y computacionalmente costosos.
Estructura Algorítmica:
- Descomposición (Dicotomía del Problema): El programa diario se divide en dos subproblemas (Mañana y Tarde) basados en los solapamientos de los turnos de los conductores, lo que permite el procesamiento paralelo.
- Heurística de Inicio en Caliente (Warm-Start): La rVNS se inicializa con una solución generada por una heurística voraz (greedy) que prioriza las tareas con menos conductores cualificados y descansos de comida obligatorios. Esto evita que la búsqueda comience en un óptimo local pobre.
- Aleatorización de Objetivo Dual: El algoritmo alterna entre dos estrategias de aleatorización basadas en la convergencia del objetivo:
  - Enfoque Primario: Desasigna tareas con posiciones temporales similares para crear espacio para las tareas no asignadas.
  - Enfoque Secundario: Desasigna tareas que contribuyen significativamente al kilometraje total.
- Heurística de Secuenciación: Una heurística rápida (Algoritmo 3) verifica si una tarea puede insertarse en la secuencia de un conductor sin violar las restricciones, lo cual es crucial para mantener la velocidad durante la fase de reconstrucción.
- Paralelización Cooperativa: Una estrategia de múltiples inicios se ejecuta en 8 núcleos (4 por cada subproblema). Cada 10 segundos, las unidades paralelas comparten resultados y reinician desde la mejor solución actual para reducir la varianza y evitar los óptimos locales.
Función Objetivo:
La función objetivo total $F$ es una suma ponderada que prioriza la asignación de tareas, seguida de la reducción de kilometraje y, finalmente, la eficiencia de la misión:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Donde $a_i$ representa las tareas no asignadas, $x_i$ y $y_i$ representan las distancias de viaje, y $e_i$ cuenta los inicios de misión.

Resultados Clave
El estudio compara la propuesta rVNS contra una Heurística Voraz (Greedy) y una Matheurística (desarrollada previamente en [1]) utilizando dos conjuntos de datos (S1: tareas menos numerosas y más restringidas; S2: tareas numerosas y menos restringidas).

Asignación de Tareas: La rVNS supera significativamente a los métodos anteriores. Mientras que los enfoques Greedy y de la Matheurística asignaron aproximadamente entre el 80% y el 89% de las tareas, la rVNS logró tasas de asignación del 99.0% al 99.8% en ambos conjuntos de datos.
Reducción de Kilometraje: La rVNS redujo el kilometraje total de la flota aproximadamente un 30% para el conjunto de datos S1 y un 20% para el S2 en comparación con la Matheurística.
Estabilidad y Convergencia:
- La rVNS paralelizada demostró mayor consistencia que la versión secuencial, con una desviación estándar en el kilometraje de 2–3% en comparación con el 4–6% de la secuencial.
- Velocidad de Convergencia: Para el conjunto de datos más pequeño (S1), el objetivo primario (conteo de tareas) convergió rápidamente (en ~1 segundo), mientras que la optimización del kilometraje continuó mejorando hasta un minuto. Para el conjunto de datos más grande (S2), el objetivo primario requirió ~10 segundos para converger, con rendimientos decrecientes después de un minuto.
Tiempo de Ejecución: Todas las soluciones se generaron dentro del margen requerido de un minuto (específicamente ~55–60 segundos incluyendo la sobrecarga).

Significancia y Reivindicaciones
El artículo sostiene que la metaheurística rVNS ofrece una solución robusta y flexible para la asistencia en tierra de aeropuertos que supera a las bases exactas y heurísticas previas. Su principal significancia radica en:

Viabilidad Operativa: Resuelve un problema altamente restringido y multiobjetivo dentro del estricto marco de un minuto requerido para la despacho en tiempo real.
Optimización Dual: Logra equilibrar con éxito la maximización de la finalización de tareas con la minimización de los costos operativos (kilometraje), una característica que no fue totalmente optimizada en trabajos anteriores.
Flexibilidad: Los autores señalan que la estructura del algoritmo permite la integración de nuevas restricciones u objetivos, como la gestión de la carga de vehículos eléctricos o operaciones de múltiples depósitos.
Aplicación en el Mundo Real: El estudio demuestra que el algoritmo puede manejar la complejidad de los datos del mundo real (incluyendo ventanas de tiempo deslizantes y flotas heterogéneas) mejor que los modelos previos, proporcionando una herramienta que los gestores de asistencia en tierra pueden usar para asignar automáticamente cientos de tareas diarias.

Los autores mantienen la modestia respecto a la optimalidad absoluta, reconociendo que, si bien el algoritmo no garantiza un óptimo global, converge consistentemente hacia soluciones que son superiores a los métodos existentes tanto en velocidad como en calidad. Destacan el potencial para futuras aplicaciones en escenarios de reasignación en tiempo real donde las tareas retrasadas deben reprogramarse dinámicamente.