Abstract

International audience To sustain the rapidly increasing air traffic demand, the future air traffic management system will rely on a concept, called Trajectory-Based Operations (TBO), that will require aircraft to follow an assigned 4D trajectory (time-constrained trajectory) with high precision. TBO involves separating aircraft via strategic (long-term) trajectory deconfliction rather than the currently-practicing tactical (short-term) conflict resolution. In this context, this chapter presents a strategic trajectory planning approach aiming at minimizing the number of conflicts between aircraft trajectories for a given day. The proposed methodology allocates an alternative departure time, a horizontal flight path, and a flight level to each aircraft at a nation-wide scale.In real-life situations, aircraft may arrive at a given position with some uncertainties on its curvilinear abscissa due to external events. To ensure robustness of the strategic trajectory plan, the aircraft arrival time to any given position will be represented here by a probabilistic distribution over its nominal assigned arrival time.The proposed approach optimizes the 4D trajectory of each aircraft so as to minimize the probability of potential conflicts between trajectories. A hybrid-metaheuristic optimization algorithm has been developed to solve this large-scale mixed-variable optimization problem. The algorithm is implemented and tested with real air traffic data taking into account uncertainty over the French airspace for which a conflict-free and robust 4D trajectory plan is produced. Document type: Part of book or chapter of book

Abstract

This paper presents a traffic engineering framework able to optimize OSPF weight setting administrative procedures. Using the proposed framework, enhanced OSPF configurations are now provided to network administrators in order to effectively improve the QoS performance of the corresponding network domain. The envisaged NP-hard optimization problem is faced resorting to Evolutionary Algorithms, which allocate OSPF weights guided by a bi-objective function. The results presented in this work show that the proposed optimization tool clearly outperforms common weight setting heuristics. Document type: Part of book or chapter of book

Abstract

Modern communication networks offer advance and diverse applications, which require huge usage of network resources while providing quality of services to the users. Advance communication is based on multiple switched networks that cannot be handle by traditional IP (internet protocol) networks. GMPLS (Generalized multiprotocol label switched) networks, an advance version of MPLS (multiprotocol label switched networks), are introduced for multiple switched networks. Traffic engineering in GMPLS networks ensures traffic movement on multiple paths. Optimal path(s) computation can be dependent on multiple objectives with multiple constraints. From optimization prospective, it is an NP (non-deterministic polynomial-time) hard optimization problem, to compute optimal paths based on multiple objectives having multiple constraints. The paper proposed a metaheuristic Pareto based Bat algorithm, which uses two objective functions; routing costs and load balancing costs to compute the optimal path(s) as an optimal solution for traffic engineering in MPLS/GMPLS networks. The proposed algorithm has implemented on different number of nodes in MPLS/GMPLS networks, to analysis the algorithm performance. Document type: Part of book or chapter of book

Abstract

This paper proposes a novel traffic engineering framework able to automatically provide near-optimal OSPF routing configurations for QoS constrained scenarios. Within this purpose, this work defines a mathematical model able to measure the QoS compliance in a class-based networking domain. Based on such model, the NP-hard optimization problem of OSPF weight setting is faced resorting to Evolutionary Algorithms. The presented results show that, independently of other QoS aware mechanisms that might be in place, the proposed framework is able to improve the QoS level of a given domain only taking into account the direct influence of the routing component of the network. The devised optimization tool is able to optimize OSPF weight configurations in scenarios either considering a single level of link weights or using multiple levels of weights (one for each class) in multi-topology routing scenarios. Document type: Part of book or chapter of book

Abstract

Offline inter-domain outbound Traffic Engineering (TE) can be formulated as an optimization problem whose objective is to determine primary egress points for traffic exiting a domain. However, when egress point failures happen, congestion may occur if secondary egress points are not carefully determined. In this paper, we formulate a bi-level outbound TE problem in order to make outbound route selection robust to egress point failures. We propose a tabu search heuristic to solve the problem and compare the performance to three alternative approaches. Simulation results demonstrate that the tabu search heuristic achieves the best performance in terms of our optimization objectives and also keeps traffic disruption to a minimum. Document type: Part of book or chapter of book

Abstract

Optimal flight gate assignment is a highly relevant optimization problem from airport management. Among others, an important goal is the minimization of the total transit time of the passengers. The corresponding objective function is quadratic in the binary decision variables encoding the flight-to-gate assignment. Hence, it is a quadratic assignment problem being hard to solve in general. In this work we investigate the solvability of this problem with a D-Wave quantum annealer. These machines are optimizers for quadratic unconstrained optimization problems (QUBO). Therefore the flight gate assignment problem seems to be well suited for these machines. We use real world data from a mid-sized German airport as well as simulation based data to extract typical instances small enough to be amenable to the D-Wave machine. In order to mitigate precision problems, we employ bin packing on the passenger numbers to reduce the precision requirements of the extracted instances. We find that, for the instances we investigated, the bin packing has little effect on the solution quality. Hence, we were able to solve small problem instances extracted from real data with the D-Wave 2000Q quantum annealer. Document type: Part of book or chapter of book

Abstract

We consider a stochastic routing model in which the goal is to find the optimal route that incorporates a measure of risk The problem arises in traffic engineering, transportation and even more abstract settings such as task planning (where the time to execute tasks is uncertain), etc The stochasticity is specified in terms of arbitrary edge length distributions with given mean and variance values in a graph The objective function is a positive linear combination of the mean and standard deviation of the route Both the nonconvex objective and exponentially sized feasible set of available routes present a challenging optimization problem for which no efficient algorithms are known In this paper we evaluate the practical performance of algorithms and heuristic approaches which show very promising results in terms of both running time and solution accuracy. Document type: Part of book or chapter of book

Abstract

International audience To sustain the continuously increasing air traffic demand, the future air traffic management system will rely on a so-called trajectory based operations concept that will increase air traffic capacity by reducing the controllers’ workload. This will be achieved by transferring tactical conflict detection and resolution tasks to the strategic planning phase. In this future air traffic management paradigm context, this paper presents a methodology to address such trajectory planning at nation-wide and continent scale. The pro-posed methodology aims at minimizing the global interaction between aircraft trajectories by allocating alternative departure times, alternative horizontal flight paths, and alternative flight levels to the trajectories involved in the interaction. To improve robustness of the strategic trajectory planning, un-certainty of aircraft position and aircraft arrival time to any given position on the trajectory are considered. This paper presents a mathematical formulation of this strategic trajectory planning problem leading to a mixed-integer optimization problem, whose objective function relies on the new concept of interaction between trajectories. A computationally efficient algorithm to compute interaction between trajectories for large-scale applications is presented and implemented. Resolution method based on hybrid-metaheuristic algorithm have been developed to solve the above large-scale optimization problems. Finally, the overall methodology is implemented and tested with real air traffic data taking into account uncertainty over the French and the European airspace, involving more than 30,000 trajectories. Conflict-free and robust 4D trajectory planning are produced within computational time acceptable for the operation context, which shows the viability of the approach. Document type: Part of book or chapter of book

Abstract

International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems. Document type: Report