Analysis of air transportation using complex networks
Delay propagation is the result of different factors, including the lack of coordination of airline flight schedules, finely tuned airline flight schedules with little slack to dampen delay propagation, high levels of congestion preventing re-accommodation of delayed flights, or high aircraft load factors preventing timely re-accommodation of passengers who misconnect or whose flights are cancelled. All combine to create passenger disruptions and lengthy passenger waits that exceed the levels of flight delays. According to the 2008 Report of the Congress Joint Economic Committee, flight delays have an economic impact in the U.S. equivalent to 40.7 billions of dollars per year, while a similar cost is expected in Europe. The situation can turn even grimmer in the next decade since the air traffic is envisaged to increase. This includes higher emissions to recover delays, image loss for the companies and damage to passengers. Delays cause immense losses to the Air Traffic System, a situation that will worsen in the near future if traffic increases. Models and methods allowing stakeholders to characterize mechanisms behind delay propagation, to forecast network congestion, and to optimize planning and operational practices to mitigate delays are thus of great relevance. The development of such tools has been the main objective of this PhD.
The use of network analysis to characterize complex systems has been generalized in the last decade. The potential of graphs for describing social systems was pointed out almost a century ago. However, the generalization of these concepts and tools occurred only much later, after the seminal works by Watts and Strogatz and by Albert and Barabasi at the end of the 90's. Ever since complex networks have been applied in a growing range of disciplines such as technology, biology, sociology or economy.
The application of network theory to air transportation has a much shorter history, for which the first results were published in 2004 and 2005. The world airport network is described as a graph formed with the passenger commercial airports as vertices and the direct flights between airports as edges. Each edge also bears a weight corresponding to the number of seats available in the connection. This initial work includes a network description with an analysis of the degree (number of connections per node) and node strength (sum over the weights of the connections of a node) distributions, degree-degree correlations, density of triangles, etc. A second work focuses on the correlations between network topology and fluxes of passengers finding a non-linear relation between them. The world airport network has been analyzed later with graph clustering techniques to classify airports according to their connectivity patterns. US Airports’ network dynamics due to seasonal effects has also been investigated.
From the ATM field a significant effort has been invested in identifying the causes for initial or primary delays. Among the sources of primary delay, some of the most devastating are related to weather perturbations as has been shown in. These primary delays can in turn trigger a cascade of secondary delays as was noted in by the introduction of a ripple effect. Because of the inherent complexity of the mechanisms that produce and boost delay spreading, different modeling techniques were proposed. A first line of research focused on simulating the air traffic system as a network of queues without considering information on aircraft schedules. A second line of research was devoted to analytical approximations for modeling the airport runway operations as a dynamic queuing system with varying demand and service rate. Another analytical queuing model was used in. In this work, airports were modeled as dynamic queues and implemented in a network. The authors ran the model in a network of 34 airports with a specific algorithm that accounts for downstream propagation of delays. An additional body of work uses statistical tools to predict the delay patterns observed in the data. Such techniques could be classified into traditional linear regression models, artificial neural networks and Bayesian networks. By considering an agent-based framework we can give insights, in a cost-effective way, of how microlevel interactions give place to emergent behavior from a network-wide perspective.
Technologically driven transport systems are characterized by a networked structure connecting operation centers and by a dynamics ruled by pre-established schedules. Schedules impose serious constraints on the timing of the operations, condition the allocation of resources and define a baseline to assess system performance. Technical, operational or meteorological issues affecting some flights give rise to primary delays. When operations continue, such delays can propagate, magnify and eventually involve a significant part of the network. Metrics have been defined to quantify the level of network congestion and a model was introduce that reproduces well the delay propagation patterns observed in the U.S. performance data. The model allows for exploring the resilience of the system in terms of congestion to external perturbations such as generalized bad weather conditions. The results indicate that there is a non-negligible risk of systemic instability even under normal operating conditions. Passenger and crew connectivity were also identified as the most relevant internal factor contributing to delay spreading.
This work is driven by real traffic data, this allows us to perform the delay propagation modelling in realistic situations as well as to validate our model with real delay information. The main data sources to be considered are BTS, IATA and Eurocontrol. The data is analyzed using standard conceptual tools of Complex Networks analysis. In this sense, the methodology applied is similar to that used in close problems such as the airport networks. After getting the data and cleaning it from exceptions, we build networks for different aspects of the flight connection networks that can be relevant for this study. Since these networks are dynamical and are constrained by different time and cost horizons, a different snapshot for the natural unit of time is build. The evolution of the air-traffic network is analyzed, after which propagation process can be simulated on them. These simulations are similar to the disease propagation models presented in Refs. The output of this work, in the form of software, could be of importance for traffic regulators and airlines, allowing for simulations of how delays produced by exceptional circumstances in a certain airports can expand.
- P. Fleurquin, J.J Ramasco, V.M. Eguíluz, "Systemic delay propagation in the US airport network", Nature Scientific Reports 3, 1159 (2013)
- P. Fleurquin, J.J Ramasco, V.M. Eguíluz, "Data-driven modeling of systemic delay propagation under severe meteorological conditions", Tenth USA/Europe Air Traffic Management R&D Seminar, Chicago, USA (2013)
- P. Fleurquin, J.J Ramasco, V.M. Eguíluz, "Characterization of delay propagation in the US air transportation network, submitted to Proceedings of the 2012 Air Transport Research Society Conference (2012)
Videos on network visualization
- Modeling delay propagation dynamics
- Evolution of clusters of congested airports throughout March 12 2010
- Joint Economic Committee of US Congress., Your flight has been delayed again: Flight delays cost passengers, airlines and the U. S. economy billions. Available online at http://www.jec.senate.gov (May 22. 2008)
- Eurocontrol Annual report, Available online at http://www.eurocontrol.int (2008–2011)
- ICCSAI. Fact Book on Air Transport in Europe, Available online at http://www.iccsai.eu (2007–2011)
- M. Jetzki "The propagation of air transport delays in Europe, PhD Thesis", Department of Airport and Air Transportation Research, RWTH Aachen University, Aachen, The Netherlands. (2009)
- LC Freeman, The development of social network analysis: A study in the sociology of science, Empirical Press (2004)
- D.J. Watts and S.H. Strogatz, "Collective dynamics of 'small-world' networks", Nature 393, 440-442 (1998)
- A.L. Barabási, R. Albert, "Emergence of scaling in random networks", Science 286, 509–512 (1999)
- BA Huberman, PL Pirolli, JE Pitkow, RM Lukose, "Strong Regularities in World Wide Web Surfing", Science 280, 95-97 (1998)
- H. Jeong, S. P. Mason, A.-L. Barabási, Z. N. Oltvai, "Lethality and centrality in protein networks", Nature 411, 41-42 (2001)
- C. Castellano, S. Fortunato and V. Loreto, "Statistical physics of social dynamics", Rev. Mod. Phys. 81, 591 (2009)
- R Mantegna, EH Stanley, Introduction to Econophysics: Correlations and complexity in finance, Cambridge Univ. Press (2007)
- R. Guimera, S. Mossa, A. Turtschi, L.A.N Amaral, "The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles", PNAS 102, 7794–7799 (2005)
- A. Barrat, R. Pastor-Satorras, A. Vespignani, "The architecture of complex weighted networks", PNAS 101, 3747–3752 (2004)
- M. Sales-Pardo, R. Guimera, A.A. Moreira, L.A.N Amaral, "Extracting the hierarchical organization of complex systems", PNAS 104, 15224–15229 (2007)
- A. Gautreau, A. Barrat, M. Barthelemy, "Microdynamics in stationary complex networks", PNAS 106, 8847–8852 (2009)
- N.G. Rupp, "Further investigations into the causes of flight delays",(Working paper, Department of Economy, East Carolina University, 2007). Available online at http://www.ecu.edu/cs-educ/econ/upload/ecu0707.pdf
- P. Belobaba, A. Odoni, C. Barnhart, "The global airline industry", Chichester, U.K., John Wiley & Sons (2009)
- S.S. Allan, J. A. Beesley, J.E. Evans, S.G. Gaddy, "Analysis of delay causality at Newark International Airport", Proceedings of the 4th USA/Europe air traffic management R&D seminar, Santa Fe, USA (2001)
- A. Klein, R. Jehlen, D. Liang, "Weather index with queuing component for national airspace system performance assessment", Proceedings of the 7th USA/Europe air traffic management R&D seminar, Barcelona, Spain (2007)
- A. Klein, S. Kavoussi, R.S. Lee, "Weather forecast accuracy: study on airport capacity and estimation of avoidable costs", Proceedings of the 8th USA/Europe air traffic management R&D seminar, Napa, USA (2009)
- R. Beatty, R. Hsu, L. Berry, J. Rome, "Preliminary evaluation of flight delay propagation through an airline schedule”, Proceedings of the 2nd USA/Europe air traffic management R&D seminar, Orlando, USA (1998)
- L. Schaefer, D. Millner, "Flights delay propagation analysis with the detailed policy assessment tool”, Procs. of the 2001 IEEE international conference on Systems, Man and Cybernetics vol. 2, pp. 1299-1303 (2001)
- K.M. Malone, "Dynamic queueing systems: behavior and approximations for individual queues and networks”, Ph.D. thesis, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA (1995)
- N Pyrgiotis, K.M. Malone, A Odoni, "Modelling delay propagation within an airport network”, Transportation Research C, in press
- A.M. Churchill, D.J. Lovell, M.O. Ball, "Examining the temporal evolution of propagated delays at individual airports: case studies", Proceedings of the 7th USA/Europe air traffic management R&D seminar, Barcelona, Spain (2007)
- B. Sridhar, Y. Wang, A. Klein, R. Jehlen "Modeling flight delays and cancellations at the national, regional and airport levels in the United States", Proceedings of the 8th USA Europe air traffic management R&D seminar, Napa, USA (2009)
- N. Xu, G. Donohue, K. Blackmond Laskey, CH. Chen "Estimation of delay propagation in the national aviation system using Bayesian networks", Proceedings of the 6th USA/Europe air traffic management R&D seminar, Baltimore, USA (2005)
- A.P. Shah et al. "Analyzing air traffic management systems using agent-based modeling and simulation", Proceedings of the 6th USA/Europe air traffic management R&D seminar, Baltimore, USA (2005)
- D. Balcan et al., "Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility", BMC Medicine 7, 45 (2009)
- D. Balcan, V Colizza, B Goncalves, H Hu, JJ Ramasco, A Vespignani, "Multiscale mobility networks and the large scale spreading of infectious diseases", PNAS 106, 21484–21489 (2009)