Stochastic Schedule–Based Optimization Model for Track Allocations in Large Railway Stations
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 145, Issue 3
Abstract
This paper develops a track allocation model for large railway stations based on stochastic schedules, which considers balanced utilization as well as minimum occupation time of station tracks. The stochastic schedule is represented by the mean and variance of both train arrival and departure times. Due to the nondeterministic polynomial completeness of the track allocation problem, a tailored simulated annealing algorithm is developed to solve the proposed model. In addition, a numerical case from the Baoji railway station is studied that demonstrates the model’s performance. After solving the model, the results of track allocation schedule can detect the limited carrying capacity area in the station, and the capacity relationship of two station bottleneck sections can be obtained. The capacity of the left station bottleneck area is about 1.48 times higher than that in the right station bottleneck area in Baoji railway station.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
We are grateful to the three anonymous reviewers for their valuable comments and suggestions to improve this study. This study is supported by research Grant No. R-302-000-172-114 of the Ministry of Education of Singapore and National Natural Science Foundation of China (NSFC) (71271023, 71271024).
References
Billionnet, A. 2003. “Using integer programming to solve the train-platforming problem.” Transp. Sci. 37 (2): 213–222. https://doi.org/10.1287/trsc.37.2.213.15250.
Burkolter, D. M. 2005. “Capacity of railways in station areas using Petri nets.” Ph.D. thesis, Dept. of Mathematics, Swiss Federal Institute of Technology.
Caimi, G., D. Burkolter, and T. Herrmann. 2005. “Finding delay-tolerant train routings through station.” In Vol. 5 of Proc., Operations Research 2004, 136–143. Berlin: Springer.
Caprara, A., M. Fischetti, and P. Toth. 2002. “Modeling and solving the train timetabling problem.” Oper. Res. 50 (5): 851–861. https://doi.org/10.1287/opre.50.5.851.362.
Cardillo, D. D. L., and N. Mione. 1998. “kL-list coloring of graphs.” Eur. J. Oper. Res. 106 (1): 160–164. https://doi.org/10.1016/S0377-2217(98)00299-9.
Carey, M., and S. Carville. 2003. “Scheduling and platforming trains at busy complex stations.” Transp. Res. Part A 37 (3): 195–224. https://doi.org/10.1016/S0965-8564(02)00012-5.
Carey, M., and I. Crawford. 2007. “Scheduling trains on a network of busy complex stations.” Transp. Sci. Part B 41 (2): 159–178. https://doi.org/10.1016/j.trb.2006.02.002.
Corman, F., A. D’Ariano, D. Pacciarelli, and M. Pranzo. 2013. “Dispatching and coordination in multi-area railway traffic management.” Comput. Oper. Res. 44 (4): 146–160. https://doi.org/10.1016/j.cor.2013.11.011.
Corman, F., R. M. P. Goverde, and A. D’Ariano. 2009. “Rescheduling dense train traffic over complex station interlocking areas.” Vol. 5868 of Robust and online large-scale optimization, 369–386. Berlin: Springer.
Corman, F., and L. Meng. 2013. “A review of online dynamic models and algorithms for railway traffic management.” IEEE Trans. Intell. Transp. Syst. 16 (3): 128–133. https://doi.org/10.1109/TITS.2014.2358392.
Cornelsen, S., and G. D. Stefano. 2007. “Track assignment.” J. Discrete Algorithms 5 (2): 250–261. https://doi.org/10.1016/j.jda.2006.05.001.
D’Ariano, A., D. Pacciarelli, and M. Pranzo. 2007. “A branch-and-bound algorithm for scheduling trains in a railway network.” Eur. J. Oper. Res. 183 (2): 643–657. https://doi.org/10.1016/j.ejor.2006.10.034.
D’Ariano, A., D. Pacciarelli, and M. Pranzo. 2008. “Assessment of flexible timetables in real-time traffic management of a railway bottleneck.” Transp. Res. Part C 16 (2): 232–245. https://doi.org/10.1016/j.trc.2007.07.006.
D’Ariano, A., D. Pacciarelli, and M. Pranzo. 2010. “A Tabu search algorithm for rerouting trains during rail operations.” Transp. Res. Part B 44 (1): 175–192. https://doi.org/10.1016/j.trb.2009.05.004.
Delorme, X., X. Gandibleux, and J. Rodriguez. 2004. “GRASP for set packing problems.” Eur. J. Oper. Res. 153 (3): 564–580. https://doi.org/10.1016/S0377-2217(03)00263-7.
Herrmann, T. M. 2006. “Stability of timetables and train routing the station regions.” Ph.D. thesis, Institute for Operations Research, Swiss Federal Institute of Technology.
Kang, L., and Q. Meng. 2017. “Two-phase decomposition method for the last train departure time choice in subway networks.” Transp. Res. Part B 104: 568–582. https://doi.org/10.1016/j.trb.2017.05.001.
Kang, L., J. Wu, and H. Sun. 2012. “Using simulated annealing in a bottleneck optimization model at railway stations.” J. Transp. Eng. 138 (11): 1396–1402. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000450.
Kang, L., X. Zhu, H. Sun, J. Wu, Z. Gao, and B. Hu. 2018. “Last train timetabling optimization and bus bridging service management in urban railway transit networks.” Omega 84: 31–44. https://doi.org/10.1016/j.omega.2018.04.003.
Kang, L., J. Wu, H. Sun, X. Zhu, and B. Wang. 2015. “A practical model for last train rescheduling with train delay in urban railway transit networks.” Omega 50: 29–42. https://doi.org/10.1016/j.omega.2014.07.005.
Khouzani, A. H. E., A. Golroo, and M. Bagheri. 2017. “Railway maintenance management using a stochastic geometrical degradation model.” J. Transp. Eng. Part A: Syst. 143 (1): 04016002. https://doi.org/10.1061/JTEPBS.0000002.
Larsen, R., M. Pranzo, A. D’Ariano, F. Corman, and D. Pacciarelli. 2014. “Susceptibility of optimal train schedules to stochastic disturbances of process times.” Flexible Serv. Manuf. J. 26 (4): 466–489. https://doi.org/10.1007/s10696-013-9172-9.
Liu, W., X. Zhu, and L. Kang. 2015. “Real-time track reallocation for emergency incidents at large railway stations.” Math. Prob. Eng. 2015: 296394. https://doi.org/10.1155/2015/296394.
Mannino, C., and A. Mascis. 2009. “Optimal real-time traffic control in metro stations.” Oper. Res. 57 (4): 1026–1039. https://doi.org/10.1287/opre.1080.0642.
Sadeghi, J., H. Heydari, and E. A. Doloei. 2017. “Improvement of railway maintenance approach by developing a new railway condition index.” J. Transp. Eng. Part A: Syst. 143 (8): 04017037. https://doi.org/10.1061/JTEPBS.0000063.
Wu, J., L. Kang, H. Sun, and X. Jia. 2013. “Track allocation optimization in railway station: Mean-variance model and case study.” J. Transp. Eng. 139 (5): 540–547. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000530.
Zhang, M., Q. Meng, and L. Kang. 2018. “Tailored Wakeby-type distribution for random bus headway adherence ratio.” Transp. Res. Part C 86: 220–244. https://doi.org/10.1016/j.trc.2017.11.013.
Zhao, F., and X. G. Zeng. 2006. “Simulated annealing-genetic algorithm for transit network optimization.” J. Comput. Civ. Eng. 57 (1): 57–68. https://doi.org/10.1061/(ASCE)0887-3801(2006)20:1(57).
Zwaneveld, P. J., L. G. Kroon, and S. P. M. V. Hoesel. 2001. “Routing trains through a railway station based on a node packing model.” Eur. J. Oper. Res. 128 (1): 14–33. https://doi.org/10.1016/S0377-2217(00)00087-4.
Zwaneveld, P. J., L. G. Kroon, H. E. Romeijn, and M. Salomon. 1996. “Routing trains through railway stations: Model formulation and algorithm.” Transp. Sci. 30 (3): 181–194. https://doi.org/10.1287/trsc.30.3.181.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 145 • Issue 3 • March 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Dec 11, 2017
Accepted: Aug 10, 2018
Published online: Jan 7, 2019
Published in print: Mar 1, 2019
Discussion open until: Jun 7, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.