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.

O presente estudo trata da configuração de uma rede de distribuição capacitada com restrição de cobertura. O objetivo é determinar quais cidades, dentre um conjunto de candidatas, devem atuar como centrais de desconsolidação de carga, de forma a minimizar o custo total de transporte (transferência e distribuição) para uma determinada demanda, atendendo às restrições operacionais e de distância de cobertura. A partir da pesquisa na literatura sobre o assunto, foi preparado um modelo de programação linear inteira para encontrar a solução ótima para o problema. Esse modelo é baseado nos clássicos problemas de localização, com modificação na função objetivo para retratar melhor a estrutura de custos de transporte, além da inclusão de restrições de cobertura e restrições de atendimento mínimas e máximas em cada central. O modelo foi implementado utilizando o suplemento Solver da planilha eletrônica Excel. Um outro enfoque de solução baseado na metaheurística Busca Tabu (Tabu Search) foi elaborado, com dois objetivos: permitir a análise de problemas quando não se tem disponível uma ferramenta para solução de modelos de programação linear; e analisar o comportamento da metaheurística quando utilizada na solução desse tipo de problema. O procedimento foi implementado a partir da construção de macros em linguagem Visual Basic for Application (VBA), também em Excel. O modelo de programação linear e a metaheurística Busca Tabu foram aplicados a alguns cenários de um problema real. Resultados, comparações e conclusões dessas aplicações são apresentados neste trabalho. / The present study deals with configuring a capacitated distribution network with coverage constraint. The objective consists of determining which cities, among a set of candidates, should act as load deconsolidation centers, aiming to minimize transportation total costs to attend a given demand, and obeying all operational constraints and coverage distances. Based on a literature review, an integer linear programming model was formulated to find the problem optimal solution. The model is based on classical location problems, but includes changes in the objective function to incorporate the transportation costs structure, besides coverage constraints and minimum and maximum central capacity constraints. The model was implemented using Excel’s Solver add-in. Another solution approach based on the Tabu Search metaheuristic was proposed, with two objectives: to permit problem analysis when linear programming tools are not available; and to learn on metaheuristic behavior when used to solve this type of problem. The Tabu Search procedure was implemented using Excel macro language in Visual Basic for Applications (VBA). Both integer linear programming and metaheuristic models were applied to some scenarios of a real-world problem. Applications results, comparisons and conclusions are presented in this work.

O trabalho apresenta o desenvolvimento e a aplicação de um modelo de localização de centros intermediários de consolidação e redistribuição de cargas em um ambiente urbano brasileiro. O método integra o TransCAD e o OpenSolver e é aplicado à cidade de Curitiba, uma das dez mais populosas do Brasil. O método proposto é caracterizado como um modelo de localização-roteirização baseado em agrupamento e subsequente roteirização, identificado na literatura por cluster-first routesecond; a adoção deste ordenamento permite tratar o problema para o atendimento de muitos estabelecimentos, como os até 65 mil em alguns dos cenários no estudo de caso de Curitiba. Cada agrupamento representa os pontos a serem visitados em uma única viagem e o processo inicial tenta minimizar as distâncias entre os estabelecimentos de cada grupo; na fase seguinte o melhor roteiro é computado para cada grupo; a terceira etapa consiste em calcular, para cada grupo e candidato, a distância total percorrida na viagem; por fim, a implantação ou não dos candidatos a centros de distribuição é obtida com a minimização em um modelo de programação linear inteira dos custos de aquisição e de operação dos centros de distribuição e dos custos de transportes. A dissertação também aborda a crescente percepção da importância da logística urbana à qualidade de vida nas cidades onde o adensamento populacional acirra a disputa pelo espaço viário e o conceito de City Logistics, que delineia entre outras medidas o ambiente cooperativo no qual implantação de centros de distribuição urbanos deve ocorrer. / This work presents the development and application of a model for the location of intermediary consolidation and redistribution freight centers in Brazilian cities. The method integrates TransCad and OpenSolver, and its use was evaluated with data from the City of Curitiba one of the ten largest in Brazil. The proposed method is characterized as a location-routing model based on clustering and subsequent tour building known as cluster-first route-second. This enables dealing with problem instances containing as many as 65 thousand customers. Each cluster comprehends the points visited on a single trip and the initial process minimizes the distances between customers; the routes are calculated in the next phase and the third step consists in computing the total distance covered in each trip for every cluster and every candidate; finally, the implementation of each distribution center candidate is decided by minimizing the costs of acquisition, operation and distribution, using an integer linear programming model. The dissertation also highlights the growing realization of the importance of urban freight transport to quality of life, especially in cities where increasing population density intensifies the competition for road space, and City Logistics concepts, that outline among other measures the cooperative environment where implementation of urban distribution centers should occur.

O presente trabalho tem como objetivo um estudo sobre perfil de consumidor e o problema de localização de lojas de diferentes canais de vendas do varejo, levando em consideração o perfil socioeconômico e perfil de compra dos consumidores. Uma análise de clusters possibilitou, com base nos dados de vendas por classes sócio-econômicas de lojas dos vários canais obtidos de um varejista, a segmentação de diferentes tipos de lojas e canais com potenciais de vendas diferenciados. Posteriormente, a pesquisa propõe uma modelagem para o problema de localização dos grupos de loja no varejo empregando programação linear inteira. O modelo visa à maximização do resultado operacional total que se obtém da política de localização de diferentes tipos de lojas e canais numa cidade ou região. O modelo é implementado para a cidade de Belo Horizonte (MG), utilizando-se os dados levantados de potenciais de vendas para os diferentes tipos de canais lojas e os dados da distribuição das populações dos bairros de BH, segmentados pelas várias classes sócioeconômicas. Uma análise de Sensibilidade apresenta os efeitos de diferentes formas de operacionalização da área de influência ou cobertura de uma loja sobre a política de localização das lojas, bem como sobre o resultado operacional. A análise sensibilizada mostrou também que o modelo buscou dentre os diferentes cenários alterados, a aproximação na indicação dos bairros a ser instalados as lojas, ao percentual de influência e ao potencial de vendas dos diferentes bairros por tipos de lojas. A segmentação das lojas em vários tipos e canais bem como a proposição de operacionalização da região de cobertura de uma loja contribuem com discussões importantes para a literatura. Por outro lado, a modelagem proposta pode apresentar subsídio para a tomada de decisão gerencial na expansão ou implantação de lojas de varejo numa determinada região. / The main objective of the present research aims to a study on consumer profile and the retail store location problem of different stores channels, taking into account the socioeconomic profile and the consumers purchase behavior. A clusters analysis, based on sales data for socio-economic classes from the various type of stores channels obtained from a retailer, targeted of different types of stores and channels different sales potential. Subsequently, the research proposes a model to the problem of location of groups of retail store employing integer linear programming. The model aims to maximize the total operational result that is obtained from the optimal location of different types of stores and channels in a city or region. It is implemented for the city of Belo Horizonte (MG), using data collected from the sales potential for the different types of stores channels and of distribution of the populations on each districts in BH, targeted by the various socio-economic classes. A sensitivity analysis shows the effects of various types of operation of the area of influence or coverage of a shop on the politics of location of the shops, as well as the operating result. The sensitive analysis also showed that the model sought among the changes of parameters over the scenarios, the proximity over the indication of districts to the store indication, the influence percentage and the sales potential over the different districts by store cluster. The segmentation of the stores throughout the various types and channels as well as the proposition of area coverage operation of a single store, contributes to important literature discussions. Moreover, the proposed model may subsidizes management of decision-making in expansion or establishment of retail stores in a given region.

Made available in DSpace on 2016-08-10T10:40:26Z (GMT). No. of bitstreams: 1 Bruno Quirino de Oliveira.pdf: 3736663 bytes, checksum: e1dc08656b351b56c485c6f1ee09217b (MD5) Previous issue date: 2015-03-12 / Telecommunications experience accelerated evolution. The environment is very competitive and the volume of financial resources involved is significant. The variety of available technologies makes system planning stage, a procedure not only desirable but necessary, especially in a competitive environment. The use of comprehensive and flexible methodologies that can assist in decision-making, based on mathematical optimization models, it seems an inevitable way. This paper presents mathematical models based on operational research, mixed integer linear programming (MILP) and fuzzy logic to assist in strategic planning and decision-making, for the telecommunications industry, where they are analyzed, discussed and applied optimization models approach node-arc and arc-path. The analysis is focused on minimizing the cost given the expected demand. The main network components, services and costs are identified and models are developed to determine the network configuration or service. The models allow for greater flexibility and a high degree of interaction with the planner. These characteristics make it possible to analyze various scenarios where there is inaccuracy, both for the selection of services and for network deployment. To ensure the practical validation of the methodology, results of computational experiments are presented and discussed. Noteworthy are the results: (1) the possibility of holding a multi-service planning, with the possibility of assigning priorities in the services and care (2) effectiveness of the model for network deployment, which revealed a gain of 2% in the optimal solution in a test instance of SNDlib repository. / As telecomunicações experimentam acelerada evolução. O ambiente é muito competitivo e o volume de recursos financeiros envolvidos é significativo. A variedade de tecnologias disponíveis faz da etapa de planejamento do sistema um procedimento não só desejável como necessário, principalmente num ambiente de competitividade. A utilização de metodologias abrangentes e flexíveis que possam auxiliar no processo de decisão, fundamentadas em modelos matemáticos de otimização, parece um caminho inevitável. Este trabalho apresenta modelos matemáticos baseados em pesquisa operacional, programação linear inteira mista (PLIM) e lógica fuzzy para ajudar no planejamento estratégico e na tomada de decisões, para o setor de telecomunicações, onde são analisados, aplicados e discutidos modelos de otimização com abordagem nó-arco e arco-caminho. A análise é orientada à minimização do custo atendendo a demanda prevista. Os principais componentes de rede, de serviços e de custos são identificados e os modelos são desenvolvidos para determinar a configuração de rede ou de prestação de serviços. Os modelos permitem uma maior flexibilidade e um alto grau de interação com o planejador. Estas características possibilitam analisar variados cenários onde há imprecisão, tanto para a seleção de serviços, quanto para a implantação de rede. Para garantir a validação prática da metodologia desenvolvida, resultados de experimentos computacionais são apresentados e discutidos. Destacam-se nos resultados: (1) a possibilidade de realizar um planejamento multi-serviço, com possibilidade de atribuir prioridades no atendimento dos serviços e (2) eficácia do modelo, para a implantação de rede, onde se obteve um ganho de 2% na solução ótima, em uma instância de teste do repositório SNDlib.

This paper aims to present the thesis developed in the Doctoral Programin Computer Science and Computational Mathematics of the ICMC/USP. The thesis theme seeks to advance the state of the art by solving the problems of scalability and representation present in mission planning algorithms for Unmanned Aerial Vehicle (UAV). Techniques based on mathematical programming and evolutionary computation are proposed. Articles have been published, submitted or they are in final stages of preparation.These studies report the most significant advances in the representation and scalability of this problem. Mission planners worked on the thesis deal with stochastic problems in non-convex environments,where collision risks or failures in mission planning are treated and limited to a tolerated value. The advances in the representation allowed to solve violations in the risks present in the original literature modeling, besides making the models more realistic when incorporating aspects such as effects of the air resistance. Efficient mathematical modeling techniques allowed to advance from a Mixed Integer Nonlinear Programming (MINLP) model, originally proposed in the literature, to a Mixed Integer Linear Programming (MILP) problem. Modeling as a MILP led to problem solving more efficiently through the branch-and-algorithm. The proposed new representations resulted in improvements from scalability, solving more complex problems within a shorter computational time. In addition, advances in scalability are even more effective when techniques combining mathematical programming and metaheuristics have been applied to the problem. / O presente documento tem por objetivo apresentar a tese desenvolvida no Programade Doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. O tema da tese busca avançar o estado da arte ao resolver os problemas de escalabilidade e representação presentes em algoritmos de planejamento para missões com Veículos Aéreos Não Tripulados (VANTs). Técnicas baseadas em programação matemática e computação evolutiva são propostas. Artigos foram publicados, submetidos ou se encontram em fase final de elaboração. Esses trabalhos reportamos avanços mais significativos obtidos na representação e escalabilidade deste problema.Os planejadores de missão trabalhados na tese lidam com problemas estocásticos em ambientes não convexos, onde os riscos de colisão ou falhas no planejamento da missão são tratados e limitados a um valor tolerado. Os avanços na representação permitiram solucionar violações nos riscos presentes na modelagem original, além de tornar os modelos mais realistas ao incorporar aspectos como efeitos da resistência do ar. Para isso, técnicas eficientes de modelagem matemática permitiram avançar de um modelo de Programação Não-Linear Inteira Mista(PNLIM), originalmente proposto na literatura, para um problema de Programação Linear Inteira Mista (PLIM). A modelagem como um PLIM levou à resolução do problema de forma mais eficiente através do algoritmo branch-and-cut. As novas representações propostas resultaram em melhorias na escalabilidade, solucionando problemas mais complexos em um tempo computacional menor.Além disso,os avanços em escalabilidade mostraram-se mais efetivos quando técnicas combinando programação matemática e metaheurísticas foram aplicadas ao problema.

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

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

The current scenario of the Brazilian electricity sector, through the constant and recent regulatory changes imposed by ANEEL in recent years, aims to ensure continuous improvement in quality standards in the provision of electricity, significantly increased surveillance on the power quality delivered to consumers. Following this guideline, ANEEL established X Factor, which set the minimum volume of investments required to electricity distribution companies. In 2010, through the PRORET ANEEL established a new methodology for the calculation of the X Factor, including the Q component, relating to quality of service, setting a milestone in the recent regulatory history of the Brazilian electricity sector, as it allows for the first time gains the annual tariff adjustment or loss according to the performance measured in the year. In this context of regulatory innovations and increasing demands with performance standards and levels of investment made on the electrical system, the correct and efficient use of increasingly scarce resources to improve and expand the electrical system are presented as a vital challenge to financial health of companies. This paper presents a methodology for prioritizing investments in primary networks of electricity distribution, involving two consolidated methodologies aid to decision-making high complexity (AHP and PROMETHEE) and operations research methods to optimize the planning of improvement works to be held in short-term horizon, with direct reflection on regulatory issues, seeking still accommodate regional characteristics of the company and the ability to execute works of each region. / O atual cenário do setor elétrico brasileiro, através das constantes e recentes alterações regulatórias impostas pela ANEEL nos últimos anos, tem como objetivo garantir a melhoria contínua nos padrões de qualidade no fornecimento de energia elétrica, aumentado significativamente a fiscalização sobre a qualidade da energia entregue aos consumidores. Seguindo esta diretriz, a ANEEL instituiu o Fator X, que define o volume de investimentos mínimos exigidos às empresas de distribuição de energia elétrica. Em 2010, através do PRORET a ANEEL estabeleceu uma nova metodologia para o cálculo do Fator X, incluindo o componente Q, referente à qualidade do serviço prestado, configurando como um marco no recente histórico regulatório do setor elétrico brasileiro, pois permite pela primeira vez ganhos no reajuste tarifário anual ou perdas de acordo com o desempenho medido no ano. Neste contexto de inovações regulatórias e exigências cada vez maiores com os padrões de desempenho e níveis de investimentos realizados no sistema elétrico, a aplicação correta e eficiente dos cada vez mais escassos recursos disponíveis para melhoria e ampliação do sistema elétrico se apresentam como um desafio vital à saúde financeira das empresas do setor elétrico. Este trabalho apresenta uma metodologia para priorização de investimentos em redes primárias de distribuição de energia elétrica, associando duas consolidadas metodologias de auxílio à tomada de decisões de elevada complexidade (AHP e PROMETHEE) e métodos de pesquisa operacional para otimização no planejamento de obras de melhoria a serem realizadas no horizonte de curto prazo, com reflexo direto nas questões regulatórias, buscando ainda contemplar características regionais da empresa e a capacidade de execução de obras de cada região.

Submitted by Augusto Cesar Pereira (augusto.pereira@feb.unesp.br) on 2017-12-20T09:42:45Z No. of bitstreams: 1 Dissertação_Augusto_Repositorio.pdf: 2651783 bytes, checksum: 084f19f166b7161411ec58baa4ecf206 (MD5) / Approved for entry into archive by Maria Marlene Zaniboni null (zaniboni@bauru.unesp.br) on 2017-12-20T10:54:46Z (GMT) No. of bitstreams: 1 pereira_ac_me_bauru.pdf: 2651783 bytes, checksum: 084f19f166b7161411ec58baa4ecf206 (MD5) / Made available in DSpace on 2017-12-20T10:54:46Z (GMT). No. of bitstreams: 1 pereira_ac_me_bauru.pdf: 2651783 bytes, checksum: 084f19f166b7161411ec58baa4ecf206 (MD5) Previous issue date: 2017-12-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho propõe um modelo de Procedimento de Equilíbrio de Mercado com Restrições de Segurança Estocásticas (PEMRSE) que pode ser utilizado como um modelo de leilão de energia e reserva do dia seguinte por operadores de sistemas hidrotérmicos. O modelo de PEMRSE tem o objetivo de minimizar o custo esperado da operação, considerando os custos associados aos excedentes de geração e consumo, partidas, contratação de reservas e a penalização econômica associada aos cortes involuntários de carga. O PEMRSE considera vários aspectos que dificultam a resolução de problemas de leilão: i) representação detalhada dos sistemas de geração hidrelétrico e termelétrico; ii) perdas na transmissão; e iii) restrições de segurança pré e pós-contingência. São propostas técnicas de linearização que não demandam o uso de variáveis binárias para a função de produção hidráulica e para as funções de potência e engolimento máximo de geradores hidrelétricos. A estrutura estocástica permite cortes involuntários de carga, isto é, o operador pode optar por não contratar a totalidade das reservas necessárias para cobrir as falhas associadas às contingências, ponderando sua decisão pela probabilidade de ocorrência destas falhas e pelo valor da penalização econômica associada ao corte de carga. Propõe-se também uma técnica para a resolução de modelos de PEMRSE em tempos computacionais menores com relação à sua resolução direta. Simulações em um sistema-teste de três barras e no sistema IEEE de 24 barras evidenciam a eficiência do modelo, das técnicas de linearização e da técnica de resolução propostos. As simulações também mostram os impactos dos aspectos complicadores nos resultados do leilão e no tempo computacional de resolução. O modelo de PEMRSE proposto pode ser resolvido de maneira eficiente por meio de pacotes computacionais disponíveis comercialmente por meio da técnica de resolução proposta. / This work proposes a Market Clearing Procedure with Stochastic Security Constraints (MCPSSC) model that can be used as an energy and reserve day-ahead auction model by hydrothermal systems operators. The MCPSSC aims to minimize the expected cost of the operation, considering the costs associated with the generation and consumption surpluses, start-ups, contracting of reserves and the economic penalization associated with involuntary load shedding events. The MCPSSC model considers several aspects that complicate the resolution of auction problems: i) detailed representation of the hydrothermal generating systems; ii) transmission losses; and iii) pre- and post-contingency security constraints. We propose linearization techniques that does not require the use of binary variables for the hydro production function and for the maximum power output and maximum water discharge functions of hydro generators. The stochastic structure allows some load shedding, ie, the operator can choose not to contract the total reserve requirements to cover the failures associated with the contingencies, weighting its decision by the probability of occurrence of these failures and by the value of lost load. We also propose a technique for the resolution of MCPSSC models in lower computational times regarding its direct resolution. Simulations in a three-bus test system and in the IEEE 24-bus system show the efficiency of the model, the linearization techniques and the resolution technique proposed. The simulations also show the the impact of the complicating aspects in the auction outcomes and in the computational time. The proposed MCPSSC model can be efficiently solved by commercially available solvers by means of the proposed resolution technique.