High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

Dans le secteur électrique et chez EDF, l'optimisation mathématique est utilisée pour modéliser et résoudre des problèmes de gestion de la production d'électricité.Citons quelques applications : la modélisation des problèmes d'équilibre des marchés, la gestion des risques d'épuisement des barrages, la programmation des arrêts de tranches nucléaires.Plus particulièrement l'hydroélectricté est une énergie renouvelable, peu chère, flexible mais limitée.Exploiter l'hydraulique constitue donc un enjeu important.Nous nous intéressons à des problèmes d'optimisation de Programmation Non Linéaire en Nombres Entiers (PNLNE) dont les variables de décision sont continues ou discrètes et dont les fonctions exprimant l'objectif et les contraintes sont linéaires ou non.Les non-linéarités et la combinatoire induite par les variables entières rendent les PNLNE difficiles à résoudre.En effet les méthodes existantes n'arrivent pas toujours à résoudre les grands PNLNE à l'optimalité avec des temps de calcul limités.En amont des performances de résolution, la faisabilité est une question préliminaire à aborder puisqu'il faut s'assurer que les PNLNE à résoudre admettent des solutions.Lorsqu'il y a des infaisabilités dans des modèles complexes, il est très utile mais très difficile de les analyser.Par ailleurs la résolution de PNLNE est plus difficile si l'on requiert une certification de la précision exacte des résultats.En effet les méthodes résolutions sont en général mises en oeuvre en arithmétique flottante, ce qui peut donner lieu à une précision approchée.Nous abordons deux problèmes d'optimisation liés à la planification de la production hydraulique, Hydro Unit-Commitment (HUC) en Anglais.Etant données des ressources d'eau finies dans les barrages l'objet du HUC est de prescrire des programmes de production les plus rentables qui soient compatibles avec les spécifications techniques des usines hydrauliques.Le volume, le débit et la puissance sont représentés par des variables continues tandis que l'activation des turbines est communément formulée avec des variables binaires.Les non-linéarités proviennent en général des fonctions qui expriment la puissance générée en fonction du volume et du débit.Nous distinguons deux problèmes : un PLNE avec des caractéristiques linéaires et discrètes et un PNL avec des caractéristiques non linéaires et continues.Dans le 2ème chapitre, nous traitons de la faisabilité d'un HUC réel en PLNE.Comparé à un HUC standard le modèle inclut deux spécifications supplémentaires : des points de fonctionnements discrets sur la courbe puissance-débit ainsi que des niveaux cibles pour le volume des réservoirs.Les complications liées aux données réelles et au calcul numérique, associées aux spécifications du modèle rendent notre problème difficile à résoudre et souvent infaisable.Nous procédons par étape pour identifier et traiter les sources d'infaisabilité, à savoir les erreurs numériques et les infaisabilités de modélisation, pour rendre le problème faisable.Des résultats numériques étayent l'efficacité de notre méthode sur un ensemble de test de 66 instances réelles qui contient de nombreuses infaisabilités.Le 3ème chapitre porte sur l'adaptation de l'algorithme Multiplicative Weights Update (MWU) à la PNLNE.Cette adaptation est fondée sur une reformulation paramétrée spécifique dénommée pointwise.Nous définissons des propriétés souhaitables pour obtenir de bonnes reformulations pointwise et nous fournissons des règles pour adapter l'algorithme étape par étape.Nous démontrons que notre matheuristique du MWU conserve une garantie d'approximation relative contrairement à la plupart des heuristiques.Le MWU est comparée à la méthode Multi-Start pour résoudre un HUC en PNL et les résultats numériques penchent en faveur du MWU. / In the electricity industry, and more specifically at the French utility company EDF, mathematical optimization is used to model and solve problems related to electricity production management.To name a few applications: planning for capacity investments, managing depletion risks of hydro-reservoirs, scheduling outages and refueling for nuclear plants.More specifically, hydroelectricity is a renewable, cheap, flexible but limited source of energy.Harnessing hydroelectricity is thus critical for electricity production management.We are interested in Mixed-Integer Non-Linear Programming (MINLP) optimization problems.They are optimization problems whose decision variables can be continuous or discrete and the functions to express the objective and constraints can be linear or non-linear.The non-linearities and the combinatorial aspect induced by the integer variables make these problems particularly difficult to solve.Indeed existing methods cannot always solve large MINLP problems to the optimum within limited computational timeframes.Prior to solution performance, feasibility is preliminary challenge to tackle since we want to ensure the MINLP problems to solve admit feasible solutions.When infeasibilities occur in complex models, it is useful but not trivial to analyze their causes.Also, certifying the exactness of the results compounds the difficulty of solving MINLP problems as solution methods are generally implemented in floating-point arithmetic, which may lead to approximate precision.In this thesis, we work on two optimization problems - a Mixed-Integer Linear Program (MILP) and a Non-Linear Program (NLP) - related to Short-Term Hydropower production Scheduling (STHS).Given finite resources of water in reservoirs, the purpose of STHS is to prescribe production schedules with largest payoffs that are compatible with technical specifications of the hydroelectric plants.While water volumes, water flows, and electric powers can be represented with continuous variables, commitment statuses of turbine units usually have to be formulated with binary variables.Non-linearities commonly originate from the Input/Output functions that model generated power according to water volume and water flow.We decide to focus on two distinguished problems: a MILP with linear discrete features and a NLP with non-linear continuous features.In the second chapter, we deal with feasibility issues of a real-world MILP STHS.Compared with a standard STHS problem, the model features two additional specifications:discrete operational points of the power-flow curve and mid-horizon and final strict targets for reservoir levels.Issues affecting real-world data and numerical computing, together with specific model features, make our problem harder to solve and often infeasible.Given real-world instances, we reformulate the model to make the problem feasible.We follow a step-by-step approach to exhibit and cope with one source of infeasility at a time, namely numerical errors and model infeasibilities.Computational results show the effectiveness of the approach on an original test set of 66 real-world instances that demonstrated a high occurrence of infeasibilities.The third chapter is about the transposition of the Multiplicative Weights Update algorithm to the (nonconvex) nonlinear and mixed integer nonlinear programming setting, based on a particular parametrized reformulation of the problem - denoted pointwise.We define desirable properties for deriving pointwise reformulation and provide generic guidelines to transpose the algorithm step-by-step.Unlike most metaheuristics, we show that our MWU metaheuristic still retains a relative approximation guarantee in the NLP and MINLP settings.We benchmark it computationally to solve a hard NLP STHS.We find it compares favorably to the well-known Multi-Start method, which, on the other hand, offers no approximation guarantee.

The main aim of this work is to provide decision makers suitable approaches for solving two crucial planning problems in the railway industry: the locomotive assignment problem and the crew scheduling problem with attendance rates. On the one hand, the focus is on practical usability and the necessary integration and consideration of real-life requirements in the planning process. On the other hand, solution approaches are to be developed, which can provide solutions of sufficiently good quality within a reasonable time by taking all these requirements into account.

Network virtualization has become a primary enabler to solve the internet ossi- fication problem. It allows to run multiple architectures or protocols on a shared physical infrastructure. One of the important aspects of network virtualization is to have a virtual network (VN) mapping technique which uses the substrate resources efficiently. Currently, there exists very few VN mapping techniques and there is no common evaluation strategy which can test these algorithms effectively. In this thesis, we advocate the need for such a tool and develop it by considering a wide spectrum of parameters and simulation scenarios. We also provide various performance metrics and do a comparison study of the existing algorithms. Based on the comparative study, we point out the positives and negatives of the existing mapping algorithms and propose a new LP formulation based on Hub location approach that efficiently allocates substrate resources to the virtual network requests. Our results show that our algorithm does better in terms of number of successful network mappings and average time to map while balancing load on the network.

This thesis analyzes the mean variance optimization problem with respect to cardinalityconstraints. The aim of this thesis is to figure out how much of an impact transactionchanges has on the profit and risk of a portfolio. We solve the problem by implementingmixed integer programming (MIP) and solving the problem by using the Gurobi solver.In doing this, we create a mathematical model that enforces the amount of transactionchanges from the initial portfolio. Our results is later showed in an Efficient Frontier,to see how the profit and risk are changing depending on the transaction changes.Overall, this thesis demonstrates that the application of MIP is an effective approachto solve the mean variance optimization problem and can lead to improved investmentoutcomes.

Due à l’augmentation de la force des changements climatiques, il devient critique d’éliminer les combustibles fossiles. Les véhicules électriques sont un bon moyen de réduire notre dépendance à ces matières polluantes, mais leur adoption est généralement limitée par le manque d’accessibilité à des stations de recharge. Dans cet article, notre but est d’agrandir l’infrastrucure liée aux stations de recharge pour fournir une meilleure qualité de service aux usagers (et une meilleure accessibilité aux stations). Nous nous attaquons spéficiquement au context urbain. Nous proposons de représenter un modèle d’assignation de demande de recharge à des stations sous la forme d’un problème de flux maximum. Ce modèle nous sert de base pour évaluer la satisfaction des usagers étant donné l’infrastruture disponible. Par la suite, nous incorporons le model de flux maximum à un programme en nombre entier mixte qui a pour but d’évaluer l’installation de nouvelles stations et d’étendre leur disponibilité en ajoutant plus de bornes de recharge. Nous présentons notre méthodologie dans le cas de la ville de Montréal et montrons que notre approche est en mesure résoudre des instances réalistes. Nous concluons en montrant l’importance de la variation dans le temps et l’espace de la demande de recharge lorsque l’on résout des instances de taille réelle. / With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of the user satisfaction by a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixedinteger linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

[pt] Este estudo apresenta um modelo de programação inteira mista para a roteirização de navios com controle de estoque nos portos para a movimentação de múltiplos produtos com uma frota heterogênea. O modelo contempla a possibilidade de transformação de produtos dentro de navios, o que representa uma flexibilidade para o modelo optar por qual produto utilizar para atender um cliente com demanda com qualidade flexível. Esta habilidade não foi encontrada em nenhum outro estudo. Ele também combina o atendimento de demandas obrigatórias com opcionais. O modelo então é aplicado em um caso real de movimentação de derivados escuros de petróleo em uma empresa de petróleo brasileira, cujo modelo atual utilizado apresenta problemas que dificultam seu uso. Devido ao longo tempo que leva para obter a solução ótima para estes tipos de modelos, são utilizadas as matheurísticas de relax-and-fix e fix-and-optimize para obter soluções boas em um tempo reduzido. São apresentados experimentos computacionais em uma série de cenários para validar a qualidade das soluções encontradas pelos métodos propostos, testando diferentes configurações e discretizações de tempo. Os resultados apresentados comprovam a superioridade dos métodos em comparação com o modelo matemático puro. O modelo proposto apresentou grande potencial de substituir o modelo atual da empresa e para alcançar a melhoria pretendida na programação dos navios. / [en] This dissertation presents a mixed integer program model to solve a ship routing and scheduling with stock control in ports, also known as maritime inventory routing. This model considers a heterogeneous fleet, carrying multiples products. It also has the ability to transform one product into another inside ships. This aspect allows the model to choose which product it wishes to deliver to a client with a less restrict quality specification in his demand. No model presented in other studies has this capability. Another possibility covered by this model is to combine mandatory demands with optional ones. The model is applied to a real case of maritime transportation of dirty oil products in a Brazilian oil company, whose current model has a series of small problems that hinders its use. Due to the long time it takes to get the optimal solution, the relax-and-fix and fix-andoptimize heuristics are used to get good solutions in a reduced time. With the use of computational experiments in a series of scenarios, it has proved the quality of the solutions found by the proposed methods, testing different configurations and discretizations of time. The results presented prove the superiority of the methods in comparison to the pure mathematical model. The proposed model has shown great potential to replace the current one and to achieve the improvement for the ship routing intended by the company.

Air transportation offers both passenger and freight services that are essential for economic growth and development. In a highly competitive environment, airline companies have to control their operating costs by managing their flights, aircraft, and crews effectively. This motivates the extensive use of analytical techniques to solve complex problems related to airline operations planning, which includes schedule design, fleet assignment, aircraft routing, and crew scheduling. The initial problem addressed by airlines is that of schedule design, whereby a set of flights having specific origin and destination cities as well as departure and arrival times is determined. Then, a fleet assignment problem is solved to assign an aircraft type to each flight so as to maximize anticipated profits. This enables a decomposition of subsequent problems according to the different aircraft types belonging to a common family, for each of which an aircraft routing problem and a crew scheduling or pairing problem are solved. Here, in the aircraft routing problem, a flight sequence or route is built for each individual aircraft so as to cover each flight exactly once at a minimum cost while satisfying maintenance requirements. Finally, in the crew scheduling or pairing optimization problem, a minimum cost set of crew rotations or pairings is constructed such that every flight is assigned a qualified crew and that work rules and collective agreements are satisfied. In practice, most airline companies solve these problems in a sequential manner to plan their operations, although recently, an increasing effort is being made to develop novel approaches for integrating some of the airline operations planning problems while retaining tractability. This dissertation formulates and analyzes three different models, each of which examines a composition of certain pertinent airline operational planning problems. A comprehensive fourth model is also proposed, but is relegated for future research. In the first model, we integrate fleet assignment and schedule design by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands pertaining to multiple fare-classes. A polyhedral analysis of the proposed mixed-integer programming model is used to derive several classes of valid inequalities for tightening its representation. Solution approaches are developed by applying Benders decomposition method to the resulting lifted model, and computational experiments are conducted using real data obtained from a major U.S. airline (United Airlines) to demonstrate the efficacy of the proposed procedures as well as the benefits of integration. A comparison of the experimental results obtained for the basic integrated model and for its different enhanced representations reveals that the best modeling strategy among those tested is the one that utilizes a variety of five types of valid inequalities for moderately sized problems, and further implements a Benders decomposition approach for relatively larger problems. In addition, when a heuristic sequential fixing step is incorporated within the algorithm for even larger sized problems, the computational results demonstrate a less than 2% deterioration in solution quality, while reducing the effort by about 21%. We also performed an experiment to assess the impact of integration by comparing the proposed integrated model with a sequential implementation in which the schedule design is implemented separately before the fleet assignment stage based on two alternative profit maximizing submodels. The results obtained demonstrate a clear advantage of utilizing the integrated model, yielding an 11.4% and 5.5% increase in profits in comparison with using the latter two sequential models, which translates to an increase in annual profits by about $28.3 million and $13.7 million, respectively. The second proposed model augments the first model with additional features such as flexible flight times (i.e., departure time-windows), schedule balance, and demand recapture considerations. Optional flight legs are incorporated to facilitate the construction of a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Moreover, network effects and realistic demand patterns are effectively represented by examining itinerary-based demands as well as multiple fare-classes. Allowing flexibility on the departure times of scheduled flight legs within the framework of an integrated model increases connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs. A provision is also made for airlines to capture an adequate market share by balancing flight schedules throughout the day. Furthermore, demand recapture considerations are modeled to more realistically represent revenue realizations. For this proposed mixed-integer programming model, which integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, itinerary-based demands, and multiple fare-classes, we perform a polyhedral analysis and utilize the Reformulation-Linearization Technique in concert with suitable separation routines to generate valid inequalities for tightening the model representation. Effective solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented to demonstrate the efficacy of the proposed procedures. Using real data obtained from United Airlines, when flight times were permitted to shift by up to 10 minutes, the estimated increase in profits was about $14.9M/year over the baseline case where only original flight legs were used. Also, the computational results indicated a 1.52% and 0.49% increase in profits, respectively, over the baseline case, while considering two levels of schedule balance restrictions, which can evidently also enhance market shares. In addition, we measured the effect of recaptured demand with respect to the parameter that penalizes switches in itineraries. Using values of the parameter that reflect 1, 50, 100, or 200 dollars per switched passenger, this yielded increases in recaptured demand that induced additional profits of 2.10%, 2.09%, 2.02%, and 1.92%, respectively, over the baseline case. Overall, the results obtained from the two schedule balance variants of the proposed integrated model that accommodate all the features of flight retiming, schedule balance, and demand recapture simultaneously, demonstrated a clear advantage by way of $35.1 and $31.8 million increases in annual profits, respectively, over the baseline case in which none of these additional features is considered. In the third model, we integrate the schedule design, fleet assignment, and aircraft maintenance routing decisions, while considering optional legs, itinerary-based demands, flexible flight retimings, recapture, and multiple fare-classes. Instead of utilizing the traditional time-space network (TSN), we formulate this model based on a flight network (FN) that provides greater flexibility in accommodating integrated operational considerations. In order to consider through-flights (i.e., a sequence of flight legs served by the same aircraft), we append a set of constraints that matches aircraft assignments on certain inbound legs into a station with that on appropriate outbound legs at the same station. Through-flights can generate greater revenue because passengers are willing to pay a premium for not having to change aircraft on connecting flights, thereby reducing the possibility of delays and missed baggage. In order to tighten the model representation and reduce its complexity, we apply the Reformulation-Linearization Technique (RLT) and also generate other classes of valid inequalities. In addition, since the model possesses many equivalent feasible solutions that can be obtained by simply reindexing the aircraft of the same type that depart from the same station, we introduce a set of suitable hierarchical symmetry-breaking constraints to enhance the model solvability by distinguishing among aircraft of the same type. For the resulting large-scale augmented model formulation, we design a Benders decomposition-based solution methodology and present extensive computational results to demonstrate the efficacy of the proposed approach. We explored four different algorithmic variants, among which the best performing procedure (Algorithm A1) adopted two sequential levels of Benders partitioning method. We then applied Algorithm A1 to perform several experiments to study the effects of different modeling features and algorithmic strategies. A summary of the results obtained is as follows. First, the case that accommodated both mandatory and optional through-flight leg pairs in the model based on their relative effects on demands and enhanced revenues achieved the most profitable strategy, with an estimated increase in expected annual profits of $2.4 million over the baseline case. Second, utilizing symmetry-breaking constraints in concert with compatible objective perturbation terms greatly enhanced problem solvability and thus promoted the detection of improved solutions, resulting in a $5.8 million increase in estimated annual profits over the baseline case. Third, in the experiment that considers recapture of spilled demand from primary itineraries to other compatible itineraries, the different penalty parameter values (100, 50, and 1 dollars per re-routed passenger) induced average respective proportions of 3.2%, 3.4%, and 3.7% in recaptured demand, resulting in additional estimated annual profits of $3.7 million, $3.8 million, and $4.0 million over the baseline case. Finally, incorporating the proposed valid inequalities within the model to tighten its representation helped reduce the computational effort by 11% on average, while achieving better solutions that yielded on average an increase in estimated annual profits of $1.4 million. In closing, we propose a fourth more comprehensive model in which the crew scheduling problem is additionally integrated with fleet assignment and aircraft routing. This integration is important for airlines because crew costs are the second largest component of airline operating expenses (after fuel costs), and the assignment and routing of aircraft plus the assignment of crews are two closely interacting components of the planning process. Since crews are qualified to typically serve a single aircraft family that is comprised of aircraft types having a common cockpit configuration and crew rating, the aircraft fleeting and routing decisions significantly impact the ensuing assignment of cockpit crews to flights. Therefore it is worthwhile to investigate new models and solution approaches for the integrated fleeting, aircraft routing, and crew scheduling problem, where all of these important inter-dependent processes are handled simultaneously, and where the model can directly accommodate various work rules such as imposing a specified minimum and maximum number of flying hours for crews on any given pairing, and a minimum number of departures at a given crew base for each fleet group. However, given that the crew scheduling problem itself is highly complex because of the restrictive work rules that must be heeded while constructing viable duties and pairings, the formulated integrated model would require further manipulation and enhancements along with the design of sophisticated algorithms to render it solvable. We therefore recommend this study for future research, and we hope that the modeling, analysis, and algorithmic development and implementation work performed in this dissertation will lend methodological insights into achieving further advances along these lines. / Ph. D.

We develop and evaluate two significant modeling concepts within the context of a large-scale Airspace Planning and Collaborative Decision-Making Model (APCDM) and, thereby, enhance its current functionality in support of both strategic and tactical level flight assessments. The first major concept is a new severe weather-modeling paradigm that can be used to assess existing tactical en route flight plan strategies such as the Flight Management System (FMS) as well as to provide rerouting strategies. The second major concept concerns modeling the mediated bartering of slot exchanges involving airline trade offers for arrival/departure slots at an arrival airport that is affected by the Ground Delay Program (GDP), while simultaneously considering issues related to sector workloads, airspace conflicts, as well as overall equity concerns among the airlines. This research effort is part of an $11.5B, 10-year, Federal Aviation Administration (FAA)-sponsored program to increase the U.S. National Airspace (NAS) capacity by 30 percent by the year 2010. Our innovative contributions of this research with respect to the severe weather rerouting include (a) the concept of "Probability-Nets" and the development of discretized representations of various weather phenomena that affect aviation operations; (b) the integration of readily accessible severe weather probabilities from existing weather forecast data provided by the National Weather Service (NWS); (c) the generation of flight plans that circumvent severe weather phenomena with specified probability levels, and (d) a probabilistic delay assessment methodology for evaluating planned flight routes that might encounter potentially disruptive weather along its trajectory. Given a fixed set of reporting stations from the CONUS Model Output Statistics (MOS), we begin by constructing weather-specific probability-nets that are dynamic with respect to time and space. Essential to the construction of the probability-nets are the point-by-point forecast probabilities associated with MOS reporting sites throughout the United States. Connections between the MOS reporting sites form the strands within the probability-nets, and are constructed based upon a user-defined adjacency threshold, which is defined as the maximum allowable great circle distance between any such pair of sites. When a flight plan traverses through a probability-net, we extract probability data corresponding to the points where the flight plan and the probability-net strand(s) intersect. The ability to quickly extract this trajectory-related probability data is critical to our weather-based rerouting concepts and the derived expected delay and related cost computations in support of the decision-making process. Next, we consider the superimposition of a flight-trajectory-grid network upon the probability-nets. Using the U.S. Navigational Aids (Navaids) as the network nodes, we develop an approach to generate flight plans that can circumvent severe weather phenomena with specified probability levels based on determining restricted, time-dependent shortest paths between the origin and destination airports. By generating alternative flight plans pertaining to specified threshold strand probabilities, we prescribe a methodology for computing appropriate expected weather delays and related disruption factors for inclusion within the APCDM model. We conclude our severe weather-modeling research by conducting an economic benefit analysis using a k-means clustering mechanism in concert with our delay assessment methodology in order to evaluate delay costs and system disruptions associated with variations in probability-net refinement-based information. As a flight passes through the probability-net(s), we can generate a probability-footprint that acts as a record of the strand intersections and the associated probabilities from origin to destination. A flight plan's probability-footprint will differ for each level of data refinement, from whence we construct route-dependent scenarios and, subsequently, compute expected weather delay costs for each scenario for comparative purposes. Our second major contribution is the development of a novel slot-exchange modeling concept within the APCDM model that incorporates various practical issues pertaining to the Ground Delay Program (GDP), a principal feature in the FAA's adoption of the Collaborative Decision-Making (CDM) paradigm. The key ideas introduced here include innovative model formulations and several new equity concepts that examine the impact of "at-least, at-most" trade offers on the entire mix of resulting flight plans from respective origins to destinations, while focusing on achieving defined measures of "fairness" with respect to the selected slot exchanges. The idea is to permit airlines to barter assigned slots at airports affected by the Ground Delay Program to their mutual advantage, with the FAA acting as a mediator, while being cognizant of the overall effect of the resulting mix of flight plans on air traffic control sector workloads, collision risk and safety, and equity considerations. We start by developing two separate slot-exchange approaches. The first consists of an external approach in which we formulate a model for generating a set of package-deals, where each package-deal represents a potential slot-exchange solution. These package-deals are then embedded within the APCDM model. We further tighten the model representation using maximal clique cover-based cuts that relate to the joint compatibility among the individual package-deals. The second approach significantly improves the overall model efficiency by automatically generating package-deals as required within the APCDM model itself. The model output prescribes a set of equitable flight plans based on admissible trades and exchanges of assigned slots, which are in addition conformant with sector workload capabilities and conflict risk restrictions. The net reduction in passenger-minutes of delay for each airline is the primary metric used to assess and compare model solutions. Appropriate constraints are included in the model to ensure that the generated slot exchanges induce nonnegative values of this realized net reduction for each airline. In keeping with the spirit of the FAA's CDM initiative, we next propose four alternative equity methods that are predicated on different specified performance ratios and related efficiency functions. These four methods respectively address equity with respect to slot-exchange-related measures such as total average delay, net delay savings, proportion of acceptable moves, and suitable value function realizations. For our computational experiments, we constructed several scenarios using real data obtained from the FAA based on the Enhanced Traffic Management System (ETMS) flight information pertaining to the Miami and Jacksonville Air Route Traffic Control Centers (ARTCC). Through our experimentation, we provide insights into the effect of the different proposed modeling concepts and study the sensitivity with respect to certain key parameters. In particular, we compare the alternative proposed equity formulations by evaluating their corresponding slot-exchange solutions with respect to the net reduction in passenger-minutes of delay for each airline. Additionally, we evaluate and compare the computational-effort performance, under both time limits and optimality thresholds, for each equity method in order to assess the efficiency of the model. The four slot-exchange-based equity formulations, in conjunction with the internal slot-exchange mechanisms, demonstrate significant net savings in computational effort ranging from 25% to 86% over the original APCDM model equity formulation. The model has been implemented using Microsoft Visual C++ and evaluated using a C++ interface with CPLEX 9.0. The overall results indicate that the proposed modeling concepts offer viable tools that can be used by the FAA in a timely fashion for both tactical purposes, as well as for exploring various strategic issues such as air traffic control policy evaluations; dynamic airspace resectorization strategies as a function of severe weather probabilities; and flight plan generation in response to various disruption scenarios. / Ph. D.

We develop a detailed, large-scale, airspace planning and collaborative decision-making model (APCDM), that is part of an $11.5B, 10-year, Federal Aviation Administration (FAA)-sponsored effort to increase U.S. National Airspace (NAS) capacity by 30 percent. Given a set of flights that must be scheduled during some planning horizon, we use a mixed-integer programming formulation to select a set of flight plans from among alternatives subject to flight safety, air traffic control workload, and airline equity constraints. Novel contributions of this research include three-dimensional probabilistic conflict analyses, the derivation of valid inequalities to tighten the conflict safety representation constraints, the development of workload metrics based on average (and its variance from) peak load measures, and the consideration of equity among airline carriers in absorbing the costs related to re-routing, delays, and cancellations. We also propose an improved set of flight plan cost factors for representing system costs and investigating fairness issues by addressing flight dependencies occurring in hubbed operations, as well as market factors such as schedule convenience, reliability, and the timeliness of connections. The APCDM model has potential use for both tactical and strategic applications, such as air traffic control in response to severe weather phenomenon or spacecraft launches, FAA policy evaluation, Homeland Defense contingency planning, and military air campaign planning. The model is tested to consider various airspace restriction scenarios imposed by dynamic severe weather systems and space launch Special Use Airspace (SUA) impositions. The results from this model can also serve to augment the FAA's National Playbook of standardized flight profiles in different disruption-prone regions of the National Airspace. / Ph. D.