- Help & FAQ
Airline crew scheduling: Models, algorithms, and data sets
- School of Philosophy, Psychology and Language Sciences
Research output : Contribution to journal › Article › peer-review
Abstract / Description of output
| Original language | English |
|---|---|
| Pages (from-to) | 111-137 |
| Number of pages | 27 |
| Journal | |
| Volume | 6 |
| Issue number | 2 |
| Early online date | 30 Jun 2017 |
| DOIs | |
| Publication status | Published - Jun 2017 |
Keywords / Materials (for Non-textual outputs)
- airline crew scheduling
- crew scheduling
- crew pairing
- crew assignment
- personalized crew assignment
- column generation
- mathematics subject classification
Access to Document
- 10.1007/s13676-015-0080-x
Fingerprint
- Scheduling Problem Computer Science 100%
- Scheduling Computer Science 100%
- Models Computer Science 100%
- Algorithms Computer Science 100%
- Column Generation Computer Science 33%
- Internet Computer Science 33%
- Problem Definition Computer Science 33%
- Problem Formulation Computer Science 33%
T1 - Airline crew scheduling
T2 - Models, algorithms, and data sets
AU - Kasirzadeh, Atoosa
AU - Saddoune, M.
AU - Soumis, F.
N1 - This research was supported by the Natural Sciences and Engineering Research Council of Canada and a collaborative R&D grant from AD OPT, a division of Kronos. Thanks are due to the personnel of AD OPT, a division of Kronos, for providing the data sets and the GENCOL software library. The authors are thankful to Frédéric Quesnel for his help in preparing the data sets and generators. The authors are grateful to the editor and two anonymous reviewers for their valuable comments.
PY - 2017/6
Y1 - 2017/6
N2 - The airline crew scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into crew pairing and crew assignment because of its large size and the complex safety agreements and contractual rules. Several solution methodologies have been developed, but many objectives and constraints are treated approximately and research is ongoing. In this paper, we present a comprehensive problem definition for the airline crew scheduling problem, and we review existing problem formulations and solution methodologies. In addition, we formulate the personalized cockpit crew scheduling problem as a set covering problem and we solve it using column generation. We present computational results for real data from a major US carrier, and we describe the data sets (available on the internet) in detail to establish a basis for future research.
AB - The airline crew scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into crew pairing and crew assignment because of its large size and the complex safety agreements and contractual rules. Several solution methodologies have been developed, but many objectives and constraints are treated approximately and research is ongoing. In this paper, we present a comprehensive problem definition for the airline crew scheduling problem, and we review existing problem formulations and solution methodologies. In addition, we formulate the personalized cockpit crew scheduling problem as a set covering problem and we solve it using column generation. We present computational results for real data from a major US carrier, and we describe the data sets (available on the internet) in detail to establish a basis for future research.
KW - airline crew scheduling
KW - crew scheduling
KW - crew pairing
KW - crew assignment
KW - personalized crew assignment
KW - column generation
KW - data set
KW - mathematics subject classification
U2 - 10.1007/s13676-015-0080-x
DO - 10.1007/s13676-015-0080-x
M3 - Article
JO - EURO Journal on Transportation and Logistics
JF - EURO Journal on Transportation and Logistics
Assignment Problem: Meaning, Methods and Variations | Operations Research
After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.
Meaning of Assignment Problem:
An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.
The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.
Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.
Definition of Assignment Problem:
ADVERTISEMENTS:
Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.
The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:
- Yiqiao Wang 7 ,
- Hanfei Shi 8 &
- Liuzhouyu Shi 9
Part of the book series: Applied Economics and Policy Studies ((AEPS))
Included in the following conference series:
- International Conference on Business and Policy Studies
849 Accesses
As the accessibility of airline transportation increases, the crew scheduling problem has received increasing attention. Moreover, especially with the limited flow of human resources and the economic stagnation during the pandemic stage, arranging the working hours of the attendants and the flight routes reasonably and effectively to reduce operational costs has become a crucial concern for airline companies. In this paper, we formulate a crew scheduling problem model with four international airports in the US with reasonable constraints to set up a set covering the problem and solve it using integer linear programming. We present computational results for our problem using MATLAB and discuss the concerns for further research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Durable hardcover edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Similar content being viewed by others
Airline crew scheduling: models, algorithms, and data sets.
A Branch-and-Cut Algorithm for Aircraft Routing with Crew Assignment for On-Demand Air Transportation
Solving a large-scale integrated fleet assignment and crew pairing problem.
Fontanet-Pérez, P., Vázquez, X.H., Carou, D.: The impact of the COVID-19 crisis on the US airline market: Are current business models equipped for upcoming changes in the Air Transport Sector? Case Studies on Transport Policy (2022). https://www.sciencedirect.com/science/article/pii/S2213624X22000256#s0030
Kasirzadeh, A., Saddoune, M., Soumis, F.: Airline crew scheduling: models, algorithms, and data sets. EURO J. Trans. Logistics 6 (2), 111–137 (2017). https://doi.org/10.1007/s13676-015-0080-x
Article Google Scholar
Aydemir-Karadag, A., Dengiz, B., Bolat, A.: Crew pairing optimization based on hybrid approaches. Comput. Ind. Eng. 65 (1), 87–96 (2013). https://doi.org/10.1016/j.cie.2011.12.005
Cheap student flights, hotels and Tours. StudentUniverse. (n.d.). 18 July 2022. https://www.studentuniverse.com
Gopalakrishnan, B., Johnson, E.L.: Airline crew scheduling: state-of-the-art. Ann. Oper. Res. 140 (1), 305–337 (2005). https://doi.org/10.1007/s10479-005-3975-3
Crew scheduling problem - mcgill university. (n.d.). 14 July 2022. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/lec7.pdf
Office of the chief counsel. Office of the Chief Counsel | Federal Aviation Administration. (n.d.). Retrieved July 29, 2022, from https://www.faa.gov/about/office_org/headquarters_offices/agc
Taboga, M.: Indicator function. Indicator function | Indicator random variable (n.d.). 29 July 2022. https://www.statlect.com/fundamentals-of-probability/indicator-functions
Vanderbei, R.J.: Chapter 23. Integer Programming. In Linear Programming: Foundations and Extensions (International Series in Operations Research & Management Science (196)), 4th ed. 2014 ed., Vol. 196, pp. 345–346 (2013). Springer. https://doi.org/10.1007/978-1-4614-7630-6
Office of The Federal Register. Code of Federal Regulations (CFR), Title 46, Shipping, Pts. 90–139, Revised as of October 1, 2020. NARA (2021)
Google Scholar
Download references
Acknowledgement
Yiqiao Wang, Hanfei Shi, and Liuzhouyu Shi, contributed equally to this work and should be considered co-first authors.
Author information
Authors and affiliations.
Department of Math, Macalester College, St.Paul, MN, 55105, USA
Yiqiao Wang
The Eberly College of Science Department of Mathematics, Pennsylvania State University, State College, 16802, USA
Faculty of Applied Science and Engineering, University of Toronto, 35 St. George Street, Toronto, ON, M5S 1A4, Canada
Liuzhouyu Shi
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Liuzhouyu Shi .
Editor information
Editors and affiliations.
King's Business School, King's College London, London, UK
Canh Thien Dang
Department of Financial Economics and Accounting, University of Murcia, Murcia, Spain
Javier Cifuentes-Faura
Department of Postal Management, Beijing University of Posts and Telecommunications, Beijing, China
Xiaolong Li
Appendix A:
Map of the USA and the selected regions.
Appendix B:
Appendix c:.
Rights and permissions
Reprints and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper.
Wang, Y., Shi, H., Shi, L. (2023). Crew Scheduling Problem: Integer Optimization Using Set-Covering Model. In: Dang, C.T., Cifuentes-Faura, J., Li, X. (eds) Proceedings of the 2nd International Conference on Business and Policy Studies. CONF-BPS 2023. Applied Economics and Policy Studies. Springer, Singapore. https://doi.org/10.1007/978-981-99-6441-3_1
Download citation
DOI : https://doi.org/10.1007/978-981-99-6441-3_1
Published : 08 October 2023
Publisher Name : Springer, Singapore
Print ISBN : 978-981-99-6440-6
Online ISBN : 978-981-99-6441-3
eBook Packages : Political Science and International Studies Political Science and International Studies (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Crew Assignment Problem: Examples
Let's solve the following problem with the Hungarian Method . We will use the same process as used in the last example.
Universal bus service operates seven days in a week. A trip from Delhi to Rajpura takes six hours by bus. A typical time table of the bus service in both directions is given below:
Use Horizontal Scrollbar to View Full Table.
The cost of providing this service by the transport company depends upon the time spent by the bus crew (driver and conductor) away from their places in addition to service times. There are five crews. There is a constraint that every crew should be provided with more than 4 hours of rest before the return trip and should not wait for more than 24 hours for the return trip. The company has residential facilities for the crew of Delhi as well as of Rajpura. Find which line of service be connected with which other line so as to reduce the waiting time to the minimum. If bus no. A is combined with bus no. 1, the crew after arriving at Rajpura at 12 noon starts at 5.30 next morning. Thus, the waiting time is 17.30 hours as shown in table 1. Some of the assignments are infeasible, e.g., bus no. 3 leaves Rajpura at 15.00 hours. Thus, the crew of bus no. A after reaching Rajpura at 12 noon are unable to take the minimum required rest of four hours, if they are asked to leave by bus no. 3. Hence, A3 is an infeasible assignment. Thus, its cost is M, a large positive number.
Similarly, if the crew are assumed to stay at Rajpura, then the waiting times of the crew in hours at Delhi are given in table 2 .
The composite layover time matrix (table 3) is obtained by selecting the smaller element from the two corresponding elements of table 1 & 2. The layover time marked with (*) represents that the crew is based at Delhi, otherwise based at Rajpura. On small screens, scroll horizontally to view full calculation
To simplify the problem, we multiply every element of the matrix with 2. Thus, the resulting matrix is:
Now solve the above problem by the Hungarian method. The optimal solution is 4.30 + 9.30 + 9 + 5 + 5.30 = 33.30 hours Share this article with your friends Operations Research Simplified Back Next Goal programming Linear programming Simplex Method Transportation Problem | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IMAGES
VIDEO
COMMENTS
The schedules must satisfy all the safety regulations and contractual rules. In contrast to the crew pairing problem, the crew assignment problem is separable by crew base and fleet type, and one of two general approaches is used: 1. Bidline schedules are constructed anonymously and the airline then announces them to the crew members. The crew ...
The airline crew scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into crew pairing and crew assignment because of its large size and the complex safety agreements and contractual rules. Several solution methodologies have been developed, but many objectives and constraints are treated approximately and research is ...
1. Introduction. For airline companies, the Crew Assignment Problem (CAP) is an economically significant issue in today's highly competitive market. Crew costs constitute one of the largest components of direct operating costs and are only dominated by fixed aircraft costs and fuel consumption costs.
Considering the large problem scale and high complexity, the airline scheduling problem is generally solved by sequentially dealing with a flight scheduling problem, fleet assignment problem, aircraft maintenance routing problem, and a crew scheduling problem (Cadarso et al., 2017).First, flight scheduling decides the flight routes to serve and the corresponding flight frequency.
A duty period (or duty) is a sequence of flight legs comprising a day of work for a crew. Alternative pairing definition: a crew pairing is a sequence of duties separated by rests. A crew schedule is a sequence of pairings. separated by time-off, satisfying numerous restrictions from regulatory agencies and collective bargaining agreements.
Abstract. The airline crew scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into crew pairing and crew assignment because ...
4. Solving the Crew Assignment Problem by standard integer linear programming techniques The first step in solving the Crew Assignment Problem is the construction of all valid flight services from the flight segments of the considered time period. 8 7 6 3 4 5 2 1 Fig. 1. Constraint graph associated to the example.
The Crew Assignment Problem is very difficult to solve because of the highly combinatorial nature of the. two sub-problems (a) and (b), the huge size of the corresponding formulations and the ...
In this paper, we present a comprehensive problem definition for the airline crew scheduling problem, and we review existing problem formulations and solution methodologies. ... KW - personalized crew assignment. KW - column generation. KW - data set. KW - mathematics subject classification. KW - 90Cxx. KW - 90-XX. U2 - 10.1007/s13676-015-0080-x.
Airline schedule planning problems are typically decomposed into smaller problems, which are solved in a sequential manner, due to the complexity of the overall problems. This results in suboptimal solutions as well as feasibility issues in the consecutive phases. In this study, we address the integrated fleet assignment and crew pairing problem (IFACPP) of a European Airline. The specific ...
For a 3 fleet, 226 flights problem: The best representative fare solution results in. gap with the optimal solution of $2,600/day. Using a shared fare scheme and integration approach, we found a solution with an $8/day gap. By simply modifying the basic spill model, significant gains can be achieved.
The crew pairing problem is defined on a set of crews, \(K\), and a flight network \(G=(N,A)\); where \(N\) is the set of nodes and \(A\) is set of arcs. A flight network is typically used to schedule domestic operations due to the large number of feasible duties [5, 16, 24, 30, 33], while a duty network is typically used to model international problems [4, 13, 25].
This problem called the Crew Assignment Problem ( CAP) is currently decomposed into two independent sub-problems which are modeled and solved sequentially: (a) the well-known Crew Pairing Problem followed by (b) the Working Schedules Construction Problem. In the first sub-problem, a set of legal minimum-cost pairings is constructed, covering ...
Abstract. This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. The problem consists of modifying, as necessary, personalized planned monthly assignments of airline crew members during day-to-day operations. It requires covering, at minimal cost, all flight segments from a ...
This paper forms the personalized cockpit crew scheduling problem as a set covering problem and is solved using column generation, and presents computational results for real data from a major US carrier. The airline crew scheduling problem has received extensive attention, particularly in the last 60 years. This problem is frequently divided into crew pairing and crew assignment because of ...
After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations. Meaning of Assignment Problem: An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total ...
The airline crew pairing problem aims to generate a set of minimal-cost crew pairings covering all flight legs. We define pairing as a series of connectable flight legs in the same fleet, usually lasting one to five days [3]. In this module, we define its period as a one-day duration. Hence, we clarify the crew scheduling problem as follows.
Problem 4. Job shop needs to assign 4 jobs to 4 workers. The cost of performing a job is a function of the skills of the workers. Table summarizes the cost of the assignments. Worker1 cannot do job3, and worker 3 cannot do job 4. Determine the optimal assignment using the Hungarian method. Job.
The crew planning problem is a key step in the urban rail transit (URT) planning process and has a critical impact on the operational efficiency of a URT line. In general, the crew planning ...
1. Introduction. For airline companies, the Crew Assignment Problem (CAP) is an economically significant issue in to-day s highly competitive market. Crew costs constitute one of the largest ...
104. 5.00 PM. 6.00 PM. Crews must have a minimum layover of 5 hours between flights. Obtain the pairing of flights that minimizes layover time away from home. For any given pairing, the crew will be based at the city that results in the smaller layover. For each pair also mention the city where crew should be based. Solution.
Thus, the waiting time is 17.30 hours as shown in table 1. Some of the assignments are infeasible, e.g., bus no. 3 leaves Rajpura at 15.00 hours. Thus, the crew of bus no. A after reaching Rajpura at 12 noon are unable to take the minimum required rest of four hours, if they are asked to leave by bus no. 3. Hence, A3 is an infeasible assignment.
assignment phase and right precedes crew rostering phase. A pairing is a sequence of connectable ... costs. Also, by the definition of pairing, the crew pairing problem is decomposed by fleet type. Hence ... If the crew pairing problem is treated as a multiobjective programming problem, then a bi-objective ...