Train Rescheduling Plan Generation Based on Train Route Combination Considering Rolling Stock Types

Railway transport is generally considered safe and punctual, but sometimes the transport cannot operate according to the scheduled timetable due to traffic accidents or natural disasters.

Train rescheduling means a transient situation to correct a suspended state and involves swapping the departure order and changing the turning or terminal station. A short delay of a few minutes which can be solved by a shorter turning time at the terminal station is not included in the above explanation of train rescheduling.

For train rescheduling, operators need both an exact prediction concerning the operation time resumption and a quick generation of the train rescheduling timetable after the resumption time. When a traffic accident suddenly happens, a rescheduling timetable has to be generated quickly, within 5–10 min.

A rescheduling timetable used to be generated by expert operators, but the number of operators was decreased due to management streamlining, and now this work has to be processed automatically. Computer processor performance has improved and processors are able to solve realistic size problems, see for example Kunimatsu et al. [1] and Takagi [2]. Many railway companies use programmed traffic control systems, and the timetable data are kept and processed on such computer systems. Therefore, automatic rescheduling became fit for computers, because manual converting is not needed according to [3]. In general, there are many circumstances to be taken under consideration, such as the location of turning facilities on the tracks, trains location, and so on. However, automatic generation is realized only under limited conditions For example, Ochiai and Nakamura [4] succeeded in quick turning back operations based on registered operation patterns taking into account only the time zone and accident location.

Recently trendy methods use software tool, such as mixed integer programming, thus often the main research aim is a description of how the tool can provide a solution, for example Keeman et al. [5] or Veelenturf et al. [6].

Imada and Tomii [7] used mixed integer linear planning to solve turning back operations. A train rescheduling algorithm considering rolling stock is also being researched, for example, Haahr et al. [8] use a mixed integer linear program, Dollevoet et al. [9] report changing track at the station for delay, and so on.

Abroad, most operation types are a spider pattern in a wide area with a relatively low density operation. In contrast, for Japanese urban railways, the numbers of tracks at the station is limited, trains are turning back on a double track between limited sections, and rolling stock types of different companies operate on each other’s sections. The rescheduling methods used abroad do not necessarily fit the Japanese operation style. Therefore, we suggest a rescheduling method which does not use integer planning tools. This method depends on computing power, but is realized only thanks to computer performance improvement.

Companies running on through other company facilities to accommodate passengers face issues such as running area restrictions for different rolling stock types. This limitation makes rescheduling difficult.

This study’s purpose is the automatic generation of a train rescheduling timetable. We are specifically considering operated rolling stock types, and we describe how to generate a rescheduling timetable based on Katori and Izumi [10]. This method adopts only turning operation on double tracks as is usual in Japanese urban areas. The rescheduled timetable has to satisfy two limitations, namely certain track areas are bound to certain rolling stock types, and more than one train cannot be positioned at the same location at the same time. To solve these limitations, the track layout is managed by dividing the time interval system into data blocks. Train routes are registered based on the tracks between start and terminal stations based on running time. The rescheduling timetable is composed with combinations of these routes.

This rescheduling procedure has four parameters: traffic accident happening time, communication time for all trains, resumption time for each rolling stock and time of recovery to scheduled conditions. We compare some rescheduled timetables based on variations of the above parameters. The combinations are searched for by round robin. Thus, solutions that indicate a possible operation are definitely included as possible candidates. Generated rescheduling plans are evaluated for passenger convenience. The evaluation values are aver- age headway time at each station for both directions and standard deviation time.

By applying this method to several scheduled timetables on modelled tracks, finally, we show that the method can generate rescheduling timetables under different conditions.

When generating rescheduling timetables, we are especially considering rolling stock types because some companies are running through each other’s sections, and some rolling stock types with a limited running area are running intermingled in Japanese urban areas.

Train rescheduling timetables are generated under the following assumptions

– train operation unit time is 15 s,

– minimum headway time between trains is 2 min

– minimum dwell time is 5 min for the turning operation, and 30 s at the other middle stations,

– running time between stations is the same on the scheduled timetable as on the rescheduling timetable. Trains stop at stations only, do not stop between stations and do not operate at slow speed,

– all rolling stocks have the same driving performance,

– trains are never partitioned or combined.

There are two rescheduling methods when a traffic accident happens.

One is closing all the tracks, and the resumption of operation time happens at the same moment for all the tracks. The other one is closing only one part of the tracks, and trains are turning back around the closed-off area.

In this paper, we consider rolling stock types, and we describe how to generate rescheduling timetables for both methods, namely closing off all the tracks and including turning back operation around a part of the closed-off tracks. Each pausing time for rolling stocks is initialized due to a traffic accident, and train routes do not cross the accident location.

Figure 1 shows the rescheduling difference. In the latter method, setting the same pausing time for all rolling stocks results in the same rescheduling timetable as when the complete area is closed off.

A train diagram expresses a traced graph which indicates the train location versus time. For the diagram expression, three data types are used, namely track layout and location data which is divided in blocks, relation of the location versus time data, and possible route data for each rolling stock.

The track layout is divided by data blocks based on running time. The unit time is 15 s as indicated in the assumptions. The track layout is expressed by blocks considering both time and distance.

Figure 2 shows an example of block division for a sample track layout, and the data concerning the block number and the location from the terminal.

The block sections differ from real signalling sections, because this model is a theoretically simple model. If the unit time is shorter (10, 5, …, 1 s) , the sections can express a more detailed solution than signalling sections.

Train diagram data express a row of track layout block numbers, and train location versus time. Each rolling stock operates differently, and the rolling stocks continue to have location data after turning at the terminal station.

Table 1 shows a data form for a train schedule, and Figure 3 is a train diagram based on Table 1.

Route data are already combined in the scheduled operation. Therefore, these data are only needed for rescheduling.

Route data contain information about possible routes, required time and possible rolling stocks for a particular route between start and terminal stations.

Blue arrows indicate routes from the upper left track, and the red ones from the middle right track. All possible routes are registered per rolling stock type, between all turning tracks.

Four parameters have to be provided to generate a timetable,

– Time and location of the traffic accident,

– Time needed to communicate the traffic accident to all trains,

– Pausing time for each rolling stock,

– Time of recovery to scheduled condition.

Figure 5 shows these parameters on the train diagram.

The time and location of the traffic accident is provided in the timetable data format in Section 3.1.2.

The time needed to communicate the traffic accident to all trains means the delay that is required till all other trains are informed. The train in the accident stops immediately, but other trains continue to run on the scheduled timetable until they receive the accident information. All trains stop after this communication time.

The pausing time data for each train is an indication for the period each train should be stopped after the time the accident happened plus the communication time with other trains. The trains which did not cause the traffic accident resume operation soon, but the accident train continues to stop t minutes. For example, train No.1 pauses 60 min, but on the other hand, train No.2 pauses only 10 min and can resume operation even if train No.1 is still paused.

Time of recovery to scheduled conditions means the end of the rescheduling operation time. The rescheduling timetable is generated between the resumption and time of recovery to scheduled conditions.

All trains stop at the accident time or the communication time. The stopping location is the nearest stopping station for each train. Trains are operated by the rescheduling timetable after the resumption time. First, new destination stations are redefined for all trains. It is important to determine the destination for each train at resumption time. More than one train cannot be located on the same track at the same time, and generally, trains change to a nearer destination, but do not change to a farther destination because the rolling stocks have limitations concerning running-through operation.

In this proposed generation method, each train’s destination station remains the same as the original one. Even if several trains turn at the terminal station on the same track, most trains arrive at the destination at different times. When several trains arrive at the station at the same time, route conflict is avoided by using other tracks. When the accident train stops on a block section during rescheduling, other trains cannot run through that section and they change to a nearer destination.

Also, each train is not necessarily located at its start station on the scheduled timetable at the time of recovery to scheduled conditions. Therefore, the origin station and starting time are redefined for running trains at time of recovery to scheduled conditions.

Figure 6 shows pre-processed results for Figure 1. Train diagrams are added until the destination station after the resumption time and from the origin station before time of recovery to scheduled conditions.

A rescheduling timetable is calculated between the new origin station at the starting time and the destination at the time of recovery to scheduled conditions for each train. This time is called rescheduling time.

If each rolling stock is not on the location of the original scheduling diagram at the time of recovery to scheduled conditions, there is no problem if the same rolling stock type operates at that location and direction. Therefore, same rolling stock type connection at the time of recovery to scheduled conditions is also an important condition.

In this paper, this is also set as a parameter, and the rolling stock connection effect is compared.

Figure 7 shows some connections for rolling stock operation. Figure 7(a) indicates the trains connecting with the original operation and (b) indicates a substitution between same type rolling stocks.

In both Figs. 7(a) and (b), the red and purple train are using the same rolling stock type which can run until the middle turning station. In this case, it is possible to substitute the red train for the purple one, or the purple one for the red one in Fig. 7(b).

A train rescheduling timetable is generated as a route combination for each train, between destination station arrival time after resumption time and origin station starting time before time of recovery to scheduled conditions. If this route includes the accident location with the accident train still stopped, this route is eliminated as solution.

All possible train routes between any turning stations during rescheduling time are investigated. For this procedure, route data of Section 3.1.3 are used, and all possible route combinations are investigated recursively by round robin and saved. This investigation uses the start and terminal track number and required time. The total required time should be shorter than the rescheduling one. This investigation can be considered a knapsack problem with a limitation, where the terminal track number g_i in route R_i must be the start track number s_i+1 in next route R_i+1.

If the rescheduling time is rtime, this relation gives the inequality.

Because the route data includes the possible rolling stock types for a specific route, only route combinations for possible areas are generated. This route is a tree data structure based on different destinations for turning operation. Routes are searched for all running trains.

Figure 8 shows examples of route combinations. For one train, several route combinations exist. Possible routes are checked for all trains, and all the combinations are searched for by round robin. Only the combination that can be used in reality becomes the rescheduling timetable solution.

When different rolling stock types are in use, the trains can substitute their operation with trains of the same type. These substitution combinations are also searched for by round robin.

All routes which have a shorter total time than the rescheduling time are able to become candidate solutions. Whatever time remains is distributed to the initial waiting time. Because this method cannot distribute soft buffer waiting time in the rescheduling time, the reschedule

plan might be tight or without solution cases.

A rescheduling timetable is generated with all obtained route combinations for all trains. These combinations include cases where more than one train is located at the same time and on the same track. Such cases are rejected as impossible operation solutions. For each train i and j, location L in time t, if the following equation gives then a backtrack procedure is adopted, and computation time decreases. This way crossing hindrance is also avoided. When trains are not located on the same track, the route combina- tions that do not maintain the minimum headway time are rejected.

This method uses round robin. Therefore, a final solution is selected from among the several possible operating candidate solutions, based on the evaluation functions. Deciding on how to set these evaluation functions is an important issue.

The quality of the generated rescheduling timetable is evaluated, and the best solution is adopted. Generated rescheduling timetables are evaluated for average headway time at each station and standard deviation. For passenger convenience, a shorter average headway time results in a higher number of trains and a higher number of passengers transported. However, the distribution of number of trains per hour cannot be decided only by this. Therefore, standard deviation is used to uniformly distribute the train headway time, and ensure even distribution of passenger numbers on the trains. This type of evaluation may not seem to be considering passengers demand and convenience directly, but shorter average headway time means high boarding chance, and smaller standard deviation means equalized passenger distribution per train. Therefore, the evaluation considers passengers demand and their comfort indirectly.

A rescheduling solution which has a smaller evaluation value for both average travel time and the standard deviation means a good one.

The evaluation value is the total product at station i on average headway time ave_i and standard deviation s_i for the same operating direction.

Under the current combination of parameters, several rescheduling timetables are possible. However, the smallest evaluation value is adopted as the solution. An adopted rescheduling timetable may provide too many or not enough trains for passenger demands, however, the adopted solution is the best one for passengers under the limitation conditions which is include the rolling stock types operation area.

In this section, we first show some rescheduling examples for a theoretical track modelled on an existing track based on the above method.

Figure 9 shows a modelled track layout and divided block sections. Table 2 shows the conditions of the line under consideration.

For this modelled track, there is a mixed operation of two rolling stock types, namely one type (blue and green trains) can run on the whole line, but the other type (red and purple trains) can run between station No.0 and No.5 only. This means, station No.0 to No.5 are for example powered by directory current, and stations No.5 to No.8 are powered by alternative current or diesel operation.

Figure 10 shows a scheduled train diagram for the modelled track. Only a local train is used as train type, and the timetable is cyclic per half hour, alternatively to the terminal and to station No.5.

A rescheduling timetable is generated for this track and diagram, by changing the parameters. On a general personal computer, the computation time is about 5 min without changing rolling stock, and the time is about 40 min when changing the stocks.

On the scheduled timetable, a traffic accident happens 5 min after the train departure. Communication time is set to take 5 min, resumption time is 40 min, and time of recovery to scheduled conditions is set to vary. All parameter conditions and their evaluation values are shown in Table 3.

Diagrams (a) and (b) are similar to Fig. 7(a), i.e. they connect to the original rolling stock operation, and diagrams (c) and (d) are similar to Fig. 7(b), i.e. they connect to same type rolling stocks in different operations.

Figure 11 shows a sample of the rescheduled diagram under these conditions. Fig. 11(a) and (b) are rescheduled without changing rolling stock operation. On the diagram, some trains turn at station No.3, that is generally called the “mountain cut”, and the diagrams give a tricky impression. Diagram (b) and (d) have the smallest evaluation value based on optimum recovery time. The solution of diagram (d) is obtained by only shortening the turning time at the terminal stations. When comparing (a) and (b) with (c) and (d) in terms of flexible operation effect for the same rolling stock type, then (c) and (d) have smaller evaluation values. For operation with different rolling stock, the recovery time in Table 3(d) is shortened. Free operation shortens the time of recovery to scheduled conditions, and improves the evaluation value.

Figure 11(a)–(d) shows the generated rescheduling diagrams, however, sometimes there are no solutions due to parameter combinations.

Figure 12(a) shows a scheduled plan modelled on real operation on the track layout. The number of rolling stocks are 7, and the number is bigger than the cycle operation (Fig. 10). Two rolling stocks return to the yard, because the time zone includes varying cycle operations such as morning rush hour and daytime operation.

Figure 12(b) shows a generated rescheduling timetable in which the complete line operation is suspended for 40 min (traffic accident happens at 2 [min]). Due to an excessive number of rolling stock operating, there are not enough turning tracks at the terminal stations. Accordingly, a rescheduling solution is adopted where rolling stocks turn at middle stations. Finally, a scheduling plan is generated where two rolling stocks return to the yard.

The scheduling timetable is rescheduled with the parameters shown in Table 4, in these conditions, a traffic accident happens to each train at different times, and the solutions are com- pared with each other.

(1) An accident happens to the blue train (train #0) on the main track

In Fig. 13(a), the blue train stops on the main track before station No.2. The red train waits at terminal station No.0 where there are no turning facilities between station No.0 and No.2. The green train turns back at station No.3 to terminal No.8. The green and blue trains (same rolling stock type) change their operation connection reciprocally. The purple train waits at a turning track at station No.5.

(2) An accident happens to the purple train (train #3) on a turning track

In Fig. 13(b), the purple train stops on the turning track at station No.5. The blue and green trains (same rolling stock type) change their operation connection reciprocally. The red train turns back at station No.3.

Figure 14 shows a sample rescheduled diagram in which all trains are stopped under the same conditions as given in Table 4.

Table 5 shows evaluation values considering both a part of the closed-off area and the suspension of all trains. High convenience for passengers is obtained when the operation number is high and the headway time is homogeneous. Therefore, a generated rescheduling timetable in which an operation turns back around the closed-off area has better evaluation values.

However, for real-life operations, a rescheduling timetable is not made from zero. Some typical rescheduling patterns are prepared in advance and those are adjusted to the situation.

We suggested how to generate an automatic rescheduling timetable when traffic accidents occur. We considered rolling stock types in particular. Possible routes per rolling stock type were registered, in order to deal with different private companies running through on each other’s tracks. The rescheduling timetable is a combination of route combinations including information on rolling stock types that can be used.

The rescheduling timetable is composed of these routes combinations investigated by round robin, and all possible operation timetables are candidate solutions. The evaluation values are average headway time at each station for both directions and standard deviation time for the passengers.

The proposed method can generate rescheduling plans for when the complete line is suspended as well as for turning back operations around the closed-off area. All possible route data for each rolling stock type are registered, and the routes connect to the same types, and a rescheduling timetable is composed for the route combinations. The combinations are searched for by round robin, and therefore, the best solution is included among the candidates. Choosing to close off part of the area and operate around it for a long time, or closing the complete area for a short time and aiming for resumption in a short period of time can be determined by our method, at the same time depending on track conditions.

We are also considering rolling stock types operation on real rescheduling, and we have to decide between turning back operation around a part of the closed-off area to maintain traffic or closing complete tracks to return to normal operation in a short time, depending on line characteristics.

In future research, we will need to consider and include other evaluation conditions, and we will generate rescheduling timetables for real-life scheduled timetables.