Rail-Freight Crew Scheduling with a Genetic Algorithm

This article presents a novel genetic algorithm designed for the solution
of the Crew Scheduling Problem (CSP) in the rail-freight industry. CSP is the task
of assigning drivers to a sequence of train trips while ensuring that no driver’s
schedule exceeds the permitted working hours, that each driver starts and finishes
their day’s work at the same location, and that no train routes are left without a
driver. Real-life CSPs are extremely complex due to the large number of trips,
opportunities to use other means of transportation, and numerous government
regulations and trade union agreements. CSP is usually modelled as a set-covering
problem and solved with linear programming methods. However, the sheer
volume of data makes the application of conventional techniques computationally
expensive, while existing genetic algorithms often struggle to handle the large
number of constraints. A genetic algorithm is presented that overcomes these
challenges by using an indirect chromosome representation and decoding
procedure. Experiments using real schedules on the UK national rail network
show that the algorithm provides an effective solution within a faster timeframe
than alternative approaches.