Bridging the gap between infrastructure capacity allocation and market-oriented railway: an algorithmic approach
Abstract
The European Commission initiated the process of liberalization and introducing competition in the European railway sector more than twenty-five years ago. Despite the liberalization of the railway sector, train paths are currently administratively allocated in all EU countries using the train service priority criterion, which may not treat all train operators equally. This is especially evident in those network sections where demand exceeds the available capacity. In these situations, economic theory suggests the implementation of a market-based mechanism for allocation of capacity, such as auctions. However, due to its incompatibilities with priority criteria in the process of the capacity allocation, it is necessary to develop a new procedure to support the implementation of an auction. In this paper, the proposed algorithm fills the technological gap between train timetable design and train operator requests. The new algorithm for decentralized capacity allocation is the result of a multidimensional approach, which encompasses setting new relations between train operators and the infrastructure manager, train timetable drafting and resolving the conflicting request. In addition, the algorithm provides a feasible solution ensuring equal treatment of train operators and efficient allocation, in order to foster the development of the competition in the European rail market.
First published online 10 September 2019
Keyword : railway capacity allocation, decentralized approach, train path auction, railway market, timetable design, technological gap
How to Cite
Stojadinović, N., Bošković, B., & Bugarinović, M. (2019). Bridging the gap between infrastructure capacity allocation and market-oriented railway: an algorithmic approach. Transport, 34(6), 708-721. https://doi.org/10.3846/transport.2019.11035
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Affuso, L. 2003. Auctions of rail capacity?, Utilities Policy 11(1): 43–46. https://doi.org/10.1016/S0957-1787(02)00057-7
Bablinski, K. 2016. A game-based analysis of freight paths allocation with a case study on Great Britain Brighton main line, Transportation Research Procedia 13: 196–208. https://doi.org/10.1016/j.trpro.2016.05.020
Bassanini, A.; La Bella, A.; Nastasi, A. 2002. Allocation of railroad capacity under competition: a game theoretic approach to track time pricing, Applied Optimization 63: 1–17. https://doi.org/10.1007/978-1-4757-6871-8_1
Bergantino, A. S.; Capozza, C.; Capurso, M. 2015. The impact of open access on intra- and inter-modal rail competition. A national level analysis in Italy, Transport Policy 39: 77–86. https://doi.org/10.1016/j.tranpol.2015.01.008
Beria, P.; Quinet, E.; De Rus, G.; Schulz, C. 2012. A comparison of rail liberalisation levels across four European countries, Research in Transportation Economics 36(1): 110–120. https://doi.org/10.1016/j.retrec.2012.03.014
Borndörfer, R.; Grötschel, M.; Lukac, S.; Mitusch, K.; Schlechte, T.; Schultz, S.; Tanner, A. 2006. An auctioning approach to railway slot allocation, Competition and Regulation in Network Industries 1(2): 163–196. https://doi.org/10.1177/178359170600100204
Brewer, P. J.; Plott, C. R. 1996. A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks, International Journal of Industrial Organization 14(6): 857–886. https://doi.org/10.1016/0167-7187(96)01014-4
Burdett, R. L.; Kozan, E. 2010. A disjunctive graph model and framework for constructing new train schedules, European Journal of Operational Research 200(1): 85–98. https://doi.org/10.1016/j.ejor.2008.12.005
Caprara, A.; Kroon, L.; Monaci, M.; Peeters, M.; Toth, P. 2007. Passenger railway optimization, Handbooks in Operations Research and Management Science 14: 129–187. https://doi.org/10.1016/S0927-0507(06)14003-7
CER. 2017. Public Service Rail Transport in the European Union: an Overview. Community of European Railway and Infrastructure Companies (CER), Brussels, Belgium. 144 p. Available from Internet: http://www.cer.be/publications/latest-publications/public-service-rail-transport-european-union-overview
EC. 2019. Fourth Railway Package of 2016. Available from Internet: https://ec.europa.eu/transport/modes/rail/packages/2013_en
EC. 2016. Commission Implementing Regulation (EU) 2016/545 of 7 April 2016 on Procedures and Criteria Concerning Framework Agreements for the Allocation of Rail Infrastructure Capacity. Available from Internet: http://data.europa.eu/eli/reg_impl/2016/545/oj
EC. 2014. Report from the Commission to the Council and the European Parliament: Fourth Report on Monitoring Development of the Rail Market. Available from Internet: https://ec.europa.eu/transport/modes/rail/market/market_monitoring_en
EC. 2012. Directive 2012/34/EU of the European Parliament and of the Council of 21 November 2012 Establishing a Single European Railway Area. Available from Internet: http://data.europa.eu/eli/dir/2012/34/oj
EC. 2001. Directive 2001/14/EC of the European Parliament and of the Council of 26 February 2001 on the Allocation of Railway Infrastructure Capacity and the Levying of Charges for the Use of Railway Infrastructure and Safety Certification. Available from Internet: http://data.europa.eu/eli/dir/2001/14/oj
EC. 1991. Council Directive 91/440/EEC of 29 July 1991 on the Development of the Community’s Railways. Available from Internet: http://data.europa.eu/eli/dir/1991/440/oj
ECMP. 2005. Railway Reform and Charges for the Use of Infrastructure. European Conference of Ministers of Transport (ECMT); Organisation for Economic Cooperation and Development (OECD) Paris, France: OECD Publishing. (OECD), Paris, France. 134 p. https://doi.org/10.1787/9789282103524-en
EEIG Corridor Rhine–Alpine EWIV. 2011. Rail Freight Companies Present their Requirements for the Corridor Rotterdam–Genoa. Available from Internet: https://www.corridor-rhine-alpine.eu/news-detail/rail-freight-companies-present-their-requirements-for-the-corridor-rotterdam-genoa.html
Eurostat. 2018. Statistical pocketbook 2018: EU Transport in Figures. 164 p. Available from Internet: https://publications.europa.eu/en/publication-detail/-/publication/52f721ed-c6b811e8-9424-01aa75ed71a1
Gibson, S. 2003. Allocation of capacity in the rail industry, Utilities Policy 11(1): 39–42. https://doi.org/10.1016/S0957-1787(02)00055-3
Jansson, K.; Lang, H. 2013. Rail infrastructure charging EU-directive, Swedish concerns and theory, Research in Transportation Economics 39(1): 285–293. https://doi.org/10.1016/j.retrec.2012.06.026
Klabes, S. G. 2010. Algorithmic Railway Capacity Allocation in a Competitive European Railway Market. PhD Dissertation. RWTH Aachen University, Germany. 209 p. Available from Internet: http://darwin.bth.rwth-aachen.de/opus/volltexte/2010/3134
Kozan, E.; Burdett, R. 2005. A railway capacity determination model and rail access charging methodologies, Transportation Planning and Technology 28(1): 27–45. https://doi.org/10.1080/0308106052000340378
Levy, S.; Peña-Alcaraz, M.; Prodan, A.; Sussman, J. M. 2015. Analyzing financial relationship between railway industry players in shared railway systems: train operator’s perspective, Transportation Research Record: Journal of the Transportation Research Board 2475: 27–36. https://doi.org/10.3141/2475-04
Luan, X.; Corman, F.; Meng, L. 2017. Non-discriminatory train dispatching in a rail transport market with multiple competing and collaborative train operating companies, Transportation Research Part C: Emerging Technologies 80: 148–174. https://doi.org/10.1016/j.trc.2017.04.011
Matthews, B.; Evangelinos, C.; Johnson, D.; Meunier, D. 2009. Impacts and incentives of differentiated rail infrastructure charges in Europe – focus on freight, European Transport \ Trasporti Europei 43: 83–112.
Milgrom, P. 2004. Putting Auction Theory to Work. Cambridge University Press. 396 p. https://doi.org/10.1017/CBO9780511813825
Nash, C. 2005. Rail infrastructure charges in Europe, Journal of Transport Economics and Policy 39(3): 259–278.
Nilsson, J.-E. 2015. Congestion and scarcity in scheduled transport modes, in C. Nash (Ed.). Handbook of Research Methods and Applications in Transport Economics and Policy, 134–153. https://doi.org/10.4337/9780857937933.00014
Nilsson, J.-E. 2002. Towards a welfare enhancing process to manage railway infrastructure access, Transportation Research Part A: Policy and Practice 36(5): 419–436. https://doi.org/10.1016/S0965-8564(01)00011-8
Osborne, M. J. 2004. Publicly-Available Solutions for an Introduction to Game Theory. University of Toronto, Canada. 87 p.
Pachl, J. 2009. Railway Operation and Control. VTD Rail Publishing. 255 p.
Peña-Alcaraz, M. 2015. Analysis of Capacity Pricing and Allocation Mechanisms in Shared Railway Systems. PhD Dissertation. Massachusetts Institute of Technology, US. 194 p. Available from Internet: http://dspace.mit.edu/handle/1721.1/99564
Perennes, P. 2017. Open Access for Rail Passenger Services in Europe: lesson learnt from forerunner countries, Transportation Research Procedia 25: 358–367. https://doi.org/10.1016/j.trpro.2017.05.413
Perennes, P. 2014. Use of combinatorial auctions in the railway industry: can the “invisible hand” draw the railway timetable?, Transportation Research Part A: Policy and Practice 67: 175–187. https://doi.org/10.1016/j.tra.2014.07.002
Quinet, E. 2003. Short term adjustments in rail activity: the limited role of infrastructure charges, Transport Policy 10(1): 73–79. https://doi.org/10.1016/S0967-070X(02)00047-1
Rassenti, S. J.; Smith, V. L.; Bulfin, R. L. 1982. A combinatorial auction mechanism for airport time slot allocation, The Bell Journal of Economics 13(2): 402–417. https://doi.org/10.2307/3003463
Schlechte, T. 2012. Railway Track Allocation: Models and Algorithms. Dissertation. Technical University of Berlin, Germany. 244 p. Available from Internet: http://www.zib.de/schlechte/phdthesis.pdf
Stern, J.; Turvey, R. 2003. Auctions of capacity in network industries, Utilities Policy 11(1): 1–8. https://doi.org/10.1016/S0957-1787(02)00062-0
Talebian, A.; Zou, B.; Peivandi, A. 2018. Capacity allocation in vertically integrated rail systems: A bargaining approach, Transportation Research Part B: Methodological 107: 167–191. https://doi.org/10.1016/j.trb.2017.12.001
Woodburn, A. 2014. Development of rail freight in Europe: What Regulation Can and Cannot Do: United Kingdom Case Study. Centre on Regulation in Europe (CERRE), Brussels, Belgium. 43 p. Available from Internet: http://www.cerre.eu/sites/cerre/files/141211_CERRE_RailFreight_UK_Case_Study_Final.pdf
Bablinski, K. 2016. A game-based analysis of freight paths allocation with a case study on Great Britain Brighton main line, Transportation Research Procedia 13: 196–208. https://doi.org/10.1016/j.trpro.2016.05.020
Bassanini, A.; La Bella, A.; Nastasi, A. 2002. Allocation of railroad capacity under competition: a game theoretic approach to track time pricing, Applied Optimization 63: 1–17. https://doi.org/10.1007/978-1-4757-6871-8_1
Bergantino, A. S.; Capozza, C.; Capurso, M. 2015. The impact of open access on intra- and inter-modal rail competition. A national level analysis in Italy, Transport Policy 39: 77–86. https://doi.org/10.1016/j.tranpol.2015.01.008
Beria, P.; Quinet, E.; De Rus, G.; Schulz, C. 2012. A comparison of rail liberalisation levels across four European countries, Research in Transportation Economics 36(1): 110–120. https://doi.org/10.1016/j.retrec.2012.03.014
Borndörfer, R.; Grötschel, M.; Lukac, S.; Mitusch, K.; Schlechte, T.; Schultz, S.; Tanner, A. 2006. An auctioning approach to railway slot allocation, Competition and Regulation in Network Industries 1(2): 163–196. https://doi.org/10.1177/178359170600100204
Brewer, P. J.; Plott, C. R. 1996. A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks, International Journal of Industrial Organization 14(6): 857–886. https://doi.org/10.1016/0167-7187(96)01014-4
Burdett, R. L.; Kozan, E. 2010. A disjunctive graph model and framework for constructing new train schedules, European Journal of Operational Research 200(1): 85–98. https://doi.org/10.1016/j.ejor.2008.12.005
Caprara, A.; Kroon, L.; Monaci, M.; Peeters, M.; Toth, P. 2007. Passenger railway optimization, Handbooks in Operations Research and Management Science 14: 129–187. https://doi.org/10.1016/S0927-0507(06)14003-7
CER. 2017. Public Service Rail Transport in the European Union: an Overview. Community of European Railway and Infrastructure Companies (CER), Brussels, Belgium. 144 p. Available from Internet: http://www.cer.be/publications/latest-publications/public-service-rail-transport-european-union-overview
EC. 2019. Fourth Railway Package of 2016. Available from Internet: https://ec.europa.eu/transport/modes/rail/packages/2013_en
EC. 2016. Commission Implementing Regulation (EU) 2016/545 of 7 April 2016 on Procedures and Criteria Concerning Framework Agreements for the Allocation of Rail Infrastructure Capacity. Available from Internet: http://data.europa.eu/eli/reg_impl/2016/545/oj
EC. 2014. Report from the Commission to the Council and the European Parliament: Fourth Report on Monitoring Development of the Rail Market. Available from Internet: https://ec.europa.eu/transport/modes/rail/market/market_monitoring_en
EC. 2012. Directive 2012/34/EU of the European Parliament and of the Council of 21 November 2012 Establishing a Single European Railway Area. Available from Internet: http://data.europa.eu/eli/dir/2012/34/oj
EC. 2001. Directive 2001/14/EC of the European Parliament and of the Council of 26 February 2001 on the Allocation of Railway Infrastructure Capacity and the Levying of Charges for the Use of Railway Infrastructure and Safety Certification. Available from Internet: http://data.europa.eu/eli/dir/2001/14/oj
EC. 1991. Council Directive 91/440/EEC of 29 July 1991 on the Development of the Community’s Railways. Available from Internet: http://data.europa.eu/eli/dir/1991/440/oj
ECMP. 2005. Railway Reform and Charges for the Use of Infrastructure. European Conference of Ministers of Transport (ECMT); Organisation for Economic Cooperation and Development (OECD) Paris, France: OECD Publishing. (OECD), Paris, France. 134 p. https://doi.org/10.1787/9789282103524-en
EEIG Corridor Rhine–Alpine EWIV. 2011. Rail Freight Companies Present their Requirements for the Corridor Rotterdam–Genoa. Available from Internet: https://www.corridor-rhine-alpine.eu/news-detail/rail-freight-companies-present-their-requirements-for-the-corridor-rotterdam-genoa.html
Eurostat. 2018. Statistical pocketbook 2018: EU Transport in Figures. 164 p. Available from Internet: https://publications.europa.eu/en/publication-detail/-/publication/52f721ed-c6b811e8-9424-01aa75ed71a1
Gibson, S. 2003. Allocation of capacity in the rail industry, Utilities Policy 11(1): 39–42. https://doi.org/10.1016/S0957-1787(02)00055-3
Jansson, K.; Lang, H. 2013. Rail infrastructure charging EU-directive, Swedish concerns and theory, Research in Transportation Economics 39(1): 285–293. https://doi.org/10.1016/j.retrec.2012.06.026
Klabes, S. G. 2010. Algorithmic Railway Capacity Allocation in a Competitive European Railway Market. PhD Dissertation. RWTH Aachen University, Germany. 209 p. Available from Internet: http://darwin.bth.rwth-aachen.de/opus/volltexte/2010/3134
Kozan, E.; Burdett, R. 2005. A railway capacity determination model and rail access charging methodologies, Transportation Planning and Technology 28(1): 27–45. https://doi.org/10.1080/0308106052000340378
Levy, S.; Peña-Alcaraz, M.; Prodan, A.; Sussman, J. M. 2015. Analyzing financial relationship between railway industry players in shared railway systems: train operator’s perspective, Transportation Research Record: Journal of the Transportation Research Board 2475: 27–36. https://doi.org/10.3141/2475-04
Luan, X.; Corman, F.; Meng, L. 2017. Non-discriminatory train dispatching in a rail transport market with multiple competing and collaborative train operating companies, Transportation Research Part C: Emerging Technologies 80: 148–174. https://doi.org/10.1016/j.trc.2017.04.011
Matthews, B.; Evangelinos, C.; Johnson, D.; Meunier, D. 2009. Impacts and incentives of differentiated rail infrastructure charges in Europe – focus on freight, European Transport \ Trasporti Europei 43: 83–112.
Milgrom, P. 2004. Putting Auction Theory to Work. Cambridge University Press. 396 p. https://doi.org/10.1017/CBO9780511813825
Nash, C. 2005. Rail infrastructure charges in Europe, Journal of Transport Economics and Policy 39(3): 259–278.
Nilsson, J.-E. 2015. Congestion and scarcity in scheduled transport modes, in C. Nash (Ed.). Handbook of Research Methods and Applications in Transport Economics and Policy, 134–153. https://doi.org/10.4337/9780857937933.00014
Nilsson, J.-E. 2002. Towards a welfare enhancing process to manage railway infrastructure access, Transportation Research Part A: Policy and Practice 36(5): 419–436. https://doi.org/10.1016/S0965-8564(01)00011-8
Osborne, M. J. 2004. Publicly-Available Solutions for an Introduction to Game Theory. University of Toronto, Canada. 87 p.
Pachl, J. 2009. Railway Operation and Control. VTD Rail Publishing. 255 p.
Peña-Alcaraz, M. 2015. Analysis of Capacity Pricing and Allocation Mechanisms in Shared Railway Systems. PhD Dissertation. Massachusetts Institute of Technology, US. 194 p. Available from Internet: http://dspace.mit.edu/handle/1721.1/99564
Perennes, P. 2017. Open Access for Rail Passenger Services in Europe: lesson learnt from forerunner countries, Transportation Research Procedia 25: 358–367. https://doi.org/10.1016/j.trpro.2017.05.413
Perennes, P. 2014. Use of combinatorial auctions in the railway industry: can the “invisible hand” draw the railway timetable?, Transportation Research Part A: Policy and Practice 67: 175–187. https://doi.org/10.1016/j.tra.2014.07.002
Quinet, E. 2003. Short term adjustments in rail activity: the limited role of infrastructure charges, Transport Policy 10(1): 73–79. https://doi.org/10.1016/S0967-070X(02)00047-1
Rassenti, S. J.; Smith, V. L.; Bulfin, R. L. 1982. A combinatorial auction mechanism for airport time slot allocation, The Bell Journal of Economics 13(2): 402–417. https://doi.org/10.2307/3003463
Schlechte, T. 2012. Railway Track Allocation: Models and Algorithms. Dissertation. Technical University of Berlin, Germany. 244 p. Available from Internet: http://www.zib.de/schlechte/phdthesis.pdf
Stern, J.; Turvey, R. 2003. Auctions of capacity in network industries, Utilities Policy 11(1): 1–8. https://doi.org/10.1016/S0957-1787(02)00062-0
Talebian, A.; Zou, B.; Peivandi, A. 2018. Capacity allocation in vertically integrated rail systems: A bargaining approach, Transportation Research Part B: Methodological 107: 167–191. https://doi.org/10.1016/j.trb.2017.12.001
Woodburn, A. 2014. Development of rail freight in Europe: What Regulation Can and Cannot Do: United Kingdom Case Study. Centre on Regulation in Europe (CERRE), Brussels, Belgium. 43 p. Available from Internet: http://www.cerre.eu/sites/cerre/files/141211_CERRE_RailFreight_UK_Case_Study_Final.pdf