💻 computer science

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

This paper presents a cooperative reduced Variable Neighbourhood Search (rVNS) metaheuristic to optimize the complex Multi-Trip Capacitated Vehicle Routing and Scheduling Problem with Time Windows and Meal Breaks (MTCVRSPTW-MB) for airport catering operations, demonstrating its superior efficiency and mileage reduction over exact methods on real-life instances at San Francisco International Airport.

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

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy airport as a giant, high-stakes puzzle. On one side, you have hundreds of airplanes arriving and departing, each needing food loaded or unloaded. On the other side, you have a fleet of trucks and drivers, each with specific skills, limited time, and strict rules about when they can take a lunch break.

The goal is simple: get every plane fed on time using the fewest miles driven by the trucks. But the math behind it is incredibly complex. If you try to solve this with a standard computer program, it's like trying to find a single specific grain of sand on a beach by checking every grain one by one—it takes too long.

This paper introduces a smarter, faster way to solve this puzzle using a method called rVNS (reduced Variable Neighbourhood Search). Here is how it works, broken down into everyday concepts:

1. The Problem: The "Tetris" of Airport Food

Think of the airport ground handling team as playing a high-speed game of Tetris.

The Blocks: These are the tasks (loading a plane, unloading a plane).
The Slots: These are the drivers and trucks.
The Rules: A driver can only drive a specific truck; a truck can only carry so much food; a driver must take a 30-minute lunch break between 4 and 5 hours after they start; and a plane must be fed within a specific time window.

In the past, the researchers tried two ways to solve this:

The "Perfect" Way (Exact Method): Trying to calculate every single possibility to find the absolute best solution. This is like trying to read every book in a library to find the best story. It's accurate but takes too long.
The "Fast" Way (Greedy Heuristic): Making the best choice available at the very moment. This is like grabbing the nearest book without looking at the others. It's fast, but often leads to a mediocre result.

2. The Solution: The "Smart Shuffle" (rVNS)

The new method, rVNS, is like a master puzzle solver who knows that sometimes you have to break a good arrangement to make a better one.

Instead of trying to build the perfect puzzle from scratch, the algorithm starts with a decent arrangement and then plays a game of "Shuffle and Swap."

The Shuffle: It randomly picks a few tasks (blocks) and removes them from the schedule, putting them back in a "waiting room."
The Swap: It then tries to put those tasks back in, but this time, it tries to fit them into different spots or swap them with other tasks to see if the overall picture looks better.

Why "Reduced"?
Usually, these algorithms try to shuffle huge chunks of the puzzle, which is slow. This new method shuffles small chunks but does it very quickly and repeatedly. It's like a chef tasting a soup and adding a pinch of salt, then tasting again, rather than trying to rewrite the entire recipe every time.

3. The Secret Sauce: Two Different Strategies

The algorithm is smart enough to know when to focus on what. It has two modes:

Mode A (The "Filler"): Its main goal is to make sure no task is left behind. It shuffles the schedule to ensure every plane gets fed.
Mode B (The "Mileage Saver"): Once most tasks are assigned, it switches focus to saving gas. It looks for ways to rearrange the trucks so they drive fewer miles between planes.

4. The "Team Huddle" (Parallelization)

To make this even faster, the researchers didn't just use one computer brain; they used a team. Imagine a group of detectives trying to solve a crime. Instead of one person checking every clue, they split the work:

Detective Team 1 works on the morning shift schedule.
Detective Team 2 works on the afternoon shift schedule.
Every 10 seconds, they huddle up, share their best ideas, and combine their findings.

This ensures they don't get stuck in a "dead end" (a local optimum) where they think they've found the best solution, but actually missed a better one.

5. The Results: Faster, Better, and Smoother

When they tested this new method on real data from San Francisco International Airport (SFO):

Success Rate: The old methods managed to assign about 80–89% of the tasks. The new rVNS method assigned 99% to 99.8% of the tasks. It almost never leaves a plane unfed.
Fuel Savings: Because it rearranges the schedule more efficiently, the trucks drove about 20% to 30% fewer miles than before.
Speed: It found these near-perfect solutions in less than a minute, which is fast enough to be used in real-time operations.

Summary

In short, this paper presents a new "smart shuffle" algorithm that helps airport managers assign food delivery tasks to drivers and trucks. By breaking the problem into smaller pieces, shuffling them randomly to find better fits, and using a team of computers to work together, the system ensures almost every plane gets fed while driving significantly fewer miles than previous methods. It turns a chaotic, impossible-to-solve puzzle into a manageable, efficient daily routine.

Technical Summary: Assigning and Optimising Airport Ground-Handling Operations via rVNS

Problem Definition
The study addresses the complex combinatorial optimization of airport ground-handling operations, specifically focusing on catering services. The core problem is modeled as the Multi-Trip Capacitated Vehicle Routing and Scheduling Problem with Time Windows and Meal Breaks (MTCVRSPTW-MB), extended to accommodate a heterogeneous fleet of trucks and drivers with varying qualifications and load patterns.

The objective is twofold:

Primary: Maximize the number of catering tasks (loading/unloading aircraft) assigned to available drivers and trucks.
Secondary: Minimize the total mileage required to execute these tasks.

The problem is constrained by strict operational rules, including:

Driver Constraints: Shift schedules, mandatory 30-minute meal breaks (occurring 4–5 hours after shift start), and qualification requirements for specific aircraft types and airlines.
Truck Constraints: Capacity limits, specific truck types (14FT, 16FT, 22FT), and limited daily availability.
Task Constraints: Time windows for execution, compatibility between truck/driver and the specific flight/airline, and volume requirements.
Mission Constraints: Rules governing multi-task missions, such as prohibiting domestic unloads after international loads within the same mission, ensuring sufficient travel time between tasks, and requiring all missions to start and end at the main catering unit.

The study utilizes real-world data from San Francisco International Airport (SFO) for March 2023, involving approximately 350 daily tasks, 80 drivers, and 40 trucks. A critical requirement is that solutions must be generated within one minute to be operationally viable.

Methodology
The authors propose a cooperative reduced Variable Neighborhood Search (rVNS) metaheuristic. This approach was selected over traditional Variable Neighborhood Search (VNS) and Adaptive Large Neighborhood Search (ALNS) to balance computational efficiency with solution quality.

Key components of the methodology include:

Reduced VNS (rVNS) Framework:
- Unlike classical VNS which varies step sizes, the rVNS employs a fixed, small step size.
- The algorithm operates through a deconstruction and reconstruction cycle: it unassigns a fixed number of tasks ( $n$ ) from the current solution and attempts to reassign them randomly.
- To compensate for the fixed step size, the algorithm leverages the high symmetry of the scheduling problem. By exploring "equivalent" solutions (different schedules with identical scores) through random swaps, the search diversifies without needing large, computationally expensive steps.
Algorithmic Structure:
- Decomposition (Problem Dichotomy): The daily schedule is split into two sub-problems (Morning and Afternoon) based on driver shift overlaps, allowing for parallel processing.
- Warm-Start Heuristic: The rVNS is initialized with a solution generated by a greedy heuristic that prioritizes tasks with fewer qualified drivers and mandatory meal breaks. This prevents the search from starting in a poor local optimum.
- Dual-Objective Randomization: The algorithm alternates between two randomization strategies based on objective convergence:
  - Primary Focus: Unassigns tasks with similar temporal positions to create space for unassigned tasks.
  - Secondary Focus: Unassigns tasks that contribute most significantly to total mileage.
- Sequencing Heuristic: A fast heuristic (Algorithm 3) checks if a task can be inserted into a driver's sequence without violating constraints, crucial for maintaining speed during the reconstruction phase.
- Cooperative Parallelization: A multi-start strategy runs on 8 cores (4 per sub-problem). Every 10 seconds, parallel units share results and restart from the current best solution to reduce variance and avoid local optima.
Objective Function:
The total objective function $F$ is a weighted sum prioritizing task assignment, followed by mileage reduction, and finally mission efficiency:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Where $a_i$ represents unassigned tasks, $x_i$ and $y_i$ represent travel distances, and $e_i$ counts mission starts.

Key Results
The study compares the proposed rVNS against a Greedy Heuristic and a Matheuristic (previously developed in [1]) using two datasets (S1: fewer, constrained tasks; S2: numerous, less constrained tasks).

Task Assignment: The rVNS significantly outperforms previous methods. While the Greedy and Matheuristic approaches assigned roughly 80–89% of tasks, the rVNS achieved 99.0% to 99.8% assignment rates across both datasets.
Mileage Reduction: The rVNS reduced total fleet mileage by approximately 30% for the S1 dataset and 20% for the S2 dataset compared to the Matheuristic.
Stability and Convergence:
- The parallelized rVNS demonstrated greater consistency than the sequential version, with a standard deviation in mileage of 2–3% compared to 4–6% for the sequential approach.
- Convergence Speed: For the smaller dataset (S1), the primary objective (task count) converged rapidly (within ~1 second), while mileage optimization continued to improve up to one minute. For the larger dataset (S2), the primary objective required ~10 seconds to converge, with diminishing returns after one minute.
Execution Time: All solutions were generated within the required one-minute window (specifically ~55–60 seconds including overhead).

Significance and Claims
The paper claims that the rVNS metaheuristic offers a robust, flexible solution for airport ground-handling that surpasses previous exact and heuristic baselines. Its primary significance lies in:

Operational Viability: It solves a highly constrained, multi-objective problem within the strict one-minute timeframe required for real-time dispatching.
Dual Optimization: It successfully balances the maximization of task completion with the minimization of operational costs (mileage), a feature not fully optimized in prior work.
Flexibility: The authors note that the algorithm's structure allows for the integration of new constraints or objectives, such as managing electric vehicle charging or multi-depot operations.
Real-World Application: The study demonstrates that the algorithm can handle the complexity of real-world data (including sliding time windows and heterogeneous fleets) better than previous models, providing a tool that ground handlers can use to automatically assign hundreds of daily tasks.

The authors remain modest regarding absolute optimality, acknowledging that while the algorithm does not guarantee a global optimum, it consistently converges to solutions that are superior to existing methods in both speed and quality. They highlight the potential for future application in real-time reassignment scenarios where delayed tasks must be dynamically rescheduled.