Search

The allocation of ground holding is a key problem in air traffic flow management. There is a considerable body of research in this area, which primarily considers the impact of weather-induced capacity uncertainties In this presentation, however, we focus on uncertainty that arises on the demand-side, that is, due to the unpredictable aircraft arrival times. We present procedures to determine optimal ground holding levels when such uncertainty is present, and evaluate its impact on overall flow management performance.

In this talk, we present mathematical models for the time slot allocation problem under uncertainty. The scope of the model is to allocate time slots to airlines while minimizing the deviation of the assigned slots to the requests. The model takes into account the existing EU/IATA rules, operational constraints, and coordination procedures with the ultimate objective of better accommodating airlines’ preferences at coordinated airports. To include uncertainty within the decision model, we present stochastic integer programming formulations with either recourse actions, probabilistic constraints or both. To solve the problem we present decomposition-based approaches. To ameliorate the computational performance of the proposed models, we present two approximations of the recourse function. Each approximation is characterized by a different trade-off between the quality of the solution computed and the computational performance. The first approximation uses a simple recourse function while the second utilizes a fixed recourse function. The computational analysis shows the viability of the proposed approach

The stochastic Air traffic Flow Management (ATFM) problem is now attracting a lot of interest from the research community. In this talk, we present a two-stage stochastic integer programming formulation for the problem, which balance the trade-off between the complexity of the model and its representation of reality. To solve the problem, we present a decomposition approach to take advantage of the underlying structure of the problem

In this paper we present a model to describe inbound congestion in air tra c systems. The model is based on an arrival process which adds a random delay to each arrival time of an homogeneous schedule. The deviation of the delay is much larger than the expected time between two consecutive arrivals 1 . The fact that groups of aircraft may request to land with very small interarrival times, due to the randomness of the system, causes congestion, with consequent additional queueing delay of aircraft to be spent in holding paths. This model has been proposed numerically by M. Ball and collaborators. From an experimental point of view the arrival process de ned by the model above causes a congestion that is quite similar to the observed one. This study represents an improvement of the state-of-art in this eld, mainly for the following reasons. First, we have been able to provide a complete theoretical control of the system and to do this it has been natural to split the description of the system on two di erent time scales, and this gives an additional insight to the problem. In particular the evolution of congestion, even in non-equilibrium conditions, can be viewed as the superposition of two processes. A relatively simple process that evolves on time scales of the order of the standard deviation of the delay of the aircraft (slow varying process) and a more complicate process, evolving on a time scale of the order of the landing time, and hence much faster than the rst one. The slow process can be identi ed in terms of easily measurable quantities (the number of aircraft that are arriving with a positive delay and the number of aircraft that are anticipating their arrival) and it is the relevant quantity in order to compute the average congestion in the system. The fast process describes the deviation from the average length of the queue, and it is important to evaluate the safety problems due to rare but observable peaks of tra c. All this description is absolutely non standard in the classical approach to this problem, that is based on Poisson arrivals hypothesis and/or on purely numerical approach. The second reason for considering the proposed model as state-of-art is that it bene ts of concepts and ideas coming from totally di erent elds, namely equilibrium and non- equilibrium statistical mechanics. In particular the similarity of our model of arrivals with the Poisson model on short time scales is related to the evolution of the many particle systems starting from non equilibrium conditions, while the complete control of the fast process mentioned above, which is quite complicated, has been possible due to its similarity with the computations related with a particular class of systems of particles obeying an exclusion principle. In the paper the comparison between the exact results of our model and the observed data is discussed, and a detailed control of the non-equilibrium features of the system is also 1 presented. The latter is important when one wants to control the transient times, i.e., the time needed in order to return to a stationary distribution once the system is perturbed by a shock (e.g., a sudden reduction of arrival capacity at airports and/or unforeseen peak of demand)

Several applications in the fields of computational biology, surveillance systems and facility location among others can be formalized as a generalization of the set covering problem. In this talk, we present the multi-mode set covering problem. Given a set of modalities M, a ground set S, |M| families of subsets of S, one for each modality, and a cost function defined on all the subsets of S, the multi-mode covering problem (MMCP) requires finding a least total cost collection of subsets such that each element of the ground set is covered in all the modes, with the additional condition that some constraints (of knapsack type) on the selected sets are satisfied. The MMCP is clearly NP complete and is difficult to solve by commercial solvers. We present a branch-and-bound algorithm based on lagrangian relaxation. To compute feasible solutions of the problem, we implement a Variable Neighbourhood Search metaheuristic. The algorithms are tested on a set of randomly-generated benchmark instances

In this paper, we present a software framework for the air traffic system that includes and integrates several architectural components devoted to the dynamic allocation, exchange and self-adaptation of resources. Some of these components, namely the allocation and the adaptation of resources, are managed at a centralized level by a single authority, whereas the resource exchange component is envisioned as a de- centralized decision process aiming to enlarge the participation of resources’ users in the decision pro- cess. Several variants of the resource exchange com- ponent can be proposed differing for the underly- ing mechanisms of resource exchange. By means of Petri net’s formalisms and results, we compare and validate the mechanisms underlying the resource exchange components. The architecture of the air traffic system herein proposed is consistent with the Collaborative Decision Making (CDM) philosophy and provides a solution towards a full implementation of CDM.

In this paper, we present a mathematical model to design the service network, that is the set of origin-destination connections. The resulting model considers both full and empty freight car movements, and takes into account handling costs. More specifically, the model suggests the services to provide, as well as the number of trains and the number and type of cars traveling on each connection. Quality of service, which is measured as total travel time, is established by minimizing the waiting time of cars at intermediate stations. Our approach yields a multi-commodity network design problem with concave arc cost functions. To solve this problem, we implement a tabu search procedure which adopts ``perturbing'' mechanisms to force the algorithm to explore a larger portion of the feasible region. Computational results on realistic instances show a significant improvement over current practice.

In this paper we present a branch-and-price method to solve special structured multi-stage stochastic integer programming problems. We validate our method on two different versions of a multi-stage stochastic batch-sizing problem. One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications.

Scheduling is a complex activity that is needed in a large number of fields, which can involve heterogeneous factors and that may have different goals. In this thesis, scheduling problems that involve the air traffic field at different phases are faced. At each phase, the different characteristics of the problems are considered, devoting special attention to uncertainty. Given the heterogeneous characteristics and goals of the problems, different models and methods are proposed to solve each of them. The first analyzed phase is the strategic phase. It takes place around six months before the operation of flights, when they need to be assigned scheduled departure and arrival times at the airports where they operate. Future capacity realizations are very difficult to forecast at this phase, as capacity is influenced by weather conditions. A two-stage stochastic programming model with two alternative formulations is proposed to capture this uncertainty. Since the number of scenarios may be extreme, Sample Average Approximation is used to solve the model. The utilization of the proposed model allows to identify advantageous tradeoffs between schedule/request discrepancies, i.e., the distance between the allocated schedule and airline requests, and operational delays. This tradeoff can result in substantial reductions of the cost of delays for airlines. In the computational experiments, delays were reduced up to 45% on an instance representing a network of European airports. The second considered phase is the tactical phase, which takes place on the day of operation of flights. At this time, complete flight plans need to be defined, specifying the route and operation times of flights. This is done considering two different sources of uncertainty. First, uncertainty on capacity availability is taken into account, similarly to the strategic phase. However, the number of capacity realization scenarios is now small, as they can be defined using available weather forecasts. The problem of minimizing delay costs considering this source of uncertainty is the Stochastic Air Traffic Flow Management problem. A two-stage stochastic programming model with two alternative formulations is proposed to solve this problem. An ad-hoc heuristic that takes advantage of the good structure of the model is used to solve problem instances within short computation times. The analysis of the Value of the Stochastic Solution shows that the proposed stochastic model can significantly reduce delay costs when bad weather affects the whole network. Second, the implicit uncertainty on the departure time of flights is taken into account. This kind of uncertainty involves operations that may cause a delay on the scheduled departure time of a flight. The flexibility of the scheduled time of departure, as well as the other flight operations, is determined defining time windows within which flights are granted capacity resources to operate. The narrower a time window, the more critical a flight operation. The problem of minimizing delay cost and maximizing time windows is faced by the Air Traffic Flow Management Problem with Time Windows. The problem is formulated with two alternative deterministic models, one of which is able to provide time windows in 40" on average for instances involving over 6,000 flights. Less conservative criteria to reserve capacity within time windows can also be used. Despite not granting the possibility for a flight to execute its operations at every instant of a time window, the implementation of these alternative criteria is shown to be viable. In fact, less than 0.14% of flights were subject to capacity shortages in the analyzed cases. Finally, the operational phase takes place when operations are being executed. The goal at this phase is to manage the final departure times announced by flights - with uncertain information becoming deterministic - allowing them to depart at the announced time even if this time exceeds the assigned departure time window. This problem is named Real Time Flight Rescheduling with Time Windows. Resources are provided to flights that need them by reallocating previously reserved capacity with an algorithm that follows the Ration-By-Schedule mechanism. Both the practical usage of time windows and the impact of collaboration among airlines are studied. While airline collaboration limits time window flexibility up to some time before the scheduled departure of a flight, it can allow to reduce additional flight delays by over 14%. This thesis is a first work that involves determining flight schedules from the moment of their definition to the time of execution of flights. Providing cost reductions by considering the different factors that influence each decision phase can lead to a global improvement of the management of flight operations, whose delays are very expensive in practice for airlines.