Kaspi & Raviv

SERVICE ORIENTED TRAIN TIMETABLING

M. Kaspi and T.Raviv

Department of Industrial Engineering Tel Aviv University

Ramat Aviv, Tel-Aviv 69978

The train planning problem can be divided into several sub‐problems, mainly Line Planning Timetabling, Platforming, Rolling Stock Circulation, and Crew Planning. In this study, we focus on quality of service aspects derived by decisions made during the line planning and timetabling phases. The quality of service is measured in terms of total time spent by the passengers in the railway system, including waiting time at the origin stations, connections and travel time. We formulate an integrated Line planning and Train Timetabling model, devise methods to encode a feasible solution and to quickly evaluate it. We then apply the Cross Entropy meta-heuristic in order to solve the problem. We use the Israeli railway system as a test bed. The timetable created by our algorithm saves about 20% of the total time spent by the passengers in the system as compared to the one currently in use. Similar methods are used to solve a bi-objective problem that considers both operational costs and service level. Pareto dominating solutions are derived.

1. INTRODUCTION AND PROBLEM DEFINITION

Railway operations planning has been practiced since the first trains started working early in the nineteenth century. The train planning problem can be divided into several interrelated sub‐problems, namely Line Planning – deciding which set of lines should be served by the system and in what frequencies subject to total demand for journeys and capacity constraints of trains and of the infrastructure and Train Timetabling – deciding upon the schedule of each train in each line subject to track availability and headway constraints. Other sub-problems that need to be addressed are Track Assignment, Platforming, Rolling Stock Circulation, and Crew Planning. Each of these sub‐problems is computationally hard.

Although in practice, some of the planning work is still being done manually, in the last 40 years planners have been using Decision Support Systems and optimization methods in order to improve the quality of their plans and to save labor. Typically, the planning problem is solved hierarchically in a strategic order such that the solution of each sub‐problem is used as input for the following problems. This solution strategy enables tackling real‐world problems; the disadvantage is that the global optimal solution is lost "on the way." For a comprehensive survey of optimization models see [1] [2] [3].

The development of railway infrastructure takes years, or even decades; therefore, unlike in other transportation systems, the line planning stage is mainly to choose routes between terminals on a given infrastructure. In general, the objective of the Line Planning Process is to balance the tradeoff between operational costs and service quality. Bussieck et al. [4] suggests the minimization of total travel time of all passengers as a good way to model quality service. However, since the timetable at this stage of the planning is unknown, it is impossible to calculate the total travel time. Therefore, previous studies [4] [5] considered service level indirectly by minimizing the total number of transfers or maximizing the number of direct passengers. These objectives do not fully capture the service level. For example, longer lines with many stops may reduce the number of transfers but prolong the travel time of some passengers. A partial remedy for this issue is found in [6] where actual time on board plus some arbitrary penalty for transfers is minimized.

For the Train Timetabling stage some studies focus on finding a feasible timetable [7] while others try to schedule as many trains as possible under a cost or profit criterion [8] [9] [10] [11]. In most studies, the demand pattern is ignored at this stage, assuming it was treated at the Line Planning Stage. However, timetabling considerations may have a significant impact on the quality of service. For a detailed survey of scheduling approaches see [12].

Common practice in passenger transportation is to use cyclic timetables. In a cyclic timetable, each trip is operated in a cyclic way. That is, each period of the timetable is the same. From the passengers' point of view, such timetables are more convenient because all they need to remember are the times in a cycle in which trains arrive at their station. From the planners' point of view, since each event occurs again every cycle, it is enough to plan one cycle, thus reducing the search space dramatically. A mathematical model for the Periodic Event Scheduling Problem (PESP) is developed in [13]. Our method follows similar ideas.

In our study, we focus on creating integrated Line Plans and Timetables with the objective of minimizing the total time that passengers spend in the system. This includes waiting time at station of origin, time on board the trains, and transfer times. The line planning component of our model is restricted to decisions on stopping stations and frequencies while a set of optional routes is given.

In the literature, no other work exists that represents quality of service by the total travel time of all passengers and minimizes it by solving an integrated Line Planning and Timetabling Problem.

The problem that we formulated is solved using the Cross-Entropy (CE) meta-heuristic technique. See [14] [15] [16]. CE is a randomized evolutionary optimization technique that iteratively applies to following two phases:

1.  Generation of a sample random data according to a specified random mechanism.

2.  Updating the parameters of the random mechanism, typically parameters of probability mass functions (PMF), on the basis of this data, to produce a "better" sample in the next iteration.

In the rest of this paper we present a formal definition of the Line Planning and Train Timetabling Problem and apply the CE meta-heuristic technique to solve it. The results of a numerical study based on actual data from the Israeli railway system are then reported.

2. SOLUTION PROCEDURE

In this section we present an effective CE based heuristic for solving the integrated Line Planning and Timetabling problem.

The input of our model consists of:

·  Origin-Destination matrix of passengers for each period of the planning horizon (typically a day).

·  Description of the railway infrastructure including minimal traveling time through each block and minimal dwelling time at each station.

·  Set of possible routes, maximal frequency and priority for each route. Each instance of a route is taken as a possible train in use.

The infrastructure is encoded as undirected graph where edges represent rail blocks and vertices represent either stations, siding or signals. A block is an atomic track section that may normally hold a single train at a time in order to maintain a required safety level while vertices may represent a rail section that can hold several trains at a time. A track segment that connects two vertices may contain several parallel blocks. Routes are directed paths on this graph.

The priorities of the routes are pre-determined by the planner and they define the by-passing order. Maximal frequency can be easily computed by dividing the cycle time by the traveling time on the longest block in the route. Next we present a method to encode a feasible solution in a manner that will be useful for our algorithm. Each possible train is encoded by the following variables

·  IN_USE - Boolean stating whether or not this train is being used.

·  FIRST_TIME - The earliest time (in a cycle) that the train can be inserted at the first block.

·  STOPPING_STATIONS – Set of passenger stations where the train stops. We represent this set by a characteristic (Boolean) vector.

We refer to the above triplet as a “gene.” A feasible solution is represented by a string of genes, one for each possible train. Such a string is referred to as a chromosome.

A chromosome is decoded into a timetable of a single cycle by trying to insert all the trains with true value of IN_USE one at a time in non-increasing priority order. This process is similar to the manual process done by planners. The insertion operation is done after checking whether a time slot is available for the train in all of its blocks starting at the first block from time FIRST_TIME and on. For each block we look for an available time slot that is consistent with the previous one. All times are kept in minutes modulo the cycle length (60 minutes). A train may dwell at a station or siding until the next block becomes available and it must dwell for at least some pre-specified time at each station in STOPPING_STATIONS. Next, the cycle is being duplicated over the planning horizon, usually a day, to create a feasible timetable.

A feasible timetable is evaluated with respect to a series of origin-destination matrix that represent the passenger demand over time. We calculate the total travel time of all the passengers. To accomplish this calculation an events graph is built. Each arrival and departure of trains to or out of a station is represented by a node in this graph. With each node we store the time, the station, and the train of the event. Arcs connect each pair of consecutive events of a train and each pair of consecutive events in a station. For each node in this graph we calculate the earliest reachability time to each station[1]. A specialized reachability algorithm was devised taking advantage of the special structure of the graph (i.e., directed acyclic with maximal out degree of two) and the fact that we are only interested in reachability to the earliest node of each station. The running time of this algorithm is linear in the number of events times the number of stations, i.e., in its output size.

The total travel time of a passenger is the difference between the first reachable time to the destination and his arrival time at the origin station. This calculation is valid under the assumption that the capacity of the trains is not a binding constraint.

We have developed fast methods to encode and generate a feasible cyclic timetable and to evaluate its service quality. This calls for a heuristic approach that will allow us to examine a large amount of solutions and the CE meta-heuristic technique is an attractive alternative.

We randomized a generation of chromosomes using the following multidimensional distribution function. The probability of IN_USE and the STOPPING_STATIONS being true are determined by Bernoulli random variables and FIRST_TIME is drawn from some general discrete (empirical) distribution. Initially the probability of all the Bernoulli random variables is set to 0.5 and the empirical distribution of FIRST_TIME for each train is uniform over some portion of the cycle. After a generation is created and evaluated, this distribution function is updated based on the elite set (e.g., the best 10% solutions) as follows: The probability of the Bernoulli random variables is set to the frequency of the true values and the distribution of FIRST_TIME is calculated based on the empirical distribution. The new distribution function is exponentially smoothed by a weighted average with the distribution function of the previous generation. When the distribution parameters tend to degenerate into a deterministic value the algorithm is stopped.

3. NUMERICAL EXPERIMENTS

We used the Israeli train network as a test bed. This system is composed of some 47 passenger stations, 130 blocks, and 22 sidings and operational stations. There are 14 inbound routes and 14 outbound routes. The infrastructure consists of both uni- and bi-directional blocks. We constructed cyclic timetables based on these 28 routes. The timetable created by our algorithm can save about 20% of the total travel time as compared to the current one. The construction and evaluation of a single timetable of this network size takes in average 80 milliseconds. The CE algorithm with a generation size of 1000 typically converges in few hours. The same algorithm was used to solve a bi-objective problem to explore the tradeoff between operational costs and service level and some solutions that dominate the currently used schedules with respect to both objectives were found. For example we obtained a solution with operational cost similar to the one currently in use that reduces the total traveling time of passengers by 11%.

4. CONCLUSION

The service level provided to the passengers in a railway system should be measured by their total travel time including waiting times. Integration of Line Planning and Timetabling process is required in order to allow effective optimization of this measure. We devised a method that enables us to solve this integrated problem based on the CE meta-heuristic. This is the first application of this meta-heuristic in the domain of train planning. The solution encoding used by our method can be used in other meta-heuristics such as Genetic Algorithm, Simulated Annealing and Tabu Search.

5. REFERENCES

[1]  J.-F. Cordeau, P. Toth, and D.Vigo, “A survey of optimization models for train routing and scheduling”, Transportation Science 32, no. 4 (1998): 380-404.

[2]  A. Caprara, L. Kroon, M. Monaci, M. Peeters, P. Toth (2006) “Passenger railway optimization.” In: Barnhart C, Laporte G (eds) Handbooks in operations research and management science, vol 14. Elsevier, Amsterdam, 129–187.

[3]  M. R. Bussieck, T.Winter and U. T. Zimmermann, "Discrete optimization in public rail transport". Mathematical Programming,79 (1997) 415-444.

[4]  M. R. Bussieck, P. Kreuzer and U. T. Zimmermann, “Optimal Lines for Railway Systems”, Eur. J. Operational Res, 96 (1996) 54–63.