Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs

The aircraft routing and crew pairing problems are two processes that are difficult to be solved in the airline operations planning due to the rules that each flight leg needs to be operated on by one aircraft and one crew pair. These two problems, though interrelated in practice, are usually solved...

Full description

Saved in:

Bibliographic Details
Main Author:	Mohamed, Nurul Farihan
Format:	Thesis
Language:	English
Published:	2017
Subjects:	QA Mathematics
Online Access:	http://eprints.utm.my/id/eprint/79470/1/NurulFarihanMohamedPFS2017.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.79470
record_format	uketd_dc
spelling	my-utm-ep.794702018-10-31T12:41:31Z Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs 2017 Mohamed, Nurul Farihan QA Mathematics The aircraft routing and crew pairing problems are two processes that are difficult to be solved in the airline operations planning due to the rules that each flight leg needs to be operated on by one aircraft and one crew pair. These two problems, though interrelated in practice, are usually solved sequentially and often leads to suboptimal solution. Thus, this research contributes to the solution of the integrated aircraft routing and crew pairing problem in order to determine the minimum cost of this integrated problem where each flight leg is covered by one aircraft and one crew pair. This study also considers short connection between two flight legs in order to ensure that the crews do not change the aircraft if the connection time is in between 20 to 59 minutes. Another consideration is the restricted connection that imposes penalty costs when the second flight leg uses the same crew but not the same aircraft. Based on the literature review, most of the existing solutions concentrate on minimizing the planned costs. Although the minimum costs are significantly important in airline operations planning, the efficiency of a solution method in terms of computational time cannot be neglected. It is necessary to solve the integrated problem by using an efficient model that is able to generate a good high quality solution in a short time as requested by the airline industry. In order to solve the problem, a set of feasible aircraft routes and crew pairs are initially generated to be used as the input data in solving the integrated model effectively. There are two heuristic methods which are proposed in generating the set of feasible aircraft routes and crew pairs namely constructive-based heuristic and Genetic Algorithm (GA). The generated feasible aircraft routes and crew pairs are then used in solving the integrated problem by using Integer Linear Programming (ILP) method, Dantzig Wolfe Decomposition method, Benders Decomposition method and Particle Swarm. Computational results obtained from these methods are then compared by testing them on four types of aircraft with different number of flight legs based on Malaysia local flights for one week flight cycle. From the numerical results, it can be concluded that the proposed methods are more efficient compared to the ILP method available in the literature in terms of the computational time where the hybrid algorithm of GA and Benders Decomposition is found to be advantageous compared to the others. The maximum cost deviation of only 4.77% also justifies the strength of this hybrid algorithm. One possible future research that can be extended from this study would be the development of an algorithm that incorporates a parallel GA within the proposed methods for larger instances which are likely to exist in international flights in order to speed up the planning process. 2017 Thesis http://eprints.utm.my/id/eprint/79470/ http://eprints.utm.my/id/eprint/79470/1/NurulFarihanMohamedPFS2017.pdf application/pdf en public phd doctoral Universiti Teknologi Malaysia, Faculty of Science Faculty of Science
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA Mathematics
spellingShingle	QA Mathematics Mohamed, Nurul Farihan Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
description	The aircraft routing and crew pairing problems are two processes that are difficult to be solved in the airline operations planning due to the rules that each flight leg needs to be operated on by one aircraft and one crew pair. These two problems, though interrelated in practice, are usually solved sequentially and often leads to suboptimal solution. Thus, this research contributes to the solution of the integrated aircraft routing and crew pairing problem in order to determine the minimum cost of this integrated problem where each flight leg is covered by one aircraft and one crew pair. This study also considers short connection between two flight legs in order to ensure that the crews do not change the aircraft if the connection time is in between 20 to 59 minutes. Another consideration is the restricted connection that imposes penalty costs when the second flight leg uses the same crew but not the same aircraft. Based on the literature review, most of the existing solutions concentrate on minimizing the planned costs. Although the minimum costs are significantly important in airline operations planning, the efficiency of a solution method in terms of computational time cannot be neglected. It is necessary to solve the integrated problem by using an efficient model that is able to generate a good high quality solution in a short time as requested by the airline industry. In order to solve the problem, a set of feasible aircraft routes and crew pairs are initially generated to be used as the input data in solving the integrated model effectively. There are two heuristic methods which are proposed in generating the set of feasible aircraft routes and crew pairs namely constructive-based heuristic and Genetic Algorithm (GA). The generated feasible aircraft routes and crew pairs are then used in solving the integrated problem by using Integer Linear Programming (ILP) method, Dantzig Wolfe Decomposition method, Benders Decomposition method and Particle Swarm. Computational results obtained from these methods are then compared by testing them on four types of aircraft with different number of flight legs based on Malaysia local flights for one week flight cycle. From the numerical results, it can be concluded that the proposed methods are more efficient compared to the ILP method available in the literature in terms of the computational time where the hybrid algorithm of GA and Benders Decomposition is found to be advantageous compared to the others. The maximum cost deviation of only 4.77% also justifies the strength of this hybrid algorithm. One possible future research that can be extended from this study would be the development of an algorithm that incorporates a parallel GA within the proposed methods for larger instances which are likely to exist in international flights in order to speed up the planning process.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Mohamed, Nurul Farihan
author_facet	Mohamed, Nurul Farihan
author_sort	Mohamed, Nurul Farihan
title	Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
title_short	Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
title_full	Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
title_fullStr	Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
title_full_unstemmed	Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
title_sort	hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs
granting_institution	Universiti Teknologi Malaysia, Faculty of Science
granting_department	Faculty of Science
publishDate	2017
url	http://eprints.utm.my/id/eprint/79470/1/NurulFarihanMohamedPFS2017.pdf
_version_	1747818234094026752

Hybrid methods for integrated aircraft routing and crew pairing problem with short flight legs

Similar Items