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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2010-12-8787 |
| Date | 2010 December 1900 |
| Creators | Ravidas, Amrish Deep |
| Contributors | Rathinam, Sivakumar, Darbha, Swaroop |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | application/pdf |
Page generated in 0.0022 seconds