A New Optimization Model For Railway Slot Allocation

Abstract

This study addresses a railway slot allocation model for the case of multiple competing train operating companies (TOC). The auction-based mechanisms have been studied by some researchers, to efficiently allocate the railway slots to TOCs. But the use of such approaches requires the solving of the associated winner determination problem, which can be modelled as a type of timetabling. We consider the profit-maximizing slot allocation problem, where the profit is reduced linearly depending on the deviation from the requested time. Our study suggests a new optimization model based on path-flow variables in a time-space network and a column generation approach using this formulation. The associated subproblem of finding a new path then simply becomes one of finding a shortest path for each requested slot. Compared to other approaches, our approach has the advantage of easily reflecting combinatorial bids like AND or XOR bid. We also present the experimental results applying our approach to a small network.