Abstract
To make the planning in rail transport more efficient, this work deals with a real-world Rolling Stock Circulation Problem. In this study, sequences of trips and empty runs are formed for each traction unit to cover all scheduled trips. Practical restrictions for station-wise balanced planning are integrated into a Set Covering Problem formulation which is solved with a column generation approach. The decision makers give two objectives, the number of traction units and empty run kilometers. They have different priorities at different planning stages, and it is hard for the decision makers to quantify the cost of one traction unit or one empty run kilometer. A bi-objective column generation approach is built by integrating the epsilon constraint method, which is recognized as a classical method to handle multi-objective optimization problems. To evaluate the relation between both criteria, the algorithm is tested using real-world use cases. The generated circulation plans are presented in solution fronts, illustrating the targets’ mutual influence. The identified trade-off between fewer traction units or fewer empty run kilometers can serve as decision support for planners in railway systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bach, L., Gendreau, M., Wøhlk, S.: Freight railway operator timetabling and engine scheduling. Eur. J. Oper. Res. 241(2), 309–319 (2015). https://doi.org/10.1016/j.ejor.2014.08.036
Cacchiani, V., Caprara, A., Toth, P.: An effective peak period heuristic for railway rolling stock planning. Transp. Sci. 53(3), 746–762 (2019). https://doi.org/10.1287/trsc.2018.0858
Caprara, A., Kroon, L., Monaci, M., Peeters, M., Toth, P.: Passenger railway optimization. In: Handbooks in Operations Research and Management Science. vol. 14, pp. 129–187 (2007). https://doi.org/10.1016/S0927-0507(06)14003-7
Desrosiers, J., Lübbecke, M.E.: A primer in column generation. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 1–32. Springer, Boston (2005). https://doi.org/10.1007/0-387-25486-2_1
Fioole, P.J., Kroon, L., Maróti, G., Schrijver, A.: A rolling stock circulation model for combining and splitting of passenger trains. Eur. J. Oper. Res. 174(2), 1281–1297 (2006). https://doi.org/10.1016/j.ejor.2005.03.032
Frisch, S., Hungerländer, P., Jellen, A., Primas, B., Steininger, S., Weinberger, D.: Solving a real-world locomotive scheduling problem with maintenance constraints. Transp. Res. Part B: Methodological 150, 386–409 (2021). https://doi.org/10.1016/j.trb.2021.06.017
Lingaya, N., Cordeau, J.F., Desaulniers, G., Desrosiers, J., Soumis, F.: Operational car assignment at via rail Canada. Transp. Res. Part B: Methodological 36(9), 755–778 (2002). https://doi.org/10.1016/S0191-2615(01)00027-3
Mavrotas, G.: Effective implementation of the \(\varepsilon \)-constraint method in multi-objective mathematical programming problems. Appl. Math. Comput. 213(2), 455–465 (2009). https://doi.org/10.1016/j.amc.2009.03.037
Neufeld, J.S., Scheffler, M., Tamke, F., Hoffmann, K., Buscher, U.: An efficient column generation approach for practical railway crew scheduling with attendance rates. Eur. J. Oper. Res. 293(3), 1113–1130 (2021). https://doi.org/10.1016/j.ejor.2020.12.058
Nishi, T., Ohno, A., Inuiguchi, M., Takahashi, S., Ueda, K.: A combined column generation and heuristics for railway short-term rolling stock planning with regular inspection constraints. Comput. Oper. Res. 81, 14–25 (2017). https://doi.org/10.1016/j.cor.2016.11.025
Reuther, M., Schlechte, T.: Optimization of rolling stock rotations. In: Borndörfer, R., Klug, T., Lamorgese, L., Mannino, C., Reuther, M., Schlechte, T. (eds.) Handbook of Optimization in the Railway Industry. ISORMS, vol. 268, pp. 213–241. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72153-8_10
Rößler, M., et al.: Simulation and optimization of traction unit circulations. In: 2020 Winter Simulation Conference (WSC), pp. 90–101. IEEE (2020). https://doi.org/10.1109/WSC48552.2020.9383926
Scheffler, M., Neufeld, J.S., Hölscher, M.: An MIP-based heuristic solution approach for the locomotive assignment problem focussing on (dis-) connecting processes. Transp. Res. Part B: Methodological 139, 64–80 (2020). https://doi.org/10.1016/j.trb.2020.05.020
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003). https://doi.org/10.1109/TEVC.2003.810758
Acknowledgements
This work was funded in the course of the project VIPES (FFG project number 893963) by the Federal Ministry for Climate Protection, Environment, Energy, Mobility, Innovation and Technology (BMK) as part of the call for proposals Mobilität der Zukunft. FFG is the central national funding organization and strengthens Austria’s innovative power. We also want to thank Matthias Wastian, Senior Data Scientist at dwh GmbH, for providing all the necessary information to formulate the model and use cases to run the algorithm.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Päprer, P., Neufeld, J.S., Buscher, U. (2023). A Bi-Objective Column Generation Approach for Real-World Rolling Stock Circulation Planning Problems. In: Daduna, J.R., Liedtke, G., Shi, X., Voß, S. (eds) Computational Logistics. ICCL 2023. Lecture Notes in Computer Science, vol 14239. Springer, Cham. https://doi.org/10.1007/978-3-031-43612-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-031-43612-3_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43611-6
Online ISBN: 978-3-031-43612-3
eBook Packages: Computer ScienceComputer Science (R0)