An application of wedelin's method to railway crew scheduling problem

Rei Miura*, Jun Imaizumi, Naoto Fukumura, Susumu Morito

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review


    So many scheduling problems arise in railway industries. One of the typical scheduling problems is Crew Scheduling Problem. Much attention has been paid to this problem by a lot of researchers, but many studies have not been done to the problems in railway industries in Japan. In this paper, we consider a railway crew scheduling problem in Japan. The problem can be formulated into Set Covering Problem (SCP). In SCP, a row corresponds to a trip representing a minimal task and a column corresponds to a pairing representing a sequence of trips performed by a certain crew. Many algorithms have been developed and proposed for it. On the other hand, in practical use, it is important to investigate how these algorithms behave and work on a certain problem. Therefore, we focus on Wedelin's algorithm, which is based on Lagrange relaxation and is known as one of the high performance algorithms for SCP, and mainly examine the basic idea of this algorithm. Furthermore, we show effectiveness of this procedure through computational experiments on instances from Japanese railway.

    Original languageEnglish
    Pages (from-to)1958-1967
    Number of pages10
    JournalIEEJ Transactions on Electronics, Information and Systems
    Issue number10
    Publication statusPublished - 2009


    • Crew scheduling problem
    • Heuristic
    • Mathematical programming
    • Performance evaluation by computational experiments
    • Railway

    ASJC Scopus subject areas

    • Electrical and Electronic Engineering


    Dive into the research topics of 'An application of wedelin's method to railway crew scheduling problem'. Together they form a unique fingerprint.

    Cite this