A column generation approach to railway crew recovery problem in disruption

Jun Imaizumi, Rei Miura, Eiki Shigeta, Susumu Morito

    研究成果: Article査読


    Crew Recovery Problem frequently appears in transport industries. This problem is to modify schedules of crews who cannot perform their tasks in their duties given beforehand as the result from Crew Scheduling Problem because of delays of trains or flights. To obtain a good modified schedule of crews is needed when delay occurs while it is more important to find alternative and acceptable schedule(s) quickly. In this paper, we formulate the problem in railways as an integer programming problem and propose an approach to this as a basic framework for similar problems arising in transport industries. Our heuristic approach is based on the idea of column generation method, which is one of the effective and powerful methods for large scale integer programming problems. The procedure generates various schedules for a certain instance by gradually increasing the number of crews to be rescheduled, giving the lower bound to the optimal value of the objective function in each iteration. Numerical experiments are performed to instances from Japanese railway. The results indicate that our approach successfully gives good schedules in short computation time.

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

    ASJC Scopus subject areas

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


    「A column generation approach to railway crew recovery problem in disruption」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。