TY - JOUR
T1 - Construction-Based Optimization Approaches to Airline Crew Rostering Problem
AU - Zhang, Zizhen
AU - Zhou, Meng Chu
AU - Wang, Jiahai
N1 - Funding Information:
Manuscript received August 13, 2019; revised October 12, 2019; accepted November 18, 2019. Date of publication December 19, 2019; date of current version July 2, 2020. This article was recommended for publication by Associate Editor S. Dadras and Editor Q. Zhao upon evaluation of the reviewers’ comments. This work was supported in part by the National Science Foundation of China under Grant 71601191 and Grant 61673403 and in part by the Natural Science Foundation of Guangdong Province under Grant 2016A030313264 and Grant 2019A1515011169. (Corresponding author: MengChu Zhou.) Z. Zhang and J. Wang are with the School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510275, China, and also with the Guangdong Key Laboratory of Big Data Analysis and Processing, Sun Yat-sen University, Guangzhou 510275, China (e-mail: zhangzizhen@gmail.com; wangjiah@mail.sysu.edu.cn).
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2020/7
Y1 - 2020/7
N2 - An airline crew rostering problem (ACRP) is one of the most important problems in an airline planning process. It aims at determining an optimal assignment of pairings, which refer to sequences of flights starting from and ending at the same crew base, to aircrew to form roster lines. In practice, ACRP is subject to various types of constraints. We present a constraint-implicit mathematical model taking into account the basic, horizontal, and vertical constraints. In order to solve a kind of ACRP, we propose a construction-based variable neighborhood search (VNS) framework that can build rosters effectively. Three construction methods, i.e., crew-by-crew, pairing-by-pairing, and orthogonal constructions, are introduced. To evaluate our approaches, we conduct extensive experiments on two scenarios (intense and light workload) of instances originated from a Chinese airline company and make comparisons among different VNS approaches. The computational results show that the proposed approaches are capable of producing high-quality solutions in both scenarios. Note to Practitioners-This article investigates an airline crew rostering problem (ACRP) originated from a renowned Chinese airline. The goal is to effectively utilize its manpower resources. ACRP has various kinds of rules, constraints, and objectives. It is generally very difficult to model a practical problem by using explicit formula sets. We thereby provide an implicit mathematical model to define the problem. Based on this model, concise yet effective heuristic approaches are devised to construct rosters automatically. They can handle the case that has more than 1000 attendants, 2000 pairings, and 12 000 flight tasks. We believe that the proposed approaches can serve as kinds of generic frameworks for practical and large-scale ACRPs.
AB - An airline crew rostering problem (ACRP) is one of the most important problems in an airline planning process. It aims at determining an optimal assignment of pairings, which refer to sequences of flights starting from and ending at the same crew base, to aircrew to form roster lines. In practice, ACRP is subject to various types of constraints. We present a constraint-implicit mathematical model taking into account the basic, horizontal, and vertical constraints. In order to solve a kind of ACRP, we propose a construction-based variable neighborhood search (VNS) framework that can build rosters effectively. Three construction methods, i.e., crew-by-crew, pairing-by-pairing, and orthogonal constructions, are introduced. To evaluate our approaches, we conduct extensive experiments on two scenarios (intense and light workload) of instances originated from a Chinese airline company and make comparisons among different VNS approaches. The computational results show that the proposed approaches are capable of producing high-quality solutions in both scenarios. Note to Practitioners-This article investigates an airline crew rostering problem (ACRP) originated from a renowned Chinese airline. The goal is to effectively utilize its manpower resources. ACRP has various kinds of rules, constraints, and objectives. It is generally very difficult to model a practical problem by using explicit formula sets. We thereby provide an implicit mathematical model to define the problem. Based on this model, concise yet effective heuristic approaches are devised to construct rosters automatically. They can handle the case that has more than 1000 attendants, 2000 pairings, and 12 000 flight tasks. We believe that the proposed approaches can serve as kinds of generic frameworks for practical and large-scale ACRPs.
KW - Airline crew rostering
KW - construction-based
KW - variable neighborhood search (VNS)
UR - http://www.scopus.com/inward/record.url?scp=85077276402&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077276402&partnerID=8YFLogxK
U2 - 10.1109/TASE.2019.2955988
DO - 10.1109/TASE.2019.2955988
M3 - Article
AN - SCOPUS:85077276402
SN - 1545-5955
VL - 17
SP - 1399
EP - 1409
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 3
M1 - 8936992
ER -