Genetic Algorithm–Based Column Generation Approach to Passenger Rail Crew Scheduling
Authors:
- 1 January 2010
- journal article
- research article
- Published by SAGE Publications in Transportation Research Record: Journal of the Transportation Research Board
- Vol. 2159 (1) , 36-43
Abstract
The goal of the present study was to develop and apply a genetic algorithm–based column generation heuristic to solve a passenger rail crew scheduling problem in North America. The crew scheduling problem minimized the total cost of payment to crew members on the basis of the number of hours on board, the number of hours held away from a crew base, the number of nights of lodging, and the number of onboard and away meals. Payment regulations also dictated an overtime payment and a guaranteed salary per week. Additional problem constraints included restrictions on the maximum number of continuous working hours, the maximum number of days worked per week, and the minimum number of hours of rest. The proposed heuristic produced solutions with improvements of total cost ranging from 3.0% to 27.9%.Keywords
This publication has 15 references indexed in Scilit:
- A New Pricing Scheme for Airline Crew SchedulingINFORMS Journal on Computing, 2004
- A Global Method for Crew Planning in Railway Applications2001
- Branch-and-Price: Column Generation for Solving Huge Integer ProgramsOperations Research, 1998
- A Column Generation Approach to the Urban Transit Crew Scheduling ProblemTransportation Science, 1989
- A new approach for crew pairing problems by column generation with an application to air transportationEuropean Journal of Operational Research, 1988
- A bus crew scheduling system using a set covering formulationTransportation Research Part A: General, 1988
- Routing and scheduling of vehicles and crewsComputers & Operations Research, 1983
- Exact solution of crew scheduling problems using the set partitioning model: Recent successful applicationsNetworks, 1981
- The Airline Crew Scheduling Problem: A SurveyTransportation Science, 1969
- Rotating Roster for a Transit SystemTransportation Science, 1968