Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/90758
Title: Integrated schedule recovery: a multi-agent approach
Authors: Antunes, David Joaquim Marques
Orientador: Antunes, António Pais
Vaze, Vikrant
Issue Date: 4-Oct-2019
Project: info:eu-repo/grantAgreement/FCT/PD/PD/BD/52360/2013/PT/DOCTORAL PROGRAM IN TRANSPORTATIONS SYSTEMS 
Abstract: Delays and disruptions in airline operations annually result in billions of dollars of additional costs to airlines, passengers, and the economy. Airlines strive to mitigate these costs by creating schedules that are less likely to get disrupted or schedules that are easier to repair upon disruptions. New types of aircraft, larger fleets, expanding networks and increasing constraints on crew scheduling from regulators, crew collective bargains, and decreased fares, force airlines to make their operations more efficient. The presence of considerable uncertainty makes this already complex problem faced by the airlines even harder to solve. The air transportation industry has long tradition of using operations research techniques to solve their problems. To cope with their problems the airline industry has used optimization models in one form or another. Hence schedules are trimmed to eliminate buffers and slacks, but this can lead to greater propagation of delays, even due to minor incidents. These intricate problems are hard to understand and all its interactions are virtually impossible to grasp in a purely closed-form mathematical approach. We present in this thesis several methodological approaches to help researchers and industry practitioners dealing with uncertainty in airline scheduling. First, we present a robust optimization model for the crew pairing problem, which generates crew schedules that are less likely to get disrupted. Our model allows adding robustness without requiring detailed knowledge of the underlying delay distributions. Moreover, our model allows to capture in detail the delay propagation through crew connections and the complex cost structure of the pay-and-credit crew salary scheme, thus enabling us to find a good tradeoff between the planned costs on one hand and the expected delay and disruption costs on the other hand. Our robust crew pairing model is based on a deterministic crew pairing model formulated as a mixed-integer linear program. The robust version that we propose retains the linearity of the constraints and objective function, and thus can be handled by commercial solvers, which facilitates its implementation in practice. We propose and implement a new solution algorithm for solving our model to optimality. Several optimal solutions with varying robustness levels are compared for the network of a moderate-sized airline in the United States. We test the model’s solutions in a simulation environment using real-world delay data. Our simulation results show that the robust crew pairing solutions lead to lower delays and fewer instances of operational infeasibilities, thus requiring fewer recovery actions to address them. We conclude that, with the inclusion of robustness, it is possible to generate crew pairing solutions that significantly reduce the delay and disruption costs with only a small increase in planned costs. Second, we present a new stochastic simulation platform that is able to simulate the daily operations of an airline allowing industry analysts, practitioners and researchers to evaluate the behavior of an airline network under uncertainty. This simulation platform was developed specifically to be user-friendly and require moderate input needs. We demonstrate the adequacy of an agent-based approach to model a complex system such as an airline. Additionally, we demonstrate that an accurate representation of an airline’s operation needs to explicitly consider the airline’s response to uncertainty and disruptions, by accurately modeling the airline as a decision-maker in face of uncertainty. This is demonstrated through a detailed case study where we compare two recovery models that, due to their different objectives, lead to different behaviors of the simulated airline. We demonstrate and compare the tradeoffs between cancelations and flight delays that are made by these models to reach to their objectives. Third, we present a machine learning metamodel approach where we leverage information extracted from the historic data, from previous schedule recovery problems solved by optimization models, to generate immediate solutions for the schedule recovery problem. In our proof of concept case study, we use an artificial neural network that, using historic data of solutions and problems, is able to extract the solution pattern and return the problem solution without needing to re-run the optimization model. We show that it is feasible to use machine learning metamodels to predict solutions of optimization models based on historic data. With an acceptable level of accuracy, the metamodel was able to predict the solution of a recovery optimization model
Atrasos e perturbações nas operações resultam anualmente em milhares de milhões de dólares de custos adicionais para as companhias aéreas, para os seus passageiros e para a economia em geral. As companhias aéreas tentam mitigar esses custos criando horários com menos probabilidade de serem perturbados. Novos desafios devidos a novos tipos de aeronaves, à expansão de redes, ao aumento das restrições aos horários das tripulações por parte de reguladores e contratos coletivos e à diminuição de tarifas, forçam as companhias aéreas a tornarem as suas operações mais eficientes. A presença de incerteza torna a gestão das operações de companhias aéreas ainda mais complexa. O setor do transporte aéreo tem uma longa tradição de usar técnicas de investigação operacional para resolver os seus problemas operacionais. Neste sentido, os horários são otimizados para reduzir margens, o que pode levar a uma maior propagação de atrasos. São problemas complexos e de difícil compreensão difíceis de traduzir adequadamente por modelos matemáticos. Apresentamos várias abordagens para ajudar os investigadores e profissionais da indústria a lidar com a incerteza na gestão operacional de companhias aéreas. Primeiro, apresentamos um modelo de otimização robusto para o problema do emparelhamento de tripulações, que gera horários para as tripulações com menos probabilidade de serem afetados por incerteza. O modelo permite adicionar robustez sem exigir um conhecimento detalhado das distribuições subjacentes aos atrasos. Além disso, o modelo permite capturar pormenorizadamente a propagação dos atrasos decorrentes das conexões da tripulação e a complexa estrutura de custos dos salários dos membros das tripulações, permitindo-nos encontrar um bom equilíbrio entre os custos planeados e os custos adicionais relativos a atrasos e perturbações das operações. O modelo robusto de emparelhamento de tripulação proposto é baseado num determinístico formulado como um problema inteiro misto. A versão robusta que propomos mantém a linearidade das restrições e da função objetivo e, portanto, pode ser tratada por softwares comerciais, o que facilita a sua implementação prática. Propomos e implementamos um novo algoritmo para obter soluções ótimas globais para o modelo. Soluções ótimas correspondentes a vários níveis de robustez são comparadas para uma companhia aérea de tamanho moderado que opera nos Estados Unidos. Testamos as soluções do modelo em um ambiente de simulação usando dados de atrasos reais. Os resultados da simulação mostram que as soluções robustas de emparelhamento de tripulações levam a atrasos menores e menos ocorrências de inviabilidade operacional, exigindo menos ações de recuperação para as resolver. Verificámos que, com a inclusão da robustez, é possível gerar soluções de emparelhamento de tripulações que reduzem significativamente os custos com atrasos e perturbações das operações com apenas um pequeno aumento nos custos planeados. Em segundo lugar, apresentamos uma nova plataforma de simulação estocástica que é capaz de simular as operações diárias de uma companhia aérea, permitindo que analistas, profissionais e pesquisadores do setor avaliem o comportamento da rede de uma companhia aérea sob condições de incerteza. Demonstramos a adequação de uma abordagem baseada em agentes para modelar um sistema complexo como uma companhia aérea. Além disso, demonstramos que uma representação adequada da operação de uma companhia aérea carece da consideração explícita da respetiva resposta a incertezas e perturbações. O funcionamento da plataforma é exemplificado por meio de um estudo de caso detalhado em que comparamos dois modelos de recuperação de horários de companhias aéreas que, devido terem objetivos distintos, levam a diferentes comportamentos da companhia aérea simulada. Determinamos e comparamos os trade-offs entre cancelamentos e atrasos de voo que são feitos por esses modelos em função dos objetivos da companhia. Em terceiro lugar, apresentamos uma meta-modelo “machine learning” onde aproveitamos informações extraídas dos dados históricos de problemas de recuperação de horários de companhias aéreas resolvidos por modelos de otimização para gerar soluções imediatas. No estudo de caso que desenvolvemos como prova de conceito, usamos uma rede neuronal artificial que, a partir de dados históricos de soluções e problemas, é capaz de extrair o padrão da solução e gerar a solução do problema sem precisar de resolver novamente o modelo de otimização. Mostramos que é possível usar meta-modelos de “machine learning” para prever soluções de modelos de otimização baseados em dados históricos com um nível aceitável de precisão. O meta-modelo conseguiu prever a solução de um modelo de otimização de recuperação de horários.
Description: Tese no âmbito do Programa Doutoral em Sistemas de Transportes apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
URI: https://provas-academicas.sib.uc.pt/handle/123456789/49389
http://hdl.handle.net/10316/90758
Rights: embargoedAccess
Appears in Collections:UC - Teses de Doutoramento
FCTUC Eng.Civil - Teses de Doutoramento

Files in This Item:
File Description SizeFormat Login
Integrated schedule recovery: a multi-agent approach.pdf3.96 MBAdobe PDFEmbargo Access    Request a copy
Show full item record

Page view(s)

11
checked on Sep 24, 2020

Download(s)

1
checked on Sep 24, 2020

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons