Back to search

University of Southampton

Crew Scheduling for Vietnam Airlines

Abstract

dc:description.abstract

An airline crew scheduling problem is one of the largest-scale optimization problems for the airline industry. The crew scheduling problem plays an important role in airline operations and is an interesting problem for the application of operations research. The objective of this problem is the optimal allocation of crews to flights. <br/><br/>Because of the large size of the airline industry and the complexity of safety rules and regulations, as well as employment agreements, the crew scheduling problem is divided into two sub-problems: crew-pairing and crew-rostering. For crew-pairing, all pairings are formed in order to exactly cover every flight of the schedule, and then the crew-rostering process assigns these pairings to individual crew-members and generates the monthly rosters. The objective criteria of the crew scheduling problem typically require a reduction of the number of unassigned flights, the minimization of the number of crews needed to cover the duties and fairness of crew assignment, as well as the preferences of special working-patterns of crews.<br/><br/> In this research, we decompose the problems in many stages and solve them in a day-by-day rolling manner for the crew pairing problem, with two heuristics and exact method combinational algorithms, and a crew-by-crew approach for the crew rostering problem. We combine heuristics with a new mathematic formulation in several algorithms to solve the problems. <br/><br/>Specifically, we apply techniques of constraint programming, such as domain creation, local consistency, bound consistency, local search and constraints propagation, in order to design effective heuristic algorithms for the crew rostering problem to generate rosters, thus gaining a good quality solution and reducing computational time significantly. In addition to the airline regulations being encoded by several constraints, we impose additional constraints to reduce the domains of variables. The resulting domain reductions are propagated to other constraints, which additionally reduces the search space. Numerical results based on the data for Vietnam Airlines are presented and demonstrate the potential of our approach.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nguyen, Hang Thu
Advisors dc:contributor.advisor
  • Potts, Christopher
  • Bektas, Tolga

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Nguyen, Hang Thu. Crew Scheduling for Vietnam Airlines. doctoral thesis, University of Southampton, 2019.