Paper Info
Title
Construction-Based Optimization Approaches to Airline Crew Rostering Problem
Abstract
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. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Note to Practitioners</italic> —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.
Year
DOI
Venue
2020
10.1109/TASE.2019.2955988
IEEE Transactions on Automation Science and Engineering
Keywords
DocType
Volume
Mathematical model,Planning,Atmospheric modeling,Task analysis,Genetic algorithms,Optimization,Companies
Journal
17
Issue
ISSN
Citations 
3
1545-5955
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Zizhen Zhang110017.27
MengChu Zhou28989534.94
Jiahai Wang360449.01