Optimization of a Train Traffic Management Problem
under Uncertainties and Disruptions

Adnen EL AMRAOUI¹, Khaled MESGHOUNI²
¹Université d’Orléans, Laboratoire PRISME,
63 Avenue de Lattre de Tassigny, 18020 Bourges, France
adnen.el-amraoui@univ-orleans.fr
²Ecole Centrale de Lille (EC-Lille), Cité Scientifique – CS 20048,
59651 Villeneuve d’Ascq Cedex, France
khaled.mesghouni@ec-lille.fr

Abstract: In this paper, we consider a train traffic management problem. Our aim is to find an optimal schedule for a train traffic network where time duration uncertainties are considered. This problem was intensively studied with mixed integer linear models where trains moving duration are deterministic. In this paper, a new formulation of the problem as a classical one with scenario-based stochastic programming taking expected values as objective functions is presented. Then, new criterion is proposed to quantify scheduling robustness in the face of uncertainty. Besides, a novel control policy is elaborated to find quickly, a feasible train schedule when disruption or unexpected event occurs during scheduling execution.

Keywords: Train Traffic Management, Scheduling, Control Strategy, Uncertainties, Disruptions.

>>Full text
CITE THIS PAPER AS:
Adnen EL AMRAOUI, Khaled MESGHOUNI, Optimization of a Train Traffic Management Problem under Uncertainties and Disruptions, Studies in Informatics and Control, ISSN 1220-1766, vol. 23 (4), pp. 313-323, 2014. https://doi.org/10.24846/v23i4y201401

Introduction

This paper deals with the train scheduling networks problems. It consists in finding the arrival and the departure times of the lines at certain stages of the network. Depending on required objectives, these stages can be referred to public station and/or switches.

Since 1871s, and more precisely since the first train schedule conference in Germany, train scheduling problems have been widely studied [1] and several mathematical models have been proposed ([2]-[3]-[4]-[5]-[6]-[7]).

This category of scheduling problems can be shared into two classes:

1st Class: Static or Predictive problem

It consists firstly on allocating resources (i.e. tracks and stations) to all trains in all routes. Then, the train sequencing entrains the pre-specification of the arrival and departure order of trains at stations. Finally, a time-table is then resulted. This class aims on the minimization of the makespan or the cycle time or on the maximization of the traffic frequency [8]-[9]-[10]. In [9], Harrod propose a directed hypergraph formulation for a rail network, in the aim to schedule train paths when the railway network is busy.

Harrod model is used to solve the problem of train sequencing constraints. Moreover, a heuristic approach is then derived for the same problem [9].

Besides, a heuristic approach is proposed by Kraay and Harker to find line dispatching (i.e. arrival and departure times for each train) and to define a monthly strategic schedule [10].

Nevertheless, these approaches are not able to solve the problem when an expected event happens.

2^nd Class: Dynamic or Reactive problem

It involves when the train planned schedule cannot be respected due to a disturbance handling activity. In this case, a new timetable should be found while all the problem constraints are respected. Generally, the objective function consists on the minimization of train delays [11]-[12]-[13].

Dorfman and Medanic propose a discrete event model to solve their strategy (called feedback-based travel advance strategy). Moreover, they suggest some extensions of their strategy for more complex configurations (e.g. double-track sections, trains with variable characteristics and priorities) [11]. Narayanaswami and Rangaraj develop a mixed integer linear programming model to find a solution based on their strategy of controlling disjunctive constraints (of tracks allocation) [12]. Whereas, Budai et al. [13] use a timetable planning schedule as an input and apply a control strategy to minimize the delay. In this control strategy, trains movement sequence order is not challenged.

The focus of our paper is to present a new model which can be useful for the two problem classes simultaneously.

Furthermore, the originality’s of our approach consist on the following:

Due to train travelling duration’s uncertainties, a handling scenarios approach is presented. Moreover, additional criterion is considered to find the most robust schedule.
In order to remove a disruption, if any, a new control policy is proposed. This policy aims to control train speed and train waiting time on stations.

Most previous models are handling either predictive train scheduling problem ([6]-[7]-[8]-[9]-[10]) or reactive one ([11]-[12]-[13]).

If unexpected event happens, a first schedule solution can be determined using the first problem class models. This can be reached by instantiating known decision variables. Nevertheless, this solution is very simple and cannot, at any way, guarantee the solution performance.

Besides, weather conditions can require on trains to reduce their speeds on some tracks. In fact, a wheels sliding or a wheels skating can happen due to the snow or to the tree leaves on the rail in autumn generally. So, this could lead to several perturbations in arrival and departure times of the timetabling passenger trains. This problem has become recurrent in Europe at the approach of winter holidays and Christmas while a large number of people take the train to travel; which make rail transport less competitive compared to other means of travel (air and ground transportation).

Following to these introductory remarks, Section 2 is devoted to the problem statement. Section 3 discusses the mathematical problem modelling. The problem resolving methodology and the new control policy are presented in Section 4 and 5, respectively.

REFERENCES

CORDEAU, J. F., P. TOTH, D. VIGO, A Survey of Optimization Models for Train Routing and Scheduling, Transp. Sc., vol. 32, 1998, pp. 380-404.
BAI, L., T. BOURDEAUD’HUY, B. RABENASOLO, E. CASTELAIN, A Mixed-integer Linear Program for Routing and Scheduling Trains Through a Railway STATION, 3rd Intl. Conf. on Operations Research and Enterprise Systems, Angers, 2014, pp. 445-452.
HIGGINS, A., E. KOZAN, L. FERREIRA, Optimal Scheduling of Trains on a Single Line Track, Transp. Res. – Part B, vol. 30(2), 1996, pp. 147-161.
SHERALI, H. D., R. SIVANANDAN, A. G. HOBEIKA, A Linear Programming Approach for Synthesizing Origin-Destination Trip Tables from Link Traffic Volumes, Transportation Research B, vol. 28, 1994, pp. 213-233.
CHANG, S., Y.-C. CHUNG, From Timetabling to Train Regulation – A New Train Operation Model, Information and Software Technology, vol. 47(9), 2005, pp. 575-585.
ASSAD, A. A., Models for Rail Transportation, Transportation Research – Part A, vol. 14, 1980, pp. 205-220.
NACHTIGALL, K., S. VOGET, Minimizing Waiting Times in Integrated Fixed Interval Timetables by upgrading Railways Tracks, European J. of Oper. Research, vol. 103, 1997, pp. 610-627.
HARROD, S., Modeling Network Transition Constraints with Hypergraphs, Transportation Science, vol. 45, no. 1, 2011, pp. 81-79.
ABBAS-TURKI, A., O. GRUNDER, A. EL MOUDNI, Sequence Optimization for Timetabling High Frequency Passenger Trains, IEEE Joint Rail Conf., Philadelphia, Penn., 2012, pp.831-836.
KRAAY, D. R, P. T. HARKER, Real-Time Scheduling of Freight Railroads,Transportation Research – Part B, vol. 29, no. 3, 1995, pp. 213-229.
DORFMAN, M. J., J. MEDANIC, Scheduling Trains on a Railway Network using a Discrete Event Model of Railway Traffic, Transportation Research – Part B, vol. 38, 2004, pp. 81-98.
NARAYANASWAMI, S., N. RANGARAJ, Modelling Disruptions and Resolving Conflicts Optimally in a Railway Schedul, Computers & Industrial Engineering, vol. 64, 2013, pp. 469-481.
BUDAI, G., G. MAROTI, R. DEKKER, D. HUISMAN, l. KROON, Rescheduling in Passenger Railways: The Rolling Stock Rebalancing Problem, Journal of scheduling, 2009, pp. 281-297.
VIN, J. P., G. IERAPETRITOU, Robust Short-Term Scheduling of Mutiproduct Batch Plants under Demand Uncertainty, Ind. Eng. Chem. Res., vol. 40, 2001, pp. 4543-4554.
HARDING, S. T., C. A. FLOUDAS, Global Optimization in Multiproduct and Multipurpose Batch Design under Uncertainty, Ind. Eng. Chem. Res., 36, 1997, pp. 1644-166.