Bum Hwan Park
OPEN ACCESS
This paper deals with an optimization approach to railway track allocation, which is one of the most important decision problems in the presence of multiple train operating companies (TOCs). In fact there has been deep discussion about how to boost the competition environment in Korean railway since the functional reform in 2004, which at last resulted in introducing a new entrant to high-speed railway passenger transportation market. Finally, in August 2016, two operating companies will compete on the major routes in the Korean high-speed railway network. The infra manager, KR Network, who is responsible for allocating the slots, has been developing their own allocation procedure which partly uses an optimization model for adjusting the times of requested train-paths. But one of the TOCs’ concerns with respect to the adjustment is that their train-set routing plan could be in disorder by the adjustment of the arrival/departure times. Assuming TOCs submit their routing plan as well as their desired train-paths, we present an optimization model and algorithm for track allocation problem, considering the routing plan requested by TOCs. The model is developed on a time-space network, where a train-path can be described as the sequence of the arcs. Based on the network, we developed an column-generation approach to dynamically generate the promising train-paths for each requested one so as to maximize the total profit while preventing the routing plans from disrupting by means of setting up the arcs only among the two successive train-paths in the routing plan. Also we present the experimental results applied to the Korean high-speed railway network.
track allocation, column generation, train-set routing
[1] Borndörfer, R., Grotschel, M., Lukac, S., Mitusch, K., Schlechte, T., Schultz, S. &Tanner, A., An auctioning approach to railway slot allocation. ZIB-Report, 05-45, 2005.
[2] J.-E. Nilsson., Allocation of track capacity: Experimental evidence on the use of priorityauctioning in the railway industry. International Journal of Industrial Organization, 17,pp. 1139–1162, 1999 DOI: 10.1016/S0167-7187(99)00016-8.
[3] Brewer, P.J. & Plott, C.R., A binary conflict ascending price (bicap) mechanism for thedecentralized allocation of the right to use railroads tracks. International Journal ofIndustrial Organization, 14, pp. 857–886, 1996 DOI: 10.1016/0167-7187(96)01014-4.
[4] Parkes, D.C. & Ungar, L.H., An auction-based method for decentralized train scheduling.Proceedings of the Fifth International Conference on Autonomous Agents, 2001.
[5] Caprara, A., Fischetti, M. & Toth, P., Modeling and solving the train timetablingproblem. Operations Research, 50(5), pp. 851–861, 2002.
[6] Caprara, A., Cacchiani, V. & Toth, P., A column generation approach to train timetablingon a corridor. 4OR, 6, pp. 125–142, 2008.
[7] Caprara, A., Cacchiani, V. & Toth, P., Scheduling extra freight trains on railwaynetworks. Transportation Research Part B, 44, pp. 215–231, 2010 DOI: 10.1016/j.trb.2009.07.007.
[8] Ahuja, R.K., Magnanti, T.L. & Orlin, J.B., Network Flows : Theory, Algorithms, andApplications. Prentice Hall: Upper Saddle River, NJ, 1993.
[9] Wosley, L.A., Integer Programming. John Wiley and Sons: Hoboken, NJ, 1998.