A column generation approach to the airline crew pairing problem to minimize the total person-days
-
- WU Wei
- Graduate School of Information Science, Nagoya University
-
- HU Yannan
- Graduate School of Information Science, Nagoya University
-
- HASHIMOTO Hideki
- Department of Logistics and Information Engineering, Tokyo University of Marine Science and Technology
-
- ANDO Tomohito
- Transportation and City Infrastructure Division, NEC Corporation
-
- SHIRAKI Takashi
- Data Science Research Laboratories, Central Research Laboratories, NEC Corporation
-
- YAGIURA Mutsunori
- Department of Logistics and Information Engineering, Tokyo University of Marine Science and Technology
抄録
In this paper, we consider the crew pairing problem in airline scheduling that calls for assigning crew members in order to cover all flights with the minimum total person-days under the constraints that the schedule of each crew member does not violate given constraints on the total working time, flying time, and the number of landings. In practical applications, it is difficult to create an efficient schedule satisfying all the constraints. We formulate the problem as a set covering problem and apply an LP-based column generation approach to generate a candidate set of schedules. We propose a branch-and-bound method based upon a resource constrained dynamic programming for the column generation procedure. Computational results are given for a number of large-scale instances with up to 10,000 flights.
収録刊行物
-
- Journal of Advanced Mechanical Design, Systems, and Manufacturing
-
Journal of Advanced Mechanical Design, Systems, and Manufacturing 10 (3), JAMDSM0040-JAMDSM0040, 2016
一般社団法人 日本機械学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001205272386176
-
- NII論文ID
- 130005161643
-
- ISSN
- 18813054
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可