Railway transportation has a fundamental role in development of countries. Efficient usage of capacities in this industry is essential. Solving Train Timetabling Problem (TTP) is one of the valuable ways to exploit the capacities efficiently. In this book chapter, the author introduces TTP in general, and demonstrates the solution procedure for a special case of it via graph theory techniques.
TopIntroduction
Railway transportation planning is a complicated process which requires simultaneous collaboration and management of different parts of the railway industry. Considering the large size of the problem, the planning process in railway transportation is divided into different steps. These steps are shown in Figure 1.
Figure 1. Railway transportation hierarchical planning process (Ghoseiri et al., 2004)
Number of passengers and quantity of freight between different origins and destinations are recognized in demand analysis and assessment step. In the second step, number and routes of the trains are identified. Through the trains timetabling step, the departure time of the origin stations, the arrival and departure times in intermediate stations and finally arrival times to destination stations will be computed. In the next step, the allocation of locomotives and wagons to each train is identified. Finally, in the last step, crew will be assigned to scheduled trains in two phases. In phase one, set of all missions which cover all trips (i.e. traveling between two consecutive stations) are constructed and in phase two, selected missions in previous phase are organized to produce a crew rostering.
We could divide the railway transportation into passenger and freight sections. Because of the underlying complexity in forecasting the time, the quantity of the freight and number of wagons to carry the required freight, nowadays despite the passenger section, there is no predefined timetabling in the freight section in many countries. To employ the optimum capacity of the railways and remove the negative effects of not scheduled freight trains, we have to consider predefined timetabling for freight trains.
Despite the fright section, the passenger section has special discipline and organization. Timetabling of passenger trains is considered in this chapter. The rest of this chapter is organized as follows: first some general definition of railway transportation industry which are mentioned in this chapter, are explained. Then, the problem of train timetabling is described.
Passenger trains timetabling includes departure times from origin stations, entrance and departure times in intermediate stations and entrance times to the destination stations for planned trains. Passenger trains timetabling literature includes periodic and none-periodic versions of the problem.
The main advantage of periodic timetabling is the fact that it is easy to implement for railway workers and easy to remember for passengers. On the other hand, implementation of periodic timetabling is costly for operators and needs collaboration of different parts of the railway transportation industry. This type of planning introduces one type of timetable for rush and off-peak hours of the day. The only way to encounter this problem is to change the length of the trains in different conditions which is called Rolling Stock circulation. It could have a considerable impact on variable costs of locomotives and workers (Caprara et al., 2007).
None-periodic timetabling is used in case of heavy traffic and long distance between major stations. This timetabling is designed to encounter heavy traffic and the limited capacity of infra-structures. Our focus is on None-periodic timetabling in special case which is described in the next sections.