Free Access

A Column Generation Approach to the Urban Transit Crew Scheduling Problem

Martin Desrochers
Martin Desrochers
GERAD, École des H.E.C., 5255, avenue Decelles, Montréal, Québec, Canada, H3T 1V6
Search for more papers by this author
,
François Soumis
François Soumis
GERAD, École Polytechnique, P.O. Box 6129, Stn. A, Montréal, Québec, Canada, H3C 3A7
Search for more papers by this author

Martin Desrochers

GERAD, École des H.E.C., 5255, avenue Decelles, Montréal, Québec, Canada, H3T 1V6

Search for more papers by this author

François Soumis

GERAD, École Polytechnique, P.O. Box 6129, Stn. A, Montréal, Québec, Canada, H3C 3A7

Search for more papers by this author

Published Online:1 Feb 1989https://doi.org/10.1287/trsc.23.1.1

This article is part of the Transportation Science Classics collection, celebrating the 50th anniversary of the journal.

Cited by
- A branch-and-price approach for computing the minimum number of pairwise comparisons in multicriteria selection based on convex cones
  Omega, Vol. 140
- OR-Tools Based Driver Scheduler for Cost Optimization With Efficient Driver Usage
- Reinforcement learning for urban public transport driver scheduling
  16 March 2026 | Modeling and Analysis of Information Systems, Vol. 33, No. 1
- Lexicographic column generation with a tree search pricing algorithm
  20 February 2026 | Mathematical Methods of Operations Research, Vol. 19
- A hybrid column generation-based heuristic for solving the parallel machine scheduling problem with sequence-dependent set-up times
  11 December 2025 | Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences, Vol. 383, No. 2310
- Modeling A Valid Work Schedule Using Integer Optimization Over A Non-Convex Set
  Journal of Physics: Conference Series, Vol. 3145, No. 1
- Safety-oriented multi-depot integrated vehicle and crew scheduling problem
  Transportation Research Part E: Logistics and Transportation Review, Vol. 203
- Extraboard transit operator scheduling considering driver absenteeism
  6 October 2025 | Transportmetrica A: Transport Science, Vol. 1266
- Optimizing Bus Driver Scheduling: A Set Covering Approach for Reducing Transportation Costs
  25 August 2025 | Applied System Innovation, Vol. 8, No. 5
- Set-cover master problem formulations for maximum flight coverage in branch & price solution algorithms for optimal aircrew rostering
  18 June 2025 | Operational Research, Vol. 25, No. 3
- Cross-line crew scheduling optimization in urban rail transit systems
  Computers & Industrial Engineering, Vol. 201
- Optimal allocation and route design for station-based drone inspection of large-scale facilities
  Omega, Vol. 130
- Assessing the Impact of Route Interlining via Bus Schedule Optimization
  Procedia Computer Science, Vol. 272
- CMSA based on set covering models for packing and routing problems
  8 October 2024 | Annals of Operations Research, Vol. 343, No. 1
- Raw Material Purchasing Optimization Using Column Generation
  22 May 2024 | Applied Sciences, Vol. 14, No. 11
- Electric bus scheduling with the self-adaptive charging strategy based on a course selection idea
  3 February 2023 | Transportmetrica A: Transport Science, Vol. 20, No. 2
- A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor Problems
  Shanshan Wang,
  Erick Delage,
  3 January 2024 | INFORMS Journal on Computing, Vol. 36, No. 3
- On the role of time‐of‐use electricity price in charge scheduling for electric bus fleets
  Computer-Aided Civil and Infrastructure Engineering, Vol. 39, No. 8
- Set Covering, Packing, and Partitioning Problems
  3 December 2024
- Replacing Hard Mathematical Models with Set Covering Formulations
  23 April 2024
- Exploring the Optimal Camera Placement Problem and Its Relationship with the Set Covering Problem
  28 August 2024
- LSTM‐based deep learning framework for adaptive identifying eco‐driving on intelligent vehicle multivariate time‐series data
  10 November 2023 | IET Intelligent Transport Systems, Vol. 18, No. 1
- The problem of assigning bus drivers to trips in a Spanish public transport company
  10 August 2022 | Engineering Optimization, Vol. 55, No. 9
- A New Family of Route Formulations for Split Delivery Vehicle Routing Problems
  Isaac Balster,
  Teobaldo Bulhões,
  Pedro Munari,
  Artur Alves Pessoa,
  Ruslan Sadykov
  14 August 2023 | Transportation Science, Vol. 57, No. 5
- Metro crew planning with heterogeneous duty paths and period-cycle pattern considerations
  Computers & Industrial Engineering, Vol. 182
- Optimize railway crew scheduling by using modified bacterial foraging algorithm
  Computers & Industrial Engineering, Vol. 180
- A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem
  Computers & Operations Research, Vol. 154
- Public transport for smart cities: Recent innovations and future challenges
  European Journal of Operational Research, Vol. 306, No. 3
- An ADMM-based dual decomposition mechanism for integrating crew scheduling and rostering in an urban rail transit line
  Transportation Research Part C: Emerging Technologies, Vol. 149
- Construct, Merge, Solve and Adapt Applied to a Bus Driver Scheduling Problem with Complex Break Constraints
  11 March 2023
- A column generation approach for the driver scheduling problem with staff cars
  27 September 2021 | Public Transport, Vol. 14, No. 3
- A Lagrangian relaxation approach based on a time-space-state network for railway crew scheduling
  Computers & Industrial Engineering, Vol. 172
- Electric bus planning & scheduling: A review of related problems and methodologies
  European Journal of Operational Research, Vol. 301, No. 2
- A Heuristic Algorithm Based on Travel Demand for Transit Network Design
  5 September 2022 | Sustainability, Vol. 14, No. 17
- Column generation-based optimum crew scheduling incorporating network representation for urban rail transit systems
  Computers & Industrial Engineering, Vol. 169
- Distributed Integral Column Generation for Set Partitioning Problems
  19 April 2022 | Operations Research Forum, Vol. 3, No. 2
- Crew Assignment with Duty Time Limits for Transport Services: Tight Multicommodity Models
  Anantaram Balakrishnan,
  Prakash Mirchandani,
  Sifeng Lin
  13 December 2021 | Operations Research, Vol. 70, No. 2
- Collaborative Optimization of Vehicle and Crew Scheduling for a Mixed Fleet with Electric and Conventional Buses
  19 March 2022 | Sustainability, Vol. 14, No. 6
- A column generation approach for the integrated crew re-planning problem
  Omega, Vol. 107
- Tactical Planning of Public Transport Services: Vehicle and Crew Schedules
  21 January 2023
- Solution of Multi-Crew Depots Railway Crew Scheduling Problems: The Chinese High-Speed Railway Case
  3 January 2022 | Sustainability, Vol. 14, No. 1
- Branch-and-price for a class of nonconvex mixed-integer nonlinear programs
  7 May 2021 | Journal of Global Optimization, Vol. 81, No. 4
- Optimal electric bus fleet scheduling considering battery degradation and non-linear charging profile
  Transportation Research Part E: Logistics and Transportation Review, Vol. 154
- Solution approaches for integrated vehicle and crew scheduling with electric buses
  Computers & Operations Research, Vol. 132
- A review of transport market modeling using game-theoretic principles
  European Journal of Operational Research, Vol. 291, No. 3
- An Efficient Hybrid Algorithm for Energy Expenditure Estimation for Electric Vehicles in Urban Service Enterprises
  5 April 2021 | Energies, Vol. 14, No. 7
- Ship-unloading scheduling optimization for a steel plant
  Information Sciences, Vol. 544
- Machine learning in airline crew pairing to construct initial clusters for dynamic constraint aggregation
  EURO Journal on Transportation and Logistics, Vol. 9, No. 4
- References
  19 September 2020
- Parallel Machine Production and Transportation Operations’ Scheduling with Tight Time Windows
  Complexity, Vol. 2020
- Railway crew scheduling: Models, methods and applications
  European Journal of Operational Research, Vol. 283, No. 2
- References
  17 April 2020
- Bus driver scheduling enhancement: a derandomizing approach for uncertain bus trip times
  26 February 2020 | Transportmetrica B: Transport Dynamics, Vol. 8, No. 1
- Improving set partitioning problem solutions by zooming around an improving direction
  3 May 2018 | Annals of Operations Research, Vol. 284, No. 2
- Energy-Constrained Multi-UAV Coverage Path Planning for an Aerial Imagery Mission Using Column Generation
  13 March 2019 | Journal of Intelligent & Robotic Systems, Vol. 97, No. 1
- Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile
  Transportation Research Part B: Methodological, Vol. 128
- Electric Vehicle Travel Planning with Lazy Evaluation of Recharging Times
- An integer programming approach to fisheries observer deployment
  Transportation Research Part E: Logistics and Transportation Review, Vol. 127
- Optimizing Bus Bridging Routing in Response to Disruptions of Urban Transit Rail
- A matheuristic for the driver scheduling problem with staff cars
  European Journal of Operational Research, Vol. 275, No. 1
- Bus and driver scheduling with mealtime windows for a single public bus route
  Transportation Research Part C: Emerging Technologies, Vol. 101
- Location Assignment of Capacitated Services in Smart Cities
  13 January 2019
- Integrated Route, Charging and Activity Planning for Whole Day Mobility with Electric Vehicles
  30 December 2018
- The Mean-Value-at-Risk Median Problem on a Network with Random Demand Weights
  8 October 2019
- Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates
  Computers & Industrial Engineering, Vol. 127
- Tasks of operative planning for transport management systems
- A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm
  European Journal of Operational Research, Vol. 271, No. 3
- Benefits of Multi-Destination Travel Planning for Electric Vehicles
- A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy
  2 May 2018 | TOP, Vol. 26, No. 3
- Practical Train Crew Scheduling Problems Using Parallel Tabu Search
- Coverage Path Planning for a UAS Imagery Mission using Column Generation with a Turn Penalty
- An integrated algorithm for shift scheduling problems for local public transport companies
  Omega, Vol. 75
- The Algorithm for Constrained Shortest Path Problem Based on Incremental Lagrangian Dual Solution
  15 August 2018
- Practical train crew scheduling using improved tabu search
- Simultaneous delivery time and aperture shape optimization for the volumetric-modulated arc therapy (VMAT) treatment planning problem
  14 June 2017 | Physics in Medicine & Biology, Vol. 62, No. 14
- Solving Practical Railway Crew Scheduling Problems with Attendance Rates
  5 April 2017 | Business & Information Systems Engineering, Vol. 59, No. 3
- A Novel Model and Decomposition Approach for the Integrated Airline Fleet Assignment, Aircraft Routing, and Crew Pairing Problem
  Shengzhi Shao,
  Hanif D. Sherali,
  Mohamed Haouari
  17 November 2015 | Transportation Science, Vol. 51, No. 1
- A new cross decomposition method for stochastic mixed-integer linear programming
  European Journal of Operational Research, Vol. 256, No. 2
- A Bus Crew Scheduling Problem with Eligibility Constraints and Time Limitations
  Transportation Research Procedia, Vol. 22
- Stochastic traffic assignment of mixed electric vehicle and gasoline vehicle flow with path distance constraints
  Transportation Research Procedia, Vol. 21
- A column generation algorithm for the bus driver scheduling problem
  19 October 2016 | Journal of Advanced Transportation, Vol. 50, No. 8
- A Branch-and-Price Algorithm for Solving the Hamiltonian p-Median Problem
  Ahmed M. Marzouk,
  Erick Moreno-Centeno,
  Halit Üster
  19 September 2016 | INFORMS Journal on Computing, Vol. 28, No. 4
- Exploiting symmetry in unit commitment solutions for a large-scale electricity market
  Electric Power Systems Research, Vol. 140
- A branch and price algorithm for the pharmacy duty scheduling problem
  Computers & Operations Research, Vol. 72
- The Shortest Path Problems in Battery-Electric Vehicle Dispatching with Battery Renewal
  28 June 2016 | Sustainability, Vol. 8, No. 7
- Service interactions modeling for improved management of public transport systems
  12 February 2016 | SIMULATION, Vol. 92, No. 3
- An Binary Black Hole Algorithm to Solve Set Covering Problem
  14 July 2016
- Solving the Set Covering Problem with a Binary Black Hole Inspired Algorithm
  21 July 2016
- Using Constraint Programming for the Urban Transit Crew Rescheduling Problem
  23 August 2016
- ASP, The Art and Science of Practice: Academia-Industry Interfacing in Operations Research in Montréal
  Laure Cabantous,
  Gilbert Laporte
  15 December 2015 | Interfaces, Vol. 45, No. 6
- A Heuristic Polynomial Time Algorithm for Crew Scheduling Problem
  Journal of the Korea Society of Computer and Information, Vol. 20, No. 11
- Integrated timetabling and vehicle scheduling with balanced departure times
  22 April 2015 | OR Spectrum, Vol. 37, No. 4
- O uso da metaheurística Guided Local Search para resolver o problema de escala de motoristas de ônibus urbano
  28 August 2015 | Transportes, Vol. 23, No. 2
- Applied analysis for improving rail-network operations
  Journal of Rail Transport Planning & Management, Vol. 5, No. 2
- Minimum cost path problem for Plug-in Hybrid Electric Vehicles
  Transportation Research Part E: Logistics and Transportation Review, Vol. 80
- Planning, operation, and control of bus transport systems: A literature review
  Transportation Research Part B: Methodological, Vol. 77
- Constrained shortest path problems: state-of-the-art and recent advances
- A Binary Cat Swarm Optimization Algorithm for the Non-Unicost Set Covering Problem
  Mathematical Problems in Engineering, Vol. 2015
- A Column Generation Based Hyper-Heuristic to the Bus Driver Scheduling Problem
  Discrete Dynamics in Nature and Society, Vol. 2015
- A study of different metaheuristics to solve the urban transit crew scheduling problem
  Journal of Transport Literature, Vol. 8, No. 4
- Aircraft maintenance, routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base
  Computers & Industrial Engineering, Vol. 75
- General Bibliography
  8 August 2014
- Column Generation in Integer Linear Programming
  8 August 2014
- A note on extending the generic crew scheduling model of Beasley and Cao by deadheads and layovers
  21 December 2017 | Journal of the Operational Research Society, Vol. 65, No. 5
- Symmetry issues in mixed integer programming based Unit Commitment
  International Journal of Electrical Power & Energy Systems, Vol. 54
- A survey of resource constrained shortest path problems: Exact solution approaches
  6 June 2013 | Networks, Vol. 62, No. 3
- An efficient solution approach for real-world driver scheduling problems in urban bus transportation
  26 October 2012 | Central European Journal of Operations Research, Vol. 21, No. S1
- Column Generation in Integer Linear Programming
  21 January 2013
- Management of Bus Driver Duties Using Data Mining
- A prototype column generation strategy for the multiple container loading problem
  European Journal of Operational Research, Vol. 223, No. 1
- Constrained network-based column generation for the multi-activity shift scheduling problem
  International Journal of Production Economics, Vol. 140, No. 1
- Multiple depot vehicle and crew scheduling with time windows for scheduled trips
  29 December 2011 | Public Transport, Vol. 3, No. 3
- Location Theory and Distribution Management
  4 October 2011
- Research on the Scheduling Problem of Urban Bus Crew Based on Impartiality
  Procedia - Social and Behavioral Sciences, Vol. 43
- Modeling and Algorithms of the Crew Rostering Problem with Given Cycle on High‐Speed Railway Lines
  9 October 2012 | Mathematical Problems in Engineering, Vol. 2012, No. 1
- A Model for Bus Crew Scheduling Problem with Multiple Duty Types
  24 September 2012 | Discrete Dynamics in Nature and Society, Vol. 2012, No. 1
- Ant-Line: A Line-Oriented ACO Algorithm for the Set Covering Problem
- Case studies of successful train crew scheduling optimisation
  10 December 2010 | Journal of Scheduling, Vol. 14, No. 5
- Branch and price for the vehicle routing problem with discrete split deliveries and time windows
  European Journal of Operational Research, Vol. 213, No. 3
- A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution
  22 July 2010 | Journal of Heuristics, Vol. 17, No. 4
- SLA-aware placement of multi-virtual machine elastic services in compute clouds
- Column generation with dual inequalities for railway crew scheduling problems
  11 May 2011 | Public Transport, Vol. 3, No. 1
- Application of Column Generation for Railway Crew Scheduling Problems with Practical Constraints
  IEEJ Transactions on Electronics, Information and Systems, Vol. 131, No. 6
- Resolução do problema de alocação de berços através de uma técnica de geração de colunas
  Pesquisa Operacional, Vol. 30, No. 3
- A hybrid scatter search heuristic for personalized crew rostering in the airline industry
  European Journal of Operational Research, Vol. 206, No. 1
- A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots
  Ingmar Steinzen,
  Vitali Gintner,
  Leena Suhl,
  Natalia Kliewer,
  1 January 2010 | Transportation Science, Vol. 44, No. 3
- Multi-phase dynamic constraint aggregation for set partitioning type problems
  14 November 2008 | Mathematical Programming, Vol. 123, No. 2
- Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows
  Guy Desaulniers,
  23 September 2009 | Operations Research, Vol. 58, No. 1
- Reformulation and Decomposition of Integer Programs
  6 November 2009
- Symmetry in Integer Linear Programming
  6 November 2009
- Improvement of Column Generation Method for Railway Crew Scheduling Problems
  IEEJ Transactions on Electronics, Information and Systems, Vol. 130, No. 2
- Genetic Algorithm–Based Column Generation Approach to Passenger Rail Crew Scheduling
  1 January 2010 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2159, No. 1
- Algorithm for Crew-Scheduling Problem with Bin-Packing Features
  1 January 2010 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2197, No. 1
- The impact of incorporating nurse-specific characteristics in a cyclical scheduling approach
  21 December 2017 | Journal of the Operational Research Society, Vol. 60, No. 12
- A Column Generation Model for Truck Routing in the Chilean Forest Industry
  18 January 2017 | INFOR: Information Systems and Operational Research, Vol. 47, No. 3
- Models and algorithms for solving combined vehicle and crew scheduling problems with rest constraints : an application to road feeder service planning in air cargo transportation
  21 November 2007 | OR Spectrum, Vol. 31, No. 2
- A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions
- Application of integer programming for solving crew scheduling problem in Taipei Rapid Transit Corporation
- Column generation approaches to large driver scheduling problems
- Multi-period vehicle routing and crew scheduling with outsourcing options
  International Journal of Production Economics, Vol. 113, No. 2
- Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem
  Computers & Operations Research, Vol. 35, No. 5
- Bi-dynamic constraint aggregation and subproblem reduction
  Computers & Operations Research, Vol. 35, No. 5
- Circulation of railway rolling stock: a branch-and-price approach
  Computers & Operations Research, Vol. 35, No. 2
- Operations Management in Transportation Networks
  27 January 2010
- Set Covering, Packing and Partitioning Problems
- A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit
- A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling
- Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
  European Journal of Operational Research, Vol. 183, No. 2
- Effective search space control for large and/or complex driver scheduling problems
  10 July 2007 | Annals of Operations Research, Vol. 155, No. 1
- A column generation approach for the maximal covering location problem
  12 June 2007 | International Transactions in Operational Research, Vol. 14, No. 4
- An integrated model and a decomposition-based approach for concurrent layout and material handling system design
  Computers & Industrial Engineering, Vol. 52, No. 4
- Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation
  Computers & Operations Research, Vol. 34, No. 4
- Generating, scheduling and rostering of shift crew-duties: Applications at the Hong Kong International Airport
  European Journal of Operational Research, Vol. 177, No. 3
- Location-Routing Problems with Distance Constraints
  Rosemary T. Berger,
  Collette R. Coullard,
  Mark S. Daskin,
  1 February 2007 | Transportation Science, Vol. 41, No. 1
- Chapter 2 Public Transit
- Chapter 5 Dynamic Models for Freight Transportation
- A branch-and-price approach for operational aircraft maintenance routing
  European Journal of Operational Research, Vol. 175, No. 3
- Contribution to the design of the Athletes Bus Network during the Athens 2004 Olympic Games
  Transportation Research Part A: Policy and Practice, Vol. 40, No. 9
- Solving a class of stochastic mixed-integer programs with branch and price
  25 April 2006 | Mathematical Programming, Vol. 108, No. 2-3
- Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post
  European Journal of Operational Research, Vol. 173, No. 1
- A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases
  European Journal of Operational Research, Vol. 171, No. 3
- Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
  European Journal of Operational Research, Vol. 170, No. 2
- Selected Topics in Column Generation
  Marco E. Lübbecke,
  Jacques Desrosiers,
  1 December 2005 | Operations Research, Vol. 53, No. 6
- Dynamic Aggregation of Set-Partitioning Constraints in Column Generation
  Issmail Elhallaoui,
  Daniel Villeneuve,
  François Soumis,
  Guy Desaulniers,
  1 August 2005 | Operations Research, Vol. 53, No. 4
- A branch-and-price approach to p-median location problems
  Computers & Operations Research, Vol. 32, No. 6
- Hybrid Column Generation Approaches for Urban Transit Crew Management Problems
  Tallys H. Yunes,
  Arnaldo V. Moura,
  Cid C. de Souza,
  1 May 2005 | Transportation Science, Vol. 39, No. 2
- Bombardier Flexjet Significantly Improves Its Fractional Aircraft Ownership Operations
  Richard Hicks,
  Richard Madrid,
  Chris Milligan,
  Robert Pruneau,
  Mike Kanaley,
  Yvan Dumas,
  Benoit Lacroix,
  Jacques Desrosiers,
  François Soumis,
  1 February 2005 | Interfaces, Vol. 35, No. 1
- Shortest Path Problems with Resource Constraints
- Large-Scale Models in the Airline Industry
- Integration of Fleet Assignment and Aircraft Routing
  1 January 2005 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 1915, No. 1
- Uma proposta de solução para o problema da construção de escalas de motoristas e cobradores de ônibus por meio do algoritmo do matching de peso máximo
  Gestão & Produção, Vol. 11, No. 2
- A column generation approach to capacitated p-median problems
  Computers & Operations Research, Vol. 31, No. 6
- An Annotated Bibliography of Personnel Scheduling and Rostering
  Annals of Operations Research, Vol. 127, No. 1-4
- An Exact Algorithm for the Simplified Multiple Depot Crew Scheduling Problem
  Annals of Operations Research, Vol. 127, No. 1-4
- Airline Schedule Planning: Accomplishments and Opportunities
  Cynthia Barnhart,
  Amy Cohn,
  1 January 2004 | Manufacturing & Service Operations Management, Vol. 6, No. 1
- Dispatching and Conflict-Free Routing of Automated Guided Vehicles: An Exact Approach
  International Journal of Flexible Manufacturing Systems, Vol. 15, No. 4
- Column-Generation in Integer Linear Programming
  15 November 2003 | RAIRO - Operations Research, Vol. 37, No. 2
- Multiterminal net routing for partial crossbar-based multi-FPGA systems
  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 11, No. 1
- Airline Crew Scheduling
- Planning and Scheduling Staff Duties by Goal Programming
- Duty Scheduling in Public Transit
- Part Batching and Scheduling in a Flexible Cell to Minimize Setup Costs
  Journal of Scheduling, Vol. 6, No. 1
- Models and Algorithms for Integration of Vehicle and Crew Scheduling
  Journal of Scheduling, Vol. 6, No. 1
- A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas
  Pesquisa Operacional, Vol. 23, No. 1
- A concurrent processing framework for the set partitioning problem
  Computers & Operations Research, Vol. 29, No. 10
- Generalized Column Generation for Linear Programming
  Osman Oğuz,
  1 March 2002 | Management Science, Vol. 48, No. 3
- Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems
- A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints
  Annals of Operations Research, Vol. 108, No. 1-4
- Combining Constraint Programming and Linear Programming on an Example of Bus Driver Scheduling
  Annals of Operations Research, Vol. 108, No. 1-4
- Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems
  Knut Haase,
  Guy Desaulniers,
  Jacques Desrosiers,
  1 August 2001 | Transportation Science, Vol. 35, No. 3
- Optimization of multiple objective gate assignments
  Transportation Research Part A: Policy and Practice, Vol. 35, No. 5
- A Technical Review of Column Generation in Integer Programming
  Optimization and Engineering, Vol. 2, No. 2
- A goal programming model for crew duties generation
  7 September 2001 | Journal of Multi-Criteria Decision Analysis, Vol. 10, No. 3
- Set Covering, Packing and Partitioning Problems
- Combinatorial and integer optimization
  25 October 2005
- A New Model for the Mass Transit Crew Scheduling Problem
- Days-off Scheduling in Public Transport Companies
- A Set Partitioning Approach to the Crew Scheduling Problem
  A. Mingozzi,
  M. A. Boschetti,
  S. Ricciardelli,
  L. Bianco,
  1 December 1999 | Operations Research, Vol. 47, No. 6
- A Column Generation Approach for Large-Scale Aircrew Rostering Problems
  Michel Gamache,
  François Soumis,
  Gérald Marquis,
  Jacques Desrosiers,
  1 April 1999 | Operations Research, Vol. 47, No. 2
- A Hybrid Approach for Solving Large Scale Crew Scheduling Problems
  28 January 2000
- Crew Scheduling
- Crew scheduling of light rail transit in Hong Kong: from modeling to implementation
  Computers & Operations Research, Vol. 25, No. 11
- The Operational Airline Crew Scheduling Problem
  Mirela Stojković,
  François Soumis,
  Jacques Desrosiers,
  1 August 1998 | Transportation Science, Vol. 32, No. 3
- The Preferential Bidding System at Air Canada
  Michel Gamache,
  François Soumis,
  Daniel Villeneuve,
  Jacques Desrosiers,
  Éric Gélinas,
  1 August 1998 | Transportation Science, Vol. 32, No. 3
- Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
  European Journal of Operational Research, Vol. 108, No. 3
- A dynamic programming based algorithm for the crew scheduling problem
  Computers & Operations Research, Vol. 25, No. 7-8
- Branch-and-Price: Column Generation for Solving Huge Integer Programs
  Cynthia Barnhart,
  Ellis L. Johnson,
  George L. Nemhauser,
  Martin W. P. Savelsbergh,
  Pamela H. Vance,
  1 June 1998 | Operations Research, Vol. 46, No. 3
- Routing and scheduling temporal and heterogeneous freight car traffic on rail networks
  Transportation Research Part E: Logistics and Transportation Review, Vol. 34, No. 2
- 大型機門指派問題最佳化
  Journal of the Chinese Institute of Industrial Engineers, Vol. 15, No. 3
- Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem
  Computational Optimization and Applications, Vol. 9, No. 3
- A Method for Optimally Solving the Rostering Problem
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
- Crew Scheduling in Air Transportation
- An Integrated Approach to Extra-Urban Crew and Vehicle Scheduling
- A review of current research in manufacturing shop design integration
  Journal of Intelligent Manufacturing, Vol. 9, No. 1
- Aircrew schedule generation using repeated matching
  European Journal of Operational Research, Vol. 102, No. 1
- Crew pairing at Air France
  European Journal of Operational Research, Vol. 97, No. 2
- Airline crew-scheduling problem with many irregular flights
  29 July 2005
- A tree search algorithm for the crew scheduling problem
  European Journal of Operational Research, Vol. 94, No. 3
- Column generation applied to linear programs in course registration
  European Journal of Operational Research, Vol. 87, No. 2
- Bus Driver Scheduling — An Overview
- Network Models, Lagrangean Relaxation and Subgradients Bundle Approach in Crew Scheduling Problems
- Results Obtained with Crew-Opt: A Column Generation Method for Transit Crew Scheduling
- Bestimmung optimaler Einsatzpläne für Flugpersonal
- Chapter 2 Time constrained routing and scheduling
- Solving binary cutting stock problems by column generation and branch-and-bound
  Computational Optimization and Applications, Vol. 3, No. 2
- Partitioning Problems in Cluster Analysis: A Review of Mathematical Programming Approaches
- Chapter 5 Models in urban and air transportation
- State space relaxation for set covering problems related to bus driver scheduling
  European Journal of Operational Research, Vol. 71, No. 2
- Algorithms for large scale set covering problems
  Annals of Operations Research, Vol. 43, No. 5
- Enhancing an algorithm for set covering problems
  European Journal of Operational Research, Vol. 58, No. 2
- CREW-OPT: Subproblem Modeling in a Column Generation Approach to Urban Crew Scheduling
- A New Decomposition Scheme of the Urban Public Transport Scheduling Problem
- The pickup and delivery problem with time windows
  European Journal of Operational Research, Vol. 54, No. 1
- Implantation et complexité des techniques de programmation dynamique dans les méthodes de confection de tournées et d'horaires
  29 March 2011 | RAIRO - Operations Research, Vol. 25, No. 3

Volume 23, Issue 1

February 1989

Pages 1-65

Article Information

Metrics

Information

Published Online:February 01, 1989

Cite as

Martin Desrochers, François Soumis, (1989) A Column Generation Approach to the Urban Transit Crew Scheduling Problem. Transportation Science 23(1):1-13.

https://doi.org/10.1287/trsc.23.1.1

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Column Generation Approach to the Urban Transit Crew Scheduling Problem

Volume 23, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News