Ravidas, Amrish Deep (2010-12). An Exact Algorithm and a Local Search Heuristic for a Two Runway Scheduling Problem. Master's Thesis. Thesis uri icon

abstract

  • A generalized dynamic programming based algorithm and a local search heuristic are used to solve the Two Runway Departure Scheduling Problem that arises at an airport. The objective of this work is to assign the departing aircraft to one of the runways and find a departing time for each aircraft so that the overall delay is minimized subject to the timing, safety, and the ordering constraints. A reduction in the overall delay of the departing aircraft at an airport can improve the airport surface operations and aircraft scheduling. The generalized dynamic programming algorithm is an exact algorithm, and it finds the optimal solution for the two runway scheduling problem. The performance of the generalized dynamic programming algorithm is assessed by comparing its running time with a published dynamic programming algorithm for the two runway scheduling problem. The results from the generalized dynamic programming algorithm show that this algorithm runs much faster than the dynamic programming algorithm. The local search heuristic with k - exchange neighborhoods has a short running time in the order of seconds, and it finds an approximate solution. The performance of this heuristic is assessed based on the quality of the solution found by the heuristic and its running time. The results show that the solution found by the heuristic for a 25 aircraft problem has an average savings of approximately 15 percent in delays with respect to a first come-first served solution. Also, the solutions produced by a 3-opt heuristic for a 25 aircraft scheduling problem has an average quality of 8 percent with respect to the optimal solution found by the generalized dynamic programming algorithm. The heuristic can be used for both real-time and fast-time simulations of airport surface operations, and it can also provide an upper limit for an exact algorithm. Aircraft arrival scheduling problems may also be addressed using the generalized dynamic programming algorithm and the local search heuristic with slight modification to the constraints.
  • A generalized dynamic programming based algorithm and a local search heuristic

    are used to solve the Two Runway Departure Scheduling Problem that arises at

    an airport. The objective of this work is to assign the departing aircraft to one of the

    runways and find a departing time for each aircraft so that the overall delay is minimized

    subject to the timing, safety, and the ordering constraints. A reduction in the

    overall delay of the departing aircraft at an airport can improve the airport surface

    operations and aircraft scheduling. The generalized dynamic programming algorithm

    is an exact algorithm, and it finds the optimal solution for the two runway scheduling

    problem. The performance of the generalized dynamic programming algorithm

    is assessed by comparing its running time with a published dynamic programming

    algorithm for the two runway scheduling problem. The results from the generalized

    dynamic programming algorithm show that this algorithm runs much faster than

    the dynamic programming algorithm. The local search heuristic with k - exchange

    neighborhoods has a short running time in the order of seconds, and it finds an approximate

    solution. The performance of this heuristic is assessed based on the quality

    of the solution found by the heuristic and its running time. The results show that

    the solution found by the heuristic for a 25 aircraft problem has an average savings of

    approximately 15 percent in delays with respect to a first come-first served solution. Also,

    the solutions produced by a 3-opt heuristic for a 25 aircraft scheduling problem has an average quality of 8 percent with respect to the optimal solution found by the generalized

    dynamic programming algorithm. The heuristic can be used for both real-time

    and fast-time simulations of airport surface operations, and it can also provide an

    upper limit for an exact algorithm. Aircraft arrival scheduling problems may also be

    addressed using the generalized dynamic programming algorithm and the local search

    heuristic with slight modification to the constraints.

publication date

  • December 2010