実乗務制約を有する鉄道乗務員運用計画問題に対する列生成法の適用

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2011/06/01

タイトル(英語): Application of Column Generation for Railway Crew Scheduling Problems with Practical Constraints

著者名: 西　竜志（大阪大学大学院基礎工学研究科），室井　裕喜（大阪大学大学院基礎工学研究科），乾口　雅弘（大阪大学大学院基礎工学研究科），高橋　理（三菱電機(株) 先端技術総合研究所），片岡　健司（三菱電機(株) 先端技術総合研究所）

著者名(英語): Tatsushi Nishi (Graduate School of Engineering Science, Osaka University), Yuki Muroi (Graduate School of Engineering Science, Osaka University), Masahiro Inuiguchi (Graduate School of Engineering Science, Osaka University), Satoru Takahashi (Advanced Technology R&D Center, Mitsubishi Electric Corporation), Kenji Kataoka (Advanced Technology R&D Center, Mitsubishi Electric Corporation)

キーワード: 組合せ最適化，鉄道乗務員運用計画問題，列生成法，食事休憩制約，ラベリング法，優越関係　　combinatorial optimization，railway crew scheduling，column generation，meal break time constraints，label setting algorithm，dominance relation

要約(英語): In this paper, we propose a column generation method for the railway crew scheduling problem with a variety of practical constraints such as lower and upper constraints of one continuous traveling, total working time, admissible number of crews, and meal time constraints. The proposed method consists of the two steps. The first step is to derive a lower bound by the column generation and the second step is to generate a feasible solution by a heuristic method. In the proposed method, a label setting algorithm is developed to solve the pricing problem efficiently to reduce computational time. A new dominance condition is developed to eliminate unnecessary states in the label setting algorithm. A heuristic algorithm is also proposed to reduce the generation of the infeasible solutions violating the constraint on the number of the allocated crews. The effectiveness of the proposed method is evaluated by using a real railway data.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.131 No.6 （2011） 特集：圧電材料・デバイス

本誌掲載ページ: 1199-1208 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/131/6/131_6_1199/_article/-char/ja/