定期検査制約を有する車両運用計画問題への列生成法の適用

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

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

発行日: 2012/01/01

タイトル(英語): Application of Column Generation for Train-set Scheduling Problems with Regular Maintenance Constraints

著者名: 大野　明良（大阪大学大学院基礎工学研究科システム創成専攻社会システム数理領域），西　竜志（大阪大学大学院基礎工学研究科システム創成専攻社会システム数理領域），乾口　雅弘（大阪大学大学院基礎工学研究科システム創成専攻社会システム数理領域），高橋　理（三菱電機（株）先端技術総合研究所），上田　健詞（三菱電機（株）先端技術総合研究所）

著者名(英語): Akiyoshi Ohno (Graduate School of Engineering Science, Osaka University), Tatsushi Nishi (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 Ueda (Advanced Technology R&D Center, Mitsubishi Electric Corporation)

キーワード: 組合せ最適化，車両運用計画問題，列生成法，集合分割問題，ラベリング法　　combinatorial optimization，train-set scheduling，column generation，set partitioning problem，labeling algorithm

要約(英語): In this paper, we propose a column generation for the train-set scheduling problem with regular maintenance constraints. The problem is to allocate the minimum train-set to the train operations required to operate a given train timetable. In the proposed method, a tight lower bound can be obtained from the continuous relaxation for Dantzig-Wolfe reformulation by column generation. The subproblem for the column generation is an elementary shortest path problem with resource constraints. A labeling algorithm is applied to solve the subproblem. In order to reduce the computational effort for solving subproblems, a new state space relaxation of the subproblem is developed in the labeling algorithm. An upper bound is computed by a heuristic algorithm. Computational results demonstrate the effectiveness of the proposed method.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.132 No.1 （2012） 特集：確率的最適化と機械学習の統計的設計と応用

本誌掲載ページ: 151-159 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/132/1/132_1_151/_article/-char/ja/