01518900

Component

The rewritten formulation and two modified local search heuristic algorithms for the single-line track train scheduling problem in the planning application are proposed. The local search heuristic (LSH) is modified such that when evaluating a neighbor of a resolved conflict currently being tested for improvement, the modified local search heuristics employ the depth-first search branch and bound algorithm with two possible branching rules. Given two trains with equal priority involved in a conflict, two branching rules are considered (least-lower-bound and least-delay-time), yielding two heuristics, namely MLSH-0 and MLSH-1, respectively. The detailed implementation of the modified local search heuristic algorithms are described, including the neighborhood definitions of overtaking conflicts and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for depth-first search branch-and-bound algorithm. MLSH-0, MLSH-1, LSH and the equivalent manual solution method are compared on three test problems (26-train, 50-train and 76-train) on the Thailand Southern line railway network composed of 266 single-line segments, 15 double-line segments, 282 stations/sidings and total distance of 1,577 kilometers. MLSH-0 outperforms the other methods in terms of solution quality with up to 0.72% improvement over the equivalent manual solution method. MLSH-0 and MLSH-1 requires longer computational time and a greater number of iterations to terminate than LSH. MLSH-0 converges faster than MLSH-1 on all test problems.

This paper was sponsored by TRB committee AR010 Intercity Passenger Rail.

01503729

14-0855

English

25p

2014

Transportation Research Board 93rd Annual Meeting

Digital/other

Figures; References; Tables

Algorithms; Heuristic methods; Railroad traffic; Scheduling; Single track; Traffic conflicts

Thailand

Operations and Traffic Management; Planning and Forecasting; Railroads; I70: Traffic and Transport

Transportation Research Board Annual Meeting 2014 Paper #14-0855

TRIS, TRB, ATRI

Jan 27 2014 2:21PM