zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A hybrid scatter search heuristic for personalized crew rostering in the airline industry. (English) Zbl 1188.90157
Summary: The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.

90B90Case-oriented studies in OR
90C59Approximation methods and heuristics
Full Text: DOI
[1] Ahuja, R.; Egun, O.; Orlin, J.; Punnen, A.: A survey of very large-scale neighbourhood search techniques, Discrete applied mathematics 123, 75-102 (2002) · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[2] Aickelin, U.; Dowsland, K. A.: Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem, Journal of scheduling 3, 139-153 (2000) · Zbl 0965.90019 · doi:10.1002/(SICI)1099-1425(200005/06)3:3<139::AID-JOS41>3.0.CO;2-2
[3] Beasley, J.; Chu, P.: A genetic algorithm for the set covering problem, European journal of operational research 94, 392-404 (1996) · Zbl 0953.90565 · doi:10.1016/0377-2217(95)00159-X
[4] Buhr, J., 1978. Four methods for monthly crew assignment -- A comparison of efficiency. In: 1978 AGIFORS Symposium Proceedings 18, 403 -- 430.
[5] Burke, E. K.; Cowling, P.; De Causmacker, P.; Berghe, G. Vanden: A memetic approach to the nurse rostering problem, Applied intelligence 3, 199-214 (2001) · Zbl 0993.90506 · doi:10.1023/A:1011291030731
[6] Byrne, J.: A preferential bidding system for technical aircrew, AGIFORS symposium proceeding 28, 87-99 (1988)
[7] Campbell, K. W.; Durfee, R. B.; Hines, G. S.: Fedex generates bid lines using simulated annealing, Interfaces 27, 1-16 (1997)
[8] Cappanera, P.; Gallo, G.: A multicommodity flow approach to the crew rostering problem, Operations research 52, 583-596 (2004) · Zbl 1165.90343 · doi:10.1287/opre.1040.0110
[9] Caprara, A.; Toth, P.; Vigo, D.: Modeling and solving the crew rostering problem, Operations research 46, 820-830 (1998) · Zbl 0987.90035
[10] Caprara, A.; Monaci, M.; Toth, P.: Models and algorithms for a staff scheduling problem, Mathematical programming -- series B 98, 445-476 (2003) · Zbl 1160.90471 · doi:10.1007/s10107-003-0413-7
[11] Christou, I. T.; Zakarian, A.; Liu, J.; Carter, H.: A two-phase genetic algorithm for large-scale bidline-generation problems at delta airlines, Interfaces 29, 51-65 (1999)
[12] Desrochers, M.; Soumis, F.: A column generation approach to the urban transit crew scheduling problem, Transportation science 23, 1-13 (1989) · Zbl 0668.90043 · doi:10.1287/trsc.23.1.1
[13] Desrosiers, J.; Dumas, Y.; Solomon, M.; Soumis, F.: Time constrained routing and scheduling, Handbooks in operations research and management science, network science 8, 35-139 (1995) · Zbl 0861.90052
[14] Dias, T. M.; Ferber, D. F.; De Souza, C. C.; Moura, A. V.: Constructing nurse schedules at large hospitals, International transactions in operational research 10, 245-265 (2003) · Zbl 1087.90511 · doi:10.1111/1475-3995.00406
[15] El Moudani, W.; Cosenza, C. A. N.; De Coligny, M.; Mora-Camino, F.: A bi-criterion approach for the airlines crew rostering problem, Lecture notes in computer science 1993, 486-500 (2001)
[16] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Sier, D.: Staff scheduling and rostering: A review of applications, methods and models, European journal of operational research 153, 3-27 (2004) · Zbl 1053.90034 · doi:10.1016/S0377-2217(03)00095-X
[17] Fahle, T.; Junker, U.; Karisch, S. E.; Kohl, N.; Sellmann, M.; Vaaben, B.: Constraint programming based column generation for crew assignment, Journal of heuristics 8, 59-81 (2002) · Zbl 1073.90542 · doi:10.1023/A:1013613701606
[18] Freling, R., Lentink, R., Wagelmans, A., 2001. A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. In: Voss, S., Daduna, J.R., (Eds.), Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, vol. 505, pp. 73 -- 90. · Zbl 1087.90036
[19] Gamache, M.; Soumis, F.: A method for optimally solving the rostering problem, Operations research in the airline industry, 24-157 (1998)
[20] Gamache, M.; Soumis, F.; Villeneuve, D.; Desrosiers, J.; Gélinas, E.: The preferential bidding system at air Canada, Transportation science 32, 246-255 (1998) · Zbl 1004.90518 · doi:10.1287/trsc.32.3.246
[21] Gamache, M.; Soumis, F.; Marquis, G.; Desrosiers, J.: A column generation approach for large-scale aircrew rostering problems, Operations research 47, 247-263 (1999) · Zbl 1041.90513 · doi:10.1287/opre.47.2.247
[22] Gamache, M.; Hertz, A.; Ouellet, J. O.: A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding, Computers and operations research 34, 2384-2395 (2007) · Zbl 1144.90498 · doi:10.1016/j.cor.2005.09.010
[23] Giaferri, C.; Hamon, J. P.; Lengline, J. G.: Automatic monthly assignment of medium-haul cabin crew, AGIFORS symposium proceeding 22, 69-95 (1982)
[24] Glover, F.: A template for scatter search and path relinking, Lecture notes in computer science 1363, 13-54 (1998)
[25] Glover, F.; Laguna, M.: Fundamentals of scatter search and path relinking, Control and cybernetics 3, 653-684 (2000) · Zbl 0983.90077
[26] Hansen, P.; Mladenović, N.: Variable neighbourhood search: principles and applications, European journal of operational research 130, 449-467 (2001) · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[27] Hoffman, K. L.; Padberg, M.: Solving airline crew scheduling problems by branch-and-cut, Management science 39, 657-682 (1993) · Zbl 0783.90051 · doi:10.1287/mnsc.39.6.657
[28] Ioachim, I.; Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Villeneuve, D.: A request clustering algorithm for door-to-door handicapped transportation, Transportation science 29, 63-79 (1995) · Zbl 0826.90045 · doi:10.1287/trsc.29.1.63
[29] Irnich, S., Desaulniers, G., 2004. Shortest Path Problems with Resource Constraints. Les Cahiers du Gérad, G-2004-11.
[30] Jarrah, A. I. Z.; Diamond, J. T.: The problem of generating crew bidlines, Interfaces 27, 49-64 (1997)
[31] Kapsalis, A.; Rayward-Smith, V. J.; Smith, G. D.: Solving the graphical Steiner tree problem using genetic algorithms, Journal of the operational research society 44, 397-406 (1993) · Zbl 0774.90083
[32] Kerati, S., El Moudani, W., de Coligny, M., Mora-Camino, F., 2002. A Heuristic Genetic Algorithm for the Airline Crew Scheduling Problem. EU/ME, the European Chapter on Meta-Heuristics, EURO working group.
[33] Kohl, N., Karisch, S.E., 2000. Integrating operations research and constraint programming techniques in crew scheduling. In: Proceedings of the 40th Annual AGIFORS Symposium, Istanbul, Turkey.
[34] Kohl, N.; Karisch, S. E.: Airline crew rostering: problem types, modeling and optimization, Annals of operations research 127, 223-257 (2004) · Zbl 1087.90031 · doi:10.1023/B:ANOR.0000019091.54417.ca
[35] Kolisch, R.; Hartmann, H.: Experimental investigation of heuristics for resource-constrained project scheduling: an update, European journal of operational research 174, 23-37 (2006) · Zbl 1116.90047 · doi:10.1016/j.ejor.2005.01.065
[36] Kuhn, H.: The hungarian method for the assignment problem, Naval research logistics 2, 83-97 (1955) · Zbl 0143.41905
[37] Lasry, A. D.; Mcinnis, D.; Soumis, F.; Desrosiers, J.; Solomon, M. M.: Air transat uses ALTITUDE to manage its aircraft routing, crew pairing and work assignment, Interfaces 30, 41-53 (2000)
[38] Maenhout, B., Vanhoucke, M., 2008. Crew Rostering at Brussels Airlines, Working paper 08/525, Ghent University.
[39] Makri, A.; Klabjan, D.: A new pricing scheme for airline crew scheduling, INFORMS journal on computing 16, 56-67 (2004) · Zbl 1239.90064
[40] Marti, R.; Laguna, M.; Glover, F.: Principles of scatter search, European journal of operational research 169, 359-372 (2006) · Zbl 1079.90178 · doi:10.1016/j.ejor.2004.08.004
[41] Medard, C.P., Sawhney, N., 2004, Airline crew scheduling: From planning to operations. Carmen Systems AB, Göteborg, Sweden, Carmen Research and Technology Report CRTR-0406. · Zbl 1136.90356
[42] Moore, R.; Evans, J.; Noo, H.: Computerized tailored blocking, AGIFORS symposium Proceedings 18, 343-361 (1978)
[43] Nicoletti, B.: Automatic crew rostering, Transportation science 9, 33-42 (1975)
[44] Reeves, C. R.: A genetic algorithm for flowshop sequencing, Computers & operations research 22, 5-13 (1995) · Zbl 0815.90097 · doi:10.1016/0305-0548(93)E0014-K
[45] Ryan, D. M.: The solution of massive generalized set partitioning problems in air crew rostering, Journal of the operational research society 43, 459-467 (1992)
[46] Sarra, D.: The automatic assignment model, AGIFORS symposium Proceedings 28, 23-37 (1988)
[47] Sellmann, M.; Zevoudakes, K.; Stamatopoulos, P.; Fahle, T.: Crew assignment via constraint programming: integrating column generation via heuristic tree search, Annals of operations research 115, 207-225 (2002) · Zbl 1013.90091 · doi:10.1023/A:1021105422248
[48] Thiel, M.P., 2004. Team-oriented airline crew rostering for cockpit personnel. In: Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport (CASPT 2004), pp. 1 -- 26. · Zbl 1168.90380
[49] Tingley, G. A.: Still another solution method for the monthly aircrew assignment problem, AGIFORS symposium Proceedings 19, 143-203 (1979)
[50] Vance, P. H.; Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.: Airline crew scheduling: A new formulation and decomposition algorithm, Operations research 45, 188-200 (1997) · Zbl 0891.90087 · doi:10.1287/opre.45.2.188
[51] Den Akker, M. Van; Hoogeveen, H.; Van De Velde, S.: Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem, Informs journal on computing 14, 37-51 (2002) · Zbl 1238.90096
[52] Vanderbeck, F.; Wolsey, L. A.: An exact algorithm for IP column generation, Operations research letters 19, 151-159 (1996) · Zbl 0873.90074 · doi:10.1016/0167-6377(96)00033-8
[53] Yu, G.: Operations research in airline industry, (1998)