Modeling and Solving the Aircraft Landing Problem

Tutorial Airline Scheduling

Frédéric Senior Optimization Scientist January 18, 2021

LocalSolver is the solver of choice to tackle large-scale scheduling problems. As an example, we show here how the Aircraft Landing Problem can be easily modeled and efficiently solved using LocalSolver Optimizer. This problem is described in the article “Scheduling aircraft landings – the static case” by J. E. Beasley, M. Krishnamoorthy, Y. M. Sharaiha, and D. Abramson (2000), Transportation Science 34(2), pp. 180-197. The test instances come from the OR-Library maintained by J. E. Beasley.

Definition of the Aircraft Landing Problem

In the Aircraft Landing Problem, landing times of a set of planes have to be scheduled. Each plane can land in a predetermined time window around a target time. The objective is to minimize the “cost penalty” due to landings before or after target times. A separation time has to be respected between two successive planes. This separation time depends on the types of planes. This diagram presents an example of a solution to the problem with 3 planes.

LocalSolver model of the Aircraft Landing Problem

In this LocalSolver model, here implemented in Python, the landing order is represented as a list variable. The i-th element of the list corresponds to the index of the i-th plane to land. To ensure that all planes are scheduled, the size of the list variable is constrained to be equal to the number of planes.

# A list variable: landingOrder[i] is the index of the ith plane to land
landing_order = model.list(nb_planes)

# All planes must be scheduled
model.constraint(model.count(landing_order) == nb_planes)

Another decision variable is introduced: the preferred landing time for each plane. A plane should land after the target time only if it has to wait after the landing of the preceding plane. Thus, the preferred landing time of a plane is between the earliest landing time and the target time.

# Int variable: preferred landing time for each plane
preferred_time = [model.int(earliest_time[p], target_time[p]) for p in range(nb_planes)]
preferred_time_array = model.array(preferred_time)

The landing time of each plane is defined by a recursive function as the maximum between the preferred landing time and the first time the plane can land, respecting the separation time from the previous plane.

# Landing time for each plane
landing_time_selector = model.lambda_function(lambda p, prev:
                                model.max(preferred_time_array[landing_order[p]],
                                get_min_landing_time(p, prev, model, separation_time_array,
                                landing_order)))

landing_time = model.array(model.range(0, nb_planes), landing_time_selector)

Landing times must respect the separation time with every previous plane.

for p in range(1, nb_planes):
      last_separation_end = [landing_time[previous_plane] +    
                  model.at(separation_time_array, landing_order[previous_plane], landing_order[p]) 
                  for previous_plane in range(p)]
      model.constraint(landing_time[p] >= model.max(last_separation_end))

The objective is to minimize the penalty cost due to the earliness or the lateness of each plane. To compute this cost for each plane, a ternary condition is used to select either the earliness cost or the lateness cost depending on the difference between the landing time and the target time.

Finally, we initialize the list with the planes sorted by target times.

# Initialize landing_order
list_to_init = landing_order.get_value()
list_to_init.clear()
sorted_planes_by_target = sorted(range(len(target_time)), key = lambda k: target_time[k])        
for p in sorted_planes_by_target :
      list_to_init.add(p)

LocalSolver results

Optimal solutions are known for the first 8 instances. For instances 9-13, the gap in % is computed from the best solutions reported in the literature. For the first 8 instances, LocalSolver finds the optimal solution within a few seconds. For larger instances, from 100 to 500 planes, the gap in % to the best-known solution for different time limits is presented in the figure below.

This last figure presents the results obtained on instance 9 with 100 planes.

You can find the complete model of the Aircraft Landing Problem in Python, Java, C#, C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don’t hesitate to contact us for any further information or support.