A Genetic Algorithm-Based Column Generation Approach to the Passenger Rail Crew Scheduling Problem

Abstract

The goal of this thesis was to develop and apply a genetic algorithm-based column generation heuristic to solve a passenger rail crew scheduling problem. The crew scheduling problem minimized the total cost of payment to crew members based on the hours on-board, hours away from a crew base, number of nights of lodging, and number of on-board 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, maximum number of days worked per week, and minimum hours of rest. The proposed heuristic produced solutions with improvements of total cost ranging from 3.0 percent to 27.9 percent.