ダイヤ乱れ時の乗務員スケジュール修正問題に対する列生成法に基づくヒューリスティック解法

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

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

発行日: 2014/03/01

タイトル(英語): A Column Generation Approach to Railway Crew Recovery Problem in Disruption

著者名: 今泉　淳（東洋大学経営学部），三浦　礼（早稲田大学創造理工学部），重田　英貴（日本貨物鉄道（株）ロジスティクス本部），森戸　晋（早稲田大学創造理工学部）

著者名(英語): Jun Imaizumi (Faculty of Business Administration, Toyo Univeristy), Rei Miura (School of Creative Science and Engineering, Waseda University), Eiki Shigeta (Department of Logistics, Japan Freight Railway Company), Susumu Morito (School of Creative Science and Engineering, Waseda University)

キーワード: 鉄道，乗務員運用，運転整理，整数計画，列生成法，ヒューリスティック　　railway，crew scheduling，recovery，integer programming，column generation method，heuristic

要約(英語): 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.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.134 No.3 （2014） 特集：情報環境と人間の調和に向けた工学技術

本誌掲載ページ: 418-424 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/134/3/134_418/_article/-char/ja/