Modeling of train operations is helpful to plan railway corridor activities and optimize the use of resources. This paper models the train scheduling problem of a single line railway network with main concern to minimize total operational cost and delays with relation to position of sidings.
Method
Problem is modeled as jobshop scheduling problem and solved using Branch and Bound (B&B) technique. Sensitivity analysis is done with changing the number of sidings and trains. Approach used here has quantified the relatedness between the number of sidings and train conflict delays. Objective was to show the impact of number and position of sidings on timetable.
Results
Results are quantified as conflict delays and computational effort involved for each option of sensitivity analysis. Some of sidings which don’t have any impact on scheduling of this track are mentioned using this analysis.
Conclusion
This technique can be used to determine the investments in terms of location and number of sidings because conflict related delays has direct relation with number and position of sidings.
1 Introduction
The Train scheduling is the art of finding arrival and departure time to and from each station. Efficient design of schedule can improve the level of service of railways. It is one of the initial steps in management of complex railway operations. Even attraction of traveler’s and freight carriers in traveling mode selection is also dependant on the schedule and its level of service. Railways system operations are scheduled based on the train schedule so it also effects the utilization of scarce resources such as cars, engines and crew. In order to optimize the use of infrastructure capacity, some helping tools such as Mathematical programming and simulation techniques are being used to solve long and complex scheduling problem. Albeit, train scheduling had been done manually for more than a century however to prepare train schedules for a rail network without any supporting tools and resolving conflicts “by hand” is rather a slow process. To manually schedule trains even over a small size rail network, a large number of experienced schedulers and ample amount of time is required. Nowadays, in the age of computer it cannot be conceived without the help of a computer [1].
Major use of train operations modeling is to plan railways operations. Railway planning is conveniently divided into two divisions: short to medium term planning and infrastructure planning [2], shown in Fig. 1. These models are also helpful to evaluate the changes to schedule in terms of changing arrival/departure times, addition of extra trains, change in speed etc. Calculation of the impact of these changes in main schedule is known as sensitivity analysis. Investment strategies can be defined using such type of models and sensitivity analysis.
Location of siding is a critical issue in the planning of rail line. It involves determining the number, length, position and vertical and horizontal alignment of line. Main concern in this problem is to place sidings in such a way which minimize total operating cost and total delay. Impact on the schedule, in terms of flexibility and feasibility of schedules, can be assessed by using these models if you want to extend or remove some sidings. The problem of sensitivity analysis in mathematical programming has been discussed by many authors, for example, Higgins et al. [3], Vanderplaats [4], Sobiesky et al. [5], Enevoldsen [6], Castillo et al. [7‐10], etc. Burdett and Kozan [11] finds the effect of deviations in sectional running time and additional dwell time on three objectives, namely total train delay, makespan and total time window violation. Burdett and Kozan [12] use sensitivity analysis to find the affected operations by delay in the predictive train schedule and find that this sensitivity analysis is also a measure of robustness and provide information how to control the delays when they occur in real time.
Here considered problem is that improper position and abundant sidings on the network can also cause unreasonable conflict delays. Hence, in order to optimize the investment plan, only those sidings having impact on the timetable should be improved (by adding more tracks to cater more conflicts at that sidings etc.). Others do not have impact in decreasing conflict delays or their presence or absence has same worth, should not be further considered for investment.
This paper is organized as follows; in Section 2 literature review is presented. Section 3 gives details of modeling of train operations with objective functions and constraints. Solution strategy is given in Section 4 and experimental arrangements as well as results are shown in Section 5. Finally, in Section 6 conclusions and recommendations are presented.
2 Literature review
From the very beginning scheduling has been an active area of research in railways. Even before eighties mostly train scheduling was based on optimization and simulation techniques. Assad [13] is providing a review of the models developed for rail transportation before eighties. Amit and Goldfarb [14] seems to be first to apply the mathematical programming technique to train scheduling problem. Cordeau et al. [15] presented a detailed survey of train routing and scheduling optimization modeling techniques. Sahin [16] and Ghoseiri et al. [17] divided the techniques of railway traffic control techniques into three families: expert systems, simulations and mathematical programming. Over view of rail traffic management provided by D’Ariano [18] classifies the railroad management operations into three categories: Offline timetabling, real time traffic management and dynamic traffic management. Main focus of off-line tabling is to design robust timetable such that propagation of delays should be minimum but in case of large delays and blocking of tracks no reasonable plan is robust or reliable [19]. Most of recent studies (D’Ariano [18], Montigel et al. [20], Corman [21‐23] and Tornquist [24]) focused on the real time problem to find feasible deadlock free and conflict free solutions within a short time available to take real time dispatching decisions.
Anzeige
A wide range of studies in train scheduling problem have used branch and bound (B& B) technique to solve this problem. Szpigel [25] was first to formulate a model for train scheduling problem and applied Greenberg’s solution [26] framework based on branch and bound technique to solve it. Jovanovic and Harker [27] modeled the problem to minimize the deviation between actual and planned schedules. They used nonlinear integer programming to generate feasible meet pass plan using branch and bound technique. Higgins et al. [28] also used nonlinear integer programming to model the problem with objective to minimize total delay. They developed lower bound estimate based on the number of remaining conflicts in remaining partial schedule. Zhou and Zhong [29]) modeled to minimize total train travel time with three techniques to reduce the search space; i) Lagrangian lower bound estimate, ii) exact lower bound based on remaining conflicts in the partial schedule and, iii) Upper bound using beam search heuristic. D’Ariano et al. [30] modeled real time traffic control as huge job shop scheduling problem with no store constraints. Shafia et al. [31]) formulated to find the robust time table on single line track. They used branch and bound with beam search heuristic to solve the problem. Comparison of results of branch and bound technique with Lingo shows optimality of solution.
Trains scheduling problem is formulated here as resource constrained job shop scheduling problem. To be more specific, it is an optimization problem with set of trains running on single line track. Next sections provide the detail about the modeling and solution strategies used.
3 Mathematical modeling
Single line train scheduling problem is consideration of this model, in which trains are considered as tasks which are assigned to tracks (considered as machines). In this way jobshop scheduling problem is formulated with set of single line track segments and a set of trains having predefined traveling directions and fixed running times.
Resource constrained jobshop scheduling is considered here to maintain minimum time lag between consecutive tasks of trains. Stations and tracks are considered separate resources. It is assumed that a single line connects two stations with sidings available to perform meet and pass operations. Figure 2 describes the assumed conditions for modeling. Station A and D are terminals and B and C are intermediate station with sidings available for meet pass operations.
Fig. 2
Illustration of single line track with sidings
×
3.1 Assumptions and inputs
Assumptions used in this modeling are as follows:
The track is considered to be composed of segments, separated by sidings.
It is assumed that each train has pre specified direction and route.
Free running times are assumed to be constant for a track segment.
Travelling of trains are assumed as tasks to be assigned to machines (here tracks and stations are taken as machines).
Sidings are places where trains can cross each other.
A minimum headway will be maintained for trains to follow each other on a track segment.
Trains can have maximum 30 min conflict delay otherwise this option will be neglected.
A station may have capacity to be occupied by more than one trains but only one train capacity per station is considered in here.
The model will require the following data as input to the model:
Fixed running times are calculated for each segment.
Planned departure times of all trains to be scheduled.
Maximum time a train can wait for other train at a siding.
3.2 Definition of variables
Table 1 is providing the details of variables used in this modeling with their corresponding symbols
Table 1
Definition of variables
Definition
Symbol
Train index
t
Segment index
s
Segment sequence number in train route
j
Station index
i
Set of trains
T
Set of segments |S| = m
S
Set of stations |J| = m + 1
J
Direction indicator for train t, p(t) = 0 for an inbound train and p(t) = 1 for an outbound train
p(t)
Segment index of the jth traveling segment in a route for train i, σ (t,j) = j for outbound trains, σ (t,j) = m + 1-j for inbound trains
σ(t, j)
Downstream station number of the jth traveling segment in a given route for train t, b(t,j) = j foroutbound trains, b(t,j) = m -j for inbound trains
b(t, j)
Planned departure time for train t at its first station
kt
Free running time for train t at segment s
f(t,s)
Minimum required station dwell time before train t entering segment s
d(t,s)
Maximum allowed station dwell time before train i entering segment j
\( {\overline{d}}_{\left(t,s\right)} \)
Minimum headway between arrival and departure times of two consecutive trains at segment j
hs
Minimum headway between arrival times of two consecutive trains at station u
gi
Entering time for train t at segment s, i.e., start time for job t on machine s
ot,s
Leaving time for train t at segment s, i.e., end time for job t on machine s
ct,s
Binary Variable,1 if train t is scheduled before train t’ on segment s, 0 otherwise
\( {A}_{t,{t}^{\prime },s} \)
Sufficiently large constant
M
3.3 The proposed model
3.3.1 Objective function
Objective function of model is to minimization of total travel time.
$$ {o}_{t,\sigma \left(t,j\right)}\le {c}_{t,\sigma \left(t,j-k\right)}+{\overline{d}}_{t,o\left(t,j\right)}\forall t\in T,j=1,2,\dots m $$
(7)
Inequality (2) is departure time constraint, which imposes a limit on the actual departure time of trains from starting station. This ensures that actual departure time at starting station is always equal or greater than the planned time of that train at starting station. Equation (3) states that leaving time (finish time of job) of a section must be equal to the entering time plus free running time. Constraint (4) is ensuring that scheduled stop is more than minimum dwell time which is practically required to load and unload passengers and freight trains. Constraints (5) and (6) are headway constraints to ensure safe operations. Constraint (5) is imposing minimum headway requirement for safe operation of trains running, in opposite or same direction, on the same track. While, inequality (6) imposes that minimum headway requirement on two consecutive trains approaching at same station. Constraint (7) gives the upper bound of time which a train can wait for other train at a station.
Either—or relations (8) are decision variables which will decide which train will traverse segment first
Branch and bound is applied here, which is a general algorithm applied to many areas to find optimum solution of various optimization problems. It consists of enumeration of all candidate solution systematically while a large amount of fruitless candidates are discarded based on upper and lower bound estimation of quantity to optimized.
Search tree of this train scheduling problem using branch and bound technique is generated by representing each conflict among trains as a node of search space, shown in Fig. 3. In each conflict we have two options either one train or second will traverse the segment first, which is branching in this modeling.
Fig. 3
Enumeration of search tree in application of B&B for train scheduling
×
The B&B technique applied here is as follows:
Root node is initiated with an empty schedule. Departure time, segment free running time and train directions are input and upper bound is set to 999999.
Constraints are applied at each activity and conflicts (where two or more trains want to use same resource) are identified with position and trains involved in a conflict.
For each available option child nodes are generated.
Active node for further branching is selected based on Depth First Search (DFS).
Lower bound value is estimated for each node.
Node elimination rules are applied to move further with remaining child nodes.
Loop until no more nodes are remaining in list of active nodes or until stop condition of node selection rule is satisfied.
5 Calculations and results
Track chosen is mainly single line with 156 Km length from station Lalamusa to Rawalpindi, Pakistan. About 30 trains traverse this track on the busiest day of week. There are four different types of trains scheduled over this track, namely; Mail and Express, Intercity, Passenger and Mixed trains. Taking the number of siding variable here, computational effort (in terms of nodes evaluated) and conflict delays are calculated. Figure 4, shows the number of conflicts resolved on all the stations between terminals Lalamusa and Rawalpindi, according to Pakistan Railways schedule [32]. Some intermediate sidings do not have any conflict and some has as many as five per day.
Fig. 4
Number of conflicts on each siding in actual schedule
×
In the sensitivity analysis of this track, we first consider two terminal stations with only 15 intermediate sidings, which are being used to resolve conflicts. Then, those sidings which have only one conflict are ignored one by one, starting from Lalamusa terminal. After that, we ignored the sidings which have two conflicts to get resolved.
Table 2 shows the results of the sensitivity analysis performed. Figure 5 depicts that decreasing the number of locations is resulting increase in conflict delays but the track with 10 to 13 sidings arrangement are producing exactly same results. Results between these sidings are almost straight line for all number of trains. This elaborates that they are producing same impact on network. These are four options, Kaliamawan, Sohawa, Ratial and Kalagujran which are omitted from list of conflict resolving sidings when 10 to 13 sidings are obtained. While the most margin conflict delay in each case is observed to jump from 14 to 13 sidings option, which demonstrate influence of this siding. These results conclude the fact that these sidings were arranged without any such type of conflict delay estimation or it may also be possible that the system available at that time when investments on this track was planned, may not be efficient like this modern one.
Table 2
Results of option testing
Sidings
8 Trains
9 Trains
10 Trains
11 trains
12 trains
Nodes
Margin
Delay
Margin
Nodes
Margin
Delay
Margin
Nodes
Margin
Delay
Margin
Nodes
Margin
Delay
Margin
Nodes
Margin
Delay
Margin
17
486
40
1716
57
14563
84
54389
99
179742
111
16
301
−185
52
12
1021
−695
69
12
5633
−8930
95
11
17185
−37204
110
11
64014
−115728
127
16
15
361
60
58
6
967
54
74
5
5335
−298
102
7
14048
−3137
116
6
66433
2419
138
11
14
473
112
67
9
1271
−304
83
9
6664
1329
111
9
18385
4337
125
9
91798
25365
148
10
13
253
−220
82
15
1383
−112
133
50
8710
2046
186
75
14479
−3906
202
77
64472
−27326
231
83
12
197
−56
82
0
1105
278
133
0
6400
−2310
186
0
9188
−5291
202
0
35420
−29052
231
0
11
197
0
82
0
1105
0
133
0
6400
0
186
0
8956
−232
202
0
46878
11458
242
11
10
311
114
99
17
1029
76
141
8
5527
−873
194
8
8229
−727
210
8
35005
−11873
250
8
9
409
98
138
39
837
192
174
33
3766
−1761
227
33
6017
−2212
242
32
24693
−10312
279
29
Fig. 5
Illustration of increase in delay with decrease in number of sidings
×
Figure 6 shows the impact of decrease in the number of locations where conflicts can be resolved on the computational effort involved in solving the problem. By decreasing sidings number of nodes to be evaluated decreases but the conflict delay increases. Impact of siding on the whole schedule can be judged by this manner. Here the results, show that curve is almost same for 10 to 13 sidings with curves of 12 and 13 sidings lying exactly on each other, strengthening the conclusion of previous discussion that sidings Kaliamawan, Sohawa, Ratial and Kalagujran have a very little effect on the schedule. It also suggests that by fixing some necessary places for sidings large scale problem of train scheduling can be reduced to a simple one but results may be suboptimal.
Fig. 6
Analysis of computation effort involved in sensitivity analysis
×
6 Conclusions and recommendations
The main focus of this paper is to find the significance of position of sidings on railway network. The problem is formulated as resource constrained job shop scheduling problem, with operational safety constraints. The developed model is solved by branch and bound technique. The proposed methodology is demonstrated by sensitivity analysis of real world problem of single track section of Pakistan Railways. Results are quantified as conflict delays and computational effort involved for each option of sensitivity analysis. Results show that with decrease in the number of sidings delay increases but the computation effort decreases and this phenomenon become prominent for more trains and less sidings. Some of sidings which don’t have any impact on scheduling of this track are mentioned using this analysis. This shows the potential of this technique to get applied at midterm planning level for preparation of strategic investment plans.
The contribution of this paper is to help decision makers, responsible to inspect and maintain the network, to prioritize the elements of network (i.e., sidings, tracks etc.) for improvement. By using such type of techniques they can optimally allocate the available limited resources. Further is the extension of this work by identifying and incorporating the practical considerations of investment on network. Also the future consideration is the development of decision support system for network manager to find optimum strategy for investment.
Acknowledgments
We are thankful to honorable, Dr. Muhammad Irfan, Assistant Professor at NIT, NUST, Islamabad and Dr. Xuesong Zhou, Assistant Professor of the Department of Civil and Environmental Engineering at the University of Utah, for their timely, indispensible continuous help, constructive critique and able guidance. We gratefully acknowledge Pakistan Railways (PR) department for providing us valuable data to complete this work. Especially, I owe my deepest gratitude to Mr. Umar Riaz and Mr. Ehtsham Khan, Divisional Planning Officer and Divisional Signal Engineer of Rawalpindi Division for their cooperation and guidance. We are also grateful to Zohaib Ahmed for his valuable assistance in computer programming.
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
