Rail-freight crew scheduling with a genetic algorithm

Elena Khmeleva, Adrian Alan Hopgood, Lucian Tipi, Malihe Shahidan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    129 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Title of host publicationResearch and Development in Intelligent Systems XXXI
    Subtitle of host publicationIncorporating Applications and Innovations in Intelligent Systems XXII
    EditorsMax Bramer, Miltos Petridis
    PublisherSpringer
    Pages211-223
    ISBN (Electronic)978-3-319-12069-0
    ISBN (Print)978-3-319-12068-3
    DOIs
    Publication statusPublished - Dec 2014
    Event34th SGAI International Conference on Artificial Intelligence: AI-2014 - Cambridge, United Kingdom
    Duration: 9 Dec 201411 Dec 2014
    http://www.bcs-sgai.org/ai2014/

    Conference

    Conference34th SGAI International Conference on Artificial Intelligence
    Country/TerritoryUnited Kingdom
    CityCambridge
    Period9/12/1411/12/14
    Internet address

    Fingerprint

    Dive into the research topics of 'Rail-freight crew scheduling with a genetic algorithm'. Together they form a unique fingerprint.

    Cite this