Dr Ryo Takagi, Kogakuin University, Tokyo, Japan
Automatic generation of train schedules using computers is a dream shared by railway managers and operators alike. Although its realisation is believed by many to be a distant goal, a joint research project team that includes several Japanese universities has been working with several JR companies, and is actively pursuing ways of using the Sujic programme to develop a system that will support train control on a four-track commuter line belonging to one of them.
The author’s research group at Kogakuin University is one of these research centres. The origin of the group dates back to the 1970s when Professor Satoru Sone, then at the University of Tokyo, launched research on optimising train schedules. At the core of Sone’s proposals was the way train schedules must be evaluated, together with the development of a computer programme to perform simple evaluations.
This must have been one of the first attempts to develop train scheduling methods using a systems engineering approach, which broke away from traditional scheduling done by Suji-ya, meaning men who draw lines on a graph. Sujic is derived from the Japanese word Suji, which means line.
The Sujic concept
The first Sujic programme was written in 1987 by a research student under Professor Sone’s supervision. Two decades later, it is still being maintained and used by undergraduate and research students conducting final-year and MSc projects on train scheduling and/or rescheduling after disruption.
The basic concept underlying Sujic is that evaluation of planned timetables must be approached mainly from a passenger’s point of view. This means that the two most important criteria being optimised are travel time and overcrowding inside the carriages, normally expressed as a percentage congestion rate.
Here it is important to stress that ?using traditional statistics on scheduled train speed and overcrowding to optimise timetables will not be satisfactory. If a train schedule has too many fast trains calling only at stations irrelevant to the majority of passengers, it will not be a good schedule because most passengers cannot benefit from the short travel time provided by those fast trains, even if their average scheduled speed is high.
Also, there is frequently a gap between ‘average congestion’ and what passengers actually experience. Consider two trains, one with twice as many passengers as its rated capacity and the other empty. The average congestion rate is 100% because two trains carry twice the nominal capacity of one. In reality, all the passengers experience severe 200% congestion! For these reasons, Sujic evaluates aggregated passenger travel time and the ‘effective congestion rate’.
Travel time for each passenger is calculated from entering the station of origin to exiting the destination station. The train(s) this passenger will take must be identified, together with the location and time spent changing trains where necessary. Individual travel times are then added to get the aggregated passenger travel time.
The effective congestion rate is the average that passengers experience. Suppose there are n trains and train i has capacity and passengers on board of Ci and Pi respectively; the average congestion rate can be calculated as (SPi) / (SCi). On the other hand, since the passengers on train i will experience congestion Pi/Ci the effective congestion rate is (SPi2/Ci)/(SPi).
A simple passenger flow model is used by the Sujic program to calculate aggregated passenger travel time and the effective congestion rate. Passengers are assumed to take one of two actions. One enters the origin station at a random time and boards the train(s) that will get them to their destination quickest. The other decides what time they need to arrive, and then consults the timetable to find the latest train that will get them there by that time.
If desired, Sujic can be used to estimate the cost of a given timetable to the train operator. This is calculated by aggregating train-hours, representing the cost of the train crews, and car-hours, representing the cost of rolling stock provision.
Timetable evaluation
Intensive use of Sujic was undertaken to evaluate various types of timetables on different railways. One of the most significant achievements that came out of this research was the finding that zonal separation scheduling is ideal for radial commuting railways.
Typically, such railways are predominantly used for travel between a suburban station and the city centre terminus. Zonal scheduling sees these stations grouped by geographical zones, with each zone enjoying a dedicated service calling at all stations after running non-stop through the zones closer to the city (Fig 1).
Compared with timetables combining fast and slow services, zonal timetables have been very successful in increasing line capacity through the zone nearest to the terminus, and shortening travel times without excessively increasing car-hours.
Throughout the research stages, it has been recognised that non-linear evaluation functions must be used for some criteria. For example, research suggests the disbenefit passengers feel when they experience 200% overcrowding is much more than twice the disbenefit of 100% congestion.
In addition, the ‘fairness’ of service provision must be considered. A numerically optimal timetable may serve the interest of the majority of passengers, but it may be unacceptable to impose too much disbenefit on a smaller group of passengers. For example, zonal separation scheduling tends to make travel between suburban stations in different zones more difficult. Such journeys usually require passengers to change trains at a ‘frontier’ station between zones.
Mizuno, in his MSc project at Kogakuin under the supervision of Professor Sone and the author (2007), proposed the use of an ‘OD Service Index’ to evaluate the fairness of a timetable. The basic idea is that the number of passengers between a given pair of stations must have a certain ‘desirable relationship’ with the frequency of trains between them. Note that this relationship is not ‘proportional’.
Automatic generation
Although simplistic, Sujic provides an evaluation tool which can be embedded in an automatic train timetable generator. It will start from an initial timetable and perform an iterative cycle of evaluation, gradually improving it to reach an optimal solution.
As one of the first attempts to generate train schedules automatically, Kaneda’s MSc project in 1994 used a ‘brute force attack’ approach to generate a very complicated train schedule for a four-track railway. Obviously this is not an efficient use of computational resources, and the technique could not be used for practical, large-scale problems.
Thanks to recent advances in the theory and implementation of combinatorial optimisation, the idea of automatic schedule generation now looks very promising with many researchers striving to create such a system. However, it is commonly believed that - at this stage - there is still a huge gap between real-world scheduling and what such software can do today.
Scheduling and rescheduling
Real time rescheduling for train control purposes in response to disruption is as important as creating timetables. This is an area where the development of automatic scheduling systems attracts keen interest, because most railway operators in major countries - including Japan - struggle to provide effective operational control in the event of disruption.
Evaluation tools such as Sujic can also be applied to rescheduling. The functions are similar, in the sense that a timetable is generated for future operation of trains, and numerically very similar methods can be used for both tasks.
However, applying scheduling techniques to rescheduling is not straightforward, mainly because decisions must be made quickly and often under rapidly-changing circumstances using insufficient or inaccurate information on the extent of disruption. Despite rescheduling aids, the line controller must also deal with situations which had not been foreseen when the normal timetable was planned.
Four-track railways
A four-track railway inevitably makes scheduling and line control tasks more complex, although the possibilities for keeping trains moving are greater. Fig 2 shows three arrangements of fast and slow tracks commonly used. The line controller and passengers will normally prefer arrangements (a) and (b) where tracks used by trains in the same direction are adjacent to each other.
This type of four-track railway is generally better than (c), which has two pairs of up and down lines, because passengers normally have cross-platform interchange. In layout (c) passengers must use a footbridge or a subway, and switching a train from the fast track to the slow track or vice versa conflicts with trains going the opposite way — difficult on busy lines.
Around Tokyo the less convenient track layout is widely used. Operationally, a four-track railway of this type is simply two double-track lines in parallel, although the fast line can have longer station intervals and hence faster services.
More sophisticated operation can be done using track layout (a), as on JR West’s Kobe Line (part of the original 1 067 mm gauge Tokaido Main Line) linking the major cities of Osaka and Kobe which are 43 km apart.
The JR Kobe Line has three major classes of trains: all-stations Local, Rapid services with fewer stops, and the fastest New Rapid services. During the day, Local and Rapid services share the slow tracks while New Rapid trains use the fast tracks. However, at Ashiya (Fig 3), an intermediate station served by all three classes, New Rapid and Rapid trains occupy platforms 1 and 4 while Locals occupy platforms 2 and 3. The timetable is designed so that passengers can change between Local and either New Rapid or Rapid trains (Fig 4). Through tracks are provided so that long-distance trains running at off-peak times which do not call at Ashiya can overtake both services while the passengers are interchanging.
Boosting four-track capacity
At the university laboratory level, a four-track railway can have more capacity or capability than two double-track lines. This is made possible by complex use of two tracks. For example, assume there are three classes of trains: fast, semi-fast and slow. Fast and semi-fast trains share the fast track while the slow trains use the slow track. With this arrangement the semi-fast trains must make occasional stops at passing loops to allow fast trains to overtake.
Kaneda (1994) showed that these long stops can be avoided by applying the complex scheduling method, in which each class of trains can run on both tracks. When a fast train approaches the semi-fast train in front, the semi-fast is re-directed to the slow line to make way for the fast instead of waiting in a passing loop.
Similar techniques can be used in train control. Generally, if a disruptive event blocks one track in a four-track line, two tracks will be shut down while the remaining pair keep running. Mizuno (2007) showed that by using all three remaining tracks in such cases the reduction in line capacity can be minimised.
The author is currently part of the joint research project team which is developing a system that will support train control on a four-track commuter line. In this joint research project, evaluation methods like that implemented in Sujic have been used successfully without major problems.
However, some minor issues have arisen which are connected with the fact that interchange between fast and slow tracks in layout (a) is easy. This is not compatible with some assumptions that must be made in ‘simple’ evaluation methods. For example, it is not realistic to believe that passengers will change from one train to another when they are running in parallel with a difference in timings, say, of less than 1 min. Because of its assumptions, in the simple evaluation result passengers are assumed to concentrate on the faster train, even when this train is only 10 sec faster.
This project is still actively pursuing various ways to devise automatic generation of timetables and/or train control decisions, which will probably take the form of a decision-support tool when the development is proved to be successful.
- The author would like to thank Prof Satoru Sone for his assistance with the preparation of this article.
References
In English
Sone S. Squeezing Capacity out of Commuter Lines, Developing Metros 1990, pp 9-12.
Sone S. Novel Train Stopping Patterns for High-Frequency, High-Speed Train Scheduling, Proceedings of the Third International Conference on Computer-Aided Design, Manufacture and Operation in the Railway & Other Advanced Mass Transit Systems (COMPRAIL 92).
Sone. S. High-speed, High-density Train Allocation. Proceedings of the Fourth International Conference on Computer-Aided Design, Manufacture and Operation in the Railway and Other Advanced Mass Transit Systems (COMPRAIL 94).
In Japanese
Sone S and Nakamura T. Evaluation of Train Scheduling Patterns Considering Demand Variation, 1988 National Convention of the IEE of Japan, p1569.
Kaneda H and Sone S. On Train Pathing for High-speed High-density Operation, IEE of Japan Technical Meeting on Transport & Electric Railways, TER-93-46, 1993.
Kaneda H. Automatic Generation of Stopping Patterns of Trains for High-speed High-density Scheduling, University of Tokyo (MSc thesis), 1994.
Mizuno K, Sone S. and Takagi R. Proposal of the OD Service Index to Evaluate Equality of Train Services over OD Pairs. IEE of Japan Technical Meeting on Transport & Electric Railways, TER-06-92, 2006.
Mizuno K, Sone S and Takagi R. Evaluation of Various Types of Train Scheduling Using OD Service Index. National Convention of the IEE of Japan, 5-179, 2007.
Mizuno K. Advanced Train Control Incorporating Active Use of Road Change and Reverse Running, Kogakuin University (MSc thesis), 2007.
