• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 37
  • 6
  • 3
  • 2
  • 1
  • 1
  • Tagged with
  • 63
  • 63
  • 29
  • 19
  • 15
  • 14
  • 13
  • 12
  • 12
  • 11
  • 11
  • 10
  • 10
  • 9
  • 8
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Developing models and algorithms to design a robust inland waterway transportation network under uncertainty

Nur, Farjana 07 August 2020 (has links)
This dissertation develops mathematical models to efficiently manage the inland waterway port operations while minimizing the overall supply chain cost. In the first part, a capacitated, multi-commodity, multi-period mixed-integer linear programming model is proposed capturing diversified inland waterway transportation network related properties. We developed an accelerated Benders decomposition algorithm to solve this challenging NP-hard problem. The next study develops a two-stage stochastic mixed-integer nonlinear programming model to manage congestion in an inland waterway transportation network under stochastic commodity supply and water-level fluctuation scenarios. The model also jointly optimizes trip-wise towboat and barge assignment decisions and different supply chain decisions (e.g., inventory management, transportation decisions) in such a way that the overall system cost can be minimized. We develop a parallelized hybrid decomposition algorithm, combining Constraint Generation algorithm, Sample Average Approximation (SAA), and an enhanced variant of the L-shaped algorithm, to effectively solve our proposed optimization model in a timely fashion. While the first two parts develop models from the supply chain network design viewpoint, the next two parts propose mathematical models to emphasize the port and waterway transportation related operations. Two two-stage, stochastic, mixed-integer linear programming (MILP) models are proposed under stochastic commodity supply and water level fluctuations scenarios. The last one puts the specific focus in modeling perishable inventories. To solve the third model we propose to develop a highly customized parallelized hybrid decomposition algorithm that combines SAA with an enhanced Progressive Hedging and Nested Decomposition algorithm. Similarly, to solve the last mathematical model we propose a hybrid decomposition algorithm combining the enhanced Benders decomposition algorithm and SAA to solve the large size of test instances of this complex, NP-hard problem. Both proposed approaches are highly efficient in solving the real-life test instances of the model to desired quality within a reasonable time frame. All the four developed models are validated a real-life case study focusing on the inland waterway transportation network along the Mississippi River. A number of managerial insights are drawn for different key input parameters that impact port operations. These insights will essentially help decisions makers to effectively and efficiently manage an inland waterway-based transportation network.
32

Using maximal feasible subset of constraints to accelerate a logic-based Benders decomposition scheme for a multiprocessor scheduling problem

Grgic, Alexander, Andersson, Filip January 2022 (has links)
Logic-based Benders decomposition (LBBD) is a strategy for solving discrete optimisation problems. In LBBD, the optimisation problem is divided into a master problem and a subproblem and each part is solved separately. LBBD methods that combine mixed-integer programming and constraint programming have been successfully applied to solve large-scale scheduling and resource allocation problems. Such combinations typically solve an assignment-type master problem and a scheduling-type subproblem. However, a challenge with LBBD methods that have feasibility subproblems are that they do not provide a feasible solution until an optimal solution is found.  In this thesis, we show that feasible solutions can be obtained by finding and combining feasible parts of an infeasible master problem assignment. We use these insights to develop an acceleration technique for LBBD that solves a series of subproblems, according to algorithms for constructing a maximal feasible subset of constraints (MaFS). Using a multiprocessor scheduling problem as a benchmark, we study the computational impact from using this technique. We evaluate three variants of LBBD schemes. The first uses MaFS, the second uses irreducible subset of constraints (IIS) and the third combines MaFS with IIS. Computational tests were performed on an instance set of multiprocessor scheduling problems. In total, 83 instances were tested, and their number of tasks varied between 2794 and 10,661. The results showed that when applying our acceleration technique in the decomposition scheme, the pessimistic bounds were strong, but the convergence was slow. The decomposition scheme combining our acceleration technique with the acceleration technique using IIS showed potential to accelerate the method.
33

Optimization Models and Algorithms for Pricing in e-Commerce

Shams-Shoaaee, Seyed Shervin January 2020 (has links)
With the rise of online retailer giants like Amazon, and enhancements in internet and mobile technologies, online shopping is becoming increasingly popular. This has lead to new opportunities in online price optimization. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions. In Chapter 2 a multi-period revenue maximization and pricing optimization problem in the presence of reference prices is formulated as a mixed integer nonlinear program. Two algorithms are developed to solve the optimization problem: a generalized Benders' decomposition algorithm and a myopic heuristic. This is followed by numerical computations to illustrate the effciency of the solution approaches as well as some managerial pricing insights. In Chapter 3 a data-driven quadratic programming optimization model for online pricing in the presence of customer ratings is proposed. A new demand function is developed for a multi-product, nite horizon, online retail environment. To solve the optimization problem, a myopic pricing heuristic as well as exact solution approaches are introduced. Using customer reviews ratings data from Amazon.com, a new customer rating forecasting model is validated. This is followed by several analytical and numerical insights. In Chapter 4 a multinomial choice model is used for customer purchase decision to find optimal personalized price discounts for an online retailer that incorporates customer locations and feedback from their reviews. Closed form solutions are derived for two special cases of this problem. To gain some analytical insights extensive numerical experiments are carried followed by several analytical and numerical insights. / Thesis / Doctor of Philosophy (PhD) / The increase in online retail and the improvements in mobile technologies has lead to advantages and opportunities for both customers and retailers. One of these advantages is the ability to keep and efficiently access records of historical orders for both customers and retailers. In addition, online retailing has dramatically decreased the cost of price adjustments and discounts compared to the brick and mortar environment. At the same time, with the increase in online retailing we are witnessing proliferations of online reviews in e-commerce platforms. Given this availability of data and the new capabilities in an online retail environment, there is a need to develop pricing optimization models that integrate all these new features. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions.
34

[en] RENEWABLE ENERGY COMMERCIALIZATION MODEL FOR THE FREE MARKET VIA COOPERATIVE GAMES THEORY / [pt] MODELO DE COMERCIALIZAÇÃO DE ENERGIA RENOVÁVEL NO AMBIENTE DE CONTRATAÇÃO LIVRE VIA TEORIA DE JOGOS COOPERATIVOS

LUCAS FREIRE 08 October 2013 (has links)
[pt] No Brasil, as três principais fontes renováveis de energia elétrica são eólica, pequenas centrais hidrelétricas (PCHs) e biomassa. A comercialização da energia proveniente dessas fontes ocorre majoritariamente no ambiente de contratação regulada (ACR), através de leilões, em detrimento do ambiente de contratação livre (ACL). Isso devido ao fato de seus recursos naturais serem sazonais, estabelecendo o risco de preço-quantidade no ACL, em que o excesso ou déficit de energia gerada em relação à quantidade contratada é liquidado ao preço de liquidação de diferenças (PLD), uma variável sistêmica e altamente volátil. Contudo, a complementaridade dessas fontes permite reduzir esses riscos quando a energia é comercializada de forma conjunta, através de um fundo de energia que gera aumento do valor do portfólio com relação à comercialização individual. Esta dissertação utiliza a teoria de jogos cooperativos para analisar formas de repartir o benefício gerado, através da alocação de quotas financeiras. O conjunto de soluções onde o resultado individual das fontes no fundo é maior do que o resultado individual em qualquer subcoalisão define o núcleo do jogo. Assim, a complexidade de encontrar uma solução dentro do núcleo depende do número de subcoalizões, que cresce exponencialmente com o número de jogadores. Nesse contexto, este trabalho se propôs a apresentar: (i) um modelo de portfólio que incentiva a participação de fontes renováveis no ACL; (ii) um modelo de programação linear que busca o núcleo do jogo; (iii) uma metodologia eficiente baseada em decomposição de Benders, capaz de suprimir a questão da explosão combinatória do problema. / [en] In Brazil, the three main sources of renewable energy are wind, small run-of-river hidros (SH) and biomass. The energy sale of such sources occurs mainly in the Regulated Trading Environment (RTE), through auctions, with shy occurrences in the Free Trading Environment (FTE). This is due to the fact that their natural resources are seasonal, establishing the so-called price-quantity risk in the FTE, as the surplus or deficit of energy generated relative to the contracted amount is settled at the market’s spot price, a systemic and highly volatile variable. However, the complementary nature of these sources allows risk reduction if their energy are trade jointly, through an energy hedge pool that increases the value of the portfolio in comparison to individual strategies. This work makes use of cooperative games theory to analyze ways of sharing the generated benefit, through financial quotas allocation. The set of solutions where the individual sources results in the pool are greater than its results at any possible subcoalition defines the core of the game. Thus, the challenge of finding a solution inside the core depends on the number of subcoalitions, which grows exponentially with the number of players. In this context, this work proposes to present: (i) a model of portfolio that encourages the penetration of renewable sources in the FTE; (ii) a linear programming model that pursuits the game’s core; (iii) an efficient methodology based on Benders decomposition that is capable of suppress the problem of combinatorial explosion, typical of cooperative games with many players.
35

Congestion-driven Transmission Planning Considering Incentives For Generator Investments

Tor, Osman Bulent 01 June 2008 (has links) (PDF)
This thesis study focuses on transmission expansion planning (TEP) problem for restructured power systems and addresses challenges specifically in countries where electricity market is in developing phase after liberalization of power industry for establishing a competitive market, like Turkey. A novel multi-year TEP approach is developed which considers generation investment cost and transmission congestion level in the planning horizon. The model assesses the impact of generation investments on TEP problem. Benders decomposition methodology is utilized successfully to decompose the complex mixed-integer programming TEP problem into a master problem and two subproblems. Security subproblem assesses single-contingency criteria. Transmission congestion cost is considered within operational subproblem given that congestion level is a proper criterion for measuring competitiveness level of an electricity market. The proposed approach is applied to the Turkish power system. The proposed approach could be utilized to provide indicative plans, which might be quite necessary particularly during development of a competitive market. However, there is no guarantee that independent power producers (IPPs) will follow those plans which concern the maximization of social-welfare. Given the necessity of coordinating monopoly transmission and decentralized generator investment decisions, the proposed approach is improved further to include promoting decentralized generator investments through incentive payments. Such incentives might be necessary to trigger IPPs earlier than their projections, as illustrated by numerical examples including IEEE 30-bus system.
36

Aplicação do método de decomposição de Benders para o problema de carregamento de paletes / Aplicação do método de decomposição de Benders para o problema de carregamento de paletes

Rocha, Ana Gabriela 11 December 2008 (has links)
Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2228.pdf: 979050 bytes, checksum: ffa6f96c8eada124b6f1e6ba3ebe02da (MD5) Previous issue date: 2008-12-11 / Financiadora de Estudos e Projetos / Cutting and packing problems are important in the production planning of various industrial segments involving goals such as minimizing the negative efects generated by waste of materials or idle spaces. The loss of material due to an inadequate programming of the cutting or packing patterns, can be substantial, and, in general, parts of these losses can be avoided only with a more eficient production planning, not resulting in additional investments in production processes. This study aimed at evaluating the performance of the Benders decomposition method, applied to the manufacturer and distributor pallet loading models. The manufacturer pallet loading model involves packing equal boxes on a pallet, so as to optimize its use. The distributor pallet loading model involves packing boxes of diferent sizes on a pallet, also a way to optimize its use. The approach based on Benders decomposition, defines a relaxation algorithm that partitions the original problem in two other problems easier to be solved. To check the effectiveness of the approach, computational tests were carried out by comparing the results with those obtained by a computational package composed of a modeling language (GAMS) and a last generation optimization solver (CPLEX ). / Os problemas de corte e empacotamento são importantes no planejamento da produção de vários segmentos industriais envolvendo objetivos como, por exemplo, minimizar os efeitos negativos gerados por desperdício de materiais ou espaços ociosos. As perdas de material, devido a uma programação pouco adequada dos padrões de corte ou empacotamento, podem ser substanciais, sendo que, em geral, parte destas perdas pode ser evitada apenas com uma programação da produção mais eficiente, não implicando em investimentos adicionais nos processos de produção. O objetivo deste estudo é verificar o desempenho do método de decomposição de Benders aplicado a modelos de carregamento de paletes do produtor e do distribuidor. O problema de carregamento de paletes do produtor envolve empacotar caixas iguais sobre um palete, de maneira a otimizar o aproveitamento deste. O problema de carregamento de paletes do distribuidor envolve empacotar caixas de tamanhos diferentes sobre um palete, também de maneira a otimizar o aproveitamento deste. A abordagem baseada na reformulação de Benders define um algoritmo de relaxação que particiona o problema original em dois outros problemas mais simples de serem resolvidos. Para verificar a eficiência da abordagem, realizaram-se testes computacionais, comparando os resultados obtidos com os obtidos pelo pacote computacional composto de uma linguagem de modelagem (GAMS) e um software de otimização de última geração (CPLEX).
37

Requisitos de suporte de potência reativa para operação de usinas eólicas

Bento, José Antônio Chiabai 27 February 2013 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-04-11T14:02:57Z No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-04-24T03:37:26Z (GMT) No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) / Made available in DSpace on 2016-04-24T03:37:26Z (GMT). No. of bitstreams: 1 joseantoniochiabaibento.pdf: 931983 bytes, checksum: e18793314d0e558922ed90cb19474dbb (MD5) Previous issue date: 2013-02-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A penetração de parques eólicos nos sistemas elétricos de potência tem apresentado um grande crescimento no Brasil e no mundo devido à disponibilidade da matéria prima, os ventos, e à necessidade de reformulação das matrizes energéticas a fim de reduzir os impactos ambientais decorrentes da geração de energia elétrica. Porém, as usinas eólicas apresentam variações nos despachos de potência devido à variabilidade de velocidade dos ventos. Estas variações causam impactos no sistema, podendo afetar a confiabilidade e a estabilidade de tensão. Além disto, a operação de determinados tipos de aerogeradores requer suporte adicional de potência reativa. Uma opção para aumentar as margens operativas e acomodar as intermitências de regime dos ventos em sistemas elétricos de potência consiste na utilização de compensadores estáticos de reativos (CER) junto às usinas eólicas. Estes equipamentos FACTS (Flexible AC Transmission Systems) provêm suporte de potência reativa variável e de rápido controle, de acordo com os requisitos operacionais dos aerogeradores. Neste sentido, o presente trabalho apresenta uma metodologia para ajuste ótimo dos parâmetros do CER visando dar suporte de potência reativa para a operação de usinas eólicas em sistemas elétricos de potência. Para representar as intermitências no despacho de potência dos aerogeradores, a metodologia proposta considera diferentes cenários de vento. O problema é modelado através de fluxo de potência ótimo (FPO), associado à técnica de decomposição matemática de Benders. Os parâmetros de ajuste do CER são a tensão de referência e o coeficiente de inclinação da curva característica deste equipamento em regime permanente. Destaca-se que o ajuste ótimo deste coeficiente é inédito na literatura especializada. Testes com sistemas do IEEE são realizados para validar a metodologia proposta. / The penetration of wind farms in power systems has shown tremendous growth in Brazil and in the world due to the availability of the raw material, the wind, and the need to redefine the energy mix to reduce the environmental impacts from the electrical energy generation. However, the wind farms have variable outputs due to the variation of wind speeds. These outputs impact the power system and can affect the reliability and the voltage stability. Besides, the operation of some aerogenerators requires additional support of reactive power. An option for handling this feature and increasing the operative margins of power systems is the use of static VAr compensators (SVC) together with the wind farms. These FACTS devices (Flexible AC Transmission Systems) provide a variable reactive power support, with a fast control according to the operational requirements of the aerogenerators. In this sense, this work presents a methodology for the optimal adjustment of the SVC parameters to give reactive power support for wind farms operating in power systems. The proposed methodology considers different wind scenarios to represent the variations of the wind farms outputs. The problem is modeled through an optimal power flow (OPF) and the Benders decomposition technique. The SVC parameters for adjustment are its reference voltage and the coefficient of its characteristic curve in stable state. It can be highlighted that the adjustment of this coefficient is innovative for the literature. Tests with systems of the IEEE are performed to validate the proposed methodology.
38

Décomposition de Benders pour la gestion opérationnelle du trafic ferroviaire / Benders decomposition for the real-time Railway Traffic Management Problem

Keita, Kaba 04 December 2017 (has links)
Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions. / In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features.
39

Models and algorithms for network design problems

Poss, Michaël 22 February 2011 (has links)
Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité.<p>\ / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
40

Integrated Airline Operations: Schedule Design, Fleet Assignment, Aircraft Routing, and Crew Scheduling

Bae, Ki-Hwan 05 January 2011 (has links)
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.

Page generated in 0.546 seconds