Advertisement

OD-Independent Train Scheduling for an Urban Rail Transit Line

  • Yihui WangEmail author
  • Bin Ning
  • Ton van den Boom
  • Bart De Schutter
Chapter
  • 761 Downloads
Part of the Advances in Industrial Control book series (AIC)

Abstract

In the previous two chapters, we have discussed trajectory planning for trains in a railway network based on given train schedules. In this chapter, the train scheduling problem based on origin–destination-independent (OD-independent ) passenger demands for an urban rail transit line is considered with the aim of minimizing the total travel time of passengers and the energy consumption of trains. We propose a new iterative convex programming (ICP) approach to solve this train scheduling problem. Via a case study inspired by the Beijing Yizhuang line, the performance of the ICP approach is compared with other alternative approaches, such as nonlinear programming approaches, a mixed integer nonlinear programming (MINLP) approach, and a mixed integer linear programming (MILP) approach. The research discussed in this chapter is based on Wang et al. (Efficient real-time train scheduling for urban rail transit systems using iterative convex programming. IEEE Trans Intell Transp Syst 16:3337–3352, 2015) [1]; Wang et al. (Proceedings of the 1st IEEE international conference on intelligent rail transportation (2013 IEEE ICIRT), Beijing, China, 2013) [2]; Wang et al. (Proceedings of the 16th international IEEE conference on intelligent transportation systems (ITSC 2013), The Netherlands, The Hague,pp 1334–1339, 2013) [3].

Keywords

Mixed Integer Linear Programming Sequential Quadratic Programming Total Travel Time Mixed Integer Nonlinear Programming Train Schedule 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. 1.
    Wang Y, De Schutter B, van den Boom T, Ning B, Tang T (2015) Efficient real-time train scheduling for urban rail transit systems using iterative convex programming. IEEE Trans Intell Transp Syst 16:3337–3352Google Scholar
  2. 2.
    Wang Y, De Schutter B, van den Boom T, Ning B, Tang T (2013) Real-time scheduling in urban rail transit operations control. In: Proceedings of the 1st IEEE international conference on intelligent rail transportation (2013 IEEE ICIRT), Beijing, China. Paper 108Google Scholar
  3. 3.
    Wang Y, De Schutter B, van den Boom T, Ning B, Tang T (2013) Real-time scheduling for trains in urban rail transit systems using nonlinear optimization. In: Proceedings of the 16th international IEEE conference on intelligent transportation systems (ITSC 2013), The Netherlands, The Hague, pp 1334–1339Google Scholar
  4. 4.
    Vázquez-Abad F, Zubieta L (2005) Ghost simulation model for the optimization of an urban subway system. Discret Event Dyn Syst 15:207–235MathSciNetCrossRefzbMATHGoogle Scholar
  5. 5.
    Kwan C, Chang C (2005) Application of evolutionary algorithm on a transportation scheduling problem—the mass rapid transit. In: Proceedings of the IEEE congress on evolutionary computation, Edinburgh, UK, pp 987–994Google Scholar
  6. 6.
    Gassel C, Albrecht T (2009) The impact of request stops on railway operations. In: Proceedings of the 3rd international seminar on railway operations modeling and analysis, Zürich, Switzerland, pp 1–15Google Scholar
  7. 7.
    Higgins A, Kozan E, Ferreira L (1996) Optimal scheduling of trains on a single line track. Transp Res Part B 30:147–161CrossRefGoogle Scholar
  8. 8.
    Okrent M (1974) Effects of transit service characteristics on passenger waiting times. M.S. thesis, Northwestern University, Evanston, USAGoogle Scholar
  9. 9.
    Simon J, Furth P (1985) Generating a bus route O-D matrix from on-off data. J Transp Eng 111:583–593CrossRefGoogle Scholar
  10. 10.
    Hansen I, Pachl J (2008) Railway, timetable and traffic: analysis, modelling, simulation. Eurailpress, Hamburg, GermanyGoogle Scholar
  11. 11.
    D’Ariano A, Pranzoand M, Hansen I (2007) Conflict resolution and train speed coordination for solving real-time timetable perturbations. IEEE Trans Intell Transp Syst 8:208–222CrossRefGoogle Scholar
  12. 12.
    Elberlein X, Wilson N, Bernstein D (2001) The holding problem with real-time information available. Transp Sci 35:1–18CrossRefzbMATHGoogle Scholar
  13. 13.
    Li X, Wang D, Li K, Gao Z (2013) A green train scheduling model and fuzzy multi-objective optimization algorithm. Appl Math Model 37:617–629MathSciNetGoogle Scholar
  14. 14.
    Goverde R (2005) Punctuality of railway operations and timetable stability analysis. PhD thesis, Delft University of Technology, Delft, NetherlandsGoogle Scholar
  15. 15.
    van den Boom T, Kersbergen B, De Schutter B (2012) Structured modeling, analysis, and control of complex railway operations. In: Proceedings of the 51st IEEE conference on decision and control, Maui, Hawaii, pp 7366–7371Google Scholar
  16. 16.
    Kersbergen B, van den Boom T, De Schutter B (2013) Reducing the time needed to solve the global rescheduling problem for railway networks. In: Proceedings of the 16th international IEEE conference on intelligent transportation systems (ITSC 2013), The Hague, The Netherlands, pp 791–796Google Scholar
  17. 17.
    Pachl J (2009) Railway operation and control, 2nd edn. Gorham Printing, CentraliaGoogle Scholar
  18. 18.
    Lin T, Wilson N (1992) Dwell time relationships for light rail systems. Transp Res Rec 1361:287–295Google Scholar
  19. 19.
    Vansteenwegen P, Oudheusden DV (2007) Decreasing the passenger waiting time for an intercity rail network. Transp Res Part B 41:478–492CrossRefGoogle Scholar
  20. 20.
    Ghoseiri K, Szidarovszky F, Asgharpour M (2004) A multi-objective train scheduling model and solution. Transp Res Part B 38:927–952CrossRefzbMATHGoogle Scholar
  21. 21.
    Hooke R, Jeeves T (1961) Direct search solution of numerical and statistical problems. J Assoc Comput Mach 8:212–229CrossRefzbMATHGoogle Scholar
  22. 22.
    Martí R (2010) Advaced multi-start methods. International series in operations research and management science: handbook of metaheuristics. Springer, New York, pp 265–281Google Scholar
  23. 23.
    The Mathworks Inc. (2004) Genetic algorithm and direct search toolbox for use with MATLAB: user’s guide. The Mathworks Inc., Natick, MA, USAGoogle Scholar
  24. 24.
    Boggs P, Tolle J (1995) Sequential quadratic programming. Acta Numerica 4:1–51MathSciNetCrossRefzbMATHGoogle Scholar
  25. 25.
    Gill P, Murray W, Saunders M (2002) SNOPT: an SQP algorithm for large-scale constrained optimization. Soc Ind Appl Math J Optim 12:979–1006MathSciNetzbMATHGoogle Scholar
  26. 26.
    The Mathworks Inc. (1999) Optimization toolbox for use with Matlab: user’s guide. The Mathworks Inc., Natick, MA, USAGoogle Scholar
  27. 27.
    Williams H (1999) Model building in mathematical programming, 4th edn. Wiley, ChichesterzbMATHGoogle Scholar
  28. 28.
    Holmström K, Göran AO, Edvall M (2007) User’s guide for tomlab/minlp. http://tomopt.com/docs/TOMLAB_MINLP.pdf
  29. 29.
    Berthold T, Gamrath G, Gleixner A, Heinz S, Koch T, Shinano Y (2012) Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite. ZIB-Report 12–17. Zuse Institute Berlin. Berlin, GermanyGoogle Scholar
  30. 30.
    Kvasnica M, Grieder P, Baotić M (2011) Automatic derivation of optimal piecewise affine approximations of nonlinear systems. In: Proceedings of the 18th IFAC world congress. Milano, Italy, pp 8675–8680Google Scholar
  31. 31.
    Williams H (1993) Model building in mathematical programming. Wiley, New YorkGoogle Scholar
  32. 32.
    Linderoth J, Ralphs T (2005) Noncommercial software for mixed-integer linear programming. In: Karlof J (ed) Integer programming: theory and practice., Operations research seriesCRC Press, Boca Raton, pp 253–303Google Scholar
  33. 33.
    Atamturk A, Savelsbergh M (2005) Integer-programming software systems. Annals of operations research 140:67–124MathSciNetCrossRefzbMATHGoogle Scholar
  34. 34.
    Byrd R, Hribar M, Nocedal J (1999) An interior point algorithm for large-scale nonlinear programming. SIAM J Optim 9:877–900MathSciNetCrossRefzbMATHGoogle Scholar
  35. 35.
    Grant M, Boyd S (2012) CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx
  36. 36.
    Zhang B, Lu Y (2011) Research on dwelling time modeling of urban rail transit. Traffic Transp 27:48–52Google Scholar

Copyright information

© Springer International Publishing Switzerland 2016

Authors and Affiliations

  • Yihui Wang
    • 1
    Email author
  • Bin Ning
    • 1
  • Ton van den Boom
    • 2
  • Bart De Schutter
    • 2
  1. 1.State Key Laboratory of Rail Traffic Control and SafetyBeijing Jiaotong UniversityBeijingChina
  2. 2.Delft Center for Systems and ControlDelft University of TechnologyDelftThe Netherlands

Personalised recommendations