Il genere Rhododendron L.: diversità genetica e fenomeni di ibridazione.

La terra, nel corso della sua storia, ha subito molteplici cambiamenti con la comparsa e scomparsa di numerose specie animali e vegetali. Attualmente, l’estinzioni delle specie, la riduzione degli areali e il depauperamento degli ecosistemi è da ricollegare alle attività dell’uomo. Per tali motivi, in questi ultimi decenni si è iniziato a dare importanza alla conservazione della biodiversità, alla creazione di zone protette e a sviluppare interventi di reintroduzione e rafforzamento di specie rare e a rischio di estinzione. Questo lavoro di tesi si propone di analizzare la variabilità genetica delle popolazioni di Rhododendron ferrugineum L. lungo il suo areale, con particolare attenzione alle aree marginali dell’Appennino, dove la specie rappresenta un caso di pseudo rarità, al fine di valutare lo stato di salute della specie al limite del suo areale e valutare appropriati interventi di conservazione o reintroduzione. Per effettuare le analisi sono stati messi a punto dei marcatori molecolari discontinui, i microsatelliti, che, essendo dei marcatori co-dominati, permettono di valutare differenti parametri legati alla diversità genetica delle popolazioni inclusi i livelli di eterozigotà ed il flusso genico tra popolazioni limitrofe. I campionamenti sono stati effettuati nelle uniche 3 stazioni presenti sugli Appennini. Al fine di confrontare la struttura genetica di queste popolazioni sono state considerate anche popolazioni delle Alpi Marittime, delle Alpi centro-orientali e dei Pirenei. L’analisi della diversità genetica effettuata su questo pool di popolazioni analizzate con 7 marcatori microsatelliti, ha messo in evidenza che le popolazioni relitte dell’Appennino Tosco-Emiliano presentano un ridotto livello di eterozigosità che suggerisce quindi un elevato livello di inbreeding. Si ritiene che ciò sia dovuto alla loro dislocazione sul territorio, che le rende isolate sia tra di loro che dalle popolazioni delle vicine Alpi Marittime. La stima delle relazioni genetiche tra le popolazioni appenniniche e le vicine piante alpine evidenzia come non vi sia scambio genetico tra le popolazioni. Le analisi dei cluster suggeriscono che due delle popolazioni Appenniniche siano più simili alle popolazioni della Alpi Marittime, mentre la terza ha più affinità con le popolazioni delle Alpi centro-orientali. Le popolazioni dei Pirenei risultano essere geneticamente più simili alle popolazioni delle Alpi Marittime, in particolare alle tre popolazioni del versante francese. In questo lavoro abbiamo affrontato anche il problema delle specie ibride. Rhododendron x intermedium Tausch è un ibrido frutto dell’incrocio tra Rhododendron ferrugineum L. e Rhododendron hirsutum L., in grado di incrociarsi sia con altri ibridi, sia con i parentali (fenomeno dell’introgressione). L’origine di questo ibrido risiede nella simpatria delle due specie parentali, che tuttavia, presentano esigenze ecologiche differenti. Ad oggi la presenza di Rhododendron x intermedium è stata accertata in almeno tre stazioni sulle Alpi Italiane, ma la letteratura documenta la sua presenza anche in altre zone dell’Arco Alpino. L’obiettivo di questa ricerca è stato quello di verificare la reale natura ibrida di Rhododendron x intermedium in queste stazioni utilizzando un approccio integrato ossia sia attraverso un’analisi di tipo morfologico sia attraverso un analisi di tipo molecolare. In particolare l’approccio molecolare ha previsto prima un’analisi filogenetica attraverso l’utilizzo di marcatori molecolari filogenetici nucleari e plastidiali (ITS, At103, psbA-trnH e matK) e quindi un’analisi della struttura delle popolazioni della specie ibrida attraverso l’utilizzo di marcatori molecolari microsatelliti. Da un’analisi morfologica, risulta che gli esemplari ibridi possono essere molto differenti tra loro e ciò supporta la formazione di sciami ibridi. Al fine di verificare la natura di questa specie e la struttura delle popolazioni ibride e dei rispettivi parentali, sono state campionate differenti popolazioni in tutta l’area di interesse. I campioni ottenuti sono stati quindi analizzati geneticamente mediante marcatori molecolari del DNA. I risultati ottenuti hanno permesso innanzitutto di confermare l’origine ibrida degli individui di prima generazione della specie Rhododendron x intermedium e quindi di distinguere i parentali dagli ibridi ed evidenziare la struttura genetica delle popolazioni ibride.

Formulations and Algorithms for Routing Problems

Combinatorial Optimization is a branch of optimization that deals with the problems where the set of feasible solutions is discrete. Routing problem is a well studied branch of Combinatorial Optimization that concerns the process of deciding the best way of visiting the nodes (customers) in a network. Routing problems appear in many real world applications including: Transportation, Telephone or Electronic data Networks. During the years, many solution procedures have been introduced for the solution of different Routing problems. Some of them are based on exact approaches to solve the problems to optimality and some others are based on heuristic or metaheuristic search to find optimal or near optimal solutions. There is also a less studied method, which combines both heuristic and exact approaches to face different problems including those in the Combinatorial Optimization area. The aim of this dissertation is to develop some solution procedures based on the combination of heuristic and Integer Linear Programming (ILP) techniques for some important problems in Routing Optimization. In this approach, given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in an attempt to find a new improved solution.

Integrating Crew Scheduling and Rostering Problems

Crew scheduling and crew rostering are similar and related problems which can be solved by similar procedures. So far, the existing solution methods usually create a model for each one of these problems (scheduling and rostering), and when they are solved together in some cases an interaction between models is considered in order to obtain a better solution. A single set covering model to solve simultaneously both problems is presented here, where the total quantity of drivers needed is directly considered and optimized. This integration allows to optimize all of the depots at the same time, while traditional approaches needed to work depot by depot, and also it allows to see and manage the relationship between scheduling and rostering, which was known in some degree but usually not easy to quantify as this model permits. Recent research in the area of crew scheduling and rostering has stated that one of the current challenges to be achieved is to determine a schedule where crew fatigue, which depends mainly on the quality of the rosters created, is reduced. In this approach rosters are constructed in such way that stable working hours are used in every week of work, and a change to a different shift is done only using free days in between to make easier the adaptation to the new working hours. Computational results for real-world-based instances are presented. Instances are geographically diverse to test the performance of the procedures and the model in different scenarios.

Architectures and design patterns for functional design of logic control and diagnostics in industrial automation

Recently in most of the industrial automation process an ever increasing degree of automation has been observed. This increasing is motivated by the higher requirement of systems with great performance in terms of quality of products/services generated, productivity, efficiency and low costs in the design, realization and maintenance. This trend in the growth of complex automation systems is rapidly spreading over automated manufacturing systems (AMS), where the integration of the mechanical and electronic technology, typical of the Mechatronics, is merging with other technologies such as Informatics and the communication networks. An AMS is a very complex system that can be thought constituted by a set of flexible working stations, one or more transportation systems. To understand how this machine are important in our society let considerate that every day most of us use bottles of water or soda, buy product in box like food or cigarets and so on. Another important consideration from its complexity derive from the fact that the the consortium of machine producers has estimated around 350 types of manufacturing machine. A large number of manufacturing machine industry are presented in Italy and notably packaging machine industry,in particular a great concentration of this kind of industry is located in Bologna area; for this reason the Bologna area is called “packaging valley”. Usually, the various parts of the AMS interact among them in a concurrent and asynchronous way, and coordinate the parts of the machine to obtain a desiderated overall behaviour is an hard task. Often, this is the case in large scale systems, organized in a modular and distributed manner. Even if the success of a modern AMS from a functional and behavioural point of view is still to attribute to the design choices operated in the definition of the mechanical structure and electrical electronic architecture, the system that governs the control of the plant is becoming crucial, because of the large number of duties associated to it. Apart from the activity inherent to the automation of themachine cycles, the supervisory system is called to perform other main functions such as: emulating the behaviour of traditional mechanical members thus allowing a drastic constructive simplification of the machine and a crucial functional flexibility; dynamically adapting the control strategies according to the different productive needs and to the different operational scenarios; obtaining a high quality of the final product through the verification of the correctness of the processing; addressing the operator devoted to themachine to promptly and carefully take the actions devoted to establish or restore the optimal operating conditions; managing in real time information on diagnostics, as a support of the maintenance operations of the machine. The kind of facilities that designers can directly find on themarket, in terms of software component libraries provides in fact an adequate support as regard the implementation of either top-level or bottom-level functionalities, typically pertaining to the domains of user-friendly HMIs, closed-loop regulation and motion control, fieldbus-based interconnection of remote smart devices. What is still lacking is a reference framework comprising a comprehensive set of highly reusable logic control components that, focussing on the cross-cutting functionalities characterizing the automation domain, may help the designers in the process of modelling and structuring their applications according to the specific needs. Historically, the design and verification process for complex automated industrial systems is performed in empirical way, without a clear distinction between functional and technological-implementation concepts and without a systematic method to organically deal with the complete system. Traditionally, in the field of analog and digital control design and verification through formal and simulation tools have been adopted since a long time ago, at least for multivariable and/or nonlinear controllers for complex time-driven dynamics as in the fields of vehicles, aircrafts, robots, electric drives and complex power electronics equipments. Moving to the field of logic control, typical for industrial manufacturing automation, the design and verification process is approached in a completely different way, usually very “unstructured”. No clear distinction between functions and implementations, between functional architectures and technological architectures and platforms is considered. Probably this difference is due to the different “dynamical framework”of logic control with respect to analog/digital control. As a matter of facts, in logic control discrete-events dynamics replace time-driven dynamics; hence most of the formal and mathematical tools of analog/digital control cannot be directly migrated to logic control to enlighten the distinction between functions and implementations. In addition, in the common view of application technicians, logic control design is strictly connected to the adopted implementation technology (relays in the past, software nowadays), leading again to a deep confusion among functional view and technological view. In Industrial automation software engineering, concepts as modularity, encapsulation, composability and reusability are strongly emphasized and profitably realized in the so-calledobject-oriented methodologies. Industrial automation is receiving lately this approach, as testified by some IEC standards IEC 611313, IEC 61499 which have been considered in commercial products only recently. On the other hand, in the scientific and technical literature many contributions have been already proposed to establish a suitable modelling framework for industrial automation. During last years it was possible to note a considerable growth in the exploitation of innovative concepts and technologies from ICT world in industrial automation systems. For what concerns the logic control design, Model Based Design (MBD) is being imported in industrial automation from software engineering field. Another key-point in industrial automated systems is the growth of requirements in terms of availability, reliability and safety for technological systems. In other words, the control system should not only deal with the nominal behaviour, but should also deal with other important duties, such as diagnosis and faults isolations, recovery and safety management. Indeed, together with high performance, in complex systems fault occurrences increase. This is a consequence of the fact that, as it typically occurs in reliable mechatronic systems, in complex systems such as AMS, together with reliable mechanical elements, an increasing number of electronic devices are also present, that are more vulnerable by their own nature. The diagnosis problem and the faults isolation in a generic dynamical system consists in the design of an elaboration unit that, appropriately processing the inputs and outputs of the dynamical system, is also capable of detecting incipient faults on the plant devices, reconfiguring the control system so as to guarantee satisfactory performance. The designer should be able to formally verify the product, certifying that, in its final implementation, it will perform itsrequired function guarantying the desired level of reliability and safety; the next step is that of preventing faults and eventually reconfiguring the control system so that faults are tolerated. On this topic an important improvement to formal verification of logic control, fault diagnosis and fault tolerant control results derive from Discrete Event Systems theory. The aimof this work is to define a design pattern and a control architecture to help the designer of control logic in industrial automated systems. The work starts with a brief discussion on main characteristics and description of industrial automated systems on Chapter 1. In Chapter 2 a survey on the state of the software engineering paradigm applied to industrial automation is discussed. Chapter 3 presentes a architecture for industrial automated systems based on the new concept of Generalized Actuator showing its benefits, while in Chapter 4 this architecture is refined using a novel entity, the Generalized Device in order to have a better reusability and modularity of the control logic. In Chapter 5 a new approach will be present based on Discrete Event Systems for the problemof software formal verification and an active fault tolerant control architecture using online diagnostic. Finally conclusive remarks and some ideas on new directions to explore are given. In Appendix A are briefly reported some concepts and results about Discrete Event Systems which should help the reader in understanding some crucial points in chapter 5; while in Appendix B an overview on the experimental testbed of the Laboratory of Automation of University of Bologna, is reported to validated the approach presented in chapter 3, chapter 4 and chapter 5. In Appendix C some components model used in chapter 5 for formal verification are reported.

Algorithms and Models For Combinatorial Optimization Problems

In this thesis we present some combinatorial optimization problems, suggest models and algorithms for their effective solution. For each problem,we give its description, followed by a short literature review, provide methods to solve it and, finally, present computational results and comparisons with previous works to show the effectiveness of the proposed approaches. The considered problems are: the Generalized Traveling Salesman Problem (GTSP), the Bin Packing Problem with Conflicts(BPPC) and the Fair Layout Problem (FLOP).

L'impatto delle politiche e dei programmi europei sullo sviluppo della società multiculturale e dello status sociale delle comunità minoritarie in Repubblica di Macedonia

L’oggetto della mia ricerca è la società multiculturale e il livello di sviluppo sociale delle comunità minoritarie in Macedonia, rispetto all’attuazione delle politiche e i programmi europei per la stabilizzazione democratica. L’indagine condotta nella mia tesi si è sviluppata esaminando i risultati ottenuti dai programmi CARDS, attuati per soddisfare gli obblighi stabiliti nell’Accordo di Stabilizzazione e Associazione e per l’implementazione dell’Accordo Quadro di Ohrid. Uno dei valori democratici, su cui l’UE è particolarmente attenta, ed al quale ha riservato un posto primario nei programmi CARDS, è la tutela dei diritti delle minoranze ossia il rispetto delle differenze culturali, linguistiche e religiose. L’obiettivo della mia indagine è stato quello di valutare l’impatto delle politiche europee sulla normativa macedone, concernente i diritti delle comunità minoritarie, ovvero il loro effetto sul consolidamento della società multiculturale e sullo status sociale delle comunità minoritarie in Macedonia. A tale scopo, in primo luogo sono stati esaminati gli emendamenti costituzionali e le modifiche legislative introdotti in seguito alla stipulazione dell’Accordo Quadro di Ohrid. L’analisi è stata incentrata nel verificare se la normativa macedone rientra nei parametri della normativa europea. I risultati ottenuti dimostrano quale è il tipo di multiculturalismo che promuove e garantisce la costituzione macedone. Attraverso l’analisi dei rapporti preparati dalla Commissione europea, relativi all’implementazione del Processo di Stabilizzazione e Associazione, è stato dimostrato come le politiche e i programmi europei hanno inciso sul consolidamento della società multiculturale. Analizzando invece i risultati dai rapporti relativi all’implementazione delle disposizioni dell’Accordo Quadro di Ohrid è stato valutato l’impatto che le politiche europee hanno avuto sullo sviluppo sociale delle comunità minoritarie in Macedonia. Per la valutazione di questo ultimo, sono state prese in considerazione il livello di partecipazione politica delle comunità minoritarie, la realizzazione delle richieste e delle questioni legate alla loro particolarità, l’ambito normativo regolato dal diritto di con-decisione, la rappresentanza delle comunità minoritarie nella sfera pubblica, il livello dell’accesso di istruirsi nella propria lingua e quindi il livello di istruzione e l’ambito e la libertà di usare la propria lingua nel settore pubblico. I concetti principali di questa ricerca sono: cooperazione, democrazia, multiculturalismo e sviluppo. Il termine cooperazione usato in questa ricerca si riferisce ai rapporti di cooperazione instaurati tra l’Unione Europea e la Macedonia nell’ambito dell’Accordo di Stabilizzazione e Associazione e dell’Accordo Quadro di Ohrid, ossia il sostegno dell’UE per la stabilizzazione democratica della Macedonia. Riferendosi a questa ultima, si fa riferimento al livello di garanzia di libera partecipazione dei cittadini, in ogni segmento della vita politica, sociale ed economica, senza discriminazioni etniche, linguistiche e religiose. Il termine multiculturalismo si riferisce alla società multiculturale ed è legato alla questione della politica della differenza, ossia del riconoscimento delle differenze culturali, che discendono dall’appartenenza ad una minoranza etnica e linguistica. Il multiculturalismo in questa ricerca viene analizzato, riferendosi alla multiculturalità della società macedone e ai diritti che la Costituzione macedone garantisce alle comunità minoritarie in Macedonia. Infine, per lo sviluppo in questa ricerca si fa riferimento allo sviluppo sociale delle comunità minoritarie, inteso e misurato tramite una seri di indicatori relativi all’occupazione (crescita di capitale sociale), all’educazione (capitale umano e qualifica di alta istruzione), alla partecipazione politica (occupazione dei posti principali nelle istituzione governative e della amministrazione pubblica), alla diffusione della cultura (uso e mantenimento della lingua e delle tradizioni) ecc. Prendendo in considerazione i principali concetti di questa tesi, il quadro teorico della ricerca sviluppa i nodi cruciali del dibattito sullo sviluppo e la democrazia, sul nesso tra democrazia e multiculturalismo e tra multiculturalismo e sviluppo. Attenendosi alle varie tesi, la ricerca avrà lo scopo di rilevare come si conciliano la società multiculturale macedone ed il modello democratico vigente. In questo contesto sarà fatto riferimento alle tesi fanno favoriscono la necessità di iniziare con la democrazia per poter innescare e sostenere il processo di sviluppo, alla tesi che sostiene la necessità di riconoscimento obbligatorio dei diritti collettivi nella società multiculturale, ossia dell’etnosviluppo delle comunità minoritarie. La ricerca è stata condotta tramite i seguenti metodi: - Il metodo descrittivo sarà usato per descrivere cosa è accaduto nel periodo di interesse di ricerca, riguardo i cambiamenti di natura sociale e politica delle minoranze in Macedonia. - Il metodo comparativo sarà applicato nella comparazione dell'efficacia delle leggi relative ai diritti delle minoranze e del loro status di sviluppo sociale e politico, prima e dopo l'attuazione e implementazione delle riforme europee. - Il metodo qualitativo sarà applicato per l’analisi di documenti, della legislatura e dei rapporti europei e nazionali. Le fonti usate in questa ricerca principalmente si basano su: - analisi di documenti e rapporti governativi, rapporti elaborati dalla Commissione Europea, dall’OSCE, dagli organi governativi e dalle organizzazioni non governative. - analisi di letteratura accademica, focalizzata sui problemi che sono oggetto di questa ricerca. - analisi di documenti pubblicati, come la gazzetta ufficiale, leggi costituzionali e atti legislativi, strategie nazionali e statistiche ufficiali. - analisi dei dati ottenuti da interviste e questionari.

New target tracking and monitoring guidance laws for UAV

A pursuer UAV tracking and loitering around a target is the problem analyzed in this thesis. The UAV is assumed to be a fixed-wing vehicle and constant airspeed together with bounded lateral accelerations are the main constraints of the problem. Three different guidance laws are designed for ensuring a continuos overfly on the target. Different proofs are presented to demonstrate the stability properties of the laws. All the algorithms are tested on a 6DoF Pioneer software simulator. Classic control design methods have been adopted to develop autopilots for implementig the simulation platform used for testing the guidance laws.

Cooperative teleoperation systems

This thesis deals with the studies on the Cooperative Teleoperation Systems. The literature on cooperative teleoperation did not take into account control architectures composed of pairs of wave-based bilateral teleoperators operating in a shared environment. In this work The author two cooperative control schemes based on wave variables by considering two pairs of single-master/single-slave devices collaborating to carry out operations in a shared remote environment are proposed. Such architectures have been validated both with simulations and experimental tests. Ch. 2 introduces a description of the two control architectures proposed and presents some simulation results where the cooperative teleoperation systems evolve in free space and in contact with a stiff wall. In the Ch. 3 some experimental results which confirm the positive results of the control schemes are illustred. Such results have been achieved by using a prototype custom built at Laboratory of Automaiton and Robotics of University of Bologna, which is also illustrated in this chapter. In Ch. 4 the problem of defining proper tools and procedures for an analysis, and possibly a comparison, of the performances of cooperative teleoperation systems is addressed. In particular, a novel generalization of criteria adopted for classical (i.e. one master-one slave) teleoperators is presented and illustrated on the basis of the force-position and the position-position cooperative control schemes proposed in Ch. 2, both from a transparency and stability point of view, and by assuming a null time delay in the communication channel.

Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

The cutting stock problem in the wood industry

This thesis proposes a solution for board cutting in the wood industry with the aim of usage minimization and machine productivity. The problem is dealt with as a Two-Dimensional Cutting Stock Problem and specific Combinatorial Optimization methods are used to solve it considering the features of the real problem.

Algorithms for UAS insertion in civil air space

One of the most interesting challenge of the next years will be the Air Space Systems automation. This process will involve different aspects as the Air Traffic Management, the Aircrafts and Airport Operations and the Guidance and Navigation Systems. The use of UAS (Uninhabited Aerial System) for civil mission will be one of the most important steps in this automation process. In civil air space, Air Traffic Controllers (ATC) manage the air traffic ensuring that a minimum separation between the controlled aircrafts is always provided. For this purpose ATCs use several operative avoidance techniques like holding patterns or rerouting. The use of UAS in these context will require the definition of strategies for a common management of piloted and piloted air traffic that allow the UAS to self separate. As a first employment in civil air space we consider a UAS surveillance mission that consists in departing from a ground base, taking pictures over a set of mission targets and coming back to the same ground base. During all mission a set of piloted aircrafts fly in the same airspace and thus the UAS has to self separate using the ATC avoidance as anticipated. We consider two objective, the first consists in the minimization of the air traffic impact over the mission, the second consists in the minimization of the impact of the mission over the air traffic. A particular version of the well known Travelling Salesman Problem (TSP) called Time-Dependant-TSP has been studied to deal with traffic problems in big urban areas. Its basic idea consists in a cost of the route between two clients depending on the period of the day in which it is crossed. Our thesis supports that such idea can be applied to the air traffic too using a convenient time horizon compatible with aircrafts operations. The cost of a UAS sub-route will depend on the air traffic that it will meet starting such route in a specific moment and consequently on the avoidance maneuver that it will use to avoid that conflict. The conflict avoidance is a topic that has been hardly developed in past years using different approaches. In this thesis we purpose a new approach based on the use of ATC operative techniques that makes it possible both to model the UAS problem using a TDTSP framework both to use an Air Traffic Management perspective. Starting from this kind of mission, the problem of the UAS insertion in civil air space is formalized as the UAS Routing Problem (URP). For this reason we introduce a new structure called Conflict Graph that makes it possible to model the avoidance maneuvers and to define the arc cost function of the departing time. Two Integer Linear Programming formulations of the problem are proposed. The first is based on a TDTSP formulation that, unfortunately, is weaker then the TSP formulation. Thus a new formulation based on a TSP variation that uses specific penalty to model the holdings is proposed. Different algorithms are presented: exact algorithms, simple heuristics used as Upper Bounds on the number of time steps used, and metaheuristic algorithms as Genetic Algorithm and Simulated Annealing. Finally an air traffic scenario has been simulated using real air traffic data in order to test our algorithms. Graphic Tools have been used to represent the Milano Linate air space and its air traffic during different days. Such data have been provided by ENAV S.p.A (Italian Agency for Air Navigation Services).