Airport Vehicle Routing Problem

Go to the optimization tool

The project

In this project, we consider a Responsive Dynamic Capacitated Vehicle Routing Problem with Time Windows (rich CVRPTW). The problem was initially suggested by Liege Airport (the 8th biggest cargo airport in Europe).
This research is presented in the paper "An ant colony System for Responsive Dynamic Vehicle Routing"

It is a CVRPTW since:

  • VRP: the main goal is to define the journey of a set of trucks. These trucks have to refuel a set of aircraft/flights (clients).
  • Capacitated: each truck can deliver a maximal quantity of fuel over one trip. Each aircraft has a specific demand.
  • Time Windows: each flight MUST be served within its specific specified time window (after the landing and before the take off).
Beside (strictly) satisfying these constraints, the goal is either to minimize the aircraft time on ground(a truck should complete the fueling operations as soon as possible) or to minimize the total distance traveled by the trucks (still satisfying the other constraints including the TW).

It is a rich CVRPTW since we also take into account:

  • Heterogeonous fleet: each truck has its own set of specificities:
    • Capacity: each truck may transport a different quantity of fuel
    • Speed of operations: for each truck, the operating time to serve an aircraft is specified as a fixed time and a variable time. The fixed time may cover initialization operations, closing operations, margin and pause... The variable coefficient is the time required to deliver one liter of fuel (speed of the pump).
    • Compatibility: some trucks are not allowed to serve some flights or some types of aircraft.
  • 'Split' delivery: when the remaining capacity of a truck is not large enough to serve completely an aircraft, it can still be allowed to operate this aircraft (if it can deliver a minimal quantity). Another truck will come later to complete the refueling.
  • Fuel station: when a truck is empty (or nearly empty), it can go back to the station/depot for reloading before starting a new trip. Time for reloading is also specific to each truck.
  • Real time and 'stochastic': there is a lot of uncertainties in practice. The quantities of fuel requested by each aircrapft depend on a lot of parameters including e.g. the weight of the aircraft after cargo loading. Only expectations of these quantities are known at the beginning of a day. Moreover, an aircraft could be late. A truck could experience difficulties....
    Therefore, we should be able to optimize again the planning each time new (exact) data is available all along the day. It implies a need for:
    • A fast optimization process (one more reason for a heuristic)
    • The optimization process can start with any (new) data including the fact that the trucks will not allways start from the fuel station, but from their current location and with a knowledge of their current capacity.
  • 24/7/365: an airport never stops to operate! There is no beginning nor end of a day. Optimizing again means adjusting data but also adding new flights/clients that will arrive later
  • Pre-fueling: in practice, the fueling is sometimes done in two distinct steps: a pre-fueling with a minimal/estimated quantity and a complementary fueling when the required quantity is known with certainty (new block fuel).

Approach: ant colony.
Some 'practical' parameters like the intensification of the use of the same trucks (longer routes,less trucks).

Online optimization tool

(A more flexible Java standalone version also exists)
A default realistic case is provided.
Press "Modify data" to modify the inputs or to enter your own case. Press "Start Optimization" to start the optimization and to get the results.

Size of the picture(s):
Other Tools developed for research: