Sage Journals: Discover world-class research

Abstract

By aiming to provide high-speed rail (HSR) passengers with travel convenience in the regularity of train operation, this research is devoted to optimizing a novel type of multiperiod train timetable in which trains operating with the same stop stations, speeds, and headways are classified into one period type. Moreover, trains with different period types have various operating periods on the HSR system. First, the authors propose an optimization model with the aim of minimizing the total travel times of all trains and then further reformulate the model on the basis of a weighted digraph. Through the period type–based decomposition to the reformulated model with Lagrangian relaxation, a solving algorithm that includes a multiflow shortest-path searching algorithm is designed for optimizing the multiperiod train timetable and obtaining a lower bound of the objective to evaluate its quality. Numerical examples illustrate that the solving algorithm has a good convergence and can obtain a satisfactory feasible solution with a small gap between the upper and lower bounds of the objective values.

Get full access to this article

View all access options for this article.

References

Barrena

, Canca

, Coelho

L. C.

, and Laporte

. Single-Line Rail Rapid Transit Timetabling Under Dynamic Passenger Demand. Transportation Research Part B: Methodological, Vol. 70, 2014, pp. 134–150.

Serafini

, and Ukovich

. A Mathematical Model for Periodic Scheduling Problems. SIAM Journal on Discrete Mathematics, Vol. 2, No. 4, 1989, pp. 550–581.

Odijk

M. A.

A Constraint Generation Algorithm for the Construction of Periodic Railway Timetables. Transport Research Part B: Methodological, Vol. 30, No. 6, 1996, pp. 455–464.

Willem

, and Peeters

. Cyclic Railway Timetable Optimization. Erasmus Research Institute of Management, Erasmus University, Rotterdam, Netherlands, 2003.

Liebchen

Symmetry for Periodic Railway Timetables. Electronic Notes in Theoretical Computer Science, Vol. 92, 2004, pp. 34–51.

Liebchen

, and Möhring

R. H.

. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables and Beyond. Railway Optimization, 2004, Springer-Verlag, Berlin, 2007, pp. 3–40.

Caimi

, Fuchsberger

, Marco

, and Kaspar

. Periodic Railway Timetabling with Event Flexibility. Networks, Vol. 57, No. 1, Jan. 2011, pp. 3–18.

Lindner

, and Zimmermann

U. T.

. Cost Optimal Periodic Train Scheduling. Mathematical Methods of Operations Research, Vol. 62, No. 2, 2005, pp. 281–295.

Liebchen

Periodic Timetable Optimization in Public Transport. Operation Research Proceedings, 2006, Vol. 2, Springer, Berlin, 2007, pp. 29–36.

10.

Dorfman

M. J.

, and Medanic

. Scheduling Trains on a Railway Network Using a Discrete Event Model of Railway Traffic. Transportation Research Part B: Methodological, Vol. 38, No. 1, 2004, pp. 81–98.

11.

Carey

, and Crawford

. Scheduling Trains on a Network of Busy Complex Stations. Transportation Research Part B: Methodological, Vol. 41, No. 2, 2007, pp. 159–178.

12.

, Gao

, Li

, and Yang

. Efficient Scheduling of Railway Traffic Based on Global Information of Train. Transportation Research Part B: Methodological, Vol. 42, No. 10, 2008, pp. 1008–1030.

13.

Cai

, Goh

C. J.

, and Mees

A. I.

. Greedy Heuristics for Rapid Scheduling of Trains on a Single Track. IIE Transactions, Vol. 30, No. 5, 1998, pp. 481–493.

14.

Meng

, and Zhou

. Simultaneous Train Rerouting and Rescheduling on an N-Track Network: A Model Reformulation with Network-Based Cumulative Flow Variables. Transportation Research Part B: Methodological, Vol. 67, 2014, pp. 208–234.

15.

Wolsey

L.A.

Integer Programming. John Wiley & Sons, Inc., New York, 1998.

16.

Caprara

, Fischetti

, and Toth

. Modeling and Solving the Train Timetabling Problem. Operations Research, Vol. 50, No. 5, 2002, pp. 851–861.

17.

Caprara

, Monaci

, Toth

, and Guida

P. L.

. A Lagrangian Heuristic Algorithm for a Real-World Train Timetabling Problem. Discrete Applied Mathematics, Vol. 154, No. 5, 2006, pp. 738–753.

Timetable Optimization for High-Speed Rail with Multiple Operating Periods: Solving Method Based on a Framework of Lagrangian Relaxation Decomposition

Abstract

Get full access to this article

References