Document Type : Original Article

Author

Industrial Engineering Department, Payame Noor University(PNU) ,Tehran,Iran.

Abstract

Railway scheduling is a complex task of rail operators that involves the generation of a conflict-free train timetable. This paper presents a discrete-event simulation-based optimization approach for solving the train timetabling problem to minimize total weighted unplanned stop time in a hybrid single and double track railway networks. The designed simulation model is used as a platform for generating feasible conflict-free train timetables. It includes detailed infrastructure information, such as station characteristics, trains running time and praying intervals. The proposed approach has the capability of scheduling trains in large-scale networks subject to the capacity constraints and infrastructure characteristics. In optimization procedure, a path relinking meta-heuristic algorithm is utilized to generate near-optimal train timetables. A case study of Iran railway network is selected for examining the efficiency of the meta-heuristic algorithm. The computational result shows that the proposed approach has the capability of generating near-optimal timetable in real-sized train scheduling problems. 

Keywords

Azadeh, A., GHaderi, S. and Izadbakhsh, H., (2008). "Integration of DEA and AHP with computer simulation for railway system improvement and optimization", Applied Mathematics and Computation, Vol. 195, pp. 775-785.
Bhaskar, A., Cools, M. and Chung, E., (2017). "An investigation of timed transfer coordination using event-based multi agent simulation", Transportation Research Part C: Emerging Technologies.
Cappara, A., Fischetti, M. and Toth, P., (2002). "Modeling and solving the train timetabling problem", Operations Research, Vol. 50, pp. 851-861.
Carey, M. and Carville, S., (2003). "Scheduling and platforming trains at busy complex stations",Transportation Research Part A: Policy and Practice, Vol. 37, pp. 195-224.
Confessore, G., Liotta, G., Cicini, P., Rondione, F. and De luca, P., (2009). "A simulation-based approach for estimating the commercial capacity of railways", Simulation Conference (WSC), Proceedings of the 2009 Winter, IEEE, pp. 2542-2552.
Dessouky, M. M. and Leachman, R. C., (1995). "A simulation modeling methodology for analyzing large complex rail networks",  Simulation, Vol. 65, pp. 131-142.
Dingler, M., Lai, Y.-C. and Barkan, C., (2009). "Impact of train type heterogeneity on single-track railway capacity", Transportation Research Record: Journal of the Transportation Research Board, pp. 41-49. 
Dingler, M. H., Lai, Y.-C. and Barkan, C. P., (2014). "Effect of train-type heterogeneity on single-track heavy haul railway line capacity", Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit, Vol. 228, pp. 845-856. 
Eskandari, H., Rahaee, M. A., Memarpour, M., Nayebi, E. H. and Malek, S., (2013). "A. Evaluation of different berthing scenarios in Shahid Rajaee container terminal using discrete-event simulation", Proceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World, 2013. IEEE Press, pp. 3462-3474.
Froid, O., Sipila, H. and Warg, J., (2014). "Capacity for express trains on mixed traffic lines", International Journal of Rail Transportation, Vol. 2, pp. 17-27.
Garey, M. R. and Johnson, D. S., (1979). Computers and intractability, Freeman New York.
Goverde, R. M., (2005). "Punctuality of railway operations and timetable stability analysis", Netherlands TRAIL Research School
Hajian-Heidary, M. and Aghaei, A., (2015). "Risk measurement in the global supply chain using monte-carlo simulation", Journal of Industrial Engineering and Management Studies, Vol. 2, pp. 1-12. 
Hassannayebi, E., Sajedinejad, A. and Mardani, S., (2014). "Urban rail transit planning using a two-stage simulation-based optimization approach", Simulation Modelling Practice and Theory, Vol. 49, pp. 151-166. 
Hassannayebi, E., Sajedinejad, A. and Mardani, S., (2016). Disruption Management in Urban Rail Transit System: A Simulation Based Optimization Approach, Handbook of Research on Emerging Innovations in Rail Transportation Engineering. IGI Global.
Hassannayebi E., Zegordi, S. H., Yaghini, M. and Amin naseri, M. R., (2017). "Timetable optimization models and methods for minimizing passenger waiting time at public transit terminals", Transportation Planning and Technology, Vol. 40, pp. 278-304. 
Hullinger, D. R., (1999). "Taylor enterprise dynamics", Simulation Conference Proceedings, Winter, 1999. IEEE, 227-229. 
Ilati, G., Sheikholeslami, A. and Hassannayebi, E., (2014). "A Simulation-Based Optimization Approach for Integrated Port Resource Allocation Problem", PROMET-Traffic&Transportation, Vol. 26, pp.243-255.
Jensen, L. W., Landex, A., Nielsen, O. A., Kroon, L. G. and Schmidt, M., (2017). "Strategic assessment of capacity consumption in railway networks: Framework and model", Transportation Research Part C: Emerging Technologies, Vol. 74, pp. 126-149.
 Keiji, K., Naohiko, H. and Shigeru, M., (2015). "Simulation analysis of train operation to recover knock-on delay under high-frequency intervals", Case Studies on Transport Policy, Vol. 3, pp. 92-98.
Khan, M. B. and Zhou, X., (2010). "Stochastic optimization model and solution algorithm for robust double-track train-timetabling problem", Intelligent Transportation Systems, IEEE Transactions on, Vol. 11, pp. 81-89. 
Laguna, M. and Glover, F., (1993). "Bandwidth packing: a tabu search approach", Management science, Vol. 39, pp. 492-500. 
Lia, X., Hao, J.-K., LÜ, Z. and Glover, F., (2016). "A learning-based path relinking algorithm for the bandwidth coloring problem", Engineering Applications of Artificial Intelligence, Vol. 52, pp. 81-91.
Larsen, R., Pranzo, M., D’ariano, A., Corman, F. and Pacciarelli, D., (2014). "Susceptibility of optimal train schedules to stochastic disturbances of process times", Flexible Services and Manufacturing Journal, Vol. 26, pp. 466-489.
Mattson, L.-G., (2007). "Railway capacity and train delay relationships", Critical Infrastructure, Springer.
Medeossi, G., Longo, G. and De Fabris, S., (2011). "A method for using stochastic blocking times to improve timetable planning", Journal of Rail Transport Planning & Management, Vol. 1, pp. 1-13. 
Middelkoop, D. and Bouwman, M. Simone, (2001). "large scale train network simulations",  Proceedings of the 33nd conference on Winter simulation, 2001. IEEE Computer Society, 1042-1047.
Motraghi, A. and Marinov, M. V., (2012). "Analysis of urban freight by rail using event based simulation", Simulation Modelling Practice and Theory, Vol. 25, pp. 73-89.
Noordeen, M., (1996). "Stability analysis of cyclic timetables for a highly interconnected rail network", PhD thesis.
 Pinedo, M., (2015). Scheduling, Springer.
Pouryousef, H., Lautala, P. and White, T., (2015). "Railroad capacity tools and methodologies in the US and Europe", Journal of Modern Transportation, Vol. 23, pp. 30-42.
 Rudolph, R. and Demitz, J., (2003). "Simulation of large railway networks", Robustness test for the timetable 2003 in North Rhine Westphalia, Germany.  Proceedings of the World Congress on Railway Research, 2003. 644-652.
 Sajedinejad, A., Mardani, S., Hassannayebi, E., Mir Mohammadi K, S. and Kabirian, A. Simarail, (2001). "simulation based optimization software for scheduling railway network", Simulation Conference (WSC), Proceedings of the 2011 Winter, 2011, IEEE, pp. 3730-3741.
Stankaitis, P., Iliasov, A. and Romanovsky, A., (2017). "A Railway Simulation Suite For Modelling Advanced Railway Control Systems", International Journal of Transport Development and Integration, Vol. 1, pp. 558-567.
Suhl, L., Mellouli, T., Biederbick, C. and Geocke, J., (2001). "Managing and preventing delays in railway traffic by simulation and optimization", Mathematical methods on optimization in transportation systems. Springer.
Vromans, M. J. C. M., (2005). "Reliability of railway systems", Erasmus University Rotterdam.
Warg, J. and Bohlin, M., (2016). "The use of railway simulation as an input to economic assessment of timetables", Journal of Rail Transport Planning & Management, Vol. 6, pp. 255-270.
Xu, X., LI, K. and Yang, L., (2016). "Rescheduling subway trains by a discrete event model considering service balance performance", Applied Mathematical Modelling, Vol. 40, pp. 1446-1466.
Xu, X., LI, K., Yang, L. and Ye, J., (2014). "Balanced train timetabling on a single-line railway with optimized velocity", Applied Mathematical Modelling, Vol. 38, pp. 894-909.
Zhou, L., Tong, L. C., Chen, J., Tang, J. and Zhou, X., (2017). "Joint optimization of high-speed train timetables and speed profiles: A unified modeling approach using space-time-speed grid networks", Transportation Research Part B: Methodological, Vol. 97, pp. 157-181.