Abstract
The airline crew rostering problem (CRP) is significant for balancing the workload of crew and for improving the satisfaction rate of crew's preferences, which is related to the fairness and satisfaction of crew. However, most existing work considers only one objective on fairness or satisfaction. In this study, we propose a new practical model for CRP that takes both fairness and satisfaction into account simultaneously. To solve the multi-objective CRP efficiently, we develop an ant colony system (ACS) algorithm based on the multiple populations for multiple objectives (MPMO) framework, termed multi-objective ACS (MOACS). The main contributions of MOACS lie in three aspects. Firstly, two ant colonies are utilized to optimize fairness and satisfaction objectives, respectively. Secondly, a new hybrid complementary heuristic strategy with three kinds of heuristic information schemes is proposed to avoid ant colonies focusing only on their own objectives. Ant colonies randomly choose one of the three schemes to help explore the Pareto front (PF) sufficiently. Thirdly, a local search strategy with two types of local search respectively for fairness and satisfaction is designed to further approach the global PF. The MOACS is applied to seven real-world monthly CRPs with different sizes from a major North-American airline. Experimental results show that MOACS generally outperforms the greedy algorithm and some other popular multi-objective optimization algorithms, especially on large-scale instances.
| Original language | English |
|---|---|
| Pages (from-to) | 6784-6798 |
| Journal | IEEE Transactions on Intelligent Transportation Systems |
| Volume | 22 |
| Issue number | 11 |
| Early online date | 8 Jun 2020 |
| DOIs | |
| Publication status | Published - Nov 2021 |
| Externally published | Yes |
Funding
This work was supported in part by the National Key Research and Development Program of China under Grant 2019YFB2102102, in part by the Outstanding Youth Science Foundation under Grant 61822602, in part by the National Natural Science Foundations of China (NSFC) under Grant 61772207 and Grant 61873097, in part by the Guangdong Natural Science Foundation Research Team under Grant 2018B030312003, in part by the Ministry of Science and ICT through the National Research Foundation of Korea under Grant NRF-2019H1D3A2A01101977, and in part by the Hong Kong General Research Fund (GRF)-RGC under Grant 9042489 (CityU 11206317).
Keywords
- ant colony system (ACS)
- Crew rostering problem (CRP)
- multi-objective optimization
- multiple populations for multiple objectives (MPMO)