Lagrangian Relaxation Method for Network Flow Modeled Crew and Vehicle Rescheduling
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 covers 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.Results of real-world vehicle rescheduling data from a Japanese railway line indicate that the proposed method generates a feasible solution within a practical amount of time,which is confirmed to be fairly close to the optimum according to the gap and a comparison with the heuristic solution method.
crew/vehicle rescheduling network flow model integer programming Lagrangian relaxation method railway train operation
Tatsuhiro Sato Tomoe Tomiyama Toyohisa Morita Tomohiro Murata
Systems Development Laboratory Hitachi,Ltd.Yokohama,JAPAN Graduate School of Information,Production and Systems Waseda University Kitakyushu,JAPAN
国际会议
The 2nd IEEE International Conference on Advanced Computer Control(第二届先进计算机控制国际会议 ICACC 2010)
沈阳
英文
403-408
2010-03-27（万方平台首次上网日期，不代表论文的发表时间）