Models and algorithms for the real-time railway and air traffic flow management problems

Abstract

Public transport systems with high capacity and high speed, such as railways and air traffic, efficiently address the ever increasing transport demand, reducing road congestions on highways and in densely populated areas. Building new infrastructures is a difficult task, due to high costs and physical obstacles, thus pushing infrastructure managers to better use the already existing ones. Utilization plans are carefully designed, however disturbances may arise, creating time-overlapping conflicting request done by multiple vehicles on the same resources that the dispatchers are required to address. Limited automated system aid is provided to the dispatchers which, due to the limited time available, are not allowed to fully evaluate the effect of the recovery decisions taken. Some decisions may lead to future delays, which in turn may create new conflicting requests, in a snowball effect. Optimization is thus necessary to minimizing the delay propagation and the consequential worsening of the quality of the service offered. This PhD thesis investigates how operations research models and algorithms benefit the solution process of the real-time railway and air traffic flow management problems. The railway traffic management problem consists in detecting and solving conflicting track requests done by multiple trains and creating a recovery plan in which each track is used by at most one train at a time and no deadlock exists in the network. The air traffic flow management problem deals with the assignment of an entry time to each landing and take-off aircraft in each resource the aircraft requires to traverse in such a way that potential conflicts between single aircraft are efficiently solved and all aircraft respect the minimum longitudinal and diagonal safety distances. In order to incorporate safety regulations constraints, both problems require a microscopical level of detail. This is achieved through the use of the alternative graph model. This model has already been proved successful for the railway case and thus is here applied to the air traffic one. Algorithms improving the performance of the state-of-the-art AGLIBRARY optimization solver (a set of operations research based models and algorithms for complex practical scheduling problems) are proposed. Furthermore, the thesis deals with large test cases in terms of size of the network studied, time of prediction considered and number of available alternative routings for each vehicle. Search space restriction and decomposition methods are analyzed in order to simplify the solution process of the problems when such large cases are considered. Also, lacking generally recognized objective functions both for the railway and the air traffic management problems, the gaps between solutions optimized and evaluated with different performance indicators are analyzed, together with possible ideas on how to combine multiple performance indicators when required. Different test beds have been taken into consideration for both problems. The instances considered are of practical size and affected by different disturbances, such as initial delays and infrastructure disruptions.