The gate assignment problem (GAP) is a fundamental operational challenge for airport management, given that its solution has direct impacts on airport efficiencies, passenger experience, and resource utilization. Current studies are predominantly focused on devising problem-specific heuristics, using exact algorithms / commercial solvers, which frequently suffer from getting stuck in local optima and excessive computational times, respectively. In this paper, we propose a neural combinatorial optimization (NCO) framework to solve the GAP, which can reach a balance between computational efficiency and optimality. We embed flight and gate information into hidden states, using a multilayer transformer-based encoder-decoder policy network to assign gates in an auto-regressive manner. We train multiple NCO models using reinforcement learning and compare them to traditional exact and heuristic methods. Results show that our framework, NCOGAP, can provide practical real-time decision support with superior optimality, which we believe can greatly reduce the operator’s workload, while balancing global gate assignment operational efficiency and robustness, subject to realistic constraints and rules.

Flight delay is a fundamental problem present in the global aviation system. Delay-inducing disruptions are caused by various reasons, including increased global connectivity / dependency, weather phenomena, and limited infrastructure resources. Given the excessive amount of time and money lost due to delays in aircraft operations, the prediction of flight delays has become an active research topic in recent years. Particularly, the existence of code repositories for standardized machine learning applications as well as the available data on this subject, has led to an increasing number of papers, usually comparing the performance of different new and existing delay prediction techniques. In this study, we review the contributions of papers to delay prediction in recent years. Based on a six-step comparison framework, covering many aspects, starting with data collection / processing, including, e.g., model and feature selection, and ending with evaluation, integration of various technologies, and reproducibility considerations, we find that although the current studies have put forward effective concerns, there are still some challenges in the field of delay prediction. We elaborate on how to overcome this stage by discussing a set of research directions, which hopefully help other researchers to perform better future studies and help to reduce the impact of delays on air transportation systems.

There exists a tremendous number of research surveys on various aspects of UAV logistics, mobility and monitoring tasks in the literature. These surveys have been published in distinct venues, often having a significant overlap in goals and key findings. In this study, we provide a meta review across nearly 100 extant UAV surveys and overview papers, extract their key messages, and investigate the extent of being complementary. We develop the AERIAL framework, which aggregates the major challenges on the way to a successful application of UAVs for logistics, mobility, and monitoring. We believe that AERIAL framework and meta review contribute towards a clearer understanding of the scientific UAV landscape challenges and the identification of potential directions for future research studies.

Given an extensive set of challenges, the aviation industry is required to undergo a transformation into a connected, efficient and sustainable ecosystem. This transformation is mainly supported by the development of intelligent transportation system (ITS) techniques, such as leveraging data analytics / artificial intelligence, embracing digital technologies, and developing / integrating autonomous aerial vehicles. In order for this transformation to succeed, it is crucial for professionals and researchers to collectively comprehend the research innovations and challenges shaping the industry. Given the tremendous growth of the number of research studies, this manuscript presents a comprehensive review of the current state of the art in Intelligent Air Transportation Systems (IATS). Based on a dissection of studies published in the IEEE Transactions on Intelligent Transportation Systems, the premier outlet on the subject, we have performed a data-driven clustering of papers leading to a set of the following four key themes documented in the literature: air traffic management, aerial communication networks, navigation / surveillance, and UAV-related applications. For each theme, we do not only summarize the state-of-the-art, but also hint at the challenges and interesting directions for future work. Our review aims to contribute to the ongoing dialogue among professionals and researchers working on the intersection of air transportation, information technology, and computational intelligence.

The choice of hub locations is fundamental in various transportation and communication systems, enabling transshipment, sorting, and consolidation functions. Recent research has highlighted the benefits of stratification when searching for hub facilities, taking into account the fact that the demand at each site belongs to different strata, e.g., depending on the type or quality of service the passengers or cargo require. In this study, we propose various instances of the stratified single allocation hub location problems, ranging from simple p-hub median / stratified hub location to extensions concerning direct links as well as node capacities. Moreover, four generalized problems, considering service level requirements, capacitated direct links, multi-modal hub networks, and incomplete network structures are derived from the basic problems. Given that the stratified models become intractable to solve for even medium-sized instances, we also develop a novel neighborhood-search based algorithm. Extensive experiments are performed on representative data sets, confirming the effectiveness and efficiency of our solution techniques. The results also further highlight the significance of stratification in hub-and-spoke networks. Our work complements recent studies on stratified p-hub center / maximal covering problems.

Targeting at improving door-to-door accessibility, efficiency and reducing environmental impact, recent decades have witnessed vigorous development of multimodal transport. Coupled through passenger transfer, the failure of one mode, however, is likely to cause cascading disruptions to the complete system. Therefore, to maintain safe and efficient operations, the integrated recovery of the multimodal transportation system becomes an important, timely topic, given increasingly complex schedule interactions. This study proposes a mathematical model to handle the integrated recovery problem of multimodal transportation network by minimizing the passenger travel cost and mode recovery cost under failures of multiple critical infrastructures. For a case study on air/HSR interaction in China, our model incorporates decisions in terms of aircraft recovery, railway timetable rescheduling, and passenger routing with realistic constraints (e.g. max travel time, max transfer time). A column-and-row generation based heuristic solution algorithm is developed in order to solve the complex model with given computational budgets. Results reveal that real-world test disruption scenarios can be solved within 20 minutes with a small relaxation gap. A significant amount of passenger traveling time can be reduced in contrast to a sequential recovery approach with independent reaction decisions for each transport mode. This work contributes towards the development of support tools for integrated disruption management of multimodal transportation.

On-demand air mobility services, often called air taxis, are on the way to revolutionize our urban/regional transportation sector by lifting transportation to the third dimension and thus possibly contribute to solving the congestion-induced transportation deadlock many metropolitan regions face today. Although existing research mainly focuses on the design of efficient vehicles and specifically battery technology, in the near future, a new question will arise: Where to locate the vertiports/landing pads for such air taxis? In this study, we propose a vertiport location selection problem. In contrast to existing studies, we allow the demand to be distributed over the whole metropolitan area, modeled as a grid, and exclude certain grid cells from becoming hubs, for example, because of safety/geographical constraints. The combination of these two contributions makes the problem intriguingly difficult to solve with standard solution techniques. We propose a novel variable neighborhood search heuristic, which is able to solve 12 × 12 grid instances within a few seconds of computation time and zero gaps in our experiments, whereas CPLEX needs up to 10 hours. We believe that our study contributes toward the scalable selection of vertiport locations for air taxis. Summary of Contribution: The increasing interest in opening the third dimension, that is, altitude, to transportation inside metropolitan regions raises new research challenges. Existing research mainly focuses on the design of efficient vehicles and control problems. In the near future, however, the actual operation of air taxis will lead to new set of operations research problems for so-called air taxi operations. Our contribution focuses on the optimization of vertiports for air taxi operations in a metropolitan region. We choose to model the problem over a grid-like demand structure, with a novel side constraint: selected grid cells are unavailable as hubs, for example, because of environmental, technical, cultural, or other reasons. This makes our model a special case in between the two traditional models: discrete location and continuous location. Our model is inherently difficult to solve for exact methods; for instance, solving a grid of 12 × 12 grid cells needs more than 10 hours with CPLEX, when modeled as a discrete location problem. We show that a straightforward application of existing neighborhood search heuristics is not suitable to solve this problem well. Therefore, we design an own variant of mixed variable neighborhood search, which consists of novel local search steps, tailored toward our grid structure. Our evaluation shows that by using our novel heuristic, almost all instances can be solved toward optimality.

Well-designed multi-modal transportation networks are crucial for our connected world. For instance, the excessive construction of railway tracks in China, at speeds up to 350 km/h, makes it necessary to consider the interaction of rail with air transportation for network design. In this study, we propose a model for an air/rail multi-modal, multiple allocation hub location problem with uncertainty on travel demands. Our model is unique in that it integrates features from the existing literature on multi-modal hub location problem (including hub-level capacities, link capacities, direct links, travel cost and time, transit costs and uncertainty), which have not been considered simultaneously, given its high computational complexity. We formulate this model with$O(n^{4})$variables and show that the implementation of a Benders decomposition algorithm is inherently hard, because of the cubic number of variables in the master problem. Furthermore, we derive an iterative network design algorithm and additional improvement strategies: MMHUBBI which resolves a restricted problem by the solver CPLEX and MMHUBBI-DIRECT which re-designs the transportation network by a heuristic. Our evaluation on real-world dataset for Chinese domestic transportation shows that MMHUBBI provides a significant speed-up on all instances, compared to using CPLEX, while obtaining near-optimal solutions. MMHUBBI-DIRECT further reduces the runtime/memory usage but provides solutions with worse quality. We believe that our study contributes towards the design of more realistic multi-modal hub location problems.

This study aims to clarify a few concepts when assessing the robustness of complex systems with the usage of complex network methods. Many researchers simply use the degree centrality as a proxy for node importance in a network. We show that such assumption can lead to rather overestimated robustness values, neglecting much stronger attacks.

The introduction of ADS-B, a satellite-based aircraft tracking technology, and the increasing installation of ADS-B receiver stations around the globe eases the tracking of aircraft, compared with traditional solutions using secondary radar. Given the large scale of ADS-B implementation and the high frequency of data collection, storing and managing ADS-B induced data has become increasingly difficult: The worldwide ADS-B data easily aggregates to several hundreds of terabyte per year, depending on the spatial coverage and temporal resolution. Standard data management solutions do not work well for ADS-B data, since they either require a large uncompressed index structure or cannot be queried efficiently. In this paper, we propose a novel compressed index structure for managing ADS-B data, called ADS-BI. The essential building blocks are spatio-temporal reference partitioning, reordering, and compression. On top of the partitioned, compressed representation, metadata is stored effectively, and exploited during query answering for typical ATM related task such as trajectory adherence evaluation, as well as complexity and safety metrics assessment by only accessing parts of the compressed data as necessary. Our novel index structure is evaluated on worldwide ADS-B data for a week in November 2016. For comparison, we implemented ten standard compression/indexing methods. The experiments reveal that none of these traditional methods can target the sweet spot between a small storage and efficient query answering. Our novel technique provides fast query answering at smallest storage costs. This paper contributes toward efficient handling of the increasing amount of traffic data in air traffic management, and eventually, toward more efficient and safer air transportation.

Understanding and improving global mobility has gained increased interest during the last decades. However, studies on the railway network are spatially limited so far, mostly investigating the domestic network of a country. Data availability is a major limiting factor for the analysis of these networks. Despite the increased open data movement, network operators are often reluctant to publish their infrastructure and passenger data. Existing large-scale studies usually make use of hand-collected data, for instance, based on historical cartographies. In this paper, we develop and implement a methodology to extract the worldwide railway skeleton network from the open data repository OpenStreetMap, where nodes are stations/waypoints and links are weights with information such as spatial distance, gauge, and maximum speed. We describe how we solved several data cleansing and scalability issues and developed network simplification techniques, in order to obtain an adequate representation of the network. We show that the network breaks down into few large and many small components. Furthermore, we show that this public data set can be used for efficient minimum travel time estimation between stations or cities. This paper leads to the development of a new research data set and contributes toward the ability of analyzing global mobility patterns, particularly regarding multimodality and cross-country transportation.

Transit agencies electronically publish transit schedules and route data to improve customer experience or as part of the open-data initiative. The release of such data poses several data management challenges because schedules for a single city can easily exceed storage requirements of several hundreds of megabytes. One way to deal with these challenges is data compression. The encoding of public transit schedules often follows the General Transit Feed Specification (GTFS), which cannot be compressed well out of the box. We propose GTFSCompress, which is an algorithm for compression of GTFS data, based on referential compression queues, which compress a column stream depending on previously seen items in this stream and other streams. Our evaluation on ten real-world data sets shows that GTFS feeds can be compressed by a factor of 100 and more. This is up to one order of magnitude better than using the best standard compressors.

Efficiently storing and searching collections of similar strings, such as large populations of genomes or long change histories of documents from Wikis, is a timely and challenging problem. Several recent proposals could drastically reduce space requirements by exploiting the similarity between strings in so-called reference-based compression. However, these indexes are usually not searchable any more, i.e., in these methods search efficiency is sacrificed for storage efficiency. We propose Multi-Reference Compressed Search Indexes (MRCSI) as a framework for efficiently compressing dissimilar string collections. In contrast to previous works which can use only a single reference for compression, MRCSI (a) uses multiple references for achieving increased compression rates, where the reference set need not be specified by the user but is determined automatically, and (b) supports efficient approximate string searching with edit distance constraints. We prove that finding the smallest MRCSI is NP-hard. We then propose three heuristics for computing MRCSIs achieving increasing compression ratios. Compared to state-of-the-art competitors, our methods target an interesting and novel sweet-spot between high compression ratio versus search efficiency.

Air traffic management (ATM) is facing a tremendous increase in the amount of available flight data, particularly four-dimensional (4D) trajectories. Computational requirements for analysis and storage of such bulk of data are steeply increasing. Compression is one key technology to address this challenge. In this paper we propose two techniques for compressing air traffic 4D trajectories. Our first technique analyzes a set of samples and computes a prediction for the most likely picked successor coordinate by a random walker. The second technique, i.e., referential compression, compresses a 4D trajectory as a collection of subtrajectory pointers into a reference trajectory. We evaluate our algorithms on trajectory data from the Demand Data Repository provided by EUROCONTROL. We show that a combination of our referential and statistical compression techniques compresses 4D trajectories of all air traffic over Europe in the year 2013 from 60 GB down to 0.78 GB, achieving a compression ratio of more than 75 : 1. The compression ratio for our techniques increases with the number of to-be-compressed flights, whereas standard compression techniques achieve a fixed compressed ratio for any number of flights. Our work contributes toward efficient handling of the increasing amount of traffic data in ATM.

Until recently, genomics has concentrated on comparing sequences between species. However, due to the sharply falling cost of sequencing technology, studies of populations of individuals of the same species are now feasible and promise advances in areas such as personalized medicine and treatment of genetic diseases. A core operation in such studies is read mapping, i.e., finding all parts of a set of genomes which are within edit distance k to a given query sequence ( k -approximate search). To achieve sufficient speed, current algorithms solve this problem only for one to-be-searched genome and compute only approximate solutions, i.e., they miss some k - approximate occurrences. We present RCSI, Referentially Compressed Search Index, which scales to a thousand genomes and computes the exact answer. It exploits the fact that genomes of different individuals of the same species are highly similar by first compressing the to-be-searched genomes with respect to a reference genome. Given a query, RCSI then searches the reference and all genome-specific individual differences. We propose efficient data structures for representing compressed genomes and present algorithms for scalable compression and similarity search. We evaluate our algorithms on a set of 1092 human genomes, which amount to approx. 3 TB of raw data. RCSI compresses this set by a ratio of 450:1 (26:1 including the search index) and answers similarity queries on a mid-class server in 15 ms on average even for comparably large error thresholds, thereby significantly outperforming other methods. Furthermore, we present a fast and adaptive heuristic for choosing the best reference sequence for referential compression, a problem that was never studied before at this scale.

In many applications, sets of similar texts or sequences are of high importance. Prominent examples are revision histories of documents or genomic sequences. Modern high-throughput sequencing technologies are able to generate DNA sequences at an ever-increasing rate. In parallel to the decreasing experimental time and cost necessary to produce DNA sequences, computational requirements for analysis and storage of the sequences are steeply increasing. Compression is a key technology to deal with this challenge. Recently, referential compression schemes, storing only the differences between a to-be-compressed input and a known reference sequence, gained a lot of interest in this field. In this paper, we propose a general open-source framework to compress large amounts of biological sequence data called Framework for REferential Sequence COmpression (FRESCO). Our basic compression algorithm is shown to be one to two orders of magnitudes faster than comparable related work, while achieving similar compression ratios. We also propose several techniques to further increase compression ratios, while still retaining the advantage in speed: 1) selecting a good reference sequence; and 2) rewriting a reference sequence to allow for better compression. In addition,we propose a new way of further boosting the compression ratios by applying referential compression to already referentially compressed files (second-order compression). This technique allows for compression ratios way beyond state of the art, for instance,4,000:1 and higher for human genomes. We evaluate our algorithms on a large data set from three different species (more than 1,000 genomes, more than 3 TB) and on a collection of versions of Wikipedia pages. Our results show that real-time compression of highly similar sequences at high compression ratios is possible on modern hardware.

In the last years, the vision of the Semantic Web fostered the interest in reasoning over ever larger sets of assertional statements in ontologies. It is easily conjectured that, soon, real-world ontologies will not fit into main memory anymore. If this was the case, state-of-the-art description logic reasoning systems cannot deal with these ontologies any longer, since they rely on in-memory structures.