abstract: Allocating tasks for a day's or week's schedule is known to be a challenging and difficult problem. The problem intensifies by many folds in multi-agent settings. A planner or group of planners who decide such kind of task association schedule must have a comprehensive perspective on (1) the entire array of tasks to be scheduled (2) idea on constraints like importance cum order of tasks and (3) the individual abilities of the operators. One example of such kind of scheduling is the crew scheduling done for astronauts who will spend time at International Space Station (ISS). The schedule for the crew of ISS is decided before the mission starts. Human planners take part in the decision-making process to determine the timing of activities for multiple days for multiple crew members at ISS. Given the unpredictability of individual assignments and limitations identified with the various operators, deciding upon a satisfactory timetable is a challenging task. The objective of the current work is to develop an automated decision assistant that would assist human planners in coming up with an acceptable task schedule for the crew. At the same time, the decision assistant will also ensure that human planners are always in the driver's seat throughout this process of decision-making. The decision assistant will make use of automated planning technology to assist human planners. The guidelines of Naturalistic Decision Making (NDM) and the Human-In-The -Loop decision making were followed to make sure that the human is always in the driver's seat. The use cases considered are standard situations which come up during decision-making in crew-scheduling. The effectiveness of automated decision assistance was evaluated by setting it up for domain experts on a comparable domain of scheduling courses for master students. The results of the user study evaluating the effectiveness of automated decision support were subsequently published. / Dissertation/Thesis / Masters Thesis Computer Science 2019

Efficient integrated/robust planning and recovery models were studied. The research focus was to integrate fleet assignment and crew scheduling, and, in addition, to provide solutions robust to real time operations. The contributions include: (1) To understand how schedule development and fleet assignment stages influence crew scheduling performance, schedule analysis methods were proposed to evaluate the crew friendliness of a schedule for a given fleet. (2) To meet the computational challenges of crew scheduling in integrated planning, a duty flow model was proposed which can efficiently find suboptimal legal pairing solutions. (3) A new robust crew scheduling method based on spoke purity was proposed. Computational results indicated that with little or no extra cost, a more robust crew pairing solutions can be expected. (4) By imposing station purity, an integrated and robust planning model which integrates fleet assignment and crew connections was proposed. The impact of crew base purities and fleet purities on FAM profit, crew scheduling, and computational efficiency were investigated. (5) Airline integrated recovery method was studied. A recovery scope for integrated recovery was proposed to limit the ripple effect caused by disruptions. Based on the defined recovery scope, a new integrated recovery model and Bender¡¯s decomposition solution approach was studied.

Crew scheduling is very important, especially in continuous operating environments running 24 hours a day, 7 days a week, more so if the demand for staff is varying over each hour of the day. This thesis focuses on staff optimization in a fast food chain where special conditions for scheduling like flexible starting-times and shift lengths or heterogeneous crew are present. Two new models based on a mixed integer programming approach were designed, dealing with data from a particular restaurant with the aim of improving schedules and saving time spent on the creation of those schedules. At the end of the thesis the empiric schedules and results obtained are compared and the computational efficiency of both models is discussed.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir um conjunto de tarefas aos tripulantes, considerando as regulamentações trabalhistas, as regras de segurança e as políticas das empresas, de tal maneira que o custo da tripulação seja mínimo. O PPT é normalmente dividido em dois subproblemas, resolvidos sequencialmente: Problema de Determinação das Viagens (PDV) e Problema de Atribuição de Escalas (PAE). No PDV, determina-se um conjunto de viagens que cubra todos os voos planejados. Em seguida, no PAE, as escalas, compostas pelas viagens escolhidas e outras atividades como folgas, sobreavisos, reservas, treinamentos e férias, são atribuídas aos tripulantes. Esta decomposição justifica-se pela natureza combinatória do PPT, porém não incorpora as disponibilidades e as preferências dos tripulantes em ambos os subproblemas (PDV e PAE), gerando assim custos extras relacionados aos conflitos que surgem durante a atribuição das escalas aos tripulantes no PAE. Além disso, as estimativas de custos adotadas no PDV não possuem caráter global, já que o custo real da programação só pode ser obtido após a atribuição das escalas. O estado da arte envolve a solução integrada do PPT, em que se elimina a necessidade de resolver inicialmente o PDV, provendo assim uma melhor estimativa de custo e uma programação final com melhor qualidade, por considerar os custos da tripulação, as disponibilidades e preferências dos tripulantes de forma global. O problema, no entanto, é NP-Difícil. Assim sendo, a metodologia proposta nesta pesquisa objetiva a solução do PPT de forma integrada, através de um Algoritmo Genético Híbrido (AGH) associado a um procedimento de busca em profundidade, levando em conta as particularidades da legislação brasileira. A metodologia foi testada, com sucesso, para a solução de instâncias baseadas na malha real de uma empresa aérea brasileira. / This master of science research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The main aim of the CSP is to assign a set of tasks to crew members, considering the labor regulations, safety rules and policies of companies, such that the crew cost is minimal. The CSP is divided into two subproblems, solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). First, CPP provides a set of pairings that covers all the planned flights. Then, in the CRP, the rosters, encompassing the pairings and other activities such as rest periods, alert duties, reserve duties, training times and vacations, are assigned to the crew members. This decomposition is justified by the combinatorial nature of the CSP, but it not incorporates the crew members availabilities and preferences in both subproblems (CPP and CRP), generating extra costs related to conflicts that arise during the assignment of rosters to the crew members in the CRP. Besides, the costs estimations adopted in the CPP does not have a global character, since the real cost of the global schedule can be only obtained after the assignment of the rosters. The state of the art involves the integrated solution of CSP, where the CPP does not need to be solved, thus providing a better estimated cost and a better schedule quality, considering crew costs and also crew members availabilities and preferences globally. The problem, however, is NP-Hard. Therefore, the methodology proposed in this master of science research aims to obtain an integrated solution of the CSP, through an hybrid algorithm genetic associated with a depth-first search procedure, taking into account the Brazilian legislation. The methodology was tested, with success, to solve instances related a real network of a Brazilian airline.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir um conjunto de tarefas aos tripulantes, considerando as regulamentações trabalhistas, as regras de segurança e as políticas das empresas, de tal maneira que o custo da tripulação seja mínimo. O PPT é normalmente dividido em dois subproblemas, resolvidos sequencialmente: Problema de Determinação das Viagens (PDV) e Problema de Atribuição de Escalas (PAE). No PDV, determina-se um conjunto de viagens que cubra todos os voos planejados. Em seguida, no PAE, as escalas, compostas pelas viagens escolhidas e outras atividades como folgas, sobreavisos, reservas, treinamentos e férias, são atribuídas aos tripulantes. Esta decomposição justifica-se pela natureza combinatória do PPT, porém não incorpora as disponibilidades e as preferências dos tripulantes em ambos os subproblemas (PDV e PAE), gerando assim custos extras relacionados aos conflitos que surgem durante a atribuição das escalas aos tripulantes no PAE. Além disso, as estimativas de custos adotadas no PDV não possuem caráter global, já que o custo real da programação só pode ser obtido após a atribuição das escalas. O estado da arte envolve a solução integrada do PPT, em que se elimina a necessidade de resolver inicialmente o PDV, provendo assim uma melhor estimativa de custo e uma programação final com melhor qualidade, por considerar os custos da tripulação, as disponibilidades e preferências dos tripulantes de forma global. O problema, no entanto, é NP-Difícil. Assim sendo, a metodologia proposta nesta pesquisa objetiva a solução do PPT de forma integrada, através de um Algoritmo Genético Híbrido (AGH) associado a um procedimento de busca em profundidade, levando em conta as particularidades da legislação brasileira. A metodologia foi testada, com sucesso, para a solução de instâncias baseadas na malha real de uma empresa aérea brasileira. / This master of science research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The main aim of the CSP is to assign a set of tasks to crew members, considering the labor regulations, safety rules and policies of companies, such that the crew cost is minimal. The CSP is divided into two subproblems, solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). First, CPP provides a set of pairings that covers all the planned flights. Then, in the CRP, the rosters, encompassing the pairings and other activities such as rest periods, alert duties, reserve duties, training times and vacations, are assigned to the crew members. This decomposition is justified by the combinatorial nature of the CSP, but it not incorporates the crew members availabilities and preferences in both subproblems (CPP and CRP), generating extra costs related to conflicts that arise during the assignment of rosters to the crew members in the CRP. Besides, the costs estimations adopted in the CPP does not have a global character, since the real cost of the global schedule can be only obtained after the assignment of the rosters. The state of the art involves the integrated solution of CSP, where the CPP does not need to be solved, thus providing a better estimated cost and a better schedule quality, considering crew costs and also crew members availabilities and preferences globally. The problem, however, is NP-Hard. Therefore, the methodology proposed in this master of science research aims to obtain an integrated solution of the CSP, through an hybrid algorithm genetic associated with a depth-first search procedure, taking into account the Brazilian legislation. The methodology was tested, with success, to solve instances related a real network of a Brazilian airline.

In Deutschland nehmen die Fahrgastzahlen und die Verkehrsleistung im Schienenpersonennah- und -fernverkehr in den letzten Jahrzehnten stetig zu. So stieg beispielsweise die Zahl der beförderten Fahrgäste im Schienenpersonennahverkehr von 1,96 Milliarden im Jahr 2004 auf 2,72 Milliarden im Jahr 2018. Dies entspricht einer Zunahme von fast 39%. Allerdings wird es für die Eisenbahnverkehrsunternehmen aufgrund des Fachkräftemangels immer schwieriger, die erforderlichen Transportleistungen durch Triebfahrzeugführer und Zugbegleiter abzudecken. Dies bedeutet, dass mit weniger Ressourcen mehr Transportleistung erbracht werden muss, so dass eine ressourcenschonende und gleichzeitig kosteneffiziente Personalplanung unerlässlich ist. Ziel dieser Arbeit ist die Entwicklung eines Lösungskonzepts zur optimierten und automatisierten Planung des Bahnpersonals, insbesondere zur Sicherstellung der Zugbegleitquoten von Zugbegleitern in Regionalzügen. Da es bereits eine Vielzahl von Publikationen zu Modellierungsansätzen und Lösungsmethoden im Zusammenhang mit der Schichtplanung des Bahnpersonals gibt, wird in einem ersten Schritt die relevante Literatur identifiziert und klassifiziert. Dies ist notwendig, um geeignete mathematische Formulierungen und Lösungsansätze zu ermitteln, die auch für den Spezialfall der Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten angewendet oder weiter modifiziert werden können. Durch die Systematisierung der relevanten Artikel nach Modellformulierungen, Zielsetzungen, betrachteten Rahmenbedingungen und Lösungsmethoden können Forschungslücken leicht identifiziert und Möglichkeiten für weitere Forschungen aufgezeigt werden. Nach einer Analyse der gegebenen rechtlichen Anforderungen, Regelungen aus Tarifverträgen, operativen Bedingungen und der Forderungen aus Verkehrsverträgen ist ein erstes Ziel dieser Arbeit die Entwicklung eines mathematischen Modells, das das gegebene Schichtplanungsproblem für Zugbegleiter mit Zugbegleitquoten darstellt. Um zunächst die Auswirkungen der neuen Restriktionen für die Zugbegleitquoten zu analysieren, können weitere in der Praxis notwendige Anforderungen (z.B. Personalkapazität an den Einsatzstellen) weggelassen und der Planungshorizont auf einen Tag begrenzt werden. Nach der Modellierung des Problems mit weiteren Restriktionen soll in dieser Arbeit ein geeigneter Lösungsansatz entwickelt werden, der vor allem die Lösbarkeit großer realer Instanzen gewährleistet. Die generierten Schichtpläne müssen den gesetzlichen, vertraglichen und betrieblichen Anforderungen genügen und die dadurch entstehenden Kosten minimieren. Da in der Praxis ein Planungszeitraum von einem Tag weder betriebswirtschaftlich sinnvoll noch kosteneffizient ist, wird als nächstes Ziel die Ausdehnung des Planungszeitraums auf mehrere Tage angestrebt. Diese Ausdehnung sollte sich sowohl auf das Modell als auch auf den entwickelten Lösungsansatz auswirken. So können weitere mehrtägige Restriktionen integriert werden, wie z.B. die gleichmäßige Verteilung der von einem Zugbegleiter besetzten Fahrten. In der Forschung ist es wichtig, eine Vergleichbarkeit bzw. eine Bewertung der Qualität des Modells oder des Lösungsansatzes herzustellen. Aus diesem Grund sollte eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten formuliert werden, um kleine Instanzen optimal zu lösen und untere Schranken für reale Instanzen zu setzen. Um die Lösung der Arc-Flow-Formulierung zu beschleunigen und zu verbessern, wird die Anwendung von gültigen Ungleichungen validiert. Der Zweck dieser Arbeit, der sich aus den oben genannten Zielen ableitet, lässt sich in fünf Forschungsfragen zur Schichtplanung für Zugbegleiter mit Zugbegleitquoten zusammenfassen: Q1 Wie ist der aktuelle Forschungsstand zu Schichtplanungsproblemen für das Bahnpersonal und welche Forschungslücken können identifiziert werden? F2 Wie können Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten modelliert werden? F3 Wie können Instanzen von Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten im Hinblick auf die Anforderungen der Praxis gelöst werden? F4 Wie kann das entwickelte mathematische Modell und der hybride Lösungsansatz auf einen mehrtägigen Zeitraum ausgedehnt werden? Was ist das Potenzial eines integrierten Ansatzes im Gegensatz zum sequenziellen, tageweisen Ansatz? F5 Kann eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten verwendet werden, um die Lösungsqualität des bisherigen Ansatzes zu bewerten oder sogar zu verbessern? Können gültige Ungleichungen das Verhalten der Arc-Flow-Formulierung in Bezug auf Rechenzeiten und untere Schranken verbessern?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 155 / In Germany, the number of passengers and the transport performance in regional and long-distance rail passenger transport increase constantly over the last decades. For example, the number of passengers carried in regional rail passenger transport rose from 1.96 billion in 2004 to 2.72 billion in 2018. This represents an increase of almost 39%. However, it is becoming increasingly difficult for railway companies to cover the required transport services by drivers and conductors due to the shortage of skilled workers. This implies that a greater transport performance must be achieved with fewer resources, thus resource-saving and at the same time cost-efficient planning of personnel is essential. This work aims to develop a solution concept for optimized and automated railway crew scheduling, especially ensuring attendance rates for conductors in regional trains. Since there already exists a variety of publications concerning modeling approaches and solution methods related to railway crew scheduling, the first step is to identify and classify relevant literature. This is necessary to determine suitable mathematical formulations and solution approaches which can also be used or further modified for the special case of railway crew scheduling problems with attendance rates for conductors. By systematizing the reviewed articles according to model formulations, objectives, constraints and solution methods, research gaps can easily be identified and opportunities for further research can be revealed. After an analysis of the given legal requirements, regulations from labor contracts, operating conditions and claims under transportation contracts, a first goal of this work is the development of a mathematical model which represents the given problem with attendance rates for conductors. In order to first analyze the effect of the new constraints on attendance rates, further requirements necessary in practice can be omitted (e.g. personnel capacity at crew bases) and the planning horizon can be limited to one day. After modeling the problem with further requirements, this work aims to develop a suitable solution approach which, above all, guarantees the solvability of large real-world instances. The generated shift schedules have to meet legal, contractual and operational requirements and thereby minimize the resulting costs. Since in practice a planning period of one day is neither operationally reasonable nor cost-efficient, the next goal is to extend the planning period to several days. This extension should affect both the model and the developed solution approach. This allows further restrictions concerning several days to be integrated, such as the uniform distribution of attended trips. In research, it is important to establish comparability or an assessment of the quality of the model or solution method. For this reason, an arc-flow formulation of the crew scheduling problem with attendance rates should be formulated to solve small-sized instances optimally and provide lower bounds for real-world instances. To accelerate and improve the arc-flow formulation solution, the application of valid inequalities will be validated. The purpose of this work derived from the above mentioned objectives can be summarized into five research questions on railway crew scheduling with and without attendance rates for conductors: Q1 What is the current state of research for railway crew scheduling problems and which research gaps can be identified? Q2 How can railway crew scheduling problems with attendance rates for conductors be modeled? Q3 How can instances of railway crew scheduling problems with attendance rates be solved with regard to real-world requirements? Q4 How can the developed mathematical model and hybrid solution approach be extended to a multiple day period? What is the potential of an integrated approach in contrast to the sequential day-by-day approach? Q5 Can an arc-flow formulation of the railway crew scheduling problem with attendance rates be used to evaluate or even enhance the solution quality of the previous approach? Can valid inequalities improve the performance of the arc-flow formulation concerning computing times and lower bounds?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 155

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir o conjunto de tripulantes requeridos para a operação dos voos de uma malha aérea de maneira a minimizar o custo total da tripulação, levando em conta a legislação pertinente e a satisfação dos tripulantes. O PPT é normalmente dividido na literatura em dois subproblemas independentes, modelados e resolvidos sequencialmente: Problema de Determinação de Viagens (PDV) e Problema de Atribuição de Escalas (PAE). Esta decomposição não incorpora os atributos (disponibilidade, qualificação, senioridade e preferências individuais) dos tripulantes de forma global, o que não permite uma estimativa real de custo e afeta a qualidade da solução final. O estado da arte envolve a solução integrada do PPT, eliminando a necessidade de se resolver inicialmente o PDV e permitindo a obtenção de uma solução mais realista. O PPT, no entanto, é de natureza combinatória. Assim sendo, esta pesquisa propõe e explora modelos baseados em programação linear inteira e em heurísticas para a solução integrada do PPT. Essas heurísticas incorporam fundamentos da meta-heurística GRASP, da heurística de economias de Clarke e Wright e da heurística day-by-day. Os modelos foram testados com sucesso para a solução de instâncias baseadas na malha real de três empresas aéreas brasileiras. / This doctoral research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The CSP consists of optimally assigning the required crew members to planned flights, in such a way that it minimizes the total cost of the aircrew, taking into consideration the proper legislation and the satisfaction of the crew members. The CSP is usually divided into two independent subproblems, modeled and solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). This decomposition does not incorporate all the crew members attributes (availability, qualification, seniority and individual preferences), which does not lead to a real cost estimate and affects the quality of the final solution. The state of the art involves the integrated solution of CSP, without solving the CPP at first and providing a more realistic solution. The CSP, however, has a combinatorial nature. This research proposes and explores models based on integer linear programming and on heuristics to solve the CSP in an integrated way. These heuristics incorporate GRASP metaheuristic, Clarke and Wright savings heuristic and day-by-day heuristic. The models were successfully tested to solve instances related to the networks of three Brazilian airlines.

Fractional aircraft ownership programs offer companies and individuals all the benefits of owning private jet, such as safety, consistency, and guaranteed availability, at a fraction of the cost of owning an aircraft. In the fractional ownership model, the partial owners of an aircraft are entitled to certain number of hours per year, and the management company is responsible for all the operational considerations and making sure an aircraft is available to the owners at the requested time and location. This thesis research proposes advance optimization techniques to help the management company to optimally operate its available resources and provides tools for strategic decision making. The contributions of this thesis are: (i) The development of optimization methodologies to assign and schedule aircraft and crews so that all flight requests are covered at the lowest possible cost. First, a simple model is developed to solve the crew pairing and aircraft routing problem with column generation assuming that a crew stays with one specific aircraft during its duty period. Secondly, this assumption is partially relaxed to improve resource utilization by revising the simple model to allow a crew to use another aircraft when its original aircraft goes under long maintenance. Thirdly, a new comprehensive model utilizing Benders decomposition technique and a fleet-station time line is proposed to completely relax the assumption that crew stays with one specific aircraft. It combines the fleet assignment, aircraft routing, and crew pairing problems. In the proposed methodologies, real world details are taken into consideration, such as crew transportation and overtime costs, scheduled and unscheduled maintenance effects, crew rules, and the presence of non-crew-compatible fleets. Scheduling with time windows is also discussed. (ii) The analysis of operational strategies to provide decision making support. Scenario analyses are performed to provide insights on improving business profitability and aircraft availability, such as impact of aircraft maintenance, crew swapping, effect of increasing demand by Jet-card and geographical business expansion, size of company owned aircraft, and strategies to deal with the stochastic feature of unscheduled maintenance and demand.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir o conjunto de tripulantes requeridos para a operação dos voos de uma malha aérea de maneira a minimizar o custo total da tripulação, levando em conta a legislação pertinente e a satisfação dos tripulantes. O PPT é normalmente dividido na literatura em dois subproblemas independentes, modelados e resolvidos sequencialmente: Problema de Determinação de Viagens (PDV) e Problema de Atribuição de Escalas (PAE). Esta decomposição não incorpora os atributos (disponibilidade, qualificação, senioridade e preferências individuais) dos tripulantes de forma global, o que não permite uma estimativa real de custo e afeta a qualidade da solução final. O estado da arte envolve a solução integrada do PPT, eliminando a necessidade de se resolver inicialmente o PDV e permitindo a obtenção de uma solução mais realista. O PPT, no entanto, é de natureza combinatória. Assim sendo, esta pesquisa propõe e explora modelos baseados em programação linear inteira e em heurísticas para a solução integrada do PPT. Essas heurísticas incorporam fundamentos da meta-heurística GRASP, da heurística de economias de Clarke e Wright e da heurística day-by-day. Os modelos foram testados com sucesso para a solução de instâncias baseadas na malha real de três empresas aéreas brasileiras. / This doctoral research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The CSP consists of optimally assigning the required crew members to planned flights, in such a way that it minimizes the total cost of the aircrew, taking into consideration the proper legislation and the satisfaction of the crew members. The CSP is usually divided into two independent subproblems, modeled and solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). This decomposition does not incorporate all the crew members attributes (availability, qualification, seniority and individual preferences), which does not lead to a real cost estimate and affects the quality of the final solution. The state of the art involves the integrated solution of CSP, without solving the CPP at first and providing a more realistic solution. The CSP, however, has a combinatorial nature. This research proposes and explores models based on integer linear programming and on heuristics to solve the CSP in an integrated way. These heuristics incorporate GRASP metaheuristic, Clarke and Wright savings heuristic and day-by-day heuristic. The models were successfully tested to solve instances related to the networks of three Brazilian airlines.

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.