An Optimization Approach to Railway Track Allocation Considering the Train-Set Routings

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.