Abstract
This paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. Since it is far from trivial to build such a system from the information provided in the existing literature, technical issues about the system and its implementation are covered in more detail. We also discuss several applications. In particular, we focus on a specific aircrew rostering application. The computational results contain an interesting comparison of results obtained with the approach in which crew scheduling is carried out before crew rostering, and an approach in which these two planning problems are solved in an integrated manner.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andersson, E., E. Housos, N. Kohl, and U. Wedelin. (1998). “Crew Pairing Optimization.” In G. Yu (ed.), Operations Research in the Airline Industry. Dordrecht: Kluwer Academic.
Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance. (1998). “Branch-and-Price: Column Generation for Solving Huge Integer Programs.” Operations Research 46, 316-329.
Bixby, R., J. Gregory, I. Lustig, R. Marsten, and D. Shanno. (1992). “Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods.” Operations Research 40, 885-897.
Bodin, L., B. Golden, A. Assad, and M. Ball. (1983). “Routing and Scheduling of Vehicles and Crews: The State of the Art.” Computers and Operations Research 10(2), 63-211.
Caprara, A., M. Monaci, and P. Toth. (2001). “A Global Method for Crew Planning in Railway Applications.” In S. Voß and J.R. Daduna (eds.), Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 505. Berlin: Springer.
Day, P.R. and D.M. Ryan. (1997). “Flight Attendant Rostering for Short-Haul Airline Operations.” Operations Research 45, 649-661.
Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon, and F. Soumis. (1997). “Crew Pairing at Air France.” European Journal Operational Research 97(2), 245-259.
Desaulniers, G., J. Desrosiers, M. Gamache, and F. Soumis. (1998a). “Crew Scheduling in Air Transportation.” In T.G. Crainic and G. Laporte (eds.), Fleet Management and Logistics. Boston: Kluwer Academic.
Desaulniers, G., J. Desrosiers, I. loachim, M.M. Solomon, F. Soumis, and D. Villeneuve. (1998b). “A Uni-fied Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems.” In T.G. Crainic and G. Laporte (eds.), Fleet Management and Logistics. Norwell: Kluwer.
Desaulniers, G., J. Desrosiers, and M.M. Solomon. (2002). “Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems.” In C.C. Ribeiro and P. Hansen (eds.), Essays and Surveys in Metaheuristics. Boston: Kluwer.
Desrochers, M., J. Gilbert, M. Sauve, and F. Soumis. (1992). “Subproblem Modeling in a Column Generation Approach to the Urban Crew Scheduling Problem.” In M. Desrochers and J.M. Rousseau (eds.), Computer-Aided Transit Scheduling: Proceedings of the 5th International Workshop. Berlin: Springer.
Desrosiers, J., Y. Dumas, M.M. Solomon, and F. Soumis. (1995). “Time Constrained Routing and Scheduling”. In M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.), Handbooks in Operations Research and Management Science, Vol. 8: Network Routing. Amsterdam: North-Holland.
Desrosiers, J., A. Lasry, D. Mclnnis, M.M. Solomon, and F. Soumis. (2000). “Air Transat Uses ALTITUDE to Manage Its Aircraft Routing, Crew Pairing, and Work Assignment.” Interfaces 30(2), 41-53.
Desrosiers, J., M.M. Solomon, D. Villeneuve, and H. Ben Amor. (2001). “Stabilized Column Generation for Crew Scheduling Problems.” Presentation at TRISTAN IV Conference, Azores Islands.
Du Merle, O., D. Villeneuve, J. Desrosiers, and P. Hansen. (1999). “Stabilized Column Generation.” Discrete Mathematics 194, 229-237.
Fischetti, M. and L.G. Kroon. (2000). “Solving Large-Scale Crew Scheduling Problems at the Dutch Railways.” In S. Voß and J.R. Daduna (eds.), Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 505. Berlin: Springer.
Freling, R. (1997). “Models and Techniques for Integrating Vehicle and Crew Scheduling.” Ph.D. thesis, Tinbergen Institute, Erasmus University, Rotterdam.
Freling, R., R.M. Lentink, and M.A. Odijk. (2001). “Scheduling Train Crews: A Case Study for the Dutch Railways.” In S. Voß and J.R. Daduna (eds.), Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems, Vol. 505. Berlin: Springer.
Gamache, M. and F. Soumis. (1998). “A Method for Optimally Solving the Rostering Problem.” In G. Yu (ed.), Operations Research in the Airline Industry. Dordrecht: Kluwer Academic.
Gamache, M., F. Soumis, G. Marquis, and J. Desrosiers. (1999). “A Column Generation Approach for Large-Scale Aircrew Rostering Problems.” Operations Research 47, 247-263.
Gamache, M., F. Soumis, D. Villeneuve, J. Desrosiers, and E. Gélinas (1998). “The Preferential Bidding System at Air Canada.” Transportation Science 32, 246-255.
Kohl, N. (1995). “Exact Methods for Time Constrained Routing and Scheduling Problems.” Ph.D. thesis, Technical University of Denmark.
Nicoletti, B. (1975). “Automatic Crew Rostering.” Transportation Science 9, 33-42.
Odoni, A.R. and J.M. Rousseau. (1994). “Models in Urban and Air Transportation.” In S.M. Pollock, M.H. Rothkopf, and A. Barnett (eds.), Handbooks in Operations Research and Management Science, Vol. 6: Operations Research and the Public Sector. Amsterdam: North-Holland.
Ryan, D.M. (1992). “The Solution ofMassive Generalized Set Partitioning Problems in Aircrew Rostering.” Operations Research 43, 459-467.
Ryan, D.M. (2000). “Optimization Earns Its Wings.” OR/MS Today 27(2), 26-30.
Ryan, D.M. and Foster. (1981). “An Integer Programming Approach to Scheduling.” In A. Wren (ed.), Computer-Aided Scheduling of Public Transport, Lecture Notes in Economics and Mathematical Systems. Amsterdam: North Holland.
Sol, M. (1994). “Column Generation Techniques for Pickup and Delivery Problems.” Ph.D. thesis, Eindhoven University of Technology.
Vance, P.H., A. Atamtiirk, C. Barnhart, E. Gelman, E.L. Johnson, A. Krishna, D. Mahidhara, G.L. Nemhauser, and R. Rebello. (1997). “A Heuristic Branch-and-Price Approach for the Airline Crew Pairing Problem.” Technical Report, Georgia Institute of Technology.
Warburton, A. (1987). “Approximation of Pareto Optima in Multiobjective, Shortest Path Problems.” Operations Research 35, 70-79.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Freling, R., Lentink, R.M. & Wagelmans, A.P. A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm. Annals of Operations Research 127, 203–222 (2004). https://doi.org/10.1023/B:ANOR.0000019090.39650.32
Issue Date:
DOI: https://doi.org/10.1023/B:ANOR.0000019090.39650.32