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

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


    研究成果: Article査読


    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.

    ジャーナルIEEJ Transactions on Electronics, Information and Systems
    出版ステータスPublished - 2009

    ASJC Scopus subject areas

    • 電子工学および電気工学


    「An application of wedelin's method to railway crew scheduling problem」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。