Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-31T12:45:53Z No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) / Made available in DSpace on 2017-08-31T12:45:53Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) Previous issue date: 2017-03-07 / Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas. / In this work we address two vehicle routing problems with pickup and delivery and loading constraints. Firstly, this work addresses the Double Vehicle Routing Pro- blem with Multiple Stacks (DVRPMS). Posteriorly we formulate and propose the Double Routing Vehicle Problem with Multiple Stacks and Heterogeneous Demand (DVRPMSHD), referring to a more realistic case of the DVRPMS in which custo- mers have multiple and heterogeneous demands and all demand of a same client must be transported by a single vehicle. In both problems, the objective is to de- termine routes for a fleet of vehicles to meet the demand of a set of customers so that the distance travelled by the vehicles is the minimum possible, respecting some loading constraints imposed by the vehicles’ storage stacks. All products located in a pickup region must be collected and then delivered to a delivery region by vehicles. The pickup and delivery regions are largely separated so that all products must be loaded before any unloading. The DVRPMS was approached mainly by four heuristic methods, which were tested in several instances and compared to the exact and heuristic methods already present in literature. The computational experiments showed the efficiency of the proposed algorithms, obtaining solutions of better quality than those presented in the literature for most of the instances and with low computational time. The DVRPMSHD was approached by an exact method and a heuristic method. Initially, the implemented branch-and-price exact method presented higher efficiency compared to the proposed mathematical formu- lation for the problem. The heuristic method overcame the results achieved by the branch-and-price for most of the created instances.

DIAS, Fábio Carlos Sousa. Problema de Árvore Geradora Mínima com Restrição de Grau Mínima e Centrais e Terminais Fixos. 2014. 132 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:49:19Z No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa (jairo@ufc.br) on 2016-07-14T23:17:13Z (GMT) No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Made available in DSpace on 2016-07-14T23:17:13Z (GMT). No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) Previous issue date: 2014 / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Benders’s Decomposition. We propose a new general heuristic that combines ingredients from the Benders’s decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Árvore Geradora Mínima com Restrição de Grau Mínimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma árvore geradora mínima de um grafo onde cada vértice ou é folha da árvore ou satisfaz uma restrição de grau mínimo. Os vértices folhas são chamados terminais e os demais são os centrais. Definimos e estudamos uma variação desse problema, que denotamos MDF-MST, onde os terminais e centrais são definidos a priori. Mostramos que o problema é NP-Difícil e está na Classe FPT, parametrizado pelo número de centrais. Identificamos também casos onde o problema torna-se polinomial. Propomos várias formulações de programação inteira para o problema e comparamos teórica e computacionalmente a qualidade do limite inferior gerado por suas relaxações lineares. Propomos e testamos uma relaxação lagrangeana para o problema, que usamos também para definir heurísticas lagrangenas. Definimos heurísticas gulosas, uma busca VND e uma heurística VNS. Apresentamos uma decomposição de Benders. Propomos uma nova heurística geral que combina ingredientes da decomposição de Benders com método de subgradientes, a qual denominamos Heurística de Subgradientes. Aplicamos tal heurística ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiência computacional dos algoritmos propostos, especialmente a relaxação lagrangeana, é competitiva com a do CPLEX, e superior em vários casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este último onde a restrição sobre os centrais é de grau máximo). Quando comparamos os resultados computacionais com a literatura.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-02-18T08:12:26Z No. of bitstreams: 1 texto completo.pdf: 1523862 bytes, checksum: e1a681386ab2e9a8230f2dbed526c4ad (MD5) / Made available in DSpace on 2016-02-18T08:12:26Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1523862 bytes, checksum: e1a681386ab2e9a8230f2dbed526c4ad (MD5) Previous issue date: 2015-11-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT) é uma variação do problema clássico de Roteamento de Veículos em que as demandas dos clientes devem ser atendidas dentro de uma janela de tempo estabelecida. Neste trabalho, aborda-se o PRVJT objetivando a otimização simultânea de múltiplos objetivos. Os objetivos a serem minimizados são: distância total de percurso dos veículos, desequilíbrio nas distâncias percorridas e desequilíbrio das cargas dos veículos. Já que o problema é NP-Difícil, para determinar uma aproximação das soluções Pareto-ótimas, propõe-se duas abordagens heurísticas. A primeira abordagem é baseada na meta-heurística Iterated Local Search, que utiliza uma etapa de intensificação a qual consiste na combinação de soluções dominantes. A segunda abordagem é um algoritmo genético com uma fase de intensificação baseada na heurística de busca local Iterated Greedy, que consiste em melhorar as soluções dominantes. Os desempenhos dos algoritmos heurísticos foram testados em um conjunto de instâncias disponíveis na literatura, denominado Solomon’s benchmarks, e os resultados foram comparados com os resultados de dois algoritmos multiobjetivos da literatura. Os resultados obtidos foram analisados estatisticamente e observou-se um desempenho superior dos algoritmos propostos. / The Vehicle Routing Problem with Time Windows (VRPTW) is a variant of the classical Vehicle Routing Problem in which the demands of each customer should be met within an established time window. In this paper we address the VRPTW with multi-objective optimization. The objectives are to minimize the total distance, the imbalance in the distances traveled and the imbalance in the loads of the vehicles. Since the problem is NP-Hard, in order to find near Paretooptimal solutions, two heuristic approaches were proposed. The first approach is based on the meta-heuristic Iterated Local Search that uses an intensification stage that consists in combination of non-dominated solutions. The second approach is a genetic algorithm with an intensification stage based on the local search heuristic Iterated Greedy that consists in improving the non-dominated solutions. The heuristic algorithms’ performance was tested with a set of problems available in the literature, known as Solomon’s benchmarks, and the results were compared with two multi-objective algorithms in the literature. The results were statistically analyzed and revealed superior performance of the proposed algorithms.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

Com as crescentes expansão e popularização dos jogos digitais, sua utilização para fins além do simples entretenimento é cada vez mais visada por educadores, especialistas e estudantes. No entanto, os jogos educativos nem sempre conseguem concorrer com jogos comerciais. Nesse contexto, a presente pesquisa tem por objetivo desenvolver e avaliar um conjunto de heurísticas projetuais que contribuam com o desenvolvimento, adaptação de conteúdo instrucional e avaliação de jogos digitais educativos. Para isso, foram investigados aspectos relativos ao design instrucional e abordagens de aprendizagem, bem como características referentes a elementos que constituem os jogos digitais comerciais. Esses dados, obtidos a partir de base teórica composta por autores diversos das áreas supracitadas, foram analisados e comparados a partir de informações similares e/ou complementares, gerando um conjunto inicial de heurísticas. Esse foi revisado e incrementado com informações obtidas através de entrevistas com especialistas da área, realizadas para compreender as percepções e aspectos relacionados à prática do desenvolvimento de jogos educativos. O conjunto de heurísticas foi, então, testado e avaliado por especialistas e readequado conforme o feedback recebido. Os resultados permitiram a construção de um protótipo funcional para a adaptação de conteúdo instrucional, desenvolvimento e avaliação de jogos digitais educativos. / With the growth and popularization of videogames, their use to purposes beyond simple entertainment is increasingly targeted by educators, professionals and students. However, educational games are not always able to compete with commercial games. In this context, this research intends to develop and evaluate a set of heuristics for projects, with the purpose of contribute on the development, measurement and adaptation of instructional content on educational games. In order to achieve this goal, aspects related to instructional design and learning approaches have been researched, as well as characteristics of commercial games. These data, obtained through theoretical research, were analyzed and compared through similar/complementary informations, generating a primary set of heuristics, which has been complemented by data obtained through interviews with experts on the subject. The set of heuristics was, then, tested and evaluated by experts, and reviewed according to this feedback. The results allowed the construction of a functional prototype to improve adaptation of instructional content, development and evaluation of educative games.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2016-05-17T20:09:39Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Approved for entry into archive by Morgana Andrade (morgana.andrade@ufes.br) on 2016-06-03T14:24:51Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Made available in DSpace on 2016-06-03T14:24:51Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / CNPQ / O Problema de Grooming de Tráfego (Traffic Grooming Problem - TGP) trata da combinação eficiente de demandas de baixa velocidade em canais de alta velocidade. Com o objetivo de melhorar a utilização da capacidade da rede, o TGP é frequentemente estudado com métodos de otimização usando como função objetivo a minimização do número de transceptores eletro-´ópticos. Por´em, como o TGP pertence á classe de problemas NP-Completo, soluções ótimas com um pequeno tempo computacional são possíveis apenas para redes pequenas (por exemplo, 6 nós). Neste trabalho são propostos novos modelos de Programação Linear Inteira (Integer Linear Programming - ILP), uma heurística e uma solução híbrida para o TGP em redes translúcidas de médio porte (aproximadamente 12 n´os). Inicialmente, são propostos dois modelos ILP para o TGP, um baseado em formulação nó-enlace e outro em enlace-caminho, de forma que seus resultados foram comparados e usados como base para modelos mais complexos. No método híbrido é usada uma heurística para selecionar os caminhos ópticos (i.e., a topologia virtual) e um modelo ILP para rotear de maneira eficiente as demandas de tráfego sobre as topologias física e virtual. A aplicação desse método permitiu, primeiramente, a quantificação dos benefícios dos caminhos ópticos transparentes, em termos da redução do número de transceptores. Além disso, a diminuição do processamento eletrônico do tráfego de trânsito também foi analisada. Para redes maiores, a fase ILP no método híbrido ainda continua sendo um gargalo para as soluções ótimas, sendo assim necessárias soluções totalmente heurísticas. Este trabalho mostra que soluções eficientes podem ser encontradas usando métodos heurísticos simples e rápidos, onde não foi necessário o aumento do custo computacional para o ajuste de parâmetros complexos relacionados a heurística. Finalmente é proposta uma integração do TGP com sobrevivência. Neste trabalho são propostos modelos ILP para formulação de um método iterativo capaz de oferecer uma proteção incremental em uma rede em malha com a minimização do número de transceptores. Além disso, são estudados dois métodos para a proteção da interconexão de redes multi-anel com dois nós de interconexão, Anel Virtual e Drop&Continue. Para essa investigação os resultados numéricos incluem o grooming de tráfego para diferentes cenários como, configurações opaca vs. translúcida e crescimentos de tráfego inter-anel vs. intra-anel. / The Traffic Grooming Problem (TGP) consists in how to arrange low-bandwidth connection requests into high-capacity lightpaths efficiently. TGP solution aims at improving network capacity utilization. The minimal number optoelectronic transceivers that enable accommodating traffic demands is often used as the objec- tive function for solving TGP. However, TGP belongs to a class of NP-hard problems and optimal solutions are only possible to be found within feasible processing time for small networks (e.g., 6 nodes). This work proposes novel Integer Linear Pro- gramming (ILP) models, heuristic and a hybrid solution to TGP for medium-sized (i.e., around 12 nodes) translucent networks. Initially, ILP models using node-link and link-path paradigms are proposed and their solutions are compared. These models lay the foundations for more complex models addressing issues on network design. A hybrid method is then proposed. It makes use of a heuristic for selecting lightpaths (i.e., the virtual topology) and an ILP model to route the traffic demands over both physical and virtual topologies efficiently. The practical implications of such approach is that it allows, for the first time, the quantification of benefits of transparent lightpaths in terms of transceiver count reduction. Moreover, the miti-gation of transit traffic processing in the electronic layer is also analyzed. For large networks the ILP phase in the hybrid approach again becomes the bottleneck for optimal network design and a fully heuristic solution is necessary. This work shows that efficient solutions can be found through a simple and fast tool for network design without the need of complex parameter tuning, as comparisons with results obtained from solving the hybrid model. Finally, the integration of TGP with survivability is proposed. This work puts forward ILP models for an iterative method using two ILP models to design networks with incremental protection with minimal num- ber of transceivers in mesh networks. Dual Node Interconnected (DNI) multi-ring topologies are studied under inter-ring traffic protection using Virtual Ring (VR) and Drop and Continue (D&C) strategies. Results compare optimal solutions that take into account traffic grooming for different network scenarios including opaque vs. translucent configurations and inter vs. intra traffic growth.

En este trabajo se presenta una heurística que mejora los resultados operacionales en el despacho de pedidos de cerveza. Este trabajo está, especializado en las características de CERVECERÍAS CHILE S.A., empresa dedicada a la elaboración y transporte de cervezas a lo largo de todo Chile. La problemática diaria que se aborda en este proyecto consiste en la asignación de 400 clientes, en promedio, a rutas específicas de entrega, tomando en cuenta una flota homogénea de vehículos y restricciones horarias en la entrega de los pedidos. Se considera que la demanda de los productos es conocida y que los productos están disponibles para la entrega. Es importante notar que en este problema no existe una limitante en el número de vehículos disponibles para la entrega del producto, debido a que la empresa tiene una gran variedad de proveedores de transporte que facilitan el arrendamiento de vehículos. La formulación de la heurística desarrollada asegura el cumplimiento de las restricciones temporales en la entrega de productos y además minimiza los costos asociados al transporte diario de los productos para satisfacer la demanda de los clientes. La solución del problema se enfrentó con la técnica de Generación de Columnas. La base de esta metodología es dividir el problema en dos etapas: La primera etapa considera la generación de rutas factibles conocida como Sub Problema, y una segunda etapa la formulación de un problema de programación lineal que escoge mediante un modelo de optimización las soluciones que serán consideradas como rutas factibles para el despacho de los pedidos. Estas rutas corresponden a aquellas que tienen un costo reducido negativo para mejorar la función objetivo. El modelo decide qué cliente es asignado a cada viaje y horarios en que se realiza dicho viaje. El modelo se aplicó a datos que representan situaciones reales analizando principalmente el comportamiento de los resultados entregados por la heurística respecto a la configuración de rutas generadas y a la naturaleza de las rutas factibles generadas. El resultado final de la heurística utilizada contempla un aumento en el nivel de servicio, dado que logra entregar los pedidos cumpliendo las restricciones horarias de los clientes. Lo anterior refleja también una mejora de un 50% aproximadamente en las utilidades de los pedidos diarios.

Nas últimas décadas, avanços em tecnologias de geração, coleta e armazenamento de dados têm contribuído para aumentar o tamanho dos bancos de dados nas diversas áreas de conhecimento humano. Este aumento verifica-se não somente em relação à quantidade de amostras de dados, mas principalmente em relação à quantidade de características descrevendo cada amostra. A adição de características causa acréscimo de dimensões no espaço matemático, conduzindo ao crescimento exponencial do hipervolume dos dados, problema denominado “maldição da dimensionalidade”. A maldição da dimensionalidade tem sido um problema rotineiro para cientistas que, a fim de compreender e explicar determinados fenômenos, têm se deparado com a necessidade de encontrar estruturas significativas ocultas, de baixa dimensão, dentro de dados de alta dimensão. Este processo denomina-se redução de dimensionalidade dos dados (RDD). Do ponto de vista computacional, a conseqüência natural da RDD é uma diminuição do espaço de busca de hipóteses, melhorando o desempenho e simplificando os resultados da modelagem de conhecimento em sistemas autônomos de aprendizado. Dentre as técnicas utilizadas atualmente em sistemas autônomos de aprendizado, as redes neurais artificiais (RNAs) têm se tornado particularmente atrativas para modelagem de sistemas complexos, principalmente quando a modelagem é difícil ou quando a dinâmica do sistema não permite o controle on-line. Apesar de serem uma poderosa técnica, as RNAs têm seu desempenho afetado pela maldição da dimensionalidade. Quando a dimensão do espaço de entradas é alta, as RNAs podem utilizar boa parte de seus recursos para representar porções irrelevantes do espaço de busca, dificultando o aprendizado. Embora as RNAs, assim como outras técnicas de aprendizado de máquina, consigam identificar características mais informativas para um processo de modelagem, a utilização de técnicas de RDD frequentemente melhora os resultados do processo de aprendizado. Este trabalho propõe um wrapper que implementa um modelo neural de aprimoramento progressivo para RDD em sistemas autônomos de aprendizado supervisionado visando otimizar o processo de modelagem. Para validar o modelo neural de aprimoramento progressivo, foram realizados experimentos com bancos de dados privados e de repositórios públicos de diferentes domínios de conhecimento. A capacidade de generalização dos modelos criados é avaliada por meio de técnicas de validação cruzada. Os resultados obtidos demonstram que o modelo neural de aprimoramento progressivo consegue identificar características mais informativas, permitindo a RDD, e tornando possível criar modelos mais simples e mais precisos. A implementação da abordagem e os experimentos foram realizados no ambiente Matlab, utilizando o toolbox de RNAs. / In recent decades, advances on data generation, collection and storing technologies have contributed to increase databases size in different knowledge areas. This increase is seen not only regarding samples amount, but mainly regarding dimensionality, i.e. the amount of features describing each sample. Features adding causes dimension increasing in mathematical space, leading to an exponential growth of data hypervolume. This problem is called “the curse of dimensionality”. The curse of dimensionality has been a routine problem for scientists, that in order to understand and explain some phenomena, have faced with the demand to find meaningful low dimensional structures hidden in high dimensional search spaces. This process is called data dimensionality reduction (DDR). From computational viewpoint, DDR natural consequence is a reduction of hypothesis search space, improving performance and simplifying the knowledge modeling results in autonomous learning systems. Among currently used techniques in autonomous learning systems, artificial neural networks (ANNs) have becoming particularly attractive to model complex systems, when modeling is hard or when system dynamics does not allow on-line control. Despite ANN being a powerful tool, their performance is affected by the curse of dimensionality. When input space dimension is high, ANNs can use a significant part of their resources to represent irrelevant parts of input space making learning process harder. Although ANNs, and other machine learning techniques, can identify more informative features for a modeling process, DDR techniques often improve learning results. This thesis proposes a wrapper which implements a Progressive Enhancement Neural Model to DDR in supervised autonomous learning systems in order to optimize the modeling process. To validate the proposed approach, experiments were performed with private and public databases, from different knowledge domains. The generalization ability of developed models is evaluated by means of cross validation techniques. Obtained results demonstrate that the proposed approach can identify more informative features, allowing DDR, and becoming possible to create simpler and more accurate models. The implementation of the proposed approach and related experiments were performed in Matlab Environment, using ANNs toolbox.

O problema de alocação de aeronaves a voos, ou tail assignment problem (TAP), consiste em determinar qual aeronave realizará cada voo da malha de uma empresa aérea, visando a minimizar o custo total da operação e respeitando diversas restrições de conectividade de voos, permanência de aeronaves no solo, serviços obrigatórios de manutenção, limitações técnicas e desempenho de aeronaves, conexões de passageiros e tripulantes e famílias com diversos modelos de aeronaves. Este trabalho apresenta um modelo matemático exato e um método heurístico para a solução do TAP considerando todas as restrições citadas, o que não ocorre com os modelos encontrados na literatura. Os modelos desenvolvidos, baseados em programação linear inteira e na meta-heurística Busca Tabu, foram aplicados a problemas reais, extraídos da malha de uma empresa aérea brasileira, operadora de 35 aeronaves e cerca de 210 voos diários. Os resultados obtidos são compatíveis com a operação da empresa e apresentam ganhos em relação ao método de alocação de aeronaves utilizado na operação diária. Os tempos de processamento para solução pelo método exato são excessivamente longos, indicando que o método heurístico é mais adequado para a utilização em empresas aéreas, com resultados adequados obtidos em tempos de processamento satisfatórios. / The problem known as Aircraft Assignment or Tail Assignment Problem (TAP) is the problem of assigning flights to each aircraft of an airline\'s fleet, aiming at minimizing the total operating cost while complying with several constraints, such as network connectivity, aircraft time on ground, mandatory maintenance services, aircraft technical restrictions, passengers and crew connections, aircraft performance and aircraft families with more than one type. This work presents a deterministic mathematical model and a heuristic method to solve the TAP considering all constraints listed above, what does not happen with the models found in the literature. The proposed methods, based on mathematical integer programming and on the Tabu Search metaheuristic, were applied to problems obtained from the network of a Brazilian airline, operating 35 aircraft and around 210 daily flights. The results show the models are suitable to solve the problem and savings are observed when compared to the current assignment method. The long processing times intrinsic to the deterministic method show the heuristic method is more suitable for use in airlines, with suitable results obtained at acceptable computational times.

Made available in DSpace on 2016-06-02T19:05:16Z (GMT). No. of bitstreams: 1 DissMPr.pdf: 5452901 bytes, checksum: dd3e601629e8122c0ce032487fa894b3 (MD5) Previous issue date: 2003-05-19 / Financiadora de Estudos e Projetos / This project objectives the development of a support tool to the reverse engineering process for procedimental legacy systems implemented in COBOL, in order to be facilitating their recovery. The FAROOL (Ferramenta de Apoio à engenharia Reversa Orientada a Objetos de Legados) is a guide to software engineers in the reverse engineering process that is based on pre-defined heuristics, so that guided models to the objects are obtained from systems implemented in COBOL. FAROOL addresses two phases, in special, in the process of object guided reverse engineering. The first phase is the Elaboration of the MASA (Modelo de Análise do Sistema Atual, when a legacy systems model of pseudoguided objects is created. The second phase is of MAS Elaboration (Modelo de Análise do Sistema), when a totally model of guided objects is create, being based on the previous model (MASA). By applying the FAROOL, the software engineers are guided so that the reverse engineering process is materialized. First, the preparation of the system is made, aid of the Legacy Aid CASE tool, integrated to the FAROOL tool through macros.They follow the determination of the candidates classes, of the candidates attributes and of the candidates methods of the MASA model, that can become candidates to the class, to the attributes and to the methods, respectively, of the MAS model. Special heuristics are followed for the confection of the relationships between the candidate class in the model of guided objects. All the information are stored in a relational database, facilitating to the task of the software engineer in the reverse engineering process. The Delphi environment; the relational database Interbase; and the Legacy Aid tool were used in the elaboration of the FAROOL. / Este projeto objetiva o desenvolvimento de uma ferramenta de apoio ao processo de engenharia reversa orientada a objetos a partir de sistemas legados procedimentais implementados em COBOL, de modo a facilitar a recuperação desses. A Ferramenta de Apoio à engenharia Reversa Orientada a Objetos de Legados, denominada FAROOL, é um guia aos engenheiros de software durante o processo de engenharia reversa baseando-se em heurísticas pré-determinadas para que modelos orientados a objetos sejam obtidos a partir de sistemas implementados em COBOL. FAROOL se preocupa com duas fases, em especial, no processo de engenharia reversa orientada a objetos. A primeira fase é a de Elaboração do Modelo de Análise do Sistema Atual (MASA), quando um modelo pseudoorientado a objetos é criado a partir do sistema legado. A segunda fase é a de Elaboração do Modelo de Análise do Sistema (MAS), quando um modelo totalmente orientado a objetos é criado, abstraindo-se o modelo anterior (MASA). Através da FAROOL, os engenheiros de software são guiados para que o processo de engenharia reversa se concretize. Primeiramente, é feita a preparação do sistema, com auxílio da ferramenta CASE Legacy Aid, integrada à FAROOL através de macros. Seguem a determinação das classes, dos atributos e dos métodos candidatos do modelo MASA, que podem se tornar classes, atributos e métodos, respectivamente, do modelo MAS. Heurísticas especiais são seguidas para a confecção dos relacionamentos entre as classes no modelo orientado a objetos. Todas as informações são armazenadas em um banco de dados relacional, facilitando a tarefa do engenheiro de software no processo de engenharia reversa. O ambiente Delphi; o banco de dados relacional Interbase e a ferramenta Legacy Aid foram utilizadas na elaboração da FAROOL.