O Serviço de Gerenciamento de Fluxo de Tráfego Aéreo (ATFM) estabelece um controle de fluxo seguro, ordenado e eficiente de acordo com a capacidade da infraestrutura e dos serviços de controle. O Gerenciamento ´e realizado com o auxílio de sistemas automatizados. Tais sistemas implementam programas que ajustam a demanda de voos à capacidade do espaço aéreo. Algoritmos simples podem sugerir medidas ATFM para solucionar a saturação em um conjunto restrito de elementos regulados (aeródromos, regiões do espaço aéreo, fixos ou aerovias). A natureza interconectada dos elementos regulados, que compõem o fluxo de tráfego aéreo, demanda uma abordagem mais abrangente para atingir o uso ótimo desses recursos, uma vez que outros problemas podem surgir quando a otimização local é aplicada a um elemento sem levar em conta seus elementos relacionados. Nem sempre há a necessidade do planejamento estratégico ser um ótimo global, uma vez que cenários viáveis e sub-ótimos encontrados com menor custo computacional podem representar soluções satisfatórias. O aumento da demanda do tráfego aéreo, no entanto, tem fomentado a aplicação de programas de geração de medidas ATFM mais complexos. Esta pesquisa implementou um programa de otimização global para a geração de medidas ATFM em cenários de larga escala do mundo real. O problema ´e modelado como um problema de programa¸c~ao inteira e o modelo adotado ´e abrangente, pois prevê atraso em solo, em voo, alteração de velocidade e rerroteamento. O programa é capaz de balancear o fluxo atendendo restrições de capacidade dos aeródromos e dos setores. Além disso, foi desenvolvida uma interface de visualização e edição de dados para os cenários estudados. Dados de voos no espaço aéreo brasileiro foram processados e utilizados para testar a solução implementada e mostraram a viabilidade do método. A utilização de um programa de otimização que leva em conta mais restrições potencialmente irá contribuir com o aumento de eficiência no uso da infraestrutura e do espaço aéreo de forma segura. / The Air Traffic Flow Management Service (ATFM) establishes a secure, orderly and efficient flow control according to the capacity of the infrastructure and control services. The Management is performed with the aid of automated systems. Such systems implement programs that adjust the flight demand to the airspace capacity. Simple algorithms might suggest ATFM measures to resolve saturation in a restricted set of regulated elements (aerodromes, airspace regions, fixes or airways). The interconnected nature of the regulated elements that make up the air traffic flow requires a more comprehensive approach to achieve optimum use of these resources, since other problems can arise when local optimization is applied to an element without regard to its related elements. There is not always a need for strategic planning to be a global optimum, since feasible and sub-optimal scenarios encountered at lower computational cost might represent satisfactory solutions. The increase in air traffic demand, however, has encouraged the application of programs to generate more complex ATFM measures. This research implemented a global optimization program for the generation of ATFM measures in large-scale real-world scenarios. The problem is modeled as an integer programming problem and the adopted model is comprehensive, since it provides ground and airborne delays, change of speed and re-routing. The program is able to balance the flow by meeting capacity constraints of the aerodromes and sectors. In addition, a visualization and data editing interface was developed for the studied scenarios. Flight data in Brazilian airspace were processed and used to test the implemented solution and the viability of the method was shown. The use of an optimization program that takes into account more constraints will potentially contribute to increase the efficiency in use of infrastructure and airspace in a secure manner.

Este trabalho foi motivado pela necessidade de otimização nos serviços de entregas urbanas combinados com o alto custo de implantação e customização da maioria dos pacotes disponíveis comercialmente, que muitas empresas se defrontam, na expectativa de obtenção de respostas rápidas e eficientes, numa base diária. Geralmente a utilização destes software requerem grandes investimentos de tempo e recursos. Os custos operacionais do transporte de cargas têm experimentado um aumento expressivo devido a fatores que, de uma forma ou de outra, impedem o fluxo eficiente dos veículos na rede, tomando evidente a necessidade de ferramentas flexíveis e efetivas. Vários estudos encontrados na literatura revelaram que fatores como restrições de circulação e velocidades nos arcos têm contribuído para aumentar distâncias de percursos e a frota de veículos. Geralmente, estas rotas são planejadas de forma simplificada, utilizando um fator de correção, que fornece uma solução aproximada. Um SIG foi objeto de estudo na operação de entregas urbanas, de forma a atingir os objetivos deste trabalho. O estudo de caso abordou os serviços de entregas de bebidas na cidade de São Carlos, onde foi aplicada a heurística de economias de Clarke & Wright implementadas no software TransCAD 3.2. Foram feitas diversas simulações, comparando os resultados das distâncias em rede com os valores das distâncias estimadas, como também com as distâncias percorridas pela empresa distribuidora. / This research was motivated by the necessity of optimization of urban delivery services and the high cost of implementation and customization of most routing packages commercially available. Moreover, the companies expect to obtain fast and efficient answers on a daily base. The use of some routing software generally requires significant investments of time and other resources. The operational costs of freight transport have had a remarkable increase due to factors which somehow restraint the efficient flow of the vehicles in a network, leading to the need of flexible and effective tools. Several studies in the literature have revealed that factors such as restrictions of circulation and speed on network contribute to increase the travel distances and the fleet size. Generally, these routes are planned in a simplified way, using a correction factor to get an approximated solution. This research has considered the use of Geographical Information Systems as a tool to achieve better results for routing delivery services. The case study was the delivery service of beverages in the city of São Carlos. The Clarke & Wright\'s heuristic of economies was irnplemented in the TransCAD 3.2 software. Several simulations were carried out, comparing the results of route length, considering network and estimated distances, as well as the real one traveled by the delivery company\'s vehicles.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.

Esta pesquisa aborda o problema de alocação de jatos executivos compartilhados para casos em que a demanda diária é variável. É proposta uma ferramenta auxiliar de planejamento de uma empresa de operação de jatos compartilhados. São apresentadas as características principais do tipo de negócio que formam o problema estudado neste trabalho. Consideram-se os aspectos de uma empresa que administra jatos de propriedade compartilhada. O cliente adquire uma cota de uma aeronave e quando solicita uma viagem, com poucas horas de antecedência, a empresa deve garantir a realização do voo em uma aeronave da categoria adquirida. Também é de responsabilidade da empresa a gestão da tripulação, o reposicionamento da frota e a manutenção das aeronaves Este trabalho apresenta o desenvolvimento de uma ferramenta para auxiliar na tomada de decisões estratégicas que envolvem a escolha dos locais de base de operação e o dimensionamento da frota. A metodologia de solução é composta de um modelo de simulação e um de otimização. O modelo de simulação utiliza o método de Monte Carlo para obtenção da demanda de voos dia a dia que gera uma programação de clientes a atender. Os dados da simulação são então estruturados como um problema de fluxo em rede de mínimo custo e é realizada a alocação ótima das aeronaves. A ferramenta foi construída em ambiente de planilha eletrônica Microsoft Excel e aplicada em um caso prático de jatos executivos compartilhados com múltiplas bases. Foram testadas diversas configurações de bases e políticas operacionais como frota homogênea, frota heterogênea e frota alugada. Os resultados da ferramenta permitem determinar o impacto que a escolha das bases de operação tem no tamanho da frota e no reposicionamento de aeronaves. A metodologia mostrou-se robusta e, em tempo adequado, a ferramenta encontrou a solução ótima para cada configuração testada. / This research deals with the problem of scheduling jets with fractional ownership in cases where the demand varies daily. It has been devised a tool to support the planning phase of a company that operates shared jets. The main characteristics of the fractional shared market are presented in this manuscript and the research was developed under the point of view of a provider of fractional ownership. A client becomes a partial owner of an aircraft of a specific model and is entitled to a certain amount of flight hours. When the client requests a flight, usually only a few hours ahead, the fractional provider must guarantee that an aircraft of the requested model is available to the owner at the requested time and place. The provider is responsible for all the operational considerations, including managing the crew and having a well-maintained fleet. This work presents the development of a tool to help making decisions involving the choice of the operational bases and the size of the fleet. The solution methodology is composed of a simulation and a optimization model. Monte Carlo simulation is the method used to obtain the daily flight demand. The results of the simulation are structured as a minimum cost network flow problem to solve optimally the fleet allocation. This tool has been built in a Microsoft Excel spreadsheet environment and applied to a case of fractional jets with multiple bases. Several configurations and operational policies have been tested, such as operations with homogenous fleet, with heterogeneous fleet and with rented fleet. The results provided by the tool allow the user to evaluate the impact that the choice of the operational bases has on the size of the fleet and on the redeployment of the aircrafts. The methodology presented itself as adequate and the developed tool was able to solve optimally, in acceptable time, the problem for each case.

Este trabalho foi motivado pela necessidade de otimização nos serviços de entregas urbanas combinados com o alto custo de implantação e customização da maioria dos pacotes disponíveis comercialmente, que muitas empresas se defrontam, na expectativa de obtenção de respostas rápidas e eficientes, numa base diária. Geralmente a utilização destes software requerem grandes investimentos de tempo e recursos. Os custos operacionais do transporte de cargas têm experimentado um aumento expressivo devido a fatores que, de uma forma ou de outra, impedem o fluxo eficiente dos veículos na rede, tomando evidente a necessidade de ferramentas flexíveis e efetivas. Vários estudos encontrados na literatura revelaram que fatores como restrições de circulação e velocidades nos arcos têm contribuído para aumentar distâncias de percursos e a frota de veículos. Geralmente, estas rotas são planejadas de forma simplificada, utilizando um fator de correção, que fornece uma solução aproximada. Um SIG foi objeto de estudo na operação de entregas urbanas, de forma a atingir os objetivos deste trabalho. O estudo de caso abordou os serviços de entregas de bebidas na cidade de São Carlos, onde foi aplicada a heurística de economias de Clarke & Wright implementadas no software TransCAD 3.2. Foram feitas diversas simulações, comparando os resultados das distâncias em rede com os valores das distâncias estimadas, como também com as distâncias percorridas pela empresa distribuidora. / This research was motivated by the necessity of optimization of urban delivery services and the high cost of implementation and customization of most routing packages commercially available. Moreover, the companies expect to obtain fast and efficient answers on a daily base. The use of some routing software generally requires significant investments of time and other resources. The operational costs of freight transport have had a remarkable increase due to factors which somehow restraint the efficient flow of the vehicles in a network, leading to the need of flexible and effective tools. Several studies in the literature have revealed that factors such as restrictions of circulation and speed on network contribute to increase the travel distances and the fleet size. Generally, these routes are planned in a simplified way, using a correction factor to get an approximated solution. This research has considered the use of Geographical Information Systems as a tool to achieve better results for routing delivery services. The case study was the delivery service of beverages in the city of São Carlos. The Clarke & Wright\'s heuristic of economies was irnplemented in the TransCAD 3.2 software. Several simulations were carried out, comparing the results of route length, considering network and estimated distances, as well as the real one traveled by the delivery company\'s vehicles.

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.

Esta pesquisa aborda o problema de alocação de jatos executivos compartilhados para casos em que a demanda diária é variável. É proposta uma ferramenta auxiliar de planejamento de uma empresa de operação de jatos compartilhados. São apresentadas as características principais do tipo de negócio que formam o problema estudado neste trabalho. Consideram-se os aspectos de uma empresa que administra jatos de propriedade compartilhada. O cliente adquire uma cota de uma aeronave e quando solicita uma viagem, com poucas horas de antecedência, a empresa deve garantir a realização do voo em uma aeronave da categoria adquirida. Também é de responsabilidade da empresa a gestão da tripulação, o reposicionamento da frota e a manutenção das aeronaves Este trabalho apresenta o desenvolvimento de uma ferramenta para auxiliar na tomada de decisões estratégicas que envolvem a escolha dos locais de base de operação e o dimensionamento da frota. A metodologia de solução é composta de um modelo de simulação e um de otimização. O modelo de simulação utiliza o método de Monte Carlo para obtenção da demanda de voos dia a dia que gera uma programação de clientes a atender. Os dados da simulação são então estruturados como um problema de fluxo em rede de mínimo custo e é realizada a alocação ótima das aeronaves. A ferramenta foi construída em ambiente de planilha eletrônica Microsoft Excel e aplicada em um caso prático de jatos executivos compartilhados com múltiplas bases. Foram testadas diversas configurações de bases e políticas operacionais como frota homogênea, frota heterogênea e frota alugada. Os resultados da ferramenta permitem determinar o impacto que a escolha das bases de operação tem no tamanho da frota e no reposicionamento de aeronaves. A metodologia mostrou-se robusta e, em tempo adequado, a ferramenta encontrou a solução ótima para cada configuração testada. / This research deals with the problem of scheduling jets with fractional ownership in cases where the demand varies daily. It has been devised a tool to support the planning phase of a company that operates shared jets. The main characteristics of the fractional shared market are presented in this manuscript and the research was developed under the point of view of a provider of fractional ownership. A client becomes a partial owner of an aircraft of a specific model and is entitled to a certain amount of flight hours. When the client requests a flight, usually only a few hours ahead, the fractional provider must guarantee that an aircraft of the requested model is available to the owner at the requested time and place. The provider is responsible for all the operational considerations, including managing the crew and having a well-maintained fleet. This work presents the development of a tool to help making decisions involving the choice of the operational bases and the size of the fleet. The solution methodology is composed of a simulation and a optimization model. Monte Carlo simulation is the method used to obtain the daily flight demand. The results of the simulation are structured as a minimum cost network flow problem to solve optimally the fleet allocation. This tool has been built in a Microsoft Excel spreadsheet environment and applied to a case of fractional jets with multiple bases. Several configurations and operational policies have been tested, such as operations with homogenous fleet, with heterogeneous fleet and with rented fleet. The results provided by the tool allow the user to evaluate the impact that the choice of the operational bases has on the size of the fleet and on the redeployment of the aircrafts. The methodology presented itself as adequate and the developed tool was able to solve optimally, in acceptable time, the problem for each case.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

O adensamento populacional que as metrópoles vivenciam contribui para reduzir a disponibilidade específica de água, medida em m³/hab.ano. Adicionalmente a este evento, quando o crescimento urbano ocorre de forma não planejada, isso impacta também a qualidade dos mananciais. Esses dois efeitos ocorrem de forma combinada, sobretudo na Região Metropolitana de São Paulo (RMSP). Como consequência observam-se opções de ampliação da capacidade de produção de água potável sucessivamente mais custosas, seja por processos mais caros para o tratamento de um manancial mais poluído, próximo ao centro consumidor, seja pela maior distância de um manancial não poluído, e maiores custos com obras, como ocorre atualmente na implantação do Sistema Produtor São Lourenço (SPSL). Esse processo de encarecimento das opções para ampliação do sistema centralizado de produção de água potável persistirá na RMSP, conforme a população continue a aumentar nas próximas décadas. Existem fontes alternativas com disponibilidade satisfatória, como a água residuária, que quando adequadamente tratadas, podem ser direcionadas para usos que não demandam água potável. Essa possibilidade tem sido aproveitada de forma crescente pelo mercado imobiliário em edifícios, através da instalação de sistemas prediais de água não potável (SPANP), e há diferentes tecnologias disponíveis se consolidando com custos em tendência de queda. Nesse contexto, o objetivo da pesquisa é formular um modelo matemático de tomada de decisão para verificar se a utilização de SPANP são viáveis em relação à implantação do SPSL. Para o desenvolvimento da pesquisa, realizou-se revisão bibliográfica para avaliar as experiências de implantação de SPANP com fonte de águas cinzas em diferentes localidades, bem como para estabelecer a comparação de produção de água potável em macroescala em relação à produção de água não potável em microescala. Foram coletados dados quanto aos custos de construção, operação e manutenção de um SPANP em operação em um edifício na RMSP, e o mesmo para o SPSL. Por meio dos princípios da Programação Inteira, foi formulado um modelo para a indicação de qual opção de sistema apresenta o menor custo total acumulado durante os 20 primeiros anos de operação. Foram simulados cinco cenários com a alteração das principais variáveis que influenciam o comportamento da viabilidade das opções, sendo que as simulações foram realizadas com o uso do software LINDOTM. Em quatro dos cinco cenários simulados, o SPSL foi a opção de menor custo acumulado no 20o ano de operação, indicando a maior probabilidade do mesmo ser a opção de implantação mais econômica no presente. No entanto, devido à tendência de encarecimento das alternativas de ampliação do sistema centralizado de produção de água potável e de redução de custos dos SPANP, essa conclusão não pode ser adotada automaticamente quanto ao próximo sistema centralizado de água potável planejado para ser implantado. / The population agglomeration phenomenon that the metropolises pass through, reduces the water availability measured by the indicator m³/hab.year. Additionally, when urban growth happen in an unplanned way, it also impacts the quality of the water sources. These two effects occur in a combined way, especially in the São Paulo Metropolitan Region (SPMR). As a consequence, the options for expanding the production capacity of drinking water are successively more costly, either by more expensive processes for the treatment of a more polluted source, near the consumer center, or by the larger distance of an unpolluted source, and higer costs with construction, as it is currently happening in the implementation of the São Lourenço Producer System (SLPS). The process that is turning expensive the options for expanding the centralized drinking water system will persist in the SPMR as the population continues to increase in the coming decades. There are alternative sources with satisfactory availability, such as wastewater, which when properly treated, can be directed to uses that do not require potable water. This possibility has been used more and more by the real estate market in buildings, through the installation of non-potable water systems (NPWS), and there are different technologies available in consolidation with falling costs. Thus, the objective of the research is to formulate a mathematical decision making model to verify if the use of NPWS are viable in relation to the implementation of the SLPS. For the development of the research, a bibliographical review was carried out to evaluate the experiences of implementation of NPWS with source of gray water in different localities, as well as to establish the comparison of production of drinking water in macro scale in relation to the production of non-potable water in micro scale. Data were collected on the costs of construction, operation and maintenance of NPWS in a building in the SPMR, and the same for SLPS. Through the principles of Integer Programming, a model was formulated to indicate which system option has the lowest accumulated total cost during the first 20 years of operation. Five scenarios were simulated with the change of the main variables that influence the viability behavior of the options, the simulations were performed using LINDOTM software. In four of the five simulated scenarios, SLPS was the lowest accumulated cost option in the 20th year of operation, indicating that it is more likely to be the most economical deployment option in the present. However, due to the rising cost of alternatives for the expansion of the centralized drinking water production system and the cost reduction of NPWSs, this conclusion cannot be automatically adopted for the next centralized drinking water system planned to be implemented.