The Ideal Train Timetabling Problem

The aim of this paper is to analyze and to improve the current planning process of the passenger railway service. At first, the state-of-the-art in research is presented. However, given the recent changes in legislature allowing competitors in the railway industry, the current way of planning is not sufficient anymore. The original planning is based on the accessibility/mobility concept provided by one carrier, whereas the competitive market consists of several carriers that are driven by the profit. Moreover, the current practice does not define the ideal timetables and thus it is assumed that they evolve incrementally, based on a historical data (train occupation, ticket sales, etc.). And thus, we introduce a definition of an ideal timetable that is expressed using the passenger cost. In order to create the timetables itself, we propose to insert the Ideal Train Timetabling Problem (ITTP) that is solved for each Train Operating Company (TOC) separately, into the planning process. The ITTP approach incorporates the passenger demand in the planning and its aim is to minimize the passenger cost(s). The outcome of the ITTP is the ideal timetables (including connections between the trains and weighted by the demand), which then serve as an input for the traditional Train Timetabling Problem (TTP). The TTP takes into account wishes of each TOC (the ideal timetables) and creates global feasible timetable for the given railway network, while minimizing the changes of the TOCs wishes. The ITTP is in line with the new market structure and it can produce both: non-cyclic and cyclic timetables. The model is tested on the data provided by the Israeli Railways (IR). The instance consists of a full demand OD Matrix of an average working day in Israel during 2008. The results are compared to the current timetable of IR. Due to the large complexity of the model, it is solved using the Column Generation methodology.