01029683

Component

This paper is concerned with the train timetabling problem that minimizes the total train travel time subject to a set of operational and safety requirements on a single-track rail line. A generalized resource constrained project scheduling formulation is proposed to consider segment and station capacities as limited resources, and a branch-and-bound solution procedure is presented to obtain feasible schedules with guaranteed optimality. The proposed search algorithm eliminates train conflicts chronologically by adding precedence relation constraints between conflicting trains, while the resulting subproblems are solved by the longest path algorithm that determines earliest start times for each train at segments. In order to effectively reduce the search space, a Lagrangian relaxation based lower bound rule is used to dualize segment and station capacity constraints and decompose the original complex problem into single train scheduling problems. Another exact lower bound rule is also embedded into the branch-and-bound search procedure to estimate the least train delay for resolving each existing crossing conflict in a partial schedule. In addition, this paper applies a beam search heuristic method to provide tight initial upper bounds. Based on a real-world train timetable, comprehensive numerical experiments are conducted to illustrate the computational performance of lower bound rules and evaluate several constructive heuristic methods.

01020180

06-2501

English

17p

2006

Transportation Research Board 85th Annual Meeting

CD-ROM

Figures; References; Tables

Branch and bound algorithms; Timetables; Travel time

Lagrangian relaxation approach; Scheduling conflicts; Single track rail lines

Operations and Traffic Management; Public Transportation; Railroads

Transportation Research Board Annual Meeting 2006 Paper #06-2501

TRIS, TRB

Mar 3 2006 11:01AM