Abstract

This thesis proposes conflict-free mathematical models and solution strategies for both gate scheduling and taxiway scheduling problems by taking account all meaningful airport and flight characteristics into consideration that are not yet extensively studied in current academic literature. Since gate schedule performance has a great impact on the performance of the taxiway, we consider gate scheduling as a bi-objective optimization problem, present mathematical models and propose a two-phase solution approach. We also propose a mixed integer programming (MIP) model that considers collision avoidance on the taxiways, separation distances between aircrafts, speed changes and exact travelling times without adapting a state-time network in which the decision variables are defined with time indices. Instead, the non-time segmented model proposed in this thesis, determines a taxi plan for each aircraft by identifying the sequence of taxiway intersections represented as nodes to be visited and determines the aircrafts’ exact arrival and departure times to these nodes, average speed used on the taxiway represented as links between two consecutive nodes while ensuring the safety conditions that avoid aircraft collisions. The cost incurred from arrival and departure delays with total taxiing time is minimized. The model enables collision free airport operations considering both airlines and airport controller’s objectives in continuous time where we know the exact arrival and departure times which is more accurate in tackling collision issues. However, accuracy comes with a cost of solution time. To overcome the difficulty to solve, strategies are proposed. The first strategy proposed, called the iterative-TSM, adopts a batch by batch policy and optimizes the TSM by solving it in an iterative way where in each iteration, schedules of the previous iteration are fixed. The second strategy proposed motivates from the idea of decomposition the model into two as routing and timing problem and incorporates a genetic algorithms with TSM. All the models proposed are tested on a hypothetical data and the results are presented. Main contributions of this thesis can be listed as follows:
• A MILP model is presented for flight gate scheduling problem. The model is compared to modified version of one of the existing MILP model in literature and efficiency of the proposed model is evaluated. A two phase solution approach making use of the proposed MILP is also presented and the characteristics of the problem are analysed. While utilization of gates is maximized, on time performance is also considered.
• A MILP that considers collision avoidance on the taxiways, separation distances between aircrafts, speed changes and exact travelling times without adapting a state-time network in which the decision variables are defined with time indices. Instead, all safety constraints are modeled with Big-Ms. This enables us to know the exact arrival and departure times for each flight on each link on the ground.
• Collision free taxiway scheduling is achieved. Since the models in the existing literature either assumes arbitrary capacities on the nodes of the network or discretizes time, they do not guarantee collision avoidance.
• Speed changes, rerouting, and holding at gates and taxiway intersections are used as control options.
• Both airlines and airport authorities’ objectives are considered. Proposed models have the capability to be adopted as a decision support tool for the ground controllers and they allow airport traffic authorities to do what-if analysis in case of a change in the flight or airport network information. Proposed TSM also minimizes to total taxiing time which results in less costly taxiway schedules for airlines in terms of fuel costs and CO2 emissions.
• Two solution strategies are proposed for the TSM: iterative TSM and GA-TSM. While iterative TSM decomposes the problem into batches of flights, solves each batch by fixing the schedules of the previous batch in each batch, GA-TSM decomposes the problem into routing and timing. While GA searches for the best set of routes for the flights, fixed TSM solves the timing problem for a given set of routes.