A Lagrangian Relaxation Method for Crew and Vehicle Rescheduling of Railway Passenger Transportation and its Application
A Lagrangian Relaxation Method for Crew and Vehicle Rescheduling of Railway Passenger Transportation and its Application
カテゴリ: 論文誌(論文単位)
グループ名: 【C】電子・情報・システム部門
発行日: 2012/02/01
タイトル(英語): A Lagrangian Relaxation Method for Crew and Vehicle Rescheduling of Railway Passenger Transportation and its Application
著者名: Tatsuhiro Sato (Yokohama Laboratory, Hitachi Ltd.), Tomoe Tomiyama (Yokohama Laboratory, Hitachi Ltd.), Toyohisa Morita (Research and Development Office, Hitachi Systems, Ltd.), Tomohiro Murata (Graduate School of Information, Production and Systems, Wase
著者名(英語): Tatsuhiro Sato (Yokohama Laboratory, Hitachi Ltd.), Tomoe Tomiyama (Yokohama Laboratory, Hitachi Ltd.), Toyohisa Morita (Research and Development Office, Hitachi Systems, Ltd.), Tomohiro Murata (Graduate School of Information, Production and Systems, Waseda University)
キーワード: crew/vehicle rescheduling,network flow model,integer programming,Lagrangian relaxation method,railway train operation,shortest path algorithm
要約(英語): We propose a method for solving the crew rescheduling problem (CRP) and the vehicle rescheduling problem (VRP) based on the Lagrangian relaxation method. The CRP/VRP is formulated as an integer programming problem on the basis of a network flow modeling approach from which a Lagrangian relaxation problem is constructed by relaxing the constraint that links multiple resources. Using two procedures that generate the upper and lower bounds of the primal problem, both of which utilize an efficient shortest path algorithm for the directed acyclic graph (DAG), the proposed method gradually improves the gap between the upper and lower bounds while updating Lagrangian multipliers. Experimental results of real-world vehicle rescheduling data from Japanese railway lines indicated that the proposed method generated feasible solutions that were confirmed to be fairly close to the optimal solutions according to the gap between the upper and lower bounds, and also clarified the quality of the other method's solution by using the gap, which could lead to streamlining and sophisticating real-world rescheduling related activities.
本誌: 電気学会論文誌C(電子・情報・システム部門誌) Vol.132 No.2 (2012) 特集:多様な情報社会に適応するシステム技術
本誌掲載ページ: 260-268 p
原稿種別: 論文/英語
電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/132/2/132_2_260/_article/-char/ja/
受取状況を読み込めませんでした
